Re: [Fun With Perl] Another oddity from the days of assembler

[Mark-Jason Dominus <mjd@plover.com>]

>From vlb@cfcl.com  Mon Jun 14 09:11:22 1999  - apologies for the delay - vlb]
Message-ID: <19990614160354.24613.qmail@plover.com>
In-reply-to: Your message of "Mon, 14 Jun 1999 11:02:51 EDT."
              <19990614110251.A1607007@linguist.dartmouth.edu>
Date: Mon, 14 Jun 1999 12:03:54 -0400


> > > this little snippet is not Perl-specific, but it is a bit tricky to
> > > figure out what is going on:

When people talk about this stuff in the C newsgroups, someone always
comes along and spoils the fun by saying `The fastest *and* simplest
way it to just use a lookup table.'

> The pack/unpack/tr version is about twice as fast as the original.

The lookup table version is about twice as fast as the pack/unpack/tr
version:


     nul => sub {
         for $n (0..$m) {
#           print "$n\t$x\n";
         }
     },
     lt1 => sub {
         for $n (0..$m) {
             my $b = $bs[$n];
#           print "$n\t$b\n";
         }
     },
     lt2 => sub {
         for $n (0..$m) {
            my $b = $bs[$n & 0xff];
            $b += $bs[$n & 0xff00 >> 8] ;
            $b += $bs[$n & 0xff0000 >> 16];
            $b += $bs[$n & 0xff000000 >> 24];
#           print "$n\t$b\n";
         }
     },


Here `@bt' has been initialized with 256 values as follows:

	for ($i=0; $i < 256; $i++) {
	  my $b = 0;
	  my $n = $i;
	  while ($n) { $n &= $n-1, $b++ ; }
	  $bs[$i] = $b;
	}


Results:

plover% perl /tmp/rk.pl 5 11
        len:  6 wallclock secs ( 3.08 usr +  0.00 sys =  3.08 CPU)
        lt1:  1 wallclock secs ( 0.32 usr +  0.00 sys =  0.32 CPU)
        lt2:  2 wallclock secs ( 0.89 usr +  0.00 sys =  0.89 CPU)
        nul:  0 wallclock secs ( 0.13 usr +  0.00 sys =  0.13 CPU)
        tr_:  3 wallclock secs ( 1.49 usr +  0.00 sys =  1.49 CPU)
       vec1:  7 wallclock secs ( 3.23 usr +  0.00 sys =  3.23 CPU)
       vec2: 11 wallclock secs ( 5.84 usr +  0.00 sys =  5.84 CPU)
        whi:  1 wallclock secs ( 1.10 usr +  0.00 sys =  1.10 CPU)

lt1 is the verion to use if you know that $n will always fit in one byte.

==== Want to unsubscribe from this list? (Don't you love us anymore?)
==== Well, if you insist... Send mail with body "unsubscribe" to
==== fwp-request@technofile.org

</x-flowed>