Re: Loops loosing Performance

[kaif]

Are you a hacker? Are you not worried if your code looks like crazy old magic? Then you'll love this solution:

sub test0 {
    return ((($_[0] & $_[1]) * 2113665) & 17895697) % 15;
}

(Go ahead! Check that it's correct for all input values!) Benchmarks on my computer, against your code and [id://hv]'s:

          Rate Test4 Test5 Test7 Test6 Test0
Test4  64233/s    --  -33%  -33%  -52%  -72%
Test5  95523/s   49%    --   -1%  -29%  -58%
Test7  96399/s   50%    1%    --  -28%  -58%
Test6 133602/s  108%   40%   39%    --  -41%
Test0 227756/s  255%  138%  136%   70%    --

[ambrus]

Are you a hacker? Don't you know the C precedence table by heart? Then why do you need those crazy parentheses around the multiplication?

Isn't this enough:

sub test1 {
        (($_[0] & $_[1]) * 2113665 & 17895697) % 15;
}

Anyway, I like your method. Nice idea to search in HAKMEM. As you can see below, I've given a less concise solution.

[PerlingTheUK]

Tried and tested it, but next year by this time, I still want to understand what the heck I did. Unless set a link in my comments that would be impossible.

[jkelly]

Kaif, I'd looove to understand what's going on there in test0. I'm not going to ask you for an explanation because I reckon that'd take some time, but would you mind pointing me in the right direction? What do I need to learn first in order to take that apart? Thanks.

[kaif]

Here's a hint: 0b1000000100000010000001 == 2113665 and 0b1000100010001000100010001 == 17895697. I'd gladly explain what's going on, but it seems that some people have already done it online, so I'll link to them instead. In short, multiplying by the first value "repeats" the input four times, while the second knocks out all but every fourth bit. Finally, we "cast out 15s".

Online resources: [id://spurperl], below, linked to Bit Twiddling Hacks by Sean Eron Anderson of Stanford which contains this and many other bit hacks. Anderson, in turn, links to A Modulo Based Bit Counting Approach For 64 Bit Systems by Roshan James, an explanation of my solution above (more or less). Simply note the differences in integer size (they have 64 bits, while most of us only have 32) and requirements (our input is at most 7 bits, and they allow 16). I personally was inspired by a section of the HAKMEM, as I linked above (this also has a difference in size --- the PDP-1110 had 36-bit integers --- and requirements --- 9 bit input).

[Anonymous Monk]

Excellent! Thanks for the brief explanation and for giving me a sturdy nudge in the right direction.