[Contribution] Fowler–Noll–Vo hash function

[Clement]

Hi,

I just made my first contribution to the Go project, which was a
really nice experience.
This got me going and built some courage towards trying to contribute
some more to this wonderful project.

Also, some time ago I watched a talk (where, I forgot) about scaling
at Twitter. And one of the things I remember from the talk, is the
mention of a particular non-cryptographic hashing function called
Fowler–Noll–Vo [2] - or FNV for short - which supposedly is rather
fast.[1]
Not surprisingly it is also very simple. So even though I admittedly
know very little about hashing I got the implementation up and running
in no time.

So, now I've got a working implementation of the FNV-1a 64 bit hashing
function, along with corresponding tests, that I'd like to contribute
to the Go project as well.
I've naturally built on the Hash and Hash64 interfaces, using Adler
and CRC as a reference, so there should be no surprises for people
familiar with those.
I'm beginning work on the 32 bit implementation right away, which
shouldn't take long.

I'd love to get some feedback.
Does this have a place in the hash library ?

Best,
Clement Skau

[1] Twitter slides showing improvement from FNV (see slide 31):
http://www.slideshare.net/Eweaver/improving-running-components-at-twitter

See also:
Noll's website about FNV: http://www.isthe.com/chongo/tech/comp/fnv/index.html
Wikipedia article about FNV: http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash

[Nigel Tao]

On 21 January 2011 01:49, Clement <cleme...@gmail.com> wrote:
> So, now I've got a working implementation of the FNV-1a 64 bit hashing
> function, along with corresponding tests, that I'd like to contribute
> to the Go project as well.

Sorry to make an example of you, but it's been bugging me for a while...

I'm happy to see people writing many different Go packages, but not
every Go package needs to be in the standard package library. The
library isn't a kitchen sink dumping ground. The goinstall tool [0]
makes it easy to install packages from Bitbucket, Github, Google Code
Hosting and Launchpad. It also integrates with the Go Package
Dashboard [1].

Personally (with the caveat that I'm a crypto / hash novice), I feel
that the crypto section is a disproportionately large fraction of the
standard package library. Sure, crypto and hash features are useful in
general, and each individual sub-package is useful to some, but I'm
not convinced that they're all so broadly applicable to deserve being
in the core library.

Have you considered Bitbucket / etcetera for hosting your
Fowler-Noll-Vo-Go package? For example, I maintain
freetype-go.googlecode.com, and it goes through the same code review
process as the core package library, but it's not part of the core.

[0] http://golang.org/cmd/goinstall/
[1] http://godashboard.appspot.com/package

[Clement]

Hi Nigel,

Thanks for the feedback.

No hard feelings.
I was pretty much expecting this, so don't feel bad.
My main thought was that the crypto lib is really big, while the hash
lib has a mere two different hash algorithms - which, as you said,
seems disproportional.

The reason I didn't post to a place like Github, etc., is that I was
afraid of any trouble from posting elsewhere first, in case it would
be incorporated in the standard lib.
But with that out of the way, I'll post it right away.

/Clement


On Jan 21, 1:26 am, Nigel Tao <nigel.tao.gn...@gmail.com> wrote:

[Dan Adkins]

On Fri, Jan 21, 2011 at 12:51 AM, Clement <cleme...@gmail.com> wrote:
> My main thought was that the crypto lib is really big, while the hash
> lib has a mere two different hash algorithms - which, as you said,
> seems disproportional.

I, for one, would be happy to see more hash functions in the hash
package. Right now, there are adler32, crc32, and crc64, which are
actually checksums rather than hash functions in the traditional
sense. So why not put a good implementation of FNV in the standard
library?

-Dan

[Albert Strasheim]

Hello

On Jan 20, 4:49 pm, Clement <clements...@gmail.com> wrote:
> Also, some time ago I watched a talk (where, I forgot) about scaling
> at Twitter. And one of the things I remember from the talk, is the
> mention of a particular non-cryptographic hashing function called
> Fowler–Noll–Vo [2] - or FNV for short - which supposedly is rather
> fast.[1]

As a follow-up to this conversation: there is another hash in this
category called Murmur.

http://code.google.com/p/smhasher/

According to the author:

"Murmur3_x86_32 should be anywhere from 2-5x faster than FNV depending
on the application, and it doesn't have any of FNV's weird behavior
for difficult-to-hash keysets."

As an added bonus, he started working for Google in January. Maybe the
Go team can twist his arm so that we can have hash/murmur3 in Go. ;-)

Regards

Albert

[Clement]

Most interesting Albert ! :)

I managed to find the benchmarks the author put up and they do look
good.
However, looking at the code it seems like much of the performance is
gained from specially tailoring for the x86 and x64 Intels.
The code is actually rather long, compared to FNV.

I think it would be rather trivial to port the public domain C++ code
to Go, but the nature of it taken into account I fear it might act
radically different from the original - performance wise.
An benchmark in Go would be really cool though.

As I said I don't know much about the theory behind hashing, but I can
easily imagine there are issues of "weirdness" in FNV, which might be
better in the case of Murmur.


In any case I've pushed the code for my implementation of FNV here:
https://github.com/cskau/gofnv

Feel free to fork and comment.

Best,
Clement

On 4 Feb., 23:04, Albert Strasheim <full...@gmail.com> wrote:
> Hello
>
> On Jan 20, 4:49 pm, Clement <clements...@gmail.com> wrote:
>
> > Also, some time ago I watched a talk (where, I forgot) about scaling
> > at Twitter. And one of the things I remember from the talk, is the
> > mention of a particular non-cryptographic hashing function called

> > Fowler–Noll–Vo [2] - orFNVfor short - which supposedly is rather

> > fast.[1]
>
> As a follow-up to this conversation: there is another hash in this
> category called Murmur.
>
> http://code.google.com/p/smhasher/
>
> According to the author:
>
> "Murmur3_x86_32 should be anywhere from 2-5x faster thanFNVdepending

> on the application, and it doesn't have any ofFNV'sweird behavior

[William Waites]

Before I subscribed to the list, my first exercise in making a Go
package was also to implement FNV, https://bitbucket.org/ww/fnv

I had first looked for an implementation in the usual places but
didn't find one.

Where you implement the 32 and 64 bit hases, I implemented FNV1 and
FNV1a. Obviously the code is almost identical given that these are
very simple hash functions.

Cheers,
-w

--
William Waites <mailto:w...@styx.org>
http://river.styx.org/ww/ <sip:w...@styx.org>
F4B3 39BF E775 CF42 0BAB 3DF0 BE40 A6DF B06F FD45