The core of my protobuf-decoding library upb ( https://github.com/haberman/upb/wiki ) is 3k SLOC of C. That includes * a hash table implementation * a reference-counted string type * a generic interface for doing tree traversals of protobuf data * the protobuf decoder itself (which implements the previous interface) * all the code to load proto descriptors (including bootstrapping the first one, which is necessary to…
It really says something about C that so many useful-but-small systems have a good chunk of code devoted to hash table implementations, atoms ("a reference-counted string type"), etc. When working with C, it sometimes makes sense to have bespoke data structures, but it always makes me think of Hanson's _C Interfaces and Implementations_, Greenspun's tenth rule, etc. My 1500loc C project also has a hash table implemen…
For this speed-obsessed project, I wouldn't have it any other way:
Benchmarking hash lookups in an integer-keyed hash table.
Table size: 8, keys: 1-8 ====
upb_inttable(seq): 410 M/s
upb_inttable(rand): 334 M/s
std::map(seq): 149 M/s
std::map(rand): 170 M/s
__gnu_cxx::hash_map(seq): 69.9 M/s
__gnu_cxx::hash_map(rand): 68.0 M/s
Table size: 64, keys: 1-64 ====
upb_inttable(seq): 410 M/s
upb_inttable(rand): 333 M/s
std::map(seq): 32.4 M/s
std::map(rand): 33.4 M/s
__gnu_cxx::hash_map(seq): 67.9 M/s
__gnu_cxx::hash_map(rand): 71.4 M/s
Table size: 512, keys: 1-512 ====
upb_inttable(seq): 407 M/s
upb_inttable(rand): 330 M/s
std::map(seq): 20.8 M/s
std::map(rand): 17.2 M/s
__gnu_cxx::hash_map(seq): 70.8 M/s
__gnu_cxx::hash_map(rand): 64.6 M/s
Table size: 64, keys: 1-32 and 10133-10164 ====
upb_inttable(seq): 394 M/s
upb_inttable(rand): 334 M/s
std::map(seq): 32.0 M/s
std::map(rand): 30.7 M/s
__gnu_cxx::hash_map(seq): 71.3 M/s
__gnu_cxx::hash_map(rand): 70.6 M/s