An array of boolean values in a bitfield

Say you have an array of boolean values. Each element of the array needs to be merely true or false. I'd normally implement the array this way.

my @bools;
$bools[0] = 1;   # element 0 is true
$bools[1] = '';  # element 1 is false
[download]

To get a list (or count) of the indexes with true values, just grep.

my @trues = grep $bools[$_], 0 .. $#bools;
[download]

There's not much to do with such an array besides enumerate the true/false elements and check whether any one element is true or false.

Scaling up

But what if you have a very large array? Devel::Size tells me that the simple @bools above (with one true and one false) amounts to 116 bytes. Adding ten more elements (half true, half false), adds 252 bytes. An array of 10_000_000 elements is 287_108_904 bytes—to store data that's all single bits.

You can store the same data in a scalar as bits using vec.

my $bools;
vec( $bools, 0, 1 ) = 1;  # element 0 is true
vec( $bools, 1, 1 ) = 0;  # element 1 is false
[download]

The storage space required is much more modest—just 1_250_028 bytes for 10_000_000 elements.

You can still grep for true indexes:

my @trues = grep vec( $bools, $_, 1 ), 0 .. 8 * length $bools;
[download]

Unfortunately, that will still build a huge list to scan over, so a for loop is more memory efficient.

foreach my $i ( 0 .. 8 * length $bools ) {
    push @trues, $i if vec( $bools, $i, 1 );
}
[download]

If all you want is a count of true elements, a regular expression can scan over the field faster than a loop.

# for each character, count the on bits in that character
my %bits_in;
foreach my $char ( map { chr } 0 .. 255 ) {
    foreach my $bit ( 0 .. 7 ) {
        $bits_in{ $char } += vec( $char, $bit, 1 );
    }
}

my $count;
$count += $bits_in{ $1 } while ( $bools =~ m{([^\000])}g );
[download]

I also tested a destructive algorithm using chop, and it's usually faster than regular expressions. The regexp is still faster on a sparse array (with >90% false values).

my $count;
$count += $bits_in{ chop $bits } while $bits;
[download]

Of course, destruction of the structure has its own problems. Either you lose the data structure, or you have to copy it. That could be a problem if memory is getting tight.

Not quite as fast as chopping is to use substr and walk down the bits eight at a time.

my $count;
$count += $bits_in{ substr $bits, $_, 1 } for 0 .. length( $bits ) - 1
+;
[download]

Other implementations

I wonder if there's any interest in making this into a module that can be tied to an array. I see Tie::Array::Packed and Tie::Array::Pack on CPAN, apparently based on pack and unpack, but I don't see mention of single bit values being supported by them. There's Bit::Vector which operates on a vector like this, but it doesn't tie. I'm surprised not to find a tied array implementation based on single bits, so I'm wondering if I'm missing something.

I'd also be interested to hear other monks' implementations of enumerating or counting elements in the array. (If I were writing a tied array implementation, I'd just keep a count as a separate value, but that's not feasible for the application that lead me to this data structure. For me, it's useful to do bitwise operations on the fields I'm maintaining. I have an expression, "$x | $y ^ $y", which is every element in $x but not in $y. After that, I want to list each index.)

Thanks

Thanks to jeffa, tye, and ysth for their comments on an earlier draft of this meditation.

Performance testing

Here's the Benchmark I used for comparing performance:

use Benchmark qw( cmpthese );

my %bits_in;
foreach my $char ( map { chr } 0 .. 255 ) {
    foreach my $bit ( 0 .. 7 ) {
        $bits_in{ $char } += vec( $char, $bit, 1 );
    }
}

my @tests = (
    [          8,   1 ],
    [          8,   8 ],
    [      1_000,   1 ],
    [      1_000,  10 ],
    [      1_000, 100 ],
    [      1_000, 500 ],
    [      1_000, 900 ],
    [  1_000_000,       1 ],
    [  1_000_000,     100 ],
    [  1_000_000, 100_000 ],
    [  1_000_000, 500_000 ],
    [  1_000_000, 900_000 ],
    );

#use Test::More;
#plan 'tests' => 3 * scalar @tests;

foreach my $t ( @tests ) {
    my $bits = mkbits( @{ $t } );
    printf "%d, %d\n", @{ $t };

#    my $v = vec_count( $bits );
#    is( $v, re_count( $bits ), "re counted $v" );
#    is( $v, chop_count( $bits ), "chop counted $v" );
#    is( $v, loop_count( $bits ), "loop counted $v" );

    cmpthese( -1, {
        'vec'  => sub { vec_count( $bits ) },
        're'   => sub { re_count( $bits ) },
        'chop' => sub { chop_count( $bits ) },
        'loop' => sub { loop_count( $bits ) },
              }
        );
}

sub chop_count {
    my ( $bits ) = @_;

    my $count;
    $count += $bits_in{ chop $bits } while $bits;

    return $count;
}

sub vec_count {
    my ( $bits ) = @_;

    my $bit_count = length( $bits ) * 8;
    my $count;
    $count += vec( $bits, $_, 1 ) for 0 .. $bit_count;

    return $count;
}

sub re_count {
    my ( $bits ) = @_;

    my $count;
    $count += $bits_in{ $1 } while ( $bits =~ m{([^\000])}g );

    return $count;
}

sub loop_count {
    my ( $bits ) = @_;

    my $count;
    $count += $bits_in{ substr $bits, $_, 1 } for 0 .. length( $bits )
+ - 1;

    return $count;
}

sub mkbits {
    my ( $bitcount, $ones ) = @_;

    my $bits = "\000" x int( $bitcount / 8 );
    while ( $ones-- ) {
        vec( $bits, rand $bitcount, 1 ) = 1;
    }

    return $bits;
}
[download]

Comment on An array of boolean values in a bitfield Select or Download Code

Replies are listed 'Best First'.
Re: An array of boolean values in a bitfield by tilly (Archbishop) on Dec 03, 2008 at 17:43 UTC
This is what vec is for. I found the memory savings very useful in handling several of the Project Euler problems. However I found that if I needed to access all of the bits multiple times, and wasn't running out of memory, then the traditional array was faster. Random tip. The value undef is less than half the size of an empty string and works just as well in the traditional array approach. It is still a memory hog, but the difference can be significant if you're near your memory limit and you don't want to go to using vec yet.	[reply]
Re: An array of boolean values in a bitfield by gone2015 (Deacon) on Dec 03, 2008 at 19:14 UTC
I tried the following, which gave some performance improvements... benchmark output below. my @bits_in = map $bits_in{chr($_ & 0xFF)} + $bits_in{chr($_ >> 8)}, ( +0..65535) ; # Use vec() and @bits_in -- faster than ord(substr(..)) sub loop_count_va { # "lpva" my ( $bits ) = @_; my $count; $count += $bits_in[vec($bits, $_, 8)] for 0 .. length( $bits ) - 1 +; return $count; } # As "lpva" but 16 bits at a time sub loop_count_VA { # "lpVA" my ( $bits ) = @_; my $count; $count += $bits_in[vec($bits, $_, 16)] for 0 .. (length( $bits ) - + 1) >> 1 ; return $count; } # The other other scheme sub unpack_count { # "unpk" my ( $bits ) = @_ ; my $count = unpack("%32b*", $bits); if ($count != $COUNT) { die "unpack_count $count != $COUNT" ; } ; return $count; } [download] Read more... See benchmark output (6 kB)	[reply] [d/l]
Re^2: An array of boolean values in a bitfield by kyle (Abbot) on Dec 03, 2008 at 19:32 UTC
Thank you! That's a pretty big win for unpack. It's too bad every time I learn how to use it I forget it by the time I need it again.	[reply]
Re: An array of boolean values in a bitfield by BrowserUk (Patriarch) on Dec 03, 2008 at 23:45 UTC
You can save another ~25% or so on large bitstrings by avoiding duplicating the bitvector. Just use the aliasing nature of the elements of `@_`: `sub unpack_count_ref { my $count = unpack("%32b*", $_[ 0 ] ); return $count; }` [download] 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. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply] [d/l] [select]
Re: An array of boolean values in a bitfield by jwkrahn (Abbot) on Dec 03, 2008 at 19:44 UTC
If you want a fast bit counter use unpack: `sub unpack_count { my ( $bits ) = @_; my $count = unpack '%32b*', $bits; return $count; }` [download]	[reply] [d/l]
Re: An array of boolean values in a bitfield by LanX (Saint) on Dec 03, 2008 at 17:59 UTC
did you consider using a lookup-table to calculate the number of bits, changing time with memory-complexity? for example `# for each character, count the on bits in that character my %bits_in; foreach my $char ( map { chr } 0 .. 255 ) { foreach my $bit ( 0 .. 7 ) { $bits_in{ $char } += vec( $char, $bit, 1 ); } }` [download] could be written `# for each character, count the on bits in that character my %bits_in; foreach my $char ( map { chr } 0 .. 255 ) { $bits_in{ $char } = $sum[ $char ]; }` [download] Cheers Rolf	[reply] [d/l] [select]
Re^2: An array of boolean values in a bitfield by kyle (Abbot) on Dec 03, 2008 at 18:08 UTC
Where do you get the array `@sum`? The point of the loop that you're commenting on is specifically to build a lookup table that maps a chr to the number of '1' bits that are in it. That table gets used in some of the bit counting methods that follow.	[reply] [d/l]
Re^3: An array of boolean values in a bitfield by LanX (Saint) on Dec 03, 2008 at 18:16 UTC
I get it, so @sum and %bits_in have the same purpose! I'm just confused, why do you care about the speed to calculate a constant table with only 256 entries? And why do you use a hash if speed counts? ... arrays are much faster! Cheers Rolf	[reply]
Re^4: An array of boolean values in a bitfield by kyle (Abbot) on Dec 03, 2008 at 18:22 UTC
Re^5: An array of boolean values in a bitfield by LanX (Saint) on Dec 03, 2008 at 18:44 UTC
Some notes below your chosen depth have not been shown here
Re: An array of boolean values in a bitfield by ikegami (Patriarch) on Dec 03, 2008 at 18:25 UTC
The absence of any mention of PDL seems glaring.	[reply]
Re^2: An array of boolean values in a bitfield by bennymack (Pilgrim) on Dec 05, 2008 at 14:22 UTC
I'm not a PDL expert by any means but I did up a simple benchmark for it. It only seems to be faster for larger vectors. I didn't check them memory usage but I assume it's higher. I feel that the real win using PDL is the auto-threading and the cleanliness of the code that it provides. use PDL; foreach my $t ( @tests ) { my $bits = mkbits( @{ $t } ); my $pdl = pdl( map { vec( $bits, $_, 1 ) } 0 .. length( $bits ) * + 8 ); cmpthese( -1, { 'vec' => sub { vec_count( $bits ) }, 're' => sub { re_count( $bits ) }, 'chop' => sub { chop_count( $bits ) }, 'loop' => sub { loop_count( $bits ) }, 'pdl' => sub { pdl_count_1( $pdl ) }, }); } sub pdl_count_1 { my ( $pdl ) = @_; # return $pdl->which->getdim( 0 ); return $pdl->which->nelem; } __END__ 8, 1 Rate pdl vec re loop chop pdl 102399/s -- -75% -82% -85% -90% vec 413537/s 304% -- -29% -39% -59% re 584645/s 471% 41% -- -14% -42% loop 681314/s 565% 65% 17% -- -32% chop 1006035/s 882% 143% 72% 48% -- 8, 8 Rate pdl vec re loop chop pdl 101433/s -- -76% -83% -86% -90% vec 417552/s 312% -- -29% -41% -58% re 584645/s 476% 40% -- -17% -41% loop 703248/s 593% 68% 20% -- -29% chop 988689/s 875% 137% 69% 41% -- 1000, 1 Rate vec loop chop pdl re vec 8499/s -- -80% -82% -88% -97% loop 41533/s 389% -- -12% -40% -86% chop 47287/s 456% 14% -- -31% -84% pdl 68922/s 711% 66% 46% -- -76% re 290443/s 3317% 599% 514% 321% -- 1000, 10 Rate vec loop chop pdl re vec 8614/s -- -79% -81% -87% -93% loop 40785/s 373% -- -12% -40% -67% chop 46419/s 439% 14% -- -31% -62% pdl 67622/s 685% 66% 46% -- -45% re 123675/s 1336% 203% 166% 83% -- 1000, 100 Rate vec re loop chop pdl vec 8532/s -- -71% -79% -81% -86% re 29538/s 246% -- -27% -35% -50% loop 40193/s 371% 36% -- -12% -33% chop 45510/s 433% 54% 13% -- -24% pdl 59650/s 599% 102% 48% 31% -- 1000, 500 Rate vec re loop pdl chop vec 8533/s -- -50% -78% -80% -81% re 17148/s 101% -- -57% -60% -61% loop 39456/s 362% 130% -- -8% -11% pdl 42708/s 400% 149% 8% -- -3% chop 44246/s 419% 158% 12% 4% -- 1000, 900 Rate vec re loop pdl chop vec 9050/s -- -46% -77% -78% -80% re 16747/s 85% -- -58% -60% -63% loop 40193/s 344% 140% -- -3% -11% pdl 41533/s 359% 148% 3% -- -8% chop 45081/s 398% 169% 12% 9% -- 1000000, 1 Rate vec loop chop pdl re vec 8.57/s -- -81% -84% -96% -99% loop 44.1/s 415% -- -18% -77% -93% chop 54.1/s 531% 22% -- -72% -92% pdl 193/s 2148% 336% 256% -- -71% re 667/s 7681% 1411% 1134% 246% -- 1000000, 100 Rate vec loop chop pdl re vec 8.65/s -- -80% -83% -96% -99% loop 44.2/s 411% -- -12% -77% -93% chop 50.5/s 483% 14% -- -74% -92% pdl 194/s 2147% 340% 285% -- -70% re 643/s 7327% 1353% 1174% 231% -- 1000000, 100000 Rate vec re loop chop pdl vec 8.57/s -- -72% -80% -82% -94% re 30.5/s 256% -- -29% -35% -79% loop 42.7/s 398% 40% -- -9% -71% chop 47.1/s 450% 55% 10% -- -68% pdl 148/s 1622% 384% 245% 213% -- 1000000, 500000 Rate vec re loop chop pdl vec 8.65/s -- -51% -80% -82% -88% re 17.6/s 103% -- -58% -63% -75% loop 42.3/s 389% 140% -- -11% -40% chop 47.3/s 446% 169% 12% -- -33% pdl 70.4/s 713% 300% 66% 49% -- 1000000, 900000 Rate vec re loop chop pdl vec 8.65/s -- -50% -80% -82% -87% re 17.4/s 101% -- -59% -63% -74% loop 43.0/s 397% 147% -- -10% -35% chop 47.7/s 451% 174% 11% -- -28% pdl 66.0/s 663% 279% 54% 38% -- [download]	[reply] [d/l]
Re^2: An array of boolean values in a bitfield by kyle (Abbot) on Dec 03, 2008 at 18:27 UTC
I've never used PDL. How well does it do this kind of thing?	[reply]
Re^3: An array of boolean values in a bitfield by ikegami (Patriarch) on Dec 03, 2008 at 18:41 UTC
Neither have I, thus my curiosity.	[reply]