www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Efficiency test for various boolean strategies

reply Arcane Jill <Arcane_member pathlink.com> writes:
These examples show how various different strategies for handling boolean values
are compiled. For reference, the declarations are:
       bit b1;
       byte b2;
       int b3;
       void* b4;
       Bool b5;  // My offering

I confess I don't know how Matthew's boolean is defined. Walter's bool is currently aliased to bit. These compilations were done in debug mode with no optimization. ================================================ ASSIGNING A VARIABLE ================================================ bit b1 = 1; 0040B09A mov al,1 0040B09C mov byte ptr [b1],al ------------------------------------------------ byte b2 = 1; 0040B0A7 mov byte ptr [b2],1 ------------------------------------------------ int b3 = 1; 0040B0B3 mov dword ptr [b3],1 ------------------------------------------------ void* b4 = cast(void*)1; 0040B0C2 mov dword ptr [b4],1 ------------------------------------------------ Bool b5 = Bool.TRUE; 0040B0D1 mov ecx,dword ptr [420C20h] 0040B0D7 mov dword ptr [b5],ecx ================================================ TESTING THE VALUE ================================================ if (b1) {f();} 0040B0E2 test al,al 0040B0E4 je 0040B0EB 0040B0E6 call 0040B06C ------------------------------------------------ if (b2) {f();} 0040B0F3 cmp byte ptr [b2],0 0040B0F7 je 0040B0FE 0040B0F9 call 0040B06C ------------------------------------------------ if (b3) {f();} 0040B106 cmp dword ptr [b3],0 0040B10A je 0040B111 0040B10C call 0040B06C ------------------------------------------------ if (b4) {f();} 0040B119 cmp dword ptr [b4],0 0040B11D je 0040B124 0040B11F call 0040B06C ------------------------------------------------ if (b5) {f();} 0040B12C cmp dword ptr [b5],0 0040B130 je 0040B137 0040B132 call 0040B06C ------------------------------------------------ Though there are differences, it doesn't seem to me that there's much to write home about within those differences. We choose largely on the basis of our semantic preferences. I confess to being somewhat selfish here - in the sense that I write code for ME. I do think it's great if other people want to use it, but I don't care if they don't. I wouldn't write code if /I/ didn't want to use it. So I have my Bool class, with its marvellous (IMO) compile-time checking. I wrote it so that /I/ could use it, and so I shall use it. Yes, it's a class - but the class is never constructed in running code, because Bool is a /singleton/ class, Bool.TRUE is a reference to the one and only instance of that class, and Bool.FALSE is a null reference of the same type. It works for me. Sure, int and bit are *slightly* more efficient (see above), but the difference is small enough for me to ignore, and I want the Design-By-Contract compiler checks that Bool provides. This isn't a competition. We are all free to write our own classes. I wanted a class to do a particular job, so I wrote it. I don't care whether anyone else uses it or not, so that's end of story really. Other people will do things differently. So what?, I say. Good luck to you all. All of our various strategies have merit, and we will all use the best that is available - or write our own if we think we can do better. I, too, hope we can stop arguing with Walter (and sometimes each other) about this and move on. I've got most of what I want, so I'm largely happy. Now I'm going to move on, fix a few bugs, and write the next thing. Arcane Jill
Jun 03 2004
next sibling parent Norbert Nemec <Norbert.Nemec gmx.de> writes:
Arcane Jill wrote:

 I confess to being somewhat selfish here - in the sense that I write code
 for ME.

Ok, do whatever you want, but if you bring up a topic in the group, you should be expect it to be discussed on the group. If you say what you are doing in public, you should expect people to give their opinion. Especially, if you are requestion a feature like that "opAndAnd", you should be prepared to justify very well why it would be useful to have in the language.
Jun 03 2004
prev sibling parent reply "Walter" <newshound digitalmars.com> writes:
"Arcane Jill" <Arcane_member pathlink.com> wrote in message
news:c9nk63$5ja$1 digitaldaemon.com...
 These compilations were done in debug mode with no
 optimization.

Ok, but that can be pretty misleading when doing efficiency tests. The asm code for debug builds is more suited to clarity (!) and debuggability. There are a number of really weird, but fast, code sequences for some things when optimized. A debug build tries to slice a cow into steaks, while an optimized build grinds it up into hamburger.
 Though there are differences, it doesn't seem to me that there's much to

 home about within those differences. We choose largely on the basis of our
 semantic preferences.

There really aren't any for the task you set it to. The inefficiency of a bool type comes in the creation of a boolean value from an expression. As you discovered, though, once a bool value is already created, assigning it and testing it is no different from doing the same with an int. I know we're done arguing about this, so I'm just trying to be informative here. Let's example two equals functions, one returning 0/!0, the other returning 0/1: struct Foo { int x; int equalsA(Foo *f) { return x - f.x; } bit equalsB(Foo *f) { return x == f.x; } } Compiling with full optimization yields: equalsA: mov ECX,4[ESP] mov EAX,[EAX] sub EAX,[ECX] ret 4 equalsB: mov EDX,4[ESP] mov ECX,[EAX] mov EAX,1 cmp ECX,[EDX] je L11 xor EAX,EAX L11: ret 4
 I, too, hope we can stop arguing with Walter (and sometimes each other)

 this and move on. I've got most of what I want, so I'm largely happy. Now

 going to move on, fix a few bugs, and write the next thing.

Great!
Jun 03 2004
next sibling parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
Walter wrote:

I know we're done arguing about this, so I'm just trying to be informative
here. Let's example two equals functions, one returning 0/!0, the other
returning 0/1:

struct Foo
{  int x;
    int equalsA(Foo *f) { return x - f.x; }
    bit equalsB(Foo *f) { return x == f.x; }
}

Compiling with full optimization yields:

equalsA:
                mov     ECX,4[ESP]
                mov     EAX,[EAX]
                sub     EAX,[ECX]
                ret     4
equalsB:
                mov     EDX,4[ESP]
                mov     ECX,[EAX]
                mov     EAX,1
                cmp     ECX,[EDX]
                je      L11
                xor     EAX,EAX
L11:            ret     4
  

I'm not arguing for a bit type in opEquals, but why can't the compiler realise this optimisation? Why does a bit type require "normalization"? Can't it delay normalization until its needed? I mean why not make a non-array bit type 0/!0 but from the users perspective make it appear to be 0/1. If a user writes: bit b = foo.equalsB(); if (b == 1) then that would translate into: if (b) I don't see why normalization is nessary at that stage. -- -Anderson: http://badmama.com.au/~anderson/
Jun 04 2004
parent reply "Walter" <newshound digitalmars.com> writes:
"J Anderson" <REMOVEanderson badmama.com.au> wrote in message
news:c9ph95$30l2$2 digitaldaemon.com...
 I'm not arguing for a bit type in opEquals, but why can't the compiler
 realise this optimisation?  Why does a bit type require
 "normalization"?

It won't fit into one bit if it isn't normalized.
 Can't it delay normalization until its needed?  I mean
 why not make a non-array bit type 0/!0 but from the users perspective
 make it appear to be 0/1.  If a user writes:

 bit b = foo.equalsB();
 if (b == 1)

 then that would translate into:

 if (b)

 I don't see why normalization is nessary at that stage.

Because I'm pretty uncomfortable with two values comparing 'equal' but having different bit patterns. (Yes, I know, this happens with floats.)
Jun 04 2004
next sibling parent hellcatv hotmail.com writes:
is this proper D code:

if ((a==b)==(c==d)) {
//do something if a is the same as b and d is the saem as d or a is different
from b and c is different from d.   as in (a==b) XOR (c==d)
}

it looks all typesafe, but if equality can give bogus numbers other than 0 or 1
it may fail in certain situations

In article <c9qdif$1aej$2 digitaldaemon.com>, Walter says...
"J Anderson" <REMOVEanderson badmama.com.au> wrote in message
news:c9ph95$30l2$2 digitaldaemon.com...
 I'm not arguing for a bit type in opEquals, but why can't the compiler
 realise this optimisation?  Why does a bit type require
 "normalization"?

It won't fit into one bit if it isn't normalized.
 Can't it delay normalization until its needed?  I mean
 why not make a non-array bit type 0/!0 but from the users perspective
 make it appear to be 0/1.  If a user writes:

 bit b = foo.equalsB();
 if (b == 1)

 then that would translate into:

 if (b)

 I don't see why normalization is nessary at that stage.

Because I'm pretty uncomfortable with two values comparing 'equal' but having different bit patterns. (Yes, I know, this happens with floats.)

Jun 04 2004
prev sibling parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
Walter wrote:

Can't it delay normalization until its needed?  I mean
why not make a non-array bit type 0/!0 but from the users perspective
make it appear to be 0/1.  If a user writes:

bit b = foo.equalsB();
if (b == 1)

then that would translate into:

if (b)

I don't see why normalization is nessary at that stage.
    

Because I'm pretty uncomfortable with two values comparing 'equal' but having different bit patterns. (Yes, I know, this happens with floats.)

problem in the specs that wouldn't allow this to be done. -- -Anderson: http://badmama.com.au/~anderson/
Jun 05 2004
parent Arcane Jill <Arcane_member pathlink.com> writes:
Walter wrote:

Because I'm pretty uncomfortable with two values comparing 'equal' but
having different bit patterns. (Yes, I know, this happens with floats.)


If you recall, there is a behaviour (bug?) in the Linux implementation of D whereby opEquals() can return a value other than 0 or 1. If (a==b) returns 1, then we would presume this to mean true. If (c==d) returns 2, then we would presume this also to mean true. But we would also expect the expression ((a==b)==(c==d)) to evaluate as non-zero. Currently, it would seem that is not the case on Linux. And, since == may /in theory/ return any value in the range -32768 to +32767, it is not actually /guaranteed/ to work on Windows either. At the very least, opEquals should do this:
       int opEquals(Object o)
       out(n)
       {
           assert((n==0) || (n==1));
       }
       body

Arcane Jill
Jun 05 2004
prev sibling next sibling parent Antti =?iso-8859-1?Q?Syk=E4ri?= <jsykari gamma.hut.fi> writes:
In article <c9okol$1kvq$1 digitaldaemon.com>, Walter wrote:
 I know we're done arguing about this, so I'm just trying to be informative
 here. Let's example two equals functions, one returning 0/!0, the other
 returning 0/1:
 
 struct Foo
 {  int x;
     int equalsA(Foo *f) { return x - f.x; }
     bit equalsB(Foo *f) { return x == f.x; }
 }
 
 Compiling with full optimization yields:
 
 equalsA:
                 mov     ECX,4[ESP]
                 mov     EAX,[EAX]
                 sub     EAX,[ECX]
                 ret     4
 equalsB:
                 mov     EDX,4[ESP]
                 mov     ECX,[EAX]
                 mov     EAX,1
                 cmp     ECX,[EDX]
                 je      L11
                 xor     EAX,EAX
 L11:            ret     4

In short, the int version is faster (at least looks like faster). Then why just not call it bool instead of int? And generate code like in equalsA(Foo *f)? -Antti -- I will not be using Plan 9 in the creation of weapons of mass destruction to be used by nations other than the US.
Jun 06 2004
prev sibling parent Antti =?iso-8859-1?Q?Syk=E4ri?= <jsykari gamma.hut.fi> writes:
In article <c9okol$1kvq$1 digitaldaemon.com>, Walter wrote:
 
 "Arcane Jill" <Arcane_member pathlink.com> wrote in message
 news:c9nk63$5ja$1 digitaldaemon.com...

 There really aren't any for the task you set it to. The inefficiency of a
 bool type comes in the creation of a boolean value from an expression. As
 you discovered, though, once a bool value is already created, assigning it
 and testing it is no different from doing the same with an int.
 
 I know we're done arguing about this, so I'm just trying to be informative
 here. Let's example two equals functions, one returning 0/!0, the other
 returning 0/1:
 
 struct Foo
 {   int x;
     int equalsA(Foo *f) { return x - f.x; }
     bit equalsB(Foo *f) { return x == f.x; }
 }

When writing my own test program, I noticed a bug in this... shouldn't it be
     int equalsA(Foo *f) { return !(x - f.x); }

which actually makes the int version SLOWER? -A -- I will not be using Plan 9 in the creation of weapons of mass destruction to be used by nations other than the US.
Jun 06 2004