Aside from research, the past few days I have been putzing with reimplementing Rubinius' Array#sort and Array#sort! because, well, they sucked. The implementation is an iterative three-way partitioning Quicksort that drops down to Insertion Sort for small Arrays or subpartitions. Two observations:
The new implementation is at least one order of magnitude faster in all areas compared to the old one. Pathological cases are much improved from this, even, three orders of magnitude usually.
StringArrays are about two orders of magnitude faster on small-mediumArraysand perform at the same scale with (theoretically) infinitely large ones. The old version ran out of stack space around 2000 or so.MatzRuby is typically still far faster, but particularly the block forms are actually fairly close, in some cases actually within the same order of magnitude (albeit slower.) And the new version is pure Ruby all the way.
Here are some benchmarking figures. Note the disparity between the Array sizes.
For MatzRuby and new Rubinius:
Numeric, 1000 elements, 100 loops
146233 strings, each with 20 characters
For old Rubinius:
Numeric, 100 elements, 100 loops
1462 strings, each with 20 characters
#sort MatzRuby OLD* NEW
-----------------------------------------------
sorted 0.007812 2.581782 0.602038
sorted block 0.195312 4.064099 1.782695
reversed 0.007812 4.423980 8.090656
reversed block 0.195312 4.909585 26.117707
random 0.023438 0.920588 1.643777
random block 1.914062 0.967784 3.984373
same 0.007812 0.062574 0.462366
same block 1.906250 0.915978 4.052798
two 0.007812 0.099981 0.426605
two block 1.898438 0.902365 3.756180
three 0.000000 0.118842 0.500360
three block 1.898438 0.907539 4.471767
mixed 0.015625 0.635714 1.161138
mixed block 1.859375 0.809821 3.037062
strings 0.015625 5.512026 3.742163
strings block 0.304688 10.301844 7.038649
Next mini-project will be converting Array to use a more efficient storage mechanism. That should be fun.