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.)

In reply to Freed From the Tyranny of Math::BigInt by friedo

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.