Re: Loops loosing Performance

What you have here is the classical "bit counting problem". By ANDing the two numbers all you need is find the amount of 1s in the result. The bit counting problem is a terrific example of the tradeoffs between space and time efficiency, and is one my my favorite interview questions.

You can find a lot of info about it online, for example here.

To make a long story short, the fastest technique is table lookup. Precompute the counts for all bytes (256 of them) in a table and do a simple lookup to find results later.

What you've been shown by kaif and others are the more arcane and enjoyable methods, but table lookup will be faster.

Comment on Re: Loops loosing Performance

Replies are listed 'Best First'.
Re^2: Loops loosing Performance by kaif (Friar) on Jun 10, 2005 at 07:16 UTC
[id://spurperl] is right, table lookup is fastest. Using the notation `op` for [id://PerlingTheUK\|original poster], `lt` for "lookup table", and the rest obvious, the overall benchmark looks something like this: `Rate op4 op5 hv7 hv6 roy4 kaif lt op4 64233/s -- -33% -33% -52% -57% -72% -76% op5 96098/s 50% -- -0% -28% -36% -58% -64% hv7 96399/s 50% 0% -- -28% -35% -58% -64% hv6 134032/s 109% 39% 39% -- -10% -41% -50% roy4 149447/s 133% 56% 55% 12% -- -34% -45% kaif 227019/s 253% 136% 135% 69% 52% -- -16% lt 270514/s 321% 181% 181% 102% 81% 19% --` [download] Just be sure to initialize your table outside of your function, that is, initialize only once.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^2: Loops loosing Performance
by kaif (Friar) on Jun 10, 2005 at 07:16 UTC

[id://spurperl] is right, table lookup is fastest. Using the notation op for [id://PerlingTheUK|original poster], lt for "lookup table", and the rest obvious, the overall benchmark looks something like this:

         Rate  op4  op5  hv7  hv6 roy4 kaif   lt
op4   64233/s   -- -33% -33% -52% -57% -72% -76%
op5   96098/s  50%   --  -0% -28% -36% -58% -64%
hv7   96399/s  50%   0%   -- -28% -35% -58% -64%
hv6  134032/s 109%  39%  39%   -- -10% -41% -50%
roy4 149447/s 133%  56%  55%  12%   -- -34% -45%
kaif 227019/s 253% 136% 135%  69%  52%   -- -16%
lt   270514/s 321% 181% 181% 102%  81%  19%   --
[download]

Just be sure to initialize your table outside of your function, that is, initialize only once.

[reply]
[d/l]
[select]