Mailing-List: contact dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@lucene.apache.org
Date: Tue, 15 Mar 2011 20:42:29 +0000 (UTC)
From: "Dawid Weiss (JIRA)" <jira@apache.org>
To: dev@lucene.apache.org
Message-ID: 
 <853840591.4830.1300221749726.JavaMail.tomcat@hel.zones.apache.org>
In-Reply-To: 
 <101915481.3554.1300196129629.JavaMail.tomcat@hel.zones.apache.org>
Subject: [jira] Commented: (LUCENE-2967) Use linear probing with an
 additional good bit avalanching function in FST's NodeHash.
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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

Dawid Weiss commented on LUCENE-2967:
-------------------------------------

Yes, now I see this difference on the 38M too:

trunk:
{noformat}
56.462
55.725
55.544
55.522
{noformat}
w/patch:
{noformat}
59.9
59.6
{noformat}

I'll see if I can find out the problem here; I assume the collision ratio should be nearly identical... but who knows. This is of no priority, but interesting stuff. I'll close if I can't get it better than the trunk version.

> 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