Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(248)

Issue 6872063: code review 6872063: compress/flate: Performance improvement for inflate

Can't Edit
Can't Publish+Mail
Start Review
Created:
8 years, 9 months ago by raph
Modified:
8 years, 1 month ago
Reviewers:
rsc
CC:
rsc, dfc, minux1, bradfitz, nigeltao, golang-dev
Visibility:
Public.

Description

compress/flate: Performance improvement for inflate Decode as much as possible of a Huffman symbol in a single table lookup (much like the zlib implementation), filling more bits (conservatively, so we don't consume past the end of the stream) when the code prefix indicates more bits are needed. This results in about a 50% performance gain in speed benchmarks. The following set is benchcmp done on a retina MacBook Pro: benchmark old MB/s new MB/s speedup BenchmarkDecodeDigitsSpeed1e4 28.41 42.79 1.51x BenchmarkDecodeDigitsSpeed1e5 30.18 47.62 1.58x BenchmarkDecodeDigitsSpeed1e6 30.81 48.14 1.56x BenchmarkDecodeDigitsDefault1e4 30.28 44.61 1.47x BenchmarkDecodeDigitsDefault1e5 32.18 51.94 1.61x BenchmarkDecodeDigitsDefault1e6 35.57 53.28 1.50x BenchmarkDecodeDigitsCompress1e4 30.39 44.83 1.48x BenchmarkDecodeDigitsCompress1e5 33.05 51.64 1.56x BenchmarkDecodeDigitsCompress1e6 35.69 53.04 1.49x BenchmarkDecodeTwainSpeed1e4 25.90 43.04 1.66x BenchmarkDecodeTwainSpeed1e5 29.97 48.19 1.61x BenchmarkDecodeTwainSpeed1e6 31.36 49.43 1.58x BenchmarkDecodeTwainDefault1e4 28.79 45.02 1.56x BenchmarkDecodeTwainDefault1e5 37.12 55.65 1.50x BenchmarkDecodeTwainDefault1e6 39.28 58.16 1.48x BenchmarkDecodeTwainCompress1e4 28.64 44.90 1.57x BenchmarkDecodeTwainCompress1e5 37.40 55.98 1.50x BenchmarkDecodeTwainCompress1e6 39.35 58.06 1.48x

Patch Set 1 #

Patch Set 2 : diff -r 6e0e4077f488 https://code.google.com/p/go #

Patch Set 3 : diff -r 6e0e4077f488 https://code.google.com/p/go #

Patch Set 4 : diff -r 6e0e4077f488 https://code.google.com/p/go #

Patch Set 5 : diff -r 6e0e4077f488 https://code.google.com/p/go #

Patch Set 6 : diff -r 6e0e4077f488 https://code.google.com/p/go #

Total comments: 2

Patch Set 7 : diff -r 6e0e4077f488 https://code.google.com/p/go #

Total comments: 14

Patch Set 8 : diff -r 5f9e99e3f2ea https://code.google.com/p/go #

Patch Set 9 : diff -r 5f9e99e3f2ea https://code.google.com/p/go #

Total comments: 6

Patch Set 10 : diff -r 5f9e99e3f2ea https://code.google.com/p/go #

Total comments: 10

Patch Set 11 : diff -r 5f9e99e3f2ea https://code.google.com/p/go #

Unified diffs Side-by-side diffs Delta from patch set Stats (+315 lines, -210 lines) Patch
A src/pkg/compress/flate/fixedhuff.go View 1 2 3 4 5 6 7 8 9 10 1 chunk +74 lines, -0 lines 0 comments Download
M src/pkg/compress/flate/flate_test.go View 1 1 chunk +0 lines, -113 lines 0 comments Download
A src/pkg/compress/flate/gen.go View 1 2 3 4 5 6 7 8 9 10 1 chunk +165 lines, -0 lines 0 comments Download
M src/pkg/compress/flate/inflate.go View 1 2 3 4 5 6 7 8 9 3 chunks +76 lines, -97 lines 0 comments Download

Messages

Total messages: 22
raph
Hello rsc@golang.org (cc: golang-dev@googlegroups.com), I'd like you to review this change to https://code.google.com/p/go
8 years, 9 months ago (2012-12-21 05:18:52 UTC) #1
raph
Hello rsc@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
8 years, 9 months ago (2012-12-21 05:24:47 UTC) #2
raph
Hello rsc@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
8 years, 9 months ago (2012-12-21 05:31:51 UTC) #3
raph
Hello rsc@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
8 years, 9 months ago (2012-12-21 05:32:08 UTC) #4
dfc
You can also use hg upload NNNN To avoid sending an email. On 21/12/2012, at ...
8 years, 9 months ago (2012-12-21 05:34:42 UTC) #5
dfc
Could you please update the description with benchmarking information, there should be some benchmarks inside ...
8 years, 9 months ago (2012-12-21 06:27:25 UTC) #6
raph
Done, thanks for the suggestion and tools howto. On Thu, Dec 20, 2012 at 10:27 ...
8 years, 9 months ago (2012-12-21 07:15:33 UTC) #7
minux1
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 ...
8 years, 9 months ago (2012-12-21 17:05:15 UTC) #8
raph
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") On 2012/12/21 17:05:15, minux ...
8 years, 9 months ago (2012-12-21 23:23:17 UTC) #9
rsc
Looks good, and the performance improvements are great. I just want to make sure we ...
8 years, 9 months ago (2012-12-22 14:19:00 UTC) #10
raph
I'm making the commenting changes as you suggest, but in so doing I'm finding that ...
8 years, 8 months ago (2012-12-23 01:10:10 UTC) #11
bradfitz
On Sat, Dec 22, 2012 at 5:10 PM, Raph Levien <raph@google.com> wrote: > I'm making ...
8 years, 8 months ago (2012-12-23 01:22:21 UTC) #12
raph
Thanks for the review. There were also problems caused by the patch being against "release" ...
8 years, 8 months ago (2012-12-23 02:22:33 UTC) #13
dfc
Here are some numbers from a linux/arm system. benchmark old MB/s new MB/s speedup BenchmarkDecodeDigitsSpeed1e4 ...
8 years, 8 months ago (2012-12-27 10:16:47 UTC) #14
dfc
Encoding numbers for the same host have suffered a little, but within the margin of ...
8 years, 8 months ago (2012-12-27 10:17:19 UTC) #15
rsc
Looks good, just want to clear up the 15/16 stuff. https://codereview.appspot.com/6872063/diff/7003/src/pkg/compress/flate/inflate.go File src/pkg/compress/flate/inflate.go (right): https://codereview.appspot.com/6872063/diff/7003/src/pkg/compress/flate/inflate.go#newcode70 ...
8 years, 8 months ago (2013-01-02 21:58:47 UTC) #16
raph
Thanks for the suggestions - I think the new patch set addresses your concerns. https://codereview.appspot.com/6872063/diff/7003/src/pkg/compress/flate/inflate.go ...
8 years, 8 months ago (2013-01-03 00:11:18 UTC) #17
nigeltao
https://codereview.appspot.com/6872063/diff/23001/src/pkg/compress/flate/gen.go File src/pkg/compress/flate/gen.go (right): https://codereview.appspot.com/6872063/diff/23001/src/pkg/compress/flate/gen.go#newcode138 src/pkg/compress/flate/gen.go:138: fmt.Println("\t[...]uint32{") s/.../huffmanNumChunks/ ? https://codereview.appspot.com/6872063/diff/23001/src/pkg/compress/flate/gen.go#newcode140 src/pkg/compress/flate/gen.go:140: if (i & 7) ...
8 years, 8 months ago (2013-01-03 07:22:03 UTC) #18
raph
PTAL https://codereview.appspot.com/6872063/diff/23001/src/pkg/compress/flate/gen.go File src/pkg/compress/flate/gen.go (right): https://codereview.appspot.com/6872063/diff/23001/src/pkg/compress/flate/gen.go#newcode138 src/pkg/compress/flate/gen.go:138: fmt.Println("\t[...]uint32{") On 2013/01/03 07:22:04, nigeltao wrote: > s/.../huffmanNumChunks/ ...
8 years, 8 months ago (2013-01-03 20:22:57 UTC) #19
rsc
LGTM Looks like this got dropped over the break. Apologies for that.
8 years, 8 months ago (2013-01-18 19:24:43 UTC) #20
rsc
*** Submitted as https://code.google.com/p/go/source/detail?r=437241074f39 *** compress/flate: Performance improvement for inflate Decode as much as possible ...
8 years, 8 months ago (2013-01-18 20:09:53 UTC) #21
remyoudompheng
8 years, 1 month ago (2013-07-21 19:56:17 UTC) #22
R=close
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b