String performance + Shootout examples (was: newbie question - strings and arrays)

[Mike Pall <mikelu-0510@...>]

Hi,

Gavin Wraith wrote:
> The fact that strings in Lua are not updatable means that you have
> to use quite different algorithms for efficient string handling in Lua
> from those one would use for C.

For a drastic example, have a look at:

http://shootout.alioth.debian.org/benchmark.php?test=revcomp&lang=all&sort=fullcpu

First take a look at the C solution (labeled 'C GCC #2').
This is a simple in-place reversal mixed with a lookup table.
Performs really well.

Then have a look at the 'reference' implementation in Lua
(the one labeled 'Lua', not the one labeled 'Lua #2').
This one is 150 times slower than the C solution. Ouch!

First puzzle for your weekend:

  Try to understand what it does and why it performs so badly.
  Try to tune it, see how good you get _before_ looking at
  my solution.

Then have a look at my solution (with ideas from Rici Lake),
labeled 'Lua #2'. It's 11 times faster than the reference
implementation, which is a rather unusual improvement for
tuning a benchmark.

It's still 13 times slower than the C solution. But with
Lua 5.0 (lacking string.reverse) there is not much left
to tune.

Second puzzle:

  Try to understand how my solution works, where the magic
  constants come from and which performance tricks have been
  used. IMHO this is _really_ hard.
  I'll post the explanation next week. ;-)

If you want to test the programs yourself, you need to feed
them the input generated from the 'fasta' benchmark:

http://shootout.alioth.debian.org/benchmark.php?test=fasta&lang=all&sort=fullcpu

Third puzzle:

  Look at the fasta reference implementation ('Lua') and
  try to improve it (before looking at my solution).
  See if you can beat my solution ('Lua #2') which is
  around 2 times faster (but still 30 times slower than
  the C solution).

I bet you'll have a good laugh when you've read my solution.


BTW: Go to

  http://shootout.alioth.debian.org/

then scroll down and click on the 'Show' button to compare
all languages.

When you've regained conciousness, adjust the multipliers
in the upper right box. Try 'Code Lines = 1' and all others 0
first. Hey! :-)

Then try 'Full CPU Time = 1' and all others 0 next, which
is probably what you expected to see. Still not bad.

As of the time of this writing the score for Lua was 15.31.
A properly compiled Lua 5.0 (not the Debian shared library
version) would get a score of 17.82. Lua 5.1-alpha would
get 18.02.

LuaJIT 1.0.3 would get around 24.04. Java scores 17.06
and GCC scores 25.54. ;-)

But note that GCC, Java, Python and Perl suffer badly from
unimplemented or not working benchmarks. Realistically their
scores would be higher. But it is my belief that the overall
ranking would still be:

  Perl < Python < Lua < Java < LuaJIT < GCC

Oh and of course the scoring system is called 'CRAPS' with
a good reason. The scores themselves are meaningless. But
the ranking of the languages is still a good indicator.

Bye,
     Mike