Heaps

Yesterday, I committed a performance improvement to the heap implementation in Factor.

There's an interesting comment on the pypy implementation of the "heapq" module that discusses a performance optimization that takes advantage of the fact that sub-trees of the heap satisfy the heap invariant. The strategy is to reduce the number of comparisons that take place when sifting items into their proper place in the heap.

Below, I demonstrate the time it takes to run our heaps benchmark and to sort 1 million random numbers using heapsort, before and after making the change.

Before:

IN: scratchpad gc [ heaps-benchmark ] time
Running time: 0.224253523 seconds

IN: scratchpad 1,000,000 random-units gc [ heapsort drop ] time
Running time: 2.210408992 seconds

After:

IN: scratchpad gc [ heaps-benchmark ] time
Running time: 0.172660576 seconds

IN: scratchpad 1,000,000 random-units gc [ heapsort drop ] time
Running time: 1.688299185 seconds

Not a bad improvement!