Walter Bright wrote:
> Stewart Gordon wrote:
> 
>> xs0 wrote:
>> <snip>
>>
>>> Well, I'm just guessing, but I think something like
>>>
>>>  > int opEquals(Foo foo)
>>>  > {
>>>  >     return this.bar == foo.bar;
>>>  > }
>>>
>>> is compiled to something like
>>>
>>>> return this.bar-foo.bar; // 1 instruction
>>>
>>>
>>> but if the return type is bool, it becomes
>>>
>>>> return this.bar-foo.bar?1:0; // 3 instructions
>>
>>
>> If it does this, then there's a serious bug in the compiler.
> 
> 
> What instruction sequence do expect to be generated for it?
> 
>> Moreover, what's your evidence that subtracting one number from another might be more efficient than comparing them for equality directly?
> 
> 
> The only difference between a CMP and a SUB instruction is where the result ends up. But the CMP doesn't generate 0 or 1 as a result, it puts the result in the FLAGS register. Converting the FLAGS to a 0 or 1 in a register takes more instructions.
> 
>>> It's the 1/0 constraint on bools that causes the slowness, not the size (stack is usually size_t-aligned anyway)
>>
>>
>> But if the function only tries to return 0 or 1 anyway, then what difference does it make?  At the moment, I can't think of an example of equality testing that can be made more efficient by being allowed to return a value other than 0 or 1.
> 
> 
> I can. (a == b), where a and b are ints, can be implemented as (a - b), and the result is int 0 for equality, int !=0 for inequality.


So, why not treat false as 0, and true as not 0?  That way, it works just the same as the "int" version does (and comparing/testing against zero doesn't hit the address-bus). Yes, I can see some potential for concern there; but is there anything insurmountable?

kris wrote:
> Walter Bright wrote:
>> Stewart Gordon wrote:
>>> But if the function only tries to return 0 or 1 anyway, then what difference does it make?  At the moment, I can't think of an example of equality testing that can be made more efficient by being allowed to return a value other than 0 or 1.
>>
>>
>> I can. (a == b), where a and b are ints, can be implemented as (a - b), and the result is int 0 for equality, int !=0 for inequality.
> 
> 
> So, why not treat false as 0, and true as not 0?  That way, it works just the same as the "int" version does (and comparing/testing against zero doesn't hit the address-bus). Yes, I can see some potential for concern there; but is there anything insurmountable?

Then what would happen if a and b differ by, say, 256? Remember, an int is 4 bytes, a bool is only 1.

Frits van Bommel wrote:
> kris wrote:
> 
>> Walter Bright wrote:
>>
>>> Stewart Gordon wrote:
>>>
>>>> But if the function only tries to return 0 or 1 anyway, then what difference does it make?  At the moment, I can't think of an example of equality testing that can be made more efficient by being allowed to return a value other than 0 or 1.
>>>
>>>
>>>
>>> I can. (a == b), where a and b are ints, can be implemented as (a - b), and the result is int 0 for equality, int !=0 for inequality.
>>
>>
>>
>> So, why not treat false as 0, and true as not 0?  That way, it works just the same as the "int" version does (and comparing/testing against zero doesn't hit the address-bus). Yes, I can see some potential for concern there; but is there anything insurmountable?
> 
> 
> Then what would happen if a and b differ by, say, 256? Remember, an int is 4 bytes, a bool is only 1.

Sure, but it's generally more efficient to do all logical and arithmetic operations in the native width of the device anyway ~ generally 32bits for current D compilers.

If you're talking about issues related to actually storing a bool result, then that's part of the "concerns" noted above. Bool values derived in certains ways may need to be folded for storage, but not for testing. The subtraction case above may be included in that group, but testing should still only require a compare against zero (for both true and false). I'm suggesting only that zero values should *always* be used to test for 'truth' ~ never 1, or 255, or any value other than zero. Anywhere the keyword "true" is used (or implied) for comparative purposes, test against zero and invert the jmp-condition instead. If that's not done already, it would probably speed things up in many cases.

kris wrote:
> Frits van Bommel wrote:
>> kris wrote:
>>
>>> Walter Bright wrote:
>>>
>>>> Stewart Gordon wrote:
>>>>
>>>>> But if the function only tries to return 0 or 1 anyway, then what difference does it make?  At the moment, I can't think of an example of equality testing that can be made more efficient by being allowed to return a value other than 0 or 1.
>>>>
>>>>
>>>>
>>>> I can. (a == b), where a and b are ints, can be implemented as (a - b), and the result is int 0 for equality, int !=0 for inequality.
>>>
>>>
>>>
>>> So, why not treat false as 0, and true as not 0?  That way, it works just the same as the "int" version does (and comparing/testing against zero doesn't hit the address-bus). Yes, I can see some potential for concern there; but is there anything insurmountable?
>>
>>
>> Then what would happen if a and b differ by, say, 256? Remember, an int is 4 bytes, a bool is only 1.
> 
> Sure, but it's generally more efficient to do all logical and arithmetic operations in the native width of the device anyway ~ generally 32bits for current D compilers.
> 
> If you're talking about issues related to actually storing a bool result, then that's part of the "concerns" noted above. Bool values derived in certains ways may need to be folded for storage, but not for testing. The subtraction case above may be included in that group, but testing should still only require a compare against zero (for both true and false). I'm suggesting only that zero values should *always* be used to test for 'truth' ~ never 1, or 255, or any value other than zero. Anywhere the keyword "true" is used (or implied) for comparative purposes, test against zero and invert the jmp-condition instead. If that's not done already, it would probably speed things up in many cases.

Actually, I'm pretty sure testing for zero is already how it's done (just with 1-byte operands instead of 4-byte ones).

Something else: if there are multiple ways to represent true then equality testing just got a lot more complicated :).

Walter Bright wrote:
> Stewart Gordon wrote:
>> xs0 wrote:
>> <snip>
>>> Well, I'm just guessing, but I think something like
>>>
>>>  > int opEquals(Foo foo)
>>>  > {
>>>  >     return this.bar == foo.bar;
>>>  > }
>>>
>>> is compiled to something like
>>>
>>>> return this.bar-foo.bar; // 1 instruction
>>>
>>> but if the return type is bool, it becomes
>>>
>>>> return this.bar-foo.bar?1:0; // 3 instructions
>>
>> If it does this, then there's a serious bug in the compiler.
> 
> What instruction sequence do expect to be generated for it?

If anything resembling the above, then

    return this.bar-foo.bar?0:1;

which cancels out the advantage you mention next:

<snip>
> The only difference between a CMP and a SUB instruction is where the result ends up. But the CMP doesn't generate 0 or 1 as a result, it puts the result in the FLAGS register. Converting the FLAGS to a 0 or 1 in a register takes more instructions.

<snip>
>> But if the function only tries to return 0 or 1 anyway, then what difference does it make?  At the moment, I can't think of an example of equality testing that can be made more efficient by being allowed to return a value other than 0 or 1.
> 
> I can. (a == b), where a and b are ints, can be implemented as (a - b), and the result is int 0 for equality, int !=0 for inequality.

How is this (a == b) rather than (a != b)?

Stewart.

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/M d- s:-@ C++@ a->--- UB@ P+ L E@ W++@ N+++ o K-@ w++@ O? M V? PS- PE- Y? PGP- t- 5? X? R b DI? D G e++++ h-- r-- !y
------END GEEK CODE BLOCK------

My e-mail is valid but not my primary mailbox.  Please keep replies on the 'group where everyone may benefit.

Stewart Gordon wrote:
> Walter Bright wrote:
>> Stewart Gordon wrote:
>>> xs0 wrote:
>>> <snip>
>>>> Well, I'm just guessing, but I think something like
>>>>
>>>>  > int opEquals(Foo foo)
>>>>  > {
>>>>  >     return this.bar == foo.bar;
>>>>  > }
>>>>
>>>> is compiled to something like
>>>>
>>>>> return this.bar-foo.bar; // 1 instruction
>>>>
>>>> but if the return type is bool, it becomes
>>>>
>>>>> return this.bar-foo.bar?1:0; // 3 instructions
>>>
>>> If it does this, then there's a serious bug in the compiler.
>>
>> What instruction sequence do expect to be generated for it?
> 
> If anything resembling the above, then
> 
>     return this.bar-foo.bar?0:1;

? Let's look at an example:

class Foo
{
    int foo, bar;

    int Eq1(Foo foo)
    {
        return this.bar-foo.bar?0:1;
    }

    int Eq2(Foo foo)
    {
        return this.bar-foo.bar;
    }
}

which generates:

    Eq1:
                mov     EDX,4[ESP]
                mov     ECX,0Ch[EAX]
                sub     ECX,0Ch[EDX]
                cmp     ECX,1
                sbb     EAX,EAX
                neg     EAX
                ret     4
    Eq2:
                mov     ECX,4[ESP]
                mov     EAX,0Ch[EAX]
                sub     EAX,0Ch[ECX]
                ret     4

So we have 4 instructions generated rather than 1. If there's a trick to generate only one instruction for Eq1, I'd like to know about it.

>> I can. (a == b), where a and b are ints, can be implemented as (a - b), and the result is int 0 for equality, int !=0 for inequality.
> 
> How is this (a == b) rather than (a != b)?

I don't understand your question.

Walter Bright wrote:
> Stewart Gordon wrote:
>> Walter Bright wrote:
>>> I can. (a == b), where a and b are ints, can be implemented as (a -
>>> b), and the result is int 0 for equality, int !=0 for inequality.
>>
>> How is this (a == b) rather than (a != b)?
> 
> I don't understand your question.

(a - b), if a and b are equal ints, evaluates to 0, which is generally
considered to mean false. So isn't (a - b) actually a way of finding (a != b),
instead of (a == b)?

Deewiant wrote:
> Walter Bright wrote:
>> Stewart Gordon wrote:
>>> Walter Bright wrote:
>>>> I can. (a == b), where a and b are ints, can be implemented as (a -
>>>> b), and the result is int 0 for equality, int !=0 for inequality.
>>> How is this (a == b) rather than (a != b)?
>> I don't understand your question.
> 
> (a - b), if a and b are equal ints, evaluates to 0, which is generally
> considered to mean false. So isn't (a - b) actually a way of finding (a != b),
> instead of (a == b)?

Oh, I see what you mean.

To invert the result would take another 2 instructions for a total of 3, still less than 4.

Walter Bright wrote:
> Deewiant wrote:
>> Walter Bright wrote:
>>> Stewart Gordon wrote:
>>>> Walter Bright wrote:
>>>>> I can. (a == b), where a and b are ints, can be implemented as (a -
>>>>> b), and the result is int 0 for equality, int !=0 for inequality.
>>>> How is this (a == b) rather than (a != b)?
>>> I don't understand your question.
>>
>> (a - b), if a and b are equal ints, evaluates to 0, which is generally
>> considered to mean false. So isn't (a - b) actually a way of finding (a != b),
>> instead of (a == b)?
> 
> Oh, I see what you mean.
> 
> To invert the result would take another 2 instructions for a total of 3, still less than 4.

Exactly.  But because what we have is opEquals and not opNotEquals, the benefit of fewer instructions is lost (except when opEquals is simple enough that the compiler can inline and optimise away the double negation).

Indeed, on this basis, if we had opNotEquals then it would be just be equivalent to opCmp for many types.  So I can see people thinking that opNotEquals should just call opCmp by default.  However, there's a problem with this idea - for classes that have no ordering, even the current behaviour of comparing object references would have to be explicitly programmed in.

Stewart.

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/M d- s:-@ C++@ a->--- UB@ P+ L E@ W++@ N+++ o K-@ w++@ O? M V? PS- PE- Y? PGP- t- 5? X? R b DI? D G e++++ h-- r-- !y
------END GEEK CODE BLOCK------

My e-mail is valid but not my primary mailbox.  Please keep replies on the 'group where everyone may benefit.

Walter Bright wrote:
> Bruno Medeiros wrote:
>> But the question remains, is it then less efficient to return a byte than a int?
> 
> Yes. It's also less efficient to constrain the results to 0 or 1.
> 
>> Why?
> 
> Consider:
> 
>     a = 0x1000;
>     b = 0x2000;
> 
> Now convert (a == b) into a bool. If the result is an int, I can just do (a - b), one instruction. Converting it to a byte, or to 1 or 0, takes more.
> 
>> And if so isn't there a way for the compiler to somehow optimize it?
> 
> The math is inevitable <g>.
> 

Well, let's think about the other way around then. Why should bool be constrained to 0 or 1? Why not, same as kris said, 0 would be false, and non zero would be true. Then we could have an opEquals or any function returning a bool instead of int, without penalty loss.

The only shortcoming I see is that it would be slower to compare two bool /variables/:
   (b1 == b2)
that expression is currently just 1 instruction, a CMP, but without the 0,1 restriction it would be more (3, I think, have to check that). However, is that significantly worse? I think not. I think comparison between two bool _variables_ is likely very rare, and when it happens it is also probably not performance critical. (statistical references?)
Note: this would not affect at all comparisons between a bool variable and a bool literal. Like (b == true) or (b == false).

Or is there another reason for the 0,1 restriction?

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D