Friday, July 11, 2008

TwoFinger gets another update

So I had run into a problem with TwoFinger. The implementation had a stack usage worst case of n. This means that, in the worst possible scenario, sorting a list of n things would need n stack frames. Totally unacceptable!

Today on the other hand, I am back to happy. Not only I squished the max stack depth to lg n/2 (not even lg n)... I also wrote it in a way that the recursion, if any, causes minimal stack traffic (in terms of message sending context switching, akin to calling functions in C) and stack depth.

This is very nice compared to Quicksort. This is because, if I understand things right, Quicksort will always have to reach a stack depth of lg n/2, if not lg n itself. For TwoFinger, on the other hand, it's only an upper bound. For example, it is not unusual for TwoFinger to sort a list of 1k things using a stack no deeper than 2 or 3 frames.

So now, TwoFinger (in its "2c" incarnation) appears to be generally faster than Quicksort in the following respects.

  • Generally less swaps.
  • Generally less comparisons.
  • Generally less probes.
  • Generally less maximum stack depth.
  • Generally less stack traffic.
Things are looking good... at least for now. For example, I still do not have a proof of average complexity...

I plan to introduce it in public after my dear beta testers have a chance to go over the details. You may want to consider that I am about to send them a test suite that runs about 500 tests, and a detailed log of performance characteristics of about 140kb, so this may take a bit.

One way or the other, between TwoFinger, the Smalltalks 2008 coding contest and Assessments, the fundamentals book will have original and exciting material in it. For example, it just gained a chapter on recursion...

PS: the test suite for all the sorting algorithms is written in SUnitVM and runs inside Assessments. This is great because then I can leave my legacy tests alone, I get Assessments' much more powerful machinery and tools, and I also get to make use of an Assessments-compatible / Assessments-supported feature set. Adding the measurements for the stack depth and stack traffic, including all the needed reporting aspect of this for the 500 or so tests, was frighteningly easy to do.

No comments: