code review 4257042: hash: new FNV-1a implementation (issue4257042)

[pas...@quies.net]

Reviewers: golang-dev_googlegroups.com,

Message:
Hello golan...@googlegroups.com (cc: fnv-...@asthe.com,
golan...@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

Description:
hash: new FNV-1a implementation

Please review this at http://codereview.appspot.com/4257042/

Affected files:
A src/pkg/hash/fnv/Makefile
A src/pkg/hash/fnv/fnv.go
A src/pkg/hash/fnv/fnv_test.go

[Adam Langley]

On Sat, Feb 26, 2011 at 10:14 AM, <pas...@quies.net> wrote:
> Description:
> hash: new FNV-1a implementation

I wonder if FNV1a is sufficiently useful to be included in the
standard library. Was there something in particular that you needed it
for?

Cheers

AGL

[Russ Cox]

I don't know. If we had any hash functions yet then
it might be out of place but right now there is nothing
in the gap between CRC and cryptographic hashes
like SHA1. That is, we don't have any hash functions,
in the original sense of the term. A well written
implementation of a well engineered general purpose
hash function like FNV seems like it would fill that
gap nicely.

Russ

[Albert Strasheim]

Hello

Agreed. Another very useful one that falls into this "in-between"
category is MurmurHash:

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

Seems the author works for Google these days...

Regards

Albert

[Devon H. O'Dell]

2011/2/27 Albert Strasheim <ful...@gmail.com>:

Murmur is quite nice.

I hate to add to a list of stuff that isn't in the code base and may
just be a bikeshed about what should wind up in there, but the
burtleburtle hash is quite nice and well-tested, too.
http://burtleburtle.net/bob/hash/doobs.html

Certainly anyone can implement any of these themselves, but if Go is
looking to have a package of hashes in base, the three mentioned here
are all friendly as far as license / patent / performance /
reliability as they're all well-used and well understood.

--dho

> Regards
>
> Albert

[Pascal]

The issue with Murmur and lookup3 is that they use 32-bit input data.
This cheats the performance charisteristics slightly if you can cast
data pointers but in Go this means bit shifting. As for speed, are bit
rolls supported in one operation?

[a...@golang.org]

LGTM

http://codereview.appspot.com/4257042/diff/2001/src/pkg/hash/fnv/fnv.go
File src/pkg/hash/fnv/fnv.go (right):

http://codereview.appspot.com/4257042/diff/2001/src/pkg/hash/fnv/fnv.go#newcode5
src/pkg/hash/fnv/fnv.go:5: // Fowler-Noll-Vo is a non-cryptographic hash
function
// The fnv package implements FNV-1a, a non-cryptographic hash function
created by Glenn Fowler, Landon Curt Noll, and Phong Vo. See
http://isthe.com/chongo/tech/comp/fnv/.

http://codereview.appspot.com/4257042/diff/2001/src/pkg/hash/fnv/fnv_test.go
File src/pkg/hash/fnv/fnv_test.go (right):

http://codereview.appspot.com/4257042/diff/2001/src/pkg/hash/fnv/fnv_test.go#newcode6
src/pkg/hash/fnv/fnv_test.go:6:
I understand that you're using double newlines for grouping, but it
looks a little loose here (and also at the beginning of fnv.go).

http://codereview.appspot.com/4257042/

[Russ Cox]

I'd be just as happy without the double newlines.

// Constructs a 32-bit FNV-1a implementation
should be

// New32 returns a new hash.Hash computing the 32-bit FNV-1a hash.

similarly New64.

[pas...@quies.net]

Hello agl1, rsc (cc: golan...@googlegroups.com),

Please take another look.

http://codereview.appspot.com/4257042/

[r...@golang.org]

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go
File src/pkg/hash/fnv/fnv_test.go (right):

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#newcode16
src/pkg/hash/fnv/fnv_test.go:16: var golden32 = map[uint32]string{
more typical is

var golden32 = []struct{
sum uint32
text uint32
}{
{0x811c9dc5, ""},
...
}

and then

for tt := range golden32 {
use tt.sum, tt.range
}

the map is cute but it means you can't depend on
the iteration order.

look at the tests for hash/crc32 for example.

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#newcode36
src/pkg/hash/fnv/fnv_test.go:36: t.Errorf("Integer 0x%x instead of 0x%x
for %s", actual, expected, text)
look at crc32_test.go for error message format too.
easier to give enough details if you speak in Go code.

t.Errorf("hash32(%q) = 0x%x want 0x%x", tt.text, tt.sum, sum)

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#newcode39
src/pkg/hash/fnv/fnv_test.go:39: t.Errorf("Array 0x%x instead of 0x%x
for %s", actual, expected, text)
t.Errorf("hash32(%q) bytes = 0x%x want 0x%x", tt.text, tt.sum, sum)

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#newcode72
src/pkg/hash/fnv/fnv_test.go:72: t.Fatal("Wrong size")
all these prints should have details.

t.Fatalf("h.Size()=%d but len(sum)=%d", h.Size(), len(sum))

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#newcode76
src/pkg/hash/fnv/fnv_test.go:76: t.Fatal("Sum changed on retry")
t.Fatalf("first h.Sum()=%x, second h.Sum()=%x", sum, second)

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#newcode82
src/pkg/hash/fnv/fnv_test.go:82: t.Fatal("Sum changed with reset")
t.Fatalf("h.Sum()=%x, but after Reset h.Sum()=%x", sum, second)

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#newcode89
src/pkg/hash/fnv/fnv_test.go:89: t.Fatal("Sum changed with partitial
writes")
t.Fatalf("h.Sum()=%x, but with partial writes, h.Sum()=%x", sum, second)

http://codereview.appspot.com/4257042/

[Pascal S. de Kloe]

Hi Russ,

Thanks for the feedback.

Why would the order matter for the golden tests?

More descriptive test assertions are ofcourse always a good thing. However
doing so in Go is currently quite repetitive. After makeing the changes I'll
create a separate proposal on golang-dev to standardize this.

Cheers

On Monday 28 February 2011 22:24:12 r...@golang.org wrote:
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g
> o File src/pkg/hash/fnv/fnv_test.go (right):
>
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g
> o#newcode16 src/pkg/hash/fnv/fnv_test.go:16: var golden32 =

> map[uint32]string{ more typical is
>
> var golden32 = []struct{
> sum uint32
> text uint32
> }{
> {0x811c9dc5, ""},
> ...
> }
>
> and then
>
> for tt := range golden32 {
> use tt.sum, tt.range
> }
>
> the map is cute but it means you can't depend on
> the iteration order.
>
> look at the tests for hash/crc32 for example.
>
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g

> o#newcode36 src/pkg/hash/fnv/fnv_test.go:36: t.Errorf("Integer 0x%x instead

> of 0x%x for %s", actual, expected, text)
> look at crc32_test.go for error message format too.
> easier to give enough details if you speak in Go code.
>
> t.Errorf("hash32(%q) = 0x%x want 0x%x", tt.text, tt.sum, sum)
>
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g

> o#newcode39 src/pkg/hash/fnv/fnv_test.go:39: t.Errorf("Array 0x%x instead

> of 0x%x for %s", actual, expected, text)
> t.Errorf("hash32(%q) bytes = 0x%x want 0x%x", tt.text, tt.sum, sum)
>
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g

> o#newcode72 src/pkg/hash/fnv/fnv_test.go:72: t.Fatal("Wrong size")

> all these prints should have details.
>
> t.Fatalf("h.Size()=%d but len(sum)=%d", h.Size(), len(sum))
>
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g

> o#newcode76 src/pkg/hash/fnv/fnv_test.go:76: t.Fatal("Sum changed on

> retry")
> t.Fatalf("first h.Sum()=%x, second h.Sum()=%x", sum, second)
>
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g

> o#newcode82 src/pkg/hash/fnv/fnv_test.go:82: t.Fatal("Sum changed with

> reset") t.Fatalf("h.Sum()=%x, but after Reset h.Sum()=%x", sum, second)
>
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g

> o#newcode89 src/pkg/hash/fnv/fnv_test.go:89: t.Fatal("Sum changed with

[Russ Cox]

> Why would the order matter for the golden tests?

It's often useful to have the simple tests before the
more complicated tests. Also, the map approach
fails as soon as there is more than one argument or
more than one result or more than one test with the
same result.

Russ

[Russ Cox]

I looked again at the FNV web page.
There's no indication there that the FNV-1a hash
is meant to supersede the FNV-1 hash.
It's a little confusing for hash/fnv's New32 to
compute the FNV-1a hash. They're very similar,
of course, but I think it would be better to expose
both. People who use the package to get the
specific FNV hash (as opposed to using the
package to get some good general purpose hash)
will be surprised that it doesn't give standard FNV1.

New32, New32a, New64, New64a
?

Russ

[Pascal S. de Kloe]

Hi Russ,

It's better to reflect the algorithm in the API indeed. How about fnv1a.New32
and fnv1a.New64?

"Some people use FNV-1a instead of FNV-1 because they see slightly better
dispersion for tiny (<4 octets) chunks of memory. Either FNV-1 or FNV-1a make
a fine hash"
-- http://isthe.com/chongo/tech/comp/fnv/#FNV-1a

Now we're on the subject of consistency, I found it somewhat odd that
hash.Hash#Sum() doesn't specify it's endianness. Shall I include a comment
with this patch?

Cheers,

Pascal

[Russ Cox]

> It's better to reflect the algorithm in the API indeed. How about fnv1a.New32
> and fnv1a.New64?

I'd rather not have two distinct packages for algorithms
that differ only in one line.
Let's keep it as fnv and use New32, New32a, New64, New64a.

I'm not sure that the interface definition needs to state
the endian-ness of the check-sum. I will think about it.

Russ

[pas...@quies.net]

[r...@golang.org]

please add FNV-1 (non-a)

http://codereview.appspot.com/4257042/diff/15001/src/pkg/hash/fnv/fnv.go
File src/pkg/hash/fnv/fnv.go (right):

http://codereview.appspot.com/4257042/diff/15001/src/pkg/hash/fnv/fnv.go#newcode7
src/pkg/hash/fnv/fnv.go:7: // Noll, and Phong Vo.
move Noll, up to previous line.
just to avoid splitting his name.

http://codereview.appspot.com/4257042/diff/15001/src/pkg/hash/fnv/fnv.go#newcode28
src/pkg/hash/fnv/fnv.go:28: // New32 returns a new hash.Hash computing
the 32-bit FNV-1a hash.
New32a

http://codereview.appspot.com/4257042/

[pas...@quies.net]

[Russ Cox]

Please complete a CLA as described at
http://golang.org/doc/contribute.html#copyright

Thanks.
Russ

[r...@golang.org]

LGTM

Please make the minor comment fix below and I will submit.

http://codereview.appspot.com/4257042/diff/10003/src/pkg/hash/fnv/fnv.go
File src/pkg/hash/fnv/fnv.go (right):

http://codereview.appspot.com/4257042/diff/10003/src/pkg/hash/fnv/fnv.go#newcode5
src/pkg/hash/fnv/fnv.go:5: // The fnv package implements FNV-1 and
FNV-1a, a
s/ a//

http://codereview.appspot.com/4257042/diff/10003/src/pkg/hash/fnv/fnv.go#newcode6
src/pkg/hash/fnv/fnv.go:6: // non-cryptographic hash function created by
s/function/functions/

http://codereview.appspot.com/4257042/

[pas...@quies.net]

[pas...@quies.net]

[Russ Cox]

LGTM

[r...@golang.org]

*** Submitted as 50bc23b43d82 ***

hash: new FNV-1a implementation

R=agl1, rsc
CC=golang-dev
http://codereview.appspot.com/4257042

Committer: Russ Cox <r...@golang.org>

http://codereview.appspot.com/4257042/