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);
);
}
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

Replies are listed 'Best First'.
Re^4: Efficient bit-twiddling in Perl.
by danaj (Friar) 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);
for (1 .. \$ITERS ) {
}
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);
);
}
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 ) {
);
}
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.

Create A New User
Node Status?
node history
Node Type: note [id://1021145]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (4)
As of 2017-12-16 00:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What programming language do you hate the most?

Results (446 votes). Check out past polls.

Notices?