code review 4441073: adler32: speed up ~40% by avoiding bounds checks

adler32: speed up ~40% by avoiding bounds checks

before & after:
adler32.BenchmarkGolden	  100000	     14747 ns/op
adler32.BenchmarkGolden	  200000	      8761 ns/op

Found by profiling PNG encoding.

[bradfitz, 2011-04-28 04:20:38]

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

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

[rsc, 2011-04-28 04:23:19]

Please change the benchmark.

io.WriteString contains an allocation (string -> []byte)
so the benchmark is timing more than just adler32.

var buf bytes.Buffer
for _, g := range golden {
    io.WriteString(&buf, g.in)
}

c := New()
for i := 0; i < b.N; i++ {
    c.Write(buf.Bytes())
}

It should be even faster with the correct benchmark.

[bradfitz, 2011-04-28 04:29:36]

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

Please take another look.

[bradfitzgoog, 2011-04-28 04:30:10]

Whoops.  Was just blindly copying the existing tests as my benchmark.
 Didn't notice the allocation.

Now 40% ... nice!

On Wed, Apr 27, 2011 at 9:23 PM, Russ Cox <rsc@golang.org> wrote:

> Please change the benchmark.
>
> io.WriteString contains an allocation (string -> []byte)
> so the benchmark is timing more than just adler32.
>
> var buf bytes.Buffer
> for _, g := range golden {
>    io.WriteString(&buf, g.in)
> }
>
> c := New()
> for i := 0; i < b.N; i++ {
>     c.Write(buf.Bytes())
> }
>
> It should be even faster with the correct benchmark.
>

[eds, 2011-04-28 04:30:36]

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

http://codereview.appspot.com/4441073/diff/2001/src/pkg/hash/adler32/adler32....
src/pkg/hash/adler32/adler32.go:46: for _, pi := range p {
Other ideas (up to you if you want to pursue them in this CL):
1. Use uintptr instead of uint32 so we can do fewer modulus operations on amd64.
You'll have to change the constant too.

2. With 32-bit ints, we can run the loop up to 5552 times without doing a
modulus in the worst case. This means we can avoid branching inside the loop.
We'll end up doing a few more modulus operations on average, but it's probably
still worth it. The reference implementation in C does this.

[bradfitz, 2011-04-28 04:32:23]

Evan, I'll leave those for you.  :-)

This satisfies my current itch and I'm working on other parts too at the
moment.

On Wed, Apr 27, 2011 at 9:30 PM, <chickencha@gmail.com> wrote:

>
>
>
http://codereview.appspot.com/4441073/diff/2001/src/pkg/hash/adler32/adler32.go
> File src/pkg/hash/adler32/adler32.go (right):
>
>
>
http://codereview.appspot.com/4441073/diff/2001/src/pkg/hash/adler32/adler32....
> src/pkg/hash/adler32/adler32.go:46: for _, pi := range p {
> Other ideas (up to you if you want to pursue them in this CL):
> 1. Use uintptr instead of uint32 so we can do fewer modulus operations
> on amd64. You'll have to change the constant too.
>
> 2. With 32-bit ints, we can run the loop up to 5552 times without doing
> a modulus in the worst case. This means we can avoid branching inside
> the loop. We'll end up doing a few more modulus operations on average,
> but it's probably still worth it. The reference implementation in C does
> this.
>
>
> http://codereview.appspot.com/4441073/
>

[rsc, 2011-04-28 04:34:51]

LGTM

[bradfitz, 2011-04-28 04:36:14]

*** Submitted as http://code.google.com/p/go/source/detail?r=ff32eff02b8e ***

adler32: speed up ~40% by avoiding bounds checks

before & after:
adler32.BenchmarkGolden	  100000	     14747 ns/op
adler32.BenchmarkGolden	  200000	      8761 ns/op

Found by profiling PNG encoding.

R=rsc, bradfitzwork, eds
CC=golang-dev
http://codereview.appspot.com/4441073

[eds, 2011-04-28 07:25:33]

On Thu, Apr 28, 2011 at 4:32 PM, Brad Fitzpatrick <bradfitz@golang.org> wrote:
> Evan, I'll leave those for you.  :-)

In case anyone's curious, neither suggestion ended up making much
difference. Taking the branch out of the loop helped a little bit in
the worst case, but was actually a little worse in the current code's
best case. On average it was a slight win, but hardly worth it.

The uintptr change was just all around worse.

- Evan