Valhalla Legends Forums Archive | C/C++ Programming | Fastest way to do common things

AuthorMessageTime
Telos
I was writing a program that had two opreations that needed to be repeated quite a few times so I was trying to figure out the best way to optimize these two tasks

The first is toggling a boolean and we came up with
[code]
x = ( x ? false : true );

cmp dword ptr [x],0
sete al
movzx ecx,al
mov dword ptr [x],ecx
[/code]

[code]
x = !x;

xor eax, eax
cmp dword ptr [x], 0
sete al
mov dword ptr [x], eax
[/code]

[code]
x ^= 1;

mov eax, dword ptr [x]
xor eax, 1
mov dword ptr [x], eax
[/code]

With the boolean data type these three worked fine x ^= 1 being the fastest however when you use an integer the following seemed to be the fastest (should be only 3 clock cycles?)

[code]
__asm { not x }

not dword ptr [x]
[/code]

or even if x is a bool

[code]
__asm { not dword ptr[x] }
[/code]

or
[code]
__asm { xor dword ptr [x], 1 }
[/code]
but thats more dependent on what x is

Secondly an equality comparison for three integers
Zakath suggested
[code]
if( x == y && y == z )
[/code]

I ended up using
[code]
if( x == ( y & z ) )
[/code]

But I didnt do any disassembly on these to figure out which way is the fastest or even if there are better ways to do it

If anyone has a faster/better/cooler way of doing these please post them
February 29, 2004, 3:47 PM
Adron
[quote author=Telos link=board=30;threadid=5510;start=0#msg46702 date=1078069621]
The first is toggling a boolean and we came up with
[code]
x = ( x ? false : true );

cmp dword ptr [x],0
sete al
movzx ecx,al
mov dword ptr [x],ecx
[/code]

[code]
x = !x;

xor eax, eax
cmp dword ptr [x], 0
sete al
mov dword ptr [x], eax
[/code]
[/quote]

Is x an int or a bool? Your code is useful for turning an integer value into a real bool. We posted about this earlier on the asm board. My favorite for setting eax = !eax was "neg eax; sbb eax,eax; inc eax".


[quote author=Telos link=board=30;threadid=5510;start=0#msg46702 date=1078069621]
[code]
x ^= 1;

mov eax, dword ptr [x]
xor eax, 1
mov dword ptr [x], eax
[/code]
[/quote]

"xor dword ptr[x], 1" should be faster than moving it into a register if you're not going to use the register for anything else. Toggling bit 0 works only if you know that x is a bool value from the start.

[quote author=Telos link=board=30;threadid=5510;start=0#msg46702 date=1078069621]
With the boolean data type these three worked fine x ^= 1 being the fastest however when you use an integer the following seemed to be the fastest (should be only 3 clock cycles?)

[code]
__asm { not x }

not dword ptr [x]
[/code]
[/quote]

That's "x = ~x", not "x = !x".

[quote author=Telos link=board=30;threadid=5510;start=0#msg46702 date=1078069621]
or even if x is a bool
[code]
__asm { not dword ptr[x] }
[/code]
[/quote]

This is incorrect if x is a bool - a bool should be 0 or 1. Try "neg x; inc x" or "xor x, 1".


[quote author=Telos link=board=30;threadid=5510;start=0#msg46702 date=1078069621]
or
[code]
__asm { xor dword ptr [x], 1 }
[/code]
but thats more dependent on what x is
[/quote]

That's dependent on x being a bool, and works.


[quote author=Telos link=board=30;threadid=5510;start=0#msg46702 date=1078069621]
Secondly an equality comparison for three integers
Zakath suggested
[code]
if( x == y && y == z )
[/code]

I ended up using
[code]
if( x == ( y & z ) )
[/code]
[/quote]

Your answer is incorrect. It will return true for x = 2, y = 6, z = 10.

February 29, 2004, 4:25 PM
Telos
[quote author=Adron link=board=30;threadid=5510;start=0#msg46708 date=1078071914]
Is x an int or a bool? Your code is useful for turning an integer value into a real bool. We posted about this earlier on the asm board. My favorite for setting eax = !eax was "neg eax; sbb eax,eax; inc eax".
[/quote]

I tried using x as both for these tests in the program it hasnt made much difference which data type to use

[quote author=Adron link=board=30;threadid=5510;start=0#msg46708 date=1078071914]
"xor dword ptr[x], 1" should be faster than moving it into a register if you're not going to use the register for anything else. Toggling bit 0 works only if you know that x is a bool value from the start.
[/quote]

Yes which is why Im wary to use that unless Ive set the value initially and its not an int

[quote author=Adron link=board=30;threadid=5510;start=0#msg46708 date=1078071914]
That's "x = ~x", not "x = !x".
[/quote]

Ok but I dont think I said that asm not was equivalent to the ! operator

[quote author=Adron link=board=30;threadid=5510;start=0#msg46708 date=1078071914]
This is incorrect if x is a bool - a bool should be 0 or 1. Try "neg x; inc x" or "xor x, 1".
[/quote]

Incorrect how? Stepping through with a debugger shows correct values at that location at each step

[quote author=Adron link=board=30;threadid=5510;start=0#msg46708 date=1078071914]
That's dependent on x being a bool, and works.
[/quote]

Yes which is why I said depends on the type of x

[quote author=Adron link=board=30;threadid=5510;start=0#msg46708 date=1078071914]
Your answer is incorrect. It will return true for x = 2, y = 6, z = 10.
[/quote]

I should have clarified this one x y and z can only be 0 1 or 2 in this program so while it doesnt work on the general case it does in this program thx for input tho
February 29, 2004, 4:34 PM
Adron
[quote author=Telos link=board=30;threadid=5510;start=0#msg46709 date=1078072482]
[quote author=Adron link=board=30;threadid=5510;start=0#msg46708 date=1078071914]
Is x an int or a bool? Your code is useful for turning an integer value into a real bool. We posted about this earlier on the asm board. My favorite for setting eax = !eax was "neg eax; sbb eax,eax; inc eax".
[/quote]

I tried using x as both for these tests in the program it hasnt made much difference which data type to use
[/quote]

It makes a lot of difference. A C++ bool value can be expected to be either 0 or 1, while a C boolean integer value can be expected to be either 0 or nonzero. This makes testing a C boolean require more code/time than testing a C++ bool.



[quote author=Telos link=board=30;threadid=5510;start=0#msg46709 date=1078072482]
Ok but I dont think I said that asm not was equivalent to the ! operator
[/quote]

Ah, I may have misinterpreted you. I thought those were all intended to be examples of "toggling a boolean value", either as a C++-style bool variable, or as a C-style zero or nonzero integer. If you use that code to toggle a C-style boolean value stored in an integer, most true values input will generate a true value as output...



[quote author=Telos link=board=30;threadid=5510;start=0#msg46709 date=1078072482]
Incorrect how? Stepping through with a debugger shows correct values at that location at each step
[/quote]

[code]
__asm { not dword ptr[x] }
[/code]
is incorrect if x is a bool because:

if x is 0 before the statement, x will not be 1 after the statement (x will be -1).

if x is 1 before the statement, x will not be 0 after the statement (x will be -2).


[quote author=Telos link=board=30;threadid=5510;start=0#msg46709 date=1078072482]
I should have clarified this one x y and z can only be 0 1 or 2 in this program so while it doesnt work on the general case it does in this program thx for input tho
[/quote]

If all those values are acceptable, it's once again incorrect because it will return true for x = 0, y = 1, z = 2. You need to specify more exactly the conditions under which your statements are supposed to work.
February 29, 2004, 6:14 PM
Telos
[quote author=Adron link=board=30;threadid=5510;start=0#msg46720 date=1078078472]
It makes a lot of difference. A C++ bool value can be expected to be either 0 or 1, while a C boolean integer value can be expected to be either 0 or nonzero. This makes testing a C boolean require more code/time than testing a C++ bool.
[/quote]

(Hasnt made much different with respect to how it is toggled)

[quote author=Adron link=board=30;threadid=5510;start=0#msg46720 date=1078078472]
Ah, I may have misinterpreted you. I thought those were all intended to be examples of "toggling a boolean value", either as a C++-style bool variable, or as a C-style zero or nonzero integer. If you use that code to toggle a C-style boolean value stored in an integer, most true values input will generate a true value as output...
[/quote]

Probably not the fact that I was testing two data types has been confusing in this thread

[quote author=Adron link=board=30;threadid=5510;start=0#msg46720 date=1078078472]
[code]
__asm { not dword ptr[x] }
[/code]
is incorrect if x is a bool because:

if x is 0 before the statement, x will not be 1 after the statement (x will be -1).

if x is 1 before the statement, x will not be 0 after the statement (x will be -2).
[/quote]

I see what youre saying but the initial value (its bool x in this case) is 0 and not dword ptr [x] makes it true and not dword ptr [x] makes it false and so on

[quote author=Adron link=board=30;threadid=5510;start=0#msg46720 date=1078078472]
If all those values are acceptable, it's once again incorrect because it will return true for x = 0, y = 1, z = 2. You need to specify more exactly the conditions under which your statements are supposed to work.
[/quote]

Its just a simple tic tac toe frontend for an AI and with the cases I use x == (y & z) has been fine but theres the possibility that I havent run into a case that will cause a false positive thx for input will fix
February 29, 2004, 10:51 PM
Adron
[quote author=Telos link=board=30;threadid=5510;start=0#msg46779 date=1078095104]
[quote author=Adron link=board=30;threadid=5510;start=0#msg46720 date=1078078472]
It makes a lot of difference. A C++ bool value can be expected to be either 0 or 1, while a C boolean integer value can be expected to be either 0 or nonzero. This makes testing a C boolean require more code/time than testing a C++ bool.
[/quote]

(Hasnt made much different with respect to how it is toggled)
[/quote]

The difference of knowing that a value is either 0 or 1, or knowing that it is either zero or nonzero makes a huge difference on how to toggle it. Toggling a bool means toggling a bit, toggling a C boolean means detecting a nonzero value. It *is* very different.



[quote author=Telos link=board=30;threadid=5510;start=0#msg46779 date=1078095104]
Probably not the fact that I was testing two data types has been confusing in this thread
[/quote]

I think so. Also, for bool, you shouldn't be accessing it as a dword ptr at all, because most bools are just 8 bits.


[quote author=Telos link=board=30;threadid=5510;start=0#msg46779 date=1078095104]
I see what youre saying but the initial value (its bool x in this case) is 0 and not dword ptr [x] makes it true and not dword ptr [x] makes it false and so on
[/quote]

"not dword ptr [ x ]" when x is 0 doesn't give it the bool value "true", so it's incorrect.



[quote author=Telos link=board=30;threadid=5510;start=0#msg46779 date=1078095104]
Its just a simple tic tac toe frontend for an AI and with the cases I use x == (y & z) has been fine but theres the possibility that I havent run into a case that will cause a false positive thx for input will fix
[/quote]

Well, if you'd define the possible combinations, it'd be easier to give you an answer to whether it works or not.... :P
March 1, 2004, 12:52 AM
Telos
[quote author=Adron link=board=30;threadid=5510;start=0#msg46810 date=1078102349]
["not dword ptr [ x ]" when x is 0 doesn't give it the bool value "true", so it's incorrect.
[/quote]

I dont know where you get this from but it does toggle the value correctly Im having a hard time understanding why its incorrect
March 1, 2004, 2:40 AM
Kp
[quote author=Telos link=board=30;threadid=5510;start=0#msg46853 date=1078108814][quote author=Adron link=board=30;threadid=5510;start=0#msg46810 date=1078102349]["not dword ptr [ x ]" when x is 0 doesn't give it the bool value "true", so it's incorrect.[/quote]I dont know where you get this from but it does toggle the value correctly Im having a hard time understanding why its incorrect[/quote]

As he stated earlier, not 0 is ~0 which is all bits on, which is not equivalent to 0x01. The bool value 'true' is typically the byte value 0x01, not "any value which is not 0x00." Thus, your method produces a value that, while not zero, is not the correct value of true for a bool.
March 1, 2004, 2:47 AM
Telos
Is 0x01 true? Yes

Is 0 true? No
Is ~0 true? Yes
Is ~(~0) true? No
Is ~(~(~0)) true? Yes

Boolean is either true or false right? So does it really matter what value of true or false is used? Clearly the CPU doesnt think so
March 1, 2004, 3:28 AM
Grok
"By definition, true has the value 1 when converted to an integer and false has the value 0. Conversely, integers can be implicitly converted to bool values: nonzero integers convert to true and 0 converts to false."

So you're really discussing whether an implicit conversion is involved vs. the defined true.
March 1, 2004, 3:33 AM
Arta
It could, if your compiler assumes that true is always 1 and false is always 0... I doubt that any compiler would work like this, but the following example comes to mind:

[code]
bool eax = true;
if(eax) return false; // I know it's ugly, but bear with me
[/code]

Might be compiled to something like:

[code]
test al, al
jz somewhere_else
dec al
ret
[/code]

If your toggle had changed al from 1 to some other nonzero value, that would return an unexpected result. Like I said, I don't think it's really a viable situation, but it sprang to mind.

Edit: bah, it's late.
March 1, 2004, 3:37 AM
Adron
A bool is supposed to be either 0 or 1, which allows certain optimizations. Giving a bool the value 2 or -1 is not acceptable. This most likely produces a warning in msvc++ about forcing a conversion:

bool func(int a, int b)
{
a &= b;
return a;
}

The reason is that the compiler has to emit code to turn any nonzero value of a into 1, or the return value will not be a bool.
March 1, 2004, 9:25 AM
dRAgoN
correct me if i'm wrong but shouldent the statement x = ( x ? false : true );
be set up like x = ( x ? trueparthere : falseparthere );

[quote author=K link=board=30;threadid=5510;start=0#msg46968 date=1078178668]
[quote author=dRAgoN link=board=30;threadid=5510;start=0#msg46966 date=1078178517]
correct me if i'm wrong but shouldent the statement x = ( x ? false : true );
be set up like x = ( x ? trueparthere : falseparthere );
[/quote]

No, he's trying to toggle the value; so if x is true, x becomes false and vice versa.
[/quote]
thx was just wondering
March 1, 2004, 10:01 PM
K
[quote author=dRAgoN link=board=30;threadid=5510;start=0#msg46966 date=1078178517]
correct me if i'm wrong but shouldent the statement x = ( x ? false : true );
be set up like x = ( x ? trueparthere : falseparthere );
[/quote]

No, he's trying to toggle the value; so if x is true, x becomes false and vice versa.
March 1, 2004, 10:04 PM

Search