www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Returning int instead of bool can actually make things _less_ efficient

reply Stewart Gordon <smjg_1998 yahoo.com> writes:
There's been quite some debate over the fact that some functions in 
Phobos, including Object.opEquals, have return types of int, even though 
their returns are semantically boolean.

In some instances, it can help, if the efficiency lies in the ability to 
return a value other than 0 or 1 and avoid the overhead of converting 
the value to a boolean.

But in some cases, no efficiency can be gained by this.  Indeed, 
opEquals appears to be a prime example of this.  While a "not equals" 
function can gain efficiency by subtracting one value from the other and 
just returning the result, an "equals" function cannot.

If a function declared with a bool return type tries to return numbers 
other than 0 or 1, then the function must internally convert the value 
to a boolean.  However, if the compiler, while compiling a function 
declared to return bool, discovers that it never tries to return 
anything that isn't 0 or 1 - then there's no point generating the 
conversion code.

Moreover, if the compiler knows that a given variable or subexpression 
is boolean, then I can see a potential for the compiler to use this 
knowledge to optimise certain expressions/code forms.  For example, of 
these, which is more efficient?

b ? 43 : 42   or   42 + b
b ? 64 : 0    or   b << 6
b ? 32 : 16   or   16 << b
!b            or   1 - b
b & c         or   b * c
b & !c        or   b > c
!b | c        or   b <= c

If the compiler knows that b and c are boolean, it could optimise one 
form to the other, whichever is quicker on the processor for which the 
code is being compiled.  The last three could also work with && and ||, 
if the right operand is just a variable or something that can be reduced 
to one at compile-time.

Consider also the bit-twiddling operations common in programs that 
interface certain OS APIs.  Could these be more efficient with the 
optimisation of operations on booleans?  (OK, so _extracting_ a bit is 
an operation that could benefit from the added efficiency of returning 
an int or whatever, but that's aside.)

In both library and application code, there will be some divide between 
programmers who:
(a) have every function with a semantically boolean return value 
returning bool
(b) just use int to pass booleans around, having not got into using bool 
since migrating from C
(c) will consider each function and ask themselves which return type 
will work best from an efficiency POV

Programmers of kind (a), and to some extent (c), will sometimes want to 
make a function X return bool, but find themselves calling a third-party 
function Y that returns an int, albeit with boolean semantics.  If the 
implementation of Y never tries to return anything but 0 or 1, and the 
compiler can readily determine this fact, then nothing has been gained 
by returning an int.  The creator of X will have to either change the 
return type to int, still losing the optimisation potential of booleans 
further up the call stack, or put up with the extra instructions there 
and then to convert the int to a bool.

In conclusion....

If performance is a concern, and a given function could save a few 
instructions by returning a general integer rather than always returning 
0 or 1, then it's quite sensible to return an int.  (For libraries/APIs 
that are likely to have more than one implementation, the question is 
whether an implementation of the given function could feasibly be made 
more efficient in this way - and then if it can, it should.)  If OTOH, 
any feasible implementation would be just as efficient if it returned 
only 0 or 1, then it makes most sense to give it a return type of bool.

Stewart.
Dec 07 2006
parent reply Karen Lanrap <karen digitaldaemon.com> writes:
Stewart Gordon wrote:

 For example, of these, which is more efficient? 
This cannot be answered in general, because at least the features of the CPU and the code context play a major role. In fact Walters main argument for not having bool was an adaption to the _current_ behaviour of CPU producers whereas your argument seems right that a more precise abstraction may gain efficiency benefits. To actually have this benefits I do not see any other way than to implicitely follow the success of bytecode/VM implementations by deferring such decisions to the time of installation. Such deferring may also provide benefits on a larger scale: for example when a CPU outperforms its competitors for a specific task, a set of implementations of algorithms may also outperform another such set, especially if CPU can flag their capabilities. However, Moore's Law may render such expensive structuring useless within a close time horizon.
Dec 07 2006
parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
Karen Lanrap wrote:
 Stewart Gordon wrote:
 
 For example, of these, which is more efficient? 
This cannot be answered in general, because at least the features of the CPU and the code context play a major role.
Exactly. That's why I said next:
 If the compiler knows that b and c are boolean, it could optimise 
 one form to the other, whichever is quicker on the processor for 
 which the code is being compiled.
But when you mention "code context", do you mean that these expressions could be parts of larger expressions and this could affect what generated code is best? Obviously optimisation would take this into consideration.
 In fact Walters main argument for not having bool was an adaption to 
 the _current_ behaviour of CPU producers whereas your argument seems 
 right that a more precise abstraction may gain efficiency benefits.
But D does have bool now. And it would be silly if we didn't use it.
 To actually have this benefits I do not see any other way than to 
 implicitely follow the success of bytecode/VM implementations by 
 deferring such decisions to the time of installation.
But the D compiler generates native code. I'm not sure how we can make any meaningful changes to this native code at anything other than compile-time.
 Such deferring may also provide benefits on a larger scale: for 
 example when a CPU outperforms its competitors for a specific task, a 
 set of implementations of algorithms may also outperform another such 
 set, especially if CPU can flag their capabilities.
<snip> Hmm.... Stewart.
Dec 08 2006
parent Karen Lanrap <karen digitaldaemon.com> writes:
Stewart Gordon wrote:

 But when you mention "code context", do you mean that these
 expressions could be parts of larger expressions and this could
 affect what generated code is best?  Obviously optimisation
 would take this into consideration.
Yes, parts of larger expressions or even expressions that have been computed before for example by another core of a multi core processor.
 But D does have bool now.  And it would be silly if we didn't
 use it. 
Very true.
 But the D compiler generates native code.  I'm not sure how we
 can make any meaningful changes to this native code at anything
 other than compile-time.
Very correct again, and the conclusion is to deferr the current "compile-time" partly to the installation-time. I have already seen a word for such behavior but do not know the source anymore. Maybe it was adaptive compiling, but I am not sure.
Dec 08 2006