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


write

 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)


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.


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.)
  


I guess that should be left up to other D vendors then.  I don't see a 
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