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 …
Author Archives: rusty
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 …
Bob Jenkins and lookup8.c
I pulled Bob Jenkins’ superlative lookup3.c into ccan some time ago, and with the work on TDB2 (aka 64-bit TDB) I wondered if there was a 64-bit variant available. I didn’t look hard enough: I should have checked his top-level page and seen lookup8.c before wasting his time with an email :( I did note …
On Barriers To Entry
My philosophy for Free/Open Source Software comes down to this: that others can take what I do and do something awesome with it. Since I don’t know what you’ll need, I hand you every capability I have to get you started. Others granted me that very power to get where I am, so I seek …
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 …
Continue reading “Superfreakonomics; Superplug for Intellectual Ventures.”
LWN Quotes Of The Week
I have been petitioning Jon Corbet to introduce a “Supporter” level subscription to LWN; I think given his failure to keep up with inflation and my need to experience conferences vicariously I feel deeply indebted to them. That lead to me looking through LWN Quote of The Week; there’s no neat index of these things. …
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 …
Continue reading “More Realistic Hashing: Cache Sensitivity Part II”
Hash Tables: In A Cache-Sensitive World? (FIXED)
(FIXED: my “NoMatched” bench was bogus, and actually the same as “Matched” case. Graphs changed, but conclusions the same.) Everyone loves hash tables; certainly the networking code in the kernel uses them heavily and I do too. But with more work on TDB (which is basically a hash table in a file), I’ve been re-measuring …
Continue reading “Hash Tables: In A Cache-Sensitive World? (FIXED)”