Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re^3: Efficient bit-twiddling in Perl.

by ggoebel (Sexton)
on Mar 01, 2013 at 03:43 UTC ( #1021145=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Efficient bit-twiddling in Perl.
in thread Efficient bit-twiddling in Perl.

Bit::Vector as you might guess isn't any better...

use strict; use warnings; use Time::HiRes qw[ time ]; use Bit::Vector; my @lookup; $#lookup = 0x3ffff; $lookup[ $_ ] = [ ( $_ & 0x3f000 ) >> 12, ( $_ & 0xfc0 ) >> 6, $_ & 0x +3f ] for 0 .. 0x3ffff; my( @nxt, @mid, @bot ); $nxt[ $_ ] = ( $_ & 0x3f000 ) >> 12, $mid[ $_ ] = ( $_ & 0xfc0 ) >> 6, $bot[ $_ ] = $_ & 0x3f for 0 .. 0x3ffff; sub stuff{ # print "@_"; } our $ITERS //= 10e6; my $n = 0x80061861; my $start = time; for ( 1 .. $ITERS ) { stuff( ( $n & 0xffc00000 ) >> 18, ( $n & 0x0003f000 ) >> 12, ( $n & 0x00000fc0 ) >> 6, ( $n & 0x0000003f ) ); } printf " Shift&and took: %.12f seconds\n", ( time() - $start ) / $ITE +RS; $start = time; for ( 1 .. $ITERS ) { stuff( $n >> 18, @{ $lookup[ $n & 0x3ffff ] } ); } printf " Lookup took: %.12f seconds\n", ( time() - $start ) / $ITE +RS; $start = time; for ( 1 .. $ITERS ) { my $i = $n & 0x3ffff; stuff( $n >> 18, $nxt[ $i ], $mid[ $i ], $bot[ $i ] ); } printf " Lookup2 took: %.12f seconds\n", ( time() - $start ) / $ITE +RS; $start = time; for ( 1 .. $ITERS ) { stuff( unpack 'vccc', join'',map{ pack'b*', $_ } unpack 'a14a6a6a6 +', unpack 'B32', pack 'N', $n ); } printf " (un)pack took: %.12f seconds\n", ( time() - $start ) / $ITE +RS; $n="$n"; my $vector; $start = time; for (1 .. $ITERS ) { $vector = Bit::Vector->new_Hex(32, $n); stuff($vector->Chunk_Read(14, 18), $vector->Chunk_Read( 6, 12), $vector->Chunk_Read( 6, 6), $vector->Chunk_Read( 6, 0) ); } printf "Bit::Vector took: %.12f seconds\n", ( time() - $start ) / $ITE +RS; __END__ C:\test>perl bv.pl Shift&and took: 0.000000551174 seconds Lookup took: 0.000000272709 seconds Lookup2 took: 0.000000335823 seconds (un)pack took: 0.000003393702 seconds Bit::Vector took: 0.000005372898 seconds


Comment on Re^3: Efficient bit-twiddling in Perl.
Download Code
Re^4: Efficient bit-twiddling in Perl.
by danaj (Monk) on Mar 01, 2013 at 07:04 UTC
    The Bit::Vector code needs new_Dec, not new_Hex. Here are are some additions to your code showing Data::BitStream::XS and two alternatives using Bit::Vector. Neither are improvements over the fast simple methods, but they do show that both are at least reasonable solutions.
    $start = time; my $stream = Data::BitStream::XS->new; # $stream->write(32, $n) for 1 .. $ITERS; # Below is faster $stream->put_raw(pack("N",$n) x $ITERS, 32*$ITERS); $stream->rewind_for_read; for (1 .. $ITERS ) { stuff($stream->read(14), $stream->read(6), $stream->read(6), $stream- +>read(6)); } printf " D::B::XS took: %.12f seconds\n", ( time() - $start ) / $ITE +RS; $start = time; for (1 .. $ITERS ) { my $vector = Bit::Vector->new_Dec(32, $n); stuff($vector->Chunk_Read(14, 18), $vector->Chunk_Read( 6, 12), $vector->Chunk_Read( 6, 6), $vector->Chunk_Read( 6, 0) ); } printf "Bit::Vector took: %.12f seconds\n", ( time() - $start ) / $ITE +RS; $start = time; my $vector = Bit::Vector->new(32*$ITERS); $vector->Word_List_Store(($n) x $ITERS); for (0 .. $ITERS-1 ) { stuff($vector->Chunk_Read(14, 32*$_+18), $vector->Chunk_Read( 6, 32*$_+12), $vector->Chunk_Read( 6, 32*$_+6), $vector->Chunk_Read( 6, 32*$_+0) ); } printf "Bit::Vector took: %.12f seconds\n", ( time() - $start ) / $ITE +RS;
    I get on my computer:
    Shift&and took: 0.000000193217 seconds Lookup took: 0.000000180829 seconds Lookup2 took: 0.000000215928 seconds (un)pack took: 0.000001851533 seconds D::B::XS took: 0.000000643722 seconds Bit::Vector took: 0.000001739788 seconds Bit::Vector took: 0.000000957755 seconds
    It really depends on what the usage model is. Both Data::BitStream and Bit::Vector are going to suffer if you insist on making a new object for each word. They will do much better if you let them create a single object and fill it, then pull the data out in arbitrary sized chunks. If the OP had all the values in one chunk or array then this would be more appropriate.

    One could also write a new coding role for Data::BitStream to handle retrieving the values using code similar to one of the lookup methods, but there would have to be some real reason to want a stream vs. just doing it using one of the lookup methods.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (20)
As of 2014-11-24 20:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (147 votes), past polls