Ha! This was probably the first serious problem I ever tackled with an open source contribution!
The year was 2002, the 2.4 Linux kernel had just been released and I was making money on the side building monitoring software for a few thousand (mostly Solaris) hosts owned by a large German car manufacturer. Everything was built in parallel ksh code, “deployed” to Solaris 8 on Sun E10Ks, and mostly kicked off by cron. Keeping total script runtime down to avoid process buildup and delay was critical. The biggest offender: long timeouts for host/port combinations that would sporadically not be available.
Eventually, I grabbed W. Richard Stevens’ UNIX network programming book and created tcping [0]. FreeBSD, NetBSD, a series of Linux distros picked it up at the time and it was steady decline from there… good times!
#1 doing it in many 20-30min batches with little kids
#2 see #1
Jokes aside, IMHO there was not a single challenge standing out in terms of implementation; getting the pieces to work together and finding residual bugs was hard. LLDB was my friend but still missing valgrind on Mac. Writing (and re-writing) the docs really helped with mental clarity and not having to stress about a deadline was not hurting either. I often just closed the lid and made it my future self's problem with good success ;-)
Oh, and one thing I am proud of: how well the recursive search generalized to path copying. That came together very nicely.
Thanks! Yes, basically log_64(n) vs. log_32(n) and it would also require to switch to a 64 bit hash function and adjust hash exhaustion and bit fiddling arithmetic accordingly.
Re the impact of the recursion, that's actually zero for the search code since clang does a tail call optimization; it's a fair point for the removal code.
Thank you, happy to share. These are excellent pointers.
Regarding the batch construction, it's not immediately clear to me how to implement sorting since the order is implicit through the hash function (it seems one would need to construct a trie to build a trie?) but I might be wrong...
This. Roughly a year ago I got interested in efficient immutability for my write-from-scratch-in-C Lisp [0] and started to write a HAMT implementation in C [1], along with a (somewhat hacky, you have been warned) benchmarking suite [2].
The docs are only 70% done (in particular the "putting it all together" part is missing) but it has been a really interesting and enlightening journey so far and can only recommend embarking on this path to everyone.
To add context that seems lost on some: this is a cleaned-up version of my own notes from when I tried to understand the technical detail behind what Linus called "good taste" in the TED talk.
The main contributions of the writeup (if any) are the two conceptual insights that using an indirect pointer yields a homogeneous data structure and a convenient handle to the list item and its predecessor.
The article is not intended to show an example of clean code, there is no checking for NULLs, there are implicit expectations (the target needs to exist). It's just not the point.
I also strongly agree with the sentiment in the discussion that simple is often better than elegant. If it takes an entire article to figure out what's happening, that says something about how careful you should be with putting it in production code.
Anyways, thanks everyone on HN for a great discussion and for all the insights, comments and suggestions!
The year was 2002, the 2.4 Linux kernel had just been released and I was making money on the side building monitoring software for a few thousand (mostly Solaris) hosts owned by a large German car manufacturer. Everything was built in parallel ksh code, “deployed” to Solaris 8 on Sun E10Ks, and mostly kicked off by cron. Keeping total script runtime down to avoid process buildup and delay was critical. The biggest offender: long timeouts for host/port combinations that would sporadically not be available.
Eventually, I grabbed W. Richard Stevens’ UNIX network programming book and created tcping [0]. FreeBSD, NetBSD, a series of Linux distros picked it up at the time and it was steady decline from there… good times!
[0]: https://github.com/mkirchner/tcping
edit: grammar