ccan/opt

I reviewed the code in popt a while back, and got a mail from Jeff Johnson on whether I thought the library worth revisiting (ie. popt2).  I replied that it was, then didn’t hear anything since. There are so many option-parsing libraries around, but I really wanted something simple and yet powerful enough for the …

Back To Cacheline Tree Hash Tables

After my previous conclusion that doubling linear hash tables were good enough, it turns out that they don’t work for TDB: enlarging or moving the hash table in the presence of tdb_chainlock is not possible.  So, I ended up implementing expanding hash tables, and ran into a familiar set of problems. The design is simple; …

fcntl lock starvation and TDB

The Trivial DataBase (ccan variant here) uses fcntl locks for consistency: records are chained off a fixed-size hash table (or the free list), and a 1-byte fcntl lock at the offset of the chain head protects all records in that chain. There’s also a tdb_lockall() function which grabs a lock across all the hash chains …

Superfreakonomics; Superplug for Intellectual Ventures.

I enjoyed Levitt & Dubner’s “Freakonomics”, and picked up the followup “Superfreakonomis” recently at an airport.  The last chapter, however, was astonishing.  The entire chapter was devoted to a glowing advertisement for Intellectual Ventures, pointing out that they own 20,000 patents “more than all but a few dozen companies in the world”, but of course …

Typesafe callbacks in C (and gcc)

A classic pattern in C is to hand a generic callback function around which takes a “void *priv” pointer so the function can take arbitrary state (side note: a classic anti-pattern is not to do this, resulting in qsort being reimplemented in Samba so one can be provided!). The problem with this pattern is that …

More Realistic Hashing: Cache Sensitivity Part II

So my previous post showed a trick with stuffing extra bits into the pointers of a simple hash table.  In most real situations, we want the hash to still be useful as the number of elements increases: the simple hash I used will slow down dramatically as we pass 75% utilization.  In addition, we want …