[golang-dev] code review 6872063: compress/flate: Performance improvement for inflate (issue 6872063)

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.


https://codereview.appspot.com/6872063/

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.


https://codereview.appspot.com/6872063/

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.


https://codereview.appspot.com/6872063/

You can also use hg upload NNNN

To avoid sending an email.

Could you please update the description with benchmarking information,
there should be some benchmarks inside the flate package already. A
suggestion is

go test -bench=. > old.txt
... make changes ...
go test -bench=. > new.txt
$GOROOT/misc/benchcmp {old,new}.txt

You can also generate a stand alone benchmark as a point in time
reference with -c

go test -c
flate.test -test.bench=. > old.txt

https://codereview.appspot.com/6872063/

Done, thanks for the suggestion and tools howto.

https://codereview.appspot.com/6872063/diff/5006/src/pkg/compress/flate/gen.go
File src/pkg/compress/flate/gen.go (right):

https://codereview.appspot.com/6872063/diff/5006/src/pkg/compress/flate/gen.go#newcode128
src/pkg/compress/flate/gen.go:128: fmt.Println("package flate")
please add some notice like "// auto generated, DO NOT EDIT" to
the generated file, and preferably with the command line that
generated it.

https://codereview.appspot.com/6872063/

Thanks, good suggestion.


https://codereview.appspot.com/6872063/diff/5006/src/pkg/compress/flate/gen.go
File src/pkg/compress/flate/gen.go (right):

https://codereview.appspot.com/6872063/diff/5006/src/pkg/compress/flate/gen.go#newcode128
src/pkg/compress/flate/gen.go:128: fmt.Println("package flate")
Done.

https://codereview.appspot.com/6872063/

Looks good, and the performance improvements are great. I just want to
make sure we have enough comments here that others can make fixes or
extensions.



https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go
File src/pkg/compress/flate/inflate.go (left):

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#oldcode58
src/pkg/compress/flate/inflate.go:58: // J. Brian Connell, ``A
Huffman-Shannon-Fano Code,''
I don't mind losing this comment if it's no longer relevant, but could
you please add a comment explaining or pointing to a reference for the
new algorithm?

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go
File src/pkg/compress/flate/inflate.go (right):

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode61
src/pkg/compress/flate/inflate.go:61: // chunk & 15 is number of bits
Can this fit in uint16? You're only using 4 bits of the bottom 16 and
perhaps not many of the top 16 either.

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode71
src/pkg/compress/flate/inflate.go:71: chunks [huffmanNumChunks]uint32
Please add comments describing the meaning of these fields.
I think that if the data structure is documented clearly the code will
become more clear too.

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode114
src/pkg/compress/flate/inflate.go:114: reverse = reverse >>
uint(16-huffmanChunkBits)
reverse >>= 16 - huffmanChunkBits

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode132
src/pkg/compress/flate/inflate.go:132: here := uint32((i << 16) + n)
Does here mean something / stand for something? It's an unusual name,
and I can't figure out what it means.

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode134
src/pkg/compress/flate/inflate.go:134: reverse = reverse >> uint(16-n)
reverse >>= uint(16 - n)

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode556
src/pkg/compress/flate/inflate.go:556: // Read f.dataLen bytes into
history,
This new comment seems wrong - it says dataLen not copyLen.
I also don't understand why it moved inside the function instead of
being a doc comment. Could you put the old one back?

https://codereview.appspot.com/6872063/

I'm making the commenting changes as you suggest, but in so doing I'm
finding that there's a pretty serious version confusion going on. In
particular, these source files have significant differences:

http://code.google.com/p/go/source/browse/src/pkg/compress/flate/inflate.go
http://golang.org/src/pkg/compress/flate/inflate.go

The former has f.bits as a *[maxLit + maxDist]int, while the latter
has it as [maxLit + maxDist]int (ie not a pointer). There are other
changes in the way hist is processed at all. In addition, the former
has the comment before copyData the way you like it and the latter has
it inside the function.

These discrepancies are showing up in the code review tool as diffs.
They also show up when I do an "hg diff" in my source tree.

I don't want to change this stuff at all, just the code decoding. I
also have no idea what the f is going on with the different versions.
When I look at the hg logs, it looks like the last change to the file
is dated Nov 1, so it seems unlikely there's a change that happened
concurrently with mine.

I don't know how to proceed.

Raph

This is tip (the head of the "default" branch)


This is old, the "go1" branch, from the "go1.0.3" release.

Your local source checkout should be on the "default" branch, not "release".

$ hg update default

Thanks for the review. There were also problems caused by the patch
being against "release" rather than the current development branch, but
hopefully that's all resolved now.


https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go
File src/pkg/compress/flate/inflate.go (left):

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#oldcode58
src/pkg/compress/flate/inflate.go:58: // J. Brian Connell, ``A
Huffman-Shannon-Fano Code,''
Done.

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go
File src/pkg/compress/flate/inflate.go (right):

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode61
src/pkg/compress/flate/inflate.go:61: // chunk & 15 is number of bits
I think in the worst case the table link indices can be 13 bits, so it
doesn't quite fit. This would be a highly artificial case, of course,
but if it can happen we should decode it correctly.

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode71
src/pkg/compress/flate/inflate.go:71: chunks [huffmanNumChunks]uint32
Done.

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode114
src/pkg/compress/flate/inflate.go:114: reverse = reverse >>
uint(16-huffmanChunkBits)

Done.

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode132
src/pkg/compress/flate/inflate.go:132: here := uint32((i << 16) + n)

Changed it to "chunk." I believe "here" is the name used in zlib, but
agree it's confusing.

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode134
src/pkg/compress/flate/inflate.go:134: reverse = reverse >> uint(16-n)
Done.

https://codereview.appspot.com/6872063/diff/8002/src/pkg/compress/flate/inflate.go#newcode556
src/pkg/compress/flate/inflate.go:556: // Read f.dataLen bytes into
history,
This is actually because of version confusion between release and
default. Hopefully it's all resolved now.

https://codereview.appspot.com/6872063/

Here are some numbers from a linux/arm system.

benchmark old MB/s new MB/s speedup
BenchmarkDecodeDigitsSpeed1e4 4.40 5.06 1.15x
BenchmarkDecodeDigitsSpeed1e5 4.85 5.44 1.12x
BenchmarkDecodeDigitsSpeed1e6 4.91 5.49 1.12x
BenchmarkDecodeDigitsDefault1e4 4.59 5.29 1.15x
BenchmarkDecodeDigitsDefault1e5 5.18 6.28 1.21x
BenchmarkDecodeDigitsDefault1e6 5.53 6.50 1.18x
BenchmarkDecodeDigitsCompress1e4 4.58 5.28 1.15x
BenchmarkDecodeDigitsCompress1e5 5.18 6.27 1.21x
BenchmarkDecodeDigitsCompress1e6 5.49 6.48 1.18x
BenchmarkDecodeTwainSpeed1e4 4.20 5.44 1.30x
BenchmarkDecodeTwainSpeed1e5 5.04 6.29 1.25x
BenchmarkDecodeTwainSpeed1e6 5.22 6.46 1.24x
BenchmarkDecodeTwainDefault1e4 4.64 5.82 1.25x
BenchmarkDecodeTwainDefault1e5 6.06 7.42 1.22x
BenchmarkDecodeTwainDefault1e6 6.44 7.79 1.21x
BenchmarkDecodeTwainCompress1e4 4.64 5.83 1.26x
BenchmarkDecodeTwainCompress1e5 6.09 7.46 1.22x
BenchmarkDecodeTwainCompress1e6 6.47 7.83 1.21x

https://codereview.appspot.com/6872063/

Encoding numbers for the same host have suffered a little, but within
the margin of error

BenchmarkEncodeDigitsSpeed1e4 1.59 1.56 0.98x
BenchmarkEncodeDigitsSpeed1e5 2.21 2.17 0.98x
BenchmarkEncodeDigitsSpeed1e6 2.25 2.21 0.98x
BenchmarkEncodeDigitsDefault1e4 1.22 1.22 1.00x
BenchmarkEncodeDigitsDefault1e5 0.57 0.57 1.00x
BenchmarkEncodeDigitsDefault1e6 0.51 0.50 0.98x
BenchmarkEncodeDigitsCompress1e4 1.22 1.22 1.00x
BenchmarkEncodeDigitsCompress1e5 0.57 0.57 1.00x
BenchmarkEncodeDigitsCompress1e6 0.51 0.50 0.98x
BenchmarkEncodeTwainSpeed1e4 1.46 1.43 0.98x
BenchmarkEncodeTwainSpeed1e5 2.50 2.47 0.99x
BenchmarkEncodeTwainSpeed1e6 2.67 2.62 0.98x
BenchmarkEncodeTwainDefault1e4 1.08 1.07 0.99x
BenchmarkEncodeTwainDefault1e5 0.70 0.70 1.00x
BenchmarkEncodeTwainDefault1e6 0.65 0.65 1.00x
BenchmarkEncodeTwainCompress1e4 1.06 1.06 1.00x
BenchmarkEncodeTwainCompress1e5 0.54 0.55 1.02x
BenchmarkEncodeTwainCompress1e6 0.49 0.49 1.00x


https://codereview.appspot.com/6872063/