Tony Finch – blog

(Monday’s notes) (Tuesday’s notes) (Thursday’s notes) (Epilogue)

Today was productive, and I feel I’m over the hump of the project - though I fear I won’t get to a good stopping point this week.

Refactoring

As I hoped, I managed to finish the refactoring. Or, to be precise, I got it to the point of compiling cleanly and crashing messily.

My refactoring approach this week has been to hack in haste and debug at leisure. Hopefully not too much leisure :-)

A lot of the stripping out of unions and bitfields was fairly mechanical, but I also took the opportunity to simplify some of the internal interfaces. I also changed some of the other data representations. I hope this doesn’t turn out to be foolishly lacking in refactoring discipline!

Nibbles

The qp trie code selects a child of a branch based on a nibble somewhere in the key string. A good representation of “somewhere” is pretty important.

My original qp trie code represented indexes into keys as a pair of a byte index and some flags that selected the nibble in that byte. This turned out to be pretty good when I did the tricky expansion from 4 bit to 5 bit nibbles. However, knowledge of this detail was smeared all through the code.

In this week’s refactoring I’ve tried unifying the byte+flags into a single nibble index. Overall I think this has turned out to be simpler, and my vague handwavy feeling is that the code should compile down to about the same instructions. (If you set NDEBUG to switch all the new asserts off, that is!)

COW pushdown

I’m fairly confident now that I have a good idea of how copy-on-write will work. This afternoon I wrote a 700 word summary of the COW states and invariants - the task now (well, after the debugging) is to turn the prose into code.