• Hurd libihash

  • old

  • new

• hurd-l4 libhurd-ihash

Open Issues

Collisions

Viengoos: new hash function.

IRC, freenode, #hurd, 2008/2009

<neal> so, we need a new ihash implementation
<neal> marcusb: When 80% full, the collision rate is very high.
<neal> marcusb: I tested using 512mb / 4096 entries
<neal> marcusb: Changing the load factor to 30% resulted in my program
  running more than an order of magnitude faster.
<marcusb> yeah, it shouldn't get so full
<marcusb> don't we do an exponential back-off in the array size?
<marcusb> of course it's clear we can do much better
<marcusb> the ihash algo is very simple
<marcusb> I'm not even sure it makes much sense to have a generic
  library

Reader-Writer Locks

IRC, freenode, #hurd, 2013-12-09

<teythoon> btw, why don't we use rwlocks for serializing access to our
  hash tables ?
<braunr> teythoon: we definitely could
<teythoon> ok
<braunr> teythoon: we definitely could use rcu *whistles*
<teythoon> should we ?
<braunr> i don't know
<teythoon> yeah, ofc
<braunr> rwlocks have some overhead compared to mutexes
<braunr> and our mutexes are already quite expensive
<braunr> our condition variables are also not optimized

Object Lookups

Alternatives?

• glibc

  • include/inline-hashtab.h

  • locale/programs/simple-hash.h

  • misc/hsearch_r.c

  • NNS; cf. f46f0abfee5a2b34451708f2462a1c3b1701facd

• libstdc++: unordered_map, tr1/unordered_map, ext/hash_map

• libiberty: hashtab.c

• http://cmph.sourceforge.net/

• http://libhashish.sourceforge.net/

• http://www.azillionmonkeys.com/qed/hash.html

• CCAN's htable, idtree

• Not actually use a hashing data structure; see libports, Open Issues, IRC, freenode, #hurd, 2013-11-14.