At work we have a module that does some bitmask operations to do things like check user permissions and so forth. For example, an applicaion might have a line like:

if( $user->permits( FOO ) )
[download]

Where FOO is an imported constant integer with one bit on, which is bitwise-ANDed with the user's permissions bitfield to determine if he has the appropriate bit. Additionally, you commonly see stuff like this:

if( $user->permits( FOO | BAR | BAZ ) )
[download]

Which constructs a new bitmask with three bits on, all of which must be present in the user's permissions bits.

There are lots of permissions, and many applications have to do lots of different permissions checks all over the place. This common method was chosen because it's faster than doing a hash lookup or a method call to determine if something is allowed. Internally, the permits method is implimented quite simply:

package User;
...
use constant FOO => 1 << 1;
use constant BAR => 1 << 2;
use constnat BAZ => 1 << 3;
...
sub permits { 
    my ($self, $mask) = @_;
    return ($self->{perms} & $mask);
}
[download]

So far so good. But as client needs grew and changed, more and more permissions were added. Eventually, someone tried 1 << 32, and was dismayed when it didn't work. Our Perl only supports 32-bit integers. So someone changed those integers to Math::BigInts, and the problem was solved. Or so they thought.

Math::BigInt is very slow. Even if you use one of the C backends instead of the pure Perl implimentation, it's still painfully phlegmatic. But nobody realized just how much overhead was caused by BigInt until some Apache::DProfing revealed that nearly 20% of the program's execution time was spent in BigInt!

A better solution was demanded. After some consideration, I figured that most of the overhead of a BigInt implimentation is in dealing with integers of unlimited size, and munging integers of different sizes together. But all of our permissions could be represented as giant integers exactly 128 bits wide. The only operations they need to do are bitwise-AND and bitwise-OR, both of which are simple. I figured I could use some overloading to impliment them as arrays of four 32 bit integers each. Here's what I came up with as a test.

package FriedoBits; 

use strict;

use overload '|' => \&bitor;
use overload '&' => \&bitand;

sub bitor { 
    my ($a, $b) = @_;

    my $new = [ ];
    for(0..3) { 
        $new->[$_] = ( $a->[$_] | $b->[$_] );
    }

    return __PACKAGE__->new( $new );
}

sub bitand { 
    my ($a, $b) = @_;

    my $new = [ ];
    for(0..3) { 
        $new->[$_] = ( $a->[$_] & $b->[$_] );
    }

    return __PACKAGE__->new( $new );
}

sub new {
    return bless $_[1], ref($_[0]) || $_[0];
}


use constant PERM_0000 => FriedoBits->new( 
  [ 0x00000000, 0x00000000, 0x00000000, 0x00000001 ] );
use constant PERM_0001 => FriedoBits->new( 
  [ 0x00000000, 0x00000000, 0x00000000, 0x00000002 ] );
use constant PERM_0002 => FriedoBits->new( 
  [ 0x00000000, 0x00000000, 0x00000000, 0x00000004 ] );
use constant PERM_0003 => FriedoBits->new( 
  [ 0x00000000, 0x00000000, 0x00000000, 0x00000008 ] );
use constant PERM_0004 => FriedoBits->new( 
  [ 0x00000000, 0x00000000, 0x00000000, 0x00000010 ] );
use constant PERM_0005 => FriedoBits->new( 
  [ 0x00000000, 0x00000000, 0x00000000, 0x00000020 ] );
...
use constant PERM_0125 => FriedoBits->new( 
  [ 0x20000000, 0x00000000, 0x00000000, 0x00000000 ] );
use constant PERM_0126 => FriedoBits->new( 
  [ 0x40000000, 0x00000000, 0x00000000, 0x00000000 ] );
use constant PERM_0127 => FriedoBits->new( 
  [ 0x80000000, 0x00000000, 0x00000000, 0x00000000 ] );

1;
[download]

Benchmarking showed just how much better this was:

Benchmark: timing 100000 iterations of BigInt...
    BigInt: 188 wallclock secs 
(168.07 usr +  0.36 sys = 168.43 CPU) @ 593.72/s (n=100000)

Benchmark: timing 100000 iterations of BigIntGMP...
 BigIntGMP: 44 wallclock secs 
(38.50 usr +  0.13 sys = 38.63 CPU) @ 2588.66/s (n=100000)

Benchmark: timing 100000 iterations of FriedoBits...
FriedoBits:  3 wallclock secs ( 3.11 usr +  0.01 sys =  3.12 CPU) @ 32
+051.28/s (n=100000)
[download]

That's nearly 100 times faster than the pure Perl version, and more than 10 times faster than the C version. Of course these are not really integers. You can't add them or subtract them or find their square roots. But for our purposes we don't need to, so why waste the time? Coming up with ideas like this is one of the reasons I love programming. (I'm quite certain it's a solution which has been invented many, many times before now. But I will bask in the glory anyway.)