Beefy Boxes and Bandwidth Generously Provided by pair Networks DiBona
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: Efficient bit-twiddling in Perl.

by kcott (Abbot)
on Mar 01, 2013 at 08:56 UTC ( #1021191=note: print w/ replies, xml ) Need Help??


in reply to Efficient bit-twiddling in Perl.

G'day BrowserUk,

I tried this a few different ways. Shifting first then just ANDing the six bits seems to be faster than ANDing then shifting. About half of the time seemed to be taken with the assignments, so if you can avoid some or all of those you get additional improvements. Here's the various tests:

#!/usr/bin/env perl use 5.010; use strict; use warnings; use Benchmark qw{cmpthese :hireswallclock}; my $n = 0x80061861; say "and_rshift: $n => ", join(' : ', and_rshift()); say "lshift_rshift: $n => ", join(' : ', lshift_rshift()); say "mixed: $n => ", join(' : ', mixed()); say "mixed_assign: $n => ", join(' : ', mixed_assign()); say "just_shift: $n => ", join(' : ', just_shift()); cmpthese(-10, { and_rshift => \&and_rshift, lshift_rshift => \&lshift_rshift, mixed => \&mixed, mixed_assign => \&mixed_assign, just_shift => \&just_shift, }); sub and_rshift { my $top14 = ( $n & 0xfffc0000 ) >> 18; my $nxt6 = ( $n & 0x0003f000 ) >> 12; my $mid6 = ( $n & 0x00000fc0 ) >> 6; my $bot6 = ( $n & 0x0000003f ); return ($top14, $nxt6, $mid6, $bot6); } sub lshift_rshift { my $top14 = $n >> 18; my $nxt6 = $n << 46 >> 58; my $mid6 = $n << 52 >> 58; my $bot6 = $n << 58 >> 58; return ($top14, $nxt6, $mid6, $bot6); } sub mixed { return ($n >> 18, $n >> 12 & 0x3f, $n >> 6 & 0x3f, $n & 0x3f); } sub mixed_assign { my $top14 = $n >> 18; my $nxt6 = $n >> 12 & 0x3f; my $mid6 = $n >> 6 & 0x3f; my $bot6 = $n & 0x3f; return ($top14, $nxt6, $mid6, $bot6); } sub just_shift { return ($n >> 18, $n << 46 >> 58, $n << 52 >> 58, $n << 58 >> 58); }

Output:

$ pm_bit_twiddle.pl and_rshift: 2147883105 => 8193 : 33 : 33 : 33 lshift_rshift: 2147883105 => 8193 : 33 : 33 : 33 mixed: 2147883105 => 8193 : 33 : 33 : 33 mixed_assign: 2147883105 => 8193 : 33 : 33 : 33 just_shift: 2147883105 => 8193 : 33 : 33 : 33 Rate and_rshift lshift_rshift mixed_assign just_shi +ft mixed and_rshift 1942328/s -- -7% -11% -5 +2% -53% lshift_rshift 2088397/s 8% -- -4% -4 +8% -50% mixed_assign 2182671/s 12% 5% -- -4 +6% -48% just_shift 4037158/s 108% 93% 85% +-- -3% mixed 4163497/s 114% 99% 91% +3% --

-- Ken


Comment on Re: Efficient bit-twiddling in Perl.
Select or Download Code
Re^2: Efficient bit-twiddling in Perl.
by BrowserUk (Pope) on Mar 01, 2013 at 13:39 UTC

    I fed your JustShift solution (a cute bit of lateral thinking :), into my benchmark and on my hardware it is a tad slower than shift&and:

    C:\test>1021064 Shift&and took: 0.000000611130 seconds justshift took: 0.000000651048 seconds Lookup took: 0.000000488745 seconds Lookup2 took: 0.000000706896 seconds (un)pack took: 0.000007464467 seconds

    I was a bit surprised by that as both shift & and are designated as single clock operations on my cpu. I guess the difference is in the perl operations that overlay them.

    I follow your drift regarding the effect that assignment and stack handling can have on a benchmark of this nature; but the values are re-used several times through the rest of the body of the inner loop, so the assignment is a constant factor that I've chosen to exclude.


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re^2: Efficient bit-twiddling in Perl.
by Tux (Monsignor) on Mar 01, 2013 at 14:16 UTC

    When you reduce the overhead of the function calls (by doing the work you actually time in a tight loop), you might get other numbers

    and_rshift: 2147883105 => 8193 : 33 : 33 : 33 lshift_rshift: 2147883105 => 8193 : 33 : 33 : 33 mixed: 2147883105 => 8193 : 33 : 33 : 33 mixed_assign: 2147883105 => 8193 : 33 : 33 : 33 just_shift: 2147883105 => 8193 : 33 : 33 : 33 Rate just_shift mixed mixed_assign and_rshift lsh +ift_rshift just_shift 247/s -- -2% -43% -48% + -52% mixed 252/s 2% -- -42% -47% + -52% mixed_assign 434/s 75% 72% -- -9% + -16% and_rshift 480/s 94% 90% 10% -- + -8% lshift_rshift 520/s 110% 106% 20% 8% + --

    Enjoy, Have FUN! H.Merijn

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (8)
As of 2014-04-19 16:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (483 votes), past polls