#61: Investigate using an external hash library
---------------------+------------------------------------------------------
Reporter: coke | Owner: cotto
Type: RFC | Status: new
Priority: minor | Milestone:
Component: library | Version:
Severity: low | Keywords: hash
Lang: | Patch:
Platform: all |
---------------------+------------------------------------------------------
Comment(by nwellnhof):
LSHKIT is for locality sensitive hashing, CMPH for minimal perfect hashing
and Mhash for cryptographic hash functions. That's not what we need.
libghthash [http://www.ipd.bth.se/ska/sim_home/libghthash.html] would be
an example for a useful hash table library.
But I don't think we could gain much by using an external library. If we
want to optimize our current implementation, I'd suggest a dead simple
hash table with open addressing and linear probing. That would give us at
most one dcache miss for practically all reads if we make sure that the
fill factor stays low enough by rehashing.
Such a hash table would only require 2 words per entry vs. 4 words per
entry for our current chained implementation. So even if we limit the fill
factor to 50%, we wouldn't need more memory than now.
We'd need two additional bits to mark occupied and deleted entries. For
pointer keys or values we could store them in the low bits of the
pointers. For integer keys and values, we'd need an additional array for
those flags.
--
Ticket URL: <https://trac.parrot.org/parrot/ticket/61#comment:5>
Parrot <https://trac.parrot.org/parrot/>
Parrot Development
_______________________________________________
parrot-tickets mailing list
[email protected]
http://lists.parrot.org/mailman/listinfo/parrot-tickets
