Author: Gerd Isenberg
Date: 11:45:19 07/07/03
Go up one level in this thread
On July 07, 2003 at 12:26:17, Andrew Dados wrote:
>On July 06, 2003 at 23:25:00, Uri Blass wrote:
>
>>In movei I have a number between 0 and 255 and I want to do some functions for
>>every 1 that it has in its binary representation(number of functions to
>>implement is the same as the number of 1's in the number and there is a
>>different function based on the value of the 1)
>>
>>I do not like to call functions because functions use local varaibles and
>>generating a copy of the local varaibles only to forget them may take computer
>>time and I also do not use the functions more than once.
>>
>>I thought to use switch(see the code later in this post) but the problem is that
>>switch continue to do everything without break and I want to have switch that
>>does not continue to do everything but does not quit and simply forget about the
>>fact that I called switch.
>>
>>Here is the type of the code that I plan to have now.
>>I do not like all the if (number&2) or if (number&4) and the question is if I
>>can do it faster.
>>
>>
>>i=smallestpower[number];
>>switch(i)
>>{
>> case 0:do list of commands
>> if (number==1) break
>> else
>> {
>> number-=1;
>> i=smallestpower[number];
>> }
>> case 1:if (number&2)
>> {
>> do list of commands
>> if (number==2) break;
>> else
>> {
>> number-=2;
>> i=smallestpower[number];
>> }
>> }
>> case 2:if (number&4)
>> {
>> do list of commands
>> if (number==4) break;
>> else
>> {
>> number-=4;
>> i=smallestpower[number];
>> }
>> }
>> case 3:if (number&8)
>> ...
>> ...
>> case 6:if (number&64)
>> ...
>> case 7://if you got there you know that number is 128 because you did not get
>>out by break so you do not need to check it
>>
>>
>>Uri
>
>boolean checking is way faster then jumps; in your implementation you get about
>6 jumps in the code (case is a jump) since you have about 1.2 bit set on
>average. I'll try to go down to below 4 jumps average:
>
>if i & (128+64){
> if i & 128 {}
> if i & 64 {}
>if ! i | 63 goto done;
>}
>
>if i & (32+16){
> if i & 32 {}
> if i & 16 {}
>if ! i | 15 goto done;
>}
>
>if i & (8+4){
> if i & 8 {}
> if i & 4 {}
>}
>
>if i & (2+1){
> if i & 2 {}
> if i & 1 {}
>}
>
>done:
>
>--------------
>Since you have small number of average bits set this should be way faster then
>case switch
- no, see below.
>
>-Andrew-
Hi Andrew,
interesting asymmetric approach based on Uri's probability of the higher bits.
Lets see, One bit set:
bit 7,6 - 4 compares
bit 5,4 - 1 + 4 = 5 compares
bit 3,2 - 1 + 1 + 3 + 1 = 6 compares
bit 1,0 - 1 + 1 + 1 + 3 = 6 compares
Fine - and all seldom cases of multiple bits are handled too.
That's the real advantage of your code - it don't acts like a switch or a "if
else if" cascade with one mutual exclusive case. It behaves exactly like a
sequence of eight if stamements, considering perfectly Uri's bit derivation.
Thought about an outer if i & (128+64+32+8) for a further binary divide but it
is worse here.
The switch-statement per se should be superiour due to the consecutive cases
from 0 to 8 - with the help of Uri's firstOne byte lookup. So only one indirect
jump (eg. in assembler jmp [_jmptable + 4*eax]) - but all cases are exclusive
and one must handle multiple set bits in an outer while-loop or Reinhard's
individual goto_work do-while.
So in best case Tim's while-switch approach requires 3 conditional or indirect
jumps with one bit set (two while and one indirect switch jump, not considered
range checking) but additional memory access and clearing the traversed bit.
Reinhard's goto_work do-while approach needs one compare less and profits from
set bit 7.
So in average i guess Reinhard's approach is fastest.
But the fastest of course is the switch(256) approach, if code size doesn't
matter and the jumptable is in cache ;-)
Regards,
Gerd
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.