code review 131840043: bzip2: improve performance

bzip2: improve performance

Improve performance of move-to-front by using cache-friendly
copies instead of doubly-linked list. Simplify so that the
underlying slice is the object. Remove the n=0 special case,
      which was actually slower with the copy approach.

benchmark                 old ns/op     new ns/op     delta
BenchmarkDecodeDigits     26429714      23859699      -9.72%
BenchmarkDecodeTwain      76684510      67591946      -11.86%

benchmark                 old MB/s     new MB/s     speedup
BenchmarkDecodeDigits     1.63         1.81         1.11x
BenchmarkDecodeTwain      1.63         1.85         1.13x

Updates issue 6754.

[jra, 2014-08-17 21:59:07]

Hello golang-codereviews@googlegroups.com,

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

[adg, 2014-08-18 02:16:30]

LGTM

+agl, who wrote the package

https://codereview.appspot.com/131840043/diff/60001/src/pkg/compress/bzip2/mo...
File src/pkg/compress/bzip2/move_to_front.go (right):

https://codereview.appspot.com/131840043/diff/60001/src/pkg/compress/bzip2/mo...
src/pkg/compress/bzip2/move_to_front.go:57: copy(m.symbols[1:], m.symbols[0:n])
s/0//

[agl1, 2014-08-18 17:31:28]

LGTM with adg's comments addressed.

[josharian, 2014-08-18 18:00:09]

LGTM after adg and my comments

https://codereview.appspot.com/131840043/diff/60001/src/pkg/compress/bzip2/mo...
File src/pkg/compress/bzip2/move_to_front.go (right):

https://codereview.appspot.com/131840043/diff/60001/src/pkg/compress/bzip2/mo...
src/pkg/compress/bzip2/move_to_front.go:16: len     int
Looks like len can now be deleted.

https://codereview.appspot.com/131840043/diff/60001/src/pkg/compress/bzip2/mo...
src/pkg/compress/bzip2/move_to_front.go:48: if n == 0 {
Have you benchmarked to confirm that this special case is still helpful? I
suspect it may not matter, in which case, nicer to delete it.

[jra, 2014-08-18 21:16:33]

Hello adg@golang.org, agl@chromium.org, agl@golang.org, josharian@gmail.com (cc:
golang-codereviews@googlegroups.com),

Please take another look.

[jra, 2014-08-18 21:17:02]

Updated the performace figures to show even better perf I got from your
comments. Thanks!

https://codereview.appspot.com/131840043/diff/60001/src/pkg/compress/bzip2/mo...
File src/pkg/compress/bzip2/move_to_front.go (right):

https://codereview.appspot.com/131840043/diff/60001/src/pkg/compress/bzip2/mo...
src/pkg/compress/bzip2/move_to_front.go:16: len     int
On 2014/08/18 18:00:08, josharian wrote:
> Looks like len can now be deleted.

Wow, thanks for this. This made me think of changing the "methods on a slice"
format, which is faster!

https://codereview.appspot.com/131840043/diff/60001/src/pkg/compress/bzip2/mo...
src/pkg/compress/bzip2/move_to_front.go:48: if n == 0 {
Yanked it, got speed! Whee.

https://codereview.appspot.com/131840043/diff/60001/src/pkg/compress/bzip2/mo...
src/pkg/compress/bzip2/move_to_front.go:57: copy(m.symbols[1:], m.symbols[0:n])
On 2014/08/18 02:16:30, adg wrote:
> s/0//

Done.

[agl1, 2014-08-18 21:41:46]

*** Submitted as https://code.google.com/p/go/source/detail?r=4fa514b5c635 ***

bzip2: improve performance

Improve performance of move-to-front by using cache-friendly
copies instead of doubly-linked list. Simplify so that the
underlying slice is the object. Remove the n=0 special case,
      which was actually slower with the copy approach.

benchmark                 old ns/op     new ns/op     delta
BenchmarkDecodeDigits     26429714      23859699      -9.72%
BenchmarkDecodeTwain      76684510      67591946      -11.86%

benchmark                 old MB/s     new MB/s     speedup
BenchmarkDecodeDigits     1.63         1.81         1.11x
BenchmarkDecodeTwain      1.63         1.85         1.13x

Updates issue 6754.

LGTM=adg, agl, josharian
R=adg, agl, josharian
CC=golang-codereviews
https://codereview.appspot.com/131840043

Committer: Adam Langley <agl@golang.org>

[adg, 2014-08-18 22:29:42]

Hooray for much less code! My favourite kind of CL.

Thanks.


On 19 August 2014 07:41, <agl@golang.org> wrote:

> *** Submitted as
> https://code.google.com/p/go/source/detail?r=4fa514b5c635 ***
>
>
> bzip2: improve performance
>
> Improve performance of move-to-front by using cache-friendly
> copies instead of doubly-linked list. Simplify so that the
> underlying slice is the object. Remove the n=0 special case,
>       which was actually slower with the copy approach.
>
>
> benchmark                 old ns/op     new ns/op     delta
> BenchmarkDecodeDigits     26429714      23859699      -9.72%
> BenchmarkDecodeTwain      76684510      67591946      -11.86%
>
>
> benchmark                 old MB/s     new MB/s     speedup
> BenchmarkDecodeDigits     1.63         1.81         1.11x
> BenchmarkDecodeTwain      1.63         1.85         1.13x
>
> Updates issue 6754.
>
> LGTM=adg, agl, josharian
> R=adg, agl, josharian
> CC=golang-codereviews
> https://codereview.appspot.com/131840043
>
> Committer: Adam Langley <agl@golang.org>
>
>
> https://codereview.appspot.com/131840043/
>