5 ms·

Uthash – C macros for hash tables and more

78 points by maydemir 5y ago

macjc 5y ago
This is probably the slowest commonly used hash table library.
- rurban 5y ago
  std::unordered_map is in the similar ballpark. linked lists, oom checks, integer key support.
  - marginalia_nu 5y ago
    In a "hold my beer"-moment, I've ported GNU Trove's hash map to use memory mapped files instead of allocated memory. With good reason, granted, and it's not commonly used, but compared to almost anything else, it is fairly slow.
    - spicybright 5y ago
      That sounds pretty interesting (in a sick way ;) ) Are you able to elaborate a bit more what you were doing?
      - marginalia_nu 5y ago
        I'm using it for the lexicon in my search engine. I basically need a mapping from arbitrary short strings to unique integer identifiers, with a cardinality in the billions. Too much to keep in memory, most db solutions keel over as well.
        rurban 5y ago
        for this I would use CHM, ordered minimal perfect hashes with external mmap'ed keys. still constant lookup, just the position needs to be stored in the value also.
        marginalia_nu 5y ago
        Problem is I don't know the items beforehand, instead I need to build the hash as I encounter new pages. I don't know any way of reconcile that with a minimal perfect hash.
        rurban 5y ago
        ok, with trillions keys creating a CHM MPH is risky, and needs a few secs. then your external hash is good enough.
  - kllrnohj 5y ago
    And std::unordered_map is then the slow version in C++ compared to absl::flat_hash_map or folly::F14FastMap
- hambaleeyo 5y ago
  Care to elaborate a bit?
- tirrex 5y ago
  https://github.com/tezc/sc/tree/master/map https://github.com/tezc/sc/tree/master/map For those who are interested in faster hashmaps, I tried bunch of hashmaps and this one performs better than others. This is for C. Maybe C++ has better hashmaps.
eqvinox 5y ago
Same kind of thing, but typesafe: https://github.com/FRRouting/frr/blob/master/lib/typesafe.h https://github.com/FRRouting/frr/blob/master/lib/typesafe.h https://github.com/FRRouting/frr/blob/master/doc/developer/lists.rst https://github.com/FRRouting/frr/blob/master/doc/developer/l... (disclaimer: it's my work.)
- amir734jj 5y ago
  Awesome. Thanks for sharing
- rurban 5y ago
  mine is better :) https://github.com/rurban/ctl/ https://github.com/rurban/ctl/
  - florianist 5y ago
    And this one may be even "better" :) https://github.com/tylov/STC https://github.com/tylov/STC
    - eqvinox 5y ago
      Am I the only one confused by the C++ referential naming / the only C-but-not-C++ developer here? I have no idea what a shared_ptr is, or how a priority_queue behaves (is that a heap?)
      - mananaysiempre 5y ago
        The C++ envy does seem a bit peculiar, yes, but more so because my dissatisfaction with doing simple data structures in C is that I’m always doing a thousand twisty variations of the damn things, all just a little different, (usually to make allocations come out like I want them,) and it doesn’t feel like an STL-alike would solve that. A priority queue is usually implemented as a heap (binary or otherwise) and frequently called that as well, but in more precise usage the gadget (abstract data type) you do INSERT and REMOVE-MIN to is the “priority queue”, and the implementation device of a(n implicit or explicit) tree where the value in any node is smaller than the values in its children is the “heap”. Roughly, “priority queue” is to “heap” like “ordered dictionary / map” is to “search tree”. (I can’t think of any data structures that use heaps not for a priority queue except for treaps, but then my algorithm-fu is not particularly strong.) As for shared_ptr, it’s just a refcounted pointer, but that bit of terminology is STL-specific so there might not be much value in learning it.
david2ndaccount 5y ago
Don’t use macros for this. The better way to do it is to have headers that are designed to be included multiple times, each time with a different type. You end up with code that is possible to step through in a debugger instead of a macro-expanded mess.
- eqvinox 5y ago
  I really wish there was an _Include C preprocessor instruction for this purpose (like there is _Pragma)
mci 5y ago
See also David Hanson's book C Interfaces and Implementations [http://drh.github.io/cii/toc.html http://drh.github.io/cii/toc.html].
aleden 5y ago
Why not use the linux kernel's statically-sized hashtable code? https://pastebin.ubuntu.com/p/rvT9yKTqnP/ https://pastebin.ubuntu.com/p/rvT9yKTqnP/
toastercat 5y ago
I know this from my time doing Leetcode with C. I prefer https://github.com/rxi/map https://github.com/rxi/map for its API

78 points by maydemir 5y ago

macjc 5y ago

This is probably the slowest commonly used hash table library.

rurban 5y ago
std::unordered_map is in the similar ballpark. linked lists, oom checks, integer key support.
- marginalia_nu 5y ago
  In a "hold my beer"-moment, I've ported GNU Trove's hash map to use memory mapped files instead of allocated memory. With good reason, granted, and it's not commonly used, but compared to almost anything else, it is fairly slow.
  - spicybright 5y ago
    That sounds pretty interesting (in a sick way ;) ) Are you able to elaborate a bit more what you were doing?
    - marginalia_nu 5y ago
      I'm using it for the lexicon in my search engine. I basically need a mapping from arbitrary short strings to unique integer identifiers, with a cardinality in the billions. Too much to keep in memory, most db solutions keel over as well.
      - rurban 5y ago
        for this I would use CHM, ordered minimal perfect hashes with external mmap'ed keys. still constant lookup, just the position needs to be stored in the value also.
        marginalia_nu 5y ago
        Problem is I don't know the items beforehand, instead I need to build the hash as I encounter new pages. I don't know any way of reconcile that with a minimal perfect hash.
        rurban 5y ago
        ok, with trillions keys creating a CHM MPH is risky, and needs a few secs. then your external hash is good enough.
- kllrnohj 5y ago
  And std::unordered_map is then the slow version in C++ compared to absl::flat_hash_map or folly::F14FastMap
hambaleeyo 5y ago
Care to elaborate a bit?
tirrex 5y ago
https://github.com/tezc/sc/tree/master/map https://github.com/tezc/sc/tree/master/map For those who are interested in faster hashmaps, I tried bunch of hashmaps and this one performs better than others. This is for C. Maybe C++ has better hashmaps.

eqvinox 5y ago

Same kind of thing, but typesafe: https://github.com/FRRouting/frr/blob/master/lib/typesafe.h https://github.com/FRRouting/frr/blob/master/lib/typesafe.h https://github.com/FRRouting/frr/blob/master/doc/developer/lists.rst https://github.com/FRRouting/frr/blob/master/doc/developer/l... (disclaimer: it's my work.)

amir734jj 5y ago
Awesome. Thanks for sharing
rurban 5y ago
mine is better :) https://github.com/rurban/ctl/ https://github.com/rurban/ctl/
- florianist 5y ago
  And this one may be even "better" :) https://github.com/tylov/STC https://github.com/tylov/STC
  - eqvinox 5y ago
    Am I the only one confused by the C++ referential naming / the only C-but-not-C++ developer here? I have no idea what a shared_ptr is, or how a priority_queue behaves (is that a heap?)
    - mananaysiempre 5y ago
      The C++ envy does seem a bit peculiar, yes, but more so because my dissatisfaction with doing simple data structures in C is that I’m always doing a thousand twisty variations of the damn things, all just a little different, (usually to make allocations come out like I want them,) and it doesn’t feel like an STL-alike would solve that. A priority queue is usually implemented as a heap (binary or otherwise) and frequently called that as well, but in more precise usage the gadget (abstract data type) you do INSERT and REMOVE-MIN to is the “priority queue”, and the implementation device of a(n implicit or explicit) tree where the value in any node is smaller than the values in its children is the “heap”. Roughly, “priority queue” is to “heap” like “ordered dictionary / map” is to “search tree”. (I can’t think of any data structures that use heaps not for a priority queue except for treaps, but then my algorithm-fu is not particularly strong.) As for shared_ptr, it’s just a refcounted pointer, but that bit of terminology is STL-specific so there might not be much value in learning it.

david2ndaccount 5y ago

Don’t use macros for this. The better way to do it is to have headers that are designed to be included multiple times, each time with a different type. You end up with code that is possible to step through in a debugger instead of a macro-expanded mess.

eqvinox 5y ago
I really wish there was an _Include C preprocessor instruction for this purpose (like there is _Pragma)

mci 5y ago

See also David Hanson's book C Interfaces and Implementations [http://drh.github.io/cii/toc.html http://drh.github.io/cii/toc.html].

aleden 5y ago

Why not use the linux kernel's statically-sized hashtable code? https://pastebin.ubuntu.com/p/rvT9yKTqnP/ https://pastebin.ubuntu.com/p/rvT9yKTqnP/

toastercat 5y ago

I know this from my time doing Leetcode with C. I prefer https://github.com/rxi/map https://github.com/rxi/map for its API