## Heaps

Tuesday, December 2, 2014

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!