Use linear probing with an additional good bit avalanching function in FST's
NodeHash.
--------------------------------------------------------------------------------------
Key: LUCENE-2967
URL: https://issues.apache.org/jira/browse/LUCENE-2967
Project: Lucene - Java
Issue Type: Improvement
Reporter: Dawid Weiss
Assignee: Dawid Weiss
Priority: Trivial
Fix For: 4.0
I recently had an interesting discussion with Sebastiano Vigna (fastutil), who
suggested that linear probing, given a hash mixing function with good avalanche
properties, is a way better method of constructing lookups in associative
arrays compared to quadratic probing. Indeed, with linear probing you can
implement removals from a hash map without removed slot markers and linear
probing has nice properties with respect to modern CPUs (caches). I've
reimplemented HPPC's hash maps to use linear probing and we observed a nice
speedup (the same applies for fastutils of course).
This patch changes NodeHash's implementation to use linear probing. The code is
a bit simpler (I think :). I also moved the load factor to a constant -- 0.5
seems like a generous load factor, especially if we allow large FSTs to be
built. I don't see any significant speedup in constructing large automata, but
there is no slowdown either (I checked on one machine only for now, but will
verify on other machines too).
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
