This was my first attempt to post on PerlMonks. The main lesson I got from this fiasco is that you don't just need to find the time to post, but also post when you'll have time to respond for a day or two.

Anyway, the following benchmarks are typical of quite a few I ran (including large and huge sizes of arrays). The dramatic thing is that even though indexing into an array (called "wheel" here in the first set) is not especially fast, indexing into an array to increment the index while indexing into an array, is faster than any other way of stepping one step. The only explanation I can see, is that the code for indexing is already in the instruction cache. Any other method, by definition, requires two unrelated series of instructions to be loaded.
(Why the "pow2modix" slows down _so_ much, I don't know. update: because the first(fast) one is optimized away in void context?)

Anyway, here's some benchmarks and, no, I won't be able to respond quickly to comments, but will eventually. (It's so "stale" already, that further slow response, if there are comments, probably won't be noticed.) 
$ uname -a
SunOS xxxxxx 5.6 Generic_105181-15 sun4u sparc SUNW,Ultra-2
$ perl -v

This is perl, version 5.005_03 built for sun4-solaris

$ perl -MBenchmark -e 'my $m=3; my ($xe,$xp,$xa,$xw)=($m)x4;
                       my @n=(1..$m,0); my @a=("")x$m+1;
timethese(-5, { ashiftp => q{ shift @a if $#a==$m },
               equaland => q{ $xe < $m and ++$xe or $xe = 0 },
                pow2and => q{ scalar(++$xp, $xp &= $m) },
                pow2mod => q{ ++$xp & $m },
                  wheel => q{ $xw = $n[$xw] },
} );' |
perl -nawe '$.==1 and print and next;($x=$F[14])=~s/\/.*//;$b||=$x;
  printf"%12s %12s  %5.2fusecs  %.2f\n",@F[0,14],1000000/$x,$b/$x' -
perl -MBenchmark -e 'my $m=3;my($x,$xe,$xa,$xp,$xw)=($m)x5;my @n=(1..$
+m,0);
             my (@a,@ai,@ae,@aa,@ap,@aw); @a=@ai=@ae=@aa=@ap=@aw=("")x
+$m+1;
timethese(-5, {   ashpush => q{ shift @a; push @a, $x },
                ashifpush => q{ shift @ai if $#ai == $m; push @ai, $x 
+},
               equalandix => q{ $ae[ $xe < $m and ++$xe or $xe = 0 ] =
+ $xe },
                pow2andix => q{ $aa[ ++$xa, $xa &= $m ] = $xa },
                pow2modix => q{ $ap[ ++$xp & $m ] = $xw },
                  wheelix => q{ $aw[ $xw = $n[$xw] ] = $xw },
} );' |
perl -nawe '$.==1 and print and next;($x=$F[14])=~s/\/.*//;$b||=$x;
 printf"%12s %12s  %5.2fusecs  %.2f\n",@F[0,14],1000000/$x,$b/$x' -

> > > > > > > > Benchmark: running ashiftp, equaland, pow2and, pow2mod
+,\
 wheel, each for at least 5 CPU seconds...\

    ashiftp:  280765.34/s   3.56usecs  1.00
   equaland:  341119.76/s   2.93usecs  0.82
    pow2and:  368781.20/s   2.71usecs  0.76
    pow2mod:  568666.50/s   1.76usecs  0.49
      wheel:  451163.20/s   2.22usecs  0.62

$ > > > > > > > > > > Benchmark: running ashifpush, ashpush, equalandi
+x,\
 pow2andix, pow2modix, wheelix, each for at least 5 CPU seconds...\

  ashifpush:  115283.93/s   8.67usecs  1.00
    ashpush:  223748.51/s   4.47usecs  0.52
 equalandix:  198690.04/s   5.03usecs  0.58
  pow2andix:  209246.30/s   4.78usecs  0.55
  pow2modix:  212778.91/s   4.70usecs  0.54
    wheelix:  255846.92/s   3.91usecs  0.45


$ uname -a
Linux xxxxxx 2.2.14 #1 SMP Mon Mar 27 16:46:10 EST 2000 i686 unknown
$ perl -v

This is perl, version 5.005_03 built for i386-linux

Benchmark: running ashiftp, equaland, pow2and, pow2mod, wheel,\
 each for at least 5 CPU seconds...\

    ashiftp:  886579.73/s   1.13usecs  1.00
   equaland: 1030440.00/s   0.97usecs  0.86
    pow2and: 1309018.03/s   0.76usecs  0.68
    pow2mod: 1750427.08/s   0.57usecs  0.51
      wheel: 1243260.48/s   0.80usecs  0.71

Benchmark: running ashifpush, ashpush, equalandix, pow2andix, pow2modi
+x,\
 wheelix, each for at least 5 CPU seconds...\

  ashifpush:  237115.60/s   4.22usecs  1.00
    ashpush:  437152.00/s   2.29usecs  0.54
 equalandix:  548898.80/s   1.82usecs  0.43
  pow2andix:  514532.10/s   1.94usecs  0.46
  pow2modix:  485667.44/s   2.06usecs  0.49
    wheelix:  645636.33/s   1.55usecs  0.37

[download]


p

In reply to Re: Circular buffer instead of shift/push by petral
in thread Circular buffer instead of shift/push by petral

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.