#! perl -slw use strict; package SparseBitVector; use Config; use Inline C => Config => BUILD_NOISY => 1; use Inline C => <<'END_C', NAME => 'Junk', CLEAN_AFTER_BUILD =>0; typedef unsigned __int64 U64; typedef __int64 I64; unsigned popcnt( SV *sv ) { U64 x = (U64) SvUVX( sv ); x -=( x >> 1 ) & 0x5555555555555555ULL; x = ( x & 0x3333333333333333ULL ) + ( ( x >> 2 ) & 0x3333333333333333ULL ); x = ( x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL; return (unsigned)( ( x * 0x0101010101010101ull ) >> 56 ); } END_C use Benchmark qw( cmpthese ); sub popcount1 { my $x = shift; my $count; for ($count = 0; $x; ++$count) { $x &= $x - 1 } return $count; } sub popcount2 { return sprintf('%b', shift) =~ tr/1//; } sub popcount3 { return unpack('%32b*', pack('Q', shift)); } sub popcount4 { return unpack( '%32b*', pack('Q', $_[0] ) ); } my $start = 2**32 - 42; my $end = $start + 1000000; print "sanity test for correctness\n"; for my $i (0 .. 256, $start .. $end) { my $two = popcount2($i); my $three = popcount3($i); my $four = popcount4( $i ); my $six = popcnt( $i ); $three == $two or print "$i: $two $three\n" and die; $four == $six and $three == $six or print "$i: 2:$two 3:$three 6:$six\n" and die; } cmpthese -3, { # One => sub { popcount1($_) for $start .. $end }, Two => sub { popcount2($_) for $start .. $end }, Three => sub { popcount3($_) for $start .. $end }, Four => sub { popcount4($_) for $start .. $end }, Six => sub { popcnt( $_) for $start .. $end }, }; #### C:\test>1199987.pl sanity test for correctness Rate Two Three Four Six Two 1.02/s -- -4% -5% -58% Three 1.06/s 4% -- -1% -57% Four 1.08/s 5% 1% -- -56% Six 2.45/s 140% 131% 128% --