lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael McCandless (JIRA)" <j...@apache.org>
Subject [jira] Commented: (LUCENE-2967) Use linear probing with an additional good bit avalanching function in FST's NodeHash.
Date Tue, 15 Mar 2011 17:25:29 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-2967?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13007031#comment-13007031
] 

Michael McCandless commented on LUCENE-2967:
--------------------------------------------

Hmm, unfortunately, I'm seeing the patch make FST building slower, at
least in my env/test set.  I built FST for the 38M wikipedia terms.

I ran 6 times each, alternating trunk & patch.

I also turned off saving the FST, and ran -noverify, so I'm only
measuring time to build it.  I run java -Xmx2g -Xms2g -Xbatch, and
measure wall clock time.

Times on trunk (seconds):

{noformat}
  43.795
  43.493
  44.343
  44.045
  43.645
  43.846
{noformat}

Times w/ patch:

{noformat}
  46.595
  47.751
  47.901
  47.901
  47.901
  47.700
{noformat}

We could also try less generous load factors...


> 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
>
>         Attachments: LUCENE-2967.patch
>
>
> 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: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message