Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask

Re: Loops loosing Performance

by kaif (Friar)
on Jun 09, 2005 at 23:53 UTC ( #465358=note: print w/replies, xml ) Need Help??

in reply to Loops loosing Performance

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 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% --

Replies are listed 'Best First'.
Re^2: Loops loosing Performance
by ambrus (Abbot) on Jun 10, 2005 at 10:16 UTC

    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.

Re^2: Loops loosing Performance
by PerlingTheUK (Hermit) on Jun 10, 2005 at 06:38 UTC
    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.

Re^2: Loops loosing Performance
by jkelly (Initiate) on Jun 10, 2005 at 07:55 UTC
    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.

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

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

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://465358]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (3)
As of 2022-05-25 07:32 GMT
Find Nodes?
    Voting Booth?
    Do you prefer to work remotely?

    Results (85 votes). Check out past polls.