Mailing-List: contact mahout-dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: mahout-dev@lucene.apache.org
Received-SPF: pass (athena.apache.org: domain of dawid.weiss@gmail.com
 designates 72.14.220.153 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:in-reply-to:references:from:date:message-id:subject:to
         :content-type;
        b=Dr3ZapeUTcF/kCJwmEPFHp86wi+y1Wm9P1hFdetvDlfsXu8+rSR33ACNBw1bMiQP0q
         kAhQINHooFoq1b5HIzfkjx2EpS1Mz5e8Lc6eDXBrElojpcwCLsZeFvEKzzX83uUz140j
         KF1ybXToehMSqToTIh9fuW6JxOd0DneE9RXgw=
MIME-Version: 1.0
In-Reply-To: <m2ue2e029611004020401sfad63dd7gc9a7c66d3a98b234@mail.gmail.com>
References: <v2q61b5d9411004020357k7c6c154ek9cea5e9ef3dd436e@mail.gmail.com>
	<m2ue2e029611004020401sfad63dd7gc9a7c66d3a98b234@mail.gmail.com>
From: Dawid Weiss <dawid.weiss@gmail.com>
Date: Fri, 2 Apr 2010 16:06:55 +0200
Message-ID: <w2pbaa8c5731004020706ma61eec5at16ef49d8875266e1@mail.gmail.com>
Subject: Re: [collections] and what about 'identity'?
To: mahout-dev@lucene.apache.org
Content-Type: text/plain; charset=UTF-8

> What's the use case for needing to vary the hash function? It's one of
> those things where I assume there are incorrect ways to do it, and
> correct ways, and among the correct ways fairly clear arguments about
> which function will be better -- i.e. the object should provide the
> best function.

Unfortunately this is not true -- just recently I've hit a use case
where the keys stored were Long values and their distribution had a
very low variance in the lower bits. HPPC implemented open hashing
using 2^n arrays and hashes were modulo bitmask... this caused really,
really long conflict chains for values that were actually very
different. I looked at how JDK's HashMap solves this problem -- they
do a simple rehashing scheme internally (so it's object hash and then
remixing hash in a cascade). I've finally decided to allow external
hash functions AND changed the _default_ hash function used for
"remixing" to be murmur hash. Performance benchmarks show this yields
virtually no degradation in execution time (the CPUs seem to spend
most of their time waiting on cache misses anyway, so internal
rehashing is not an issue).

I must also apologize for a bit of inactivity with HPPC... Like I
said, we have released it internally on our "labs" Web site here:

http://labs.carrotsearch.com/hppc.html

It doesn't mean we turn our backs on contributing HPPC to Mahout --
the opposite, we would love to do it. But contrary to what I
originally thought (to push HPPC to Mahout as soon as possible) I kind
of grew reluctant because so many things are missing (equals/hashcode,
java collections adapters) or can be improved (documentation, faster
iterators).

So... I'm still going to experiment with HPPC in our labs, especially
API-wise, release one or two versions in between and then kindly ask
you to peek at the final (?) result and consider moving the code under
Mahout umbrella. Sounds good?

Dawid