Faster "shuffle"

Wednesday, February 27, 2013

A funny comment on a Reddit discussion of my last post about “shuffle” said:

“Turtle races are fun indeed.”

Improvements

Well, that is perhaps true given the performance of Factor, Python, and Ruby compared with implementations in C (or SBCL and LuaJIT). However, I’m happy to say that as of today, the performance of randomize (the standard library “shuffle” word) in Factor is greatly improved.

IN: scratchpad 10,000,000 <iota> >array

Before:

IN: scratchpad gc [ randomize ] time
Running time: 2.78315852 seconds

After:

IN: scratchpad gc [ randomize ] time
Running time: 1.373153681 seconds

Commits

So, what changed?

Well, while investigating the overhead of Factor versus C, I fixed a few things:

speed up random-integer
speed up uniform-random-float (not relevant to randomize, but a nice speedup!)
speed up randomize (similar to my version 4 of “shuffle”)
speed up fixnum-log2
re-enable fixnum-log2 intrinsic

Looking at other programming languages is useful to know where your performance can improve and by approximately how much. Since Factor is an attempt at making a high level language that produces relatively fast code, I hope someday to turn this “turtle” into a “hare”. Every little bit helps!