Too Busy For Words - the PaulWay Blog

Remember this statement from a previous blog post: "Who would have thought I could write a merge sort off the top of my head and have it work first go?"

I believe the canonical response is now: "Bwah-ha-ha-ha-ha-ha-ha!"

Of course it didn't work first go. Once I'd patched up the obvious memory leaks, it still leaked like a sieve. I then spent half a day putting in debugging code and writing a little perl program that would watch the memory allocation and work out at what stage it'd leak. That cleared up a few more bugs but it was still leaking vast swathes of memory. So I wrote more debugging code to keep a much closer eye on memory allocation, and after debugging that, I found the final leak. That wasn't too difficult to plug, as it turned out, and after a comprehensive run didn't show up any errors and the results matched the known-good-but-memory-inefficient version's output, I was moderately satisfied.

I feel like scrat in the first scene from Ice Age, where he's holding onto a cliff trying to stop it leaking out at him, and balancing a large, precious acorn on his head. There's some satisfaction that I've tracked the problems down, but the overall solution is... tense.

To cut a long story short, I've tested a bunch of different methods: creating new blocks, not creating new blocks, array increments versus array indexing, and in-line sorting of two and three element arrays. The results are generally about equal - interestingly, the overhead from creating huge numbers of pointers and almost immediately disposing of them, and the speed gain of doing tense things like in-place array incrementing, wasn't as much as I thought. The major foul was the 'in-place' merge, which did a fair bit of realloc'ing, which was about three times slower than every other method. No big surprises there.

Of course, now I'm re-implementing it again (that's the fourth time this week!), with my heap-merge method. Stay tuned.