code review 4432077: png: speed up opaque RGBA encoding

png: speed up opaque RGBA encoding

With Linux/8g on a 2006 Mac Mini (1.66 GHz Intel Core Duo,
2KB L1, 2MB L2, 2G main memory), GOMAXPROCS unset:

start:
png.BenchmarkEncodePaletted	      50	  44772820 ns/op
png.BenchmarkEncodeRGBOpaque	      10	 208395900 ns/op
png.BenchmarkEncodeRGBA		       5	 331088000 ns/op

remove interface method calls:
png.BenchmarkEncodePaletted	      50	  44722880 ns/op
png.BenchmarkEncodeRGBOpaque	      10	 139042600 ns/op
png.BenchmarkEncodeRGBA		       5	 334033600 ns/op

flate inline min/max():
png.BenchmarkEncodePaletted	      50	  40631180 ns/op
png.BenchmarkEncodeRGBOpaque	      10	 124894900 ns/op
png.BenchmarkEncodeRGBA		       5	 312099000 ns/op

after adler change:
png.BenchmarkEncodePaletted	      50	  40181760 ns/op
png.BenchmarkEncodeRGBOpaque	      20	 121781950 ns/op
png.BenchmarkEncodeRGBA		       5	 313890800 ns/op

In comparison to 121 ms on this 2006 machine, on my
Core2 Duo 2.66 GHz laptop, the final BenchmarkEncodeRGBOpaque
runs in 27 ms. (these are all for 640x480 images)

[bradfitz, 2011-04-28 05:02:04]

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

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

[bradfitz, 2011-04-28 05:06:54]

I'm also fine leaving the min and max inlining out of this. While it's
noticeable, it's not the biggest win and it's arguably the compiler's job
anyway. I'd favor readable code.

Killing two interface method calls per pixel seems like a win, too, as well
as removing 6 unnecessary shifts, etc per pixel. R, G, B << 8 then >> 8.

On Wed, Apr 27, 2011 at 10:02 PM, <bradfitz@golang.org> wrote:

> Reviewers: nigeltao, rsc, r,
>
> Message:
> Hello nigeltao, rsc, r (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://go.googlecode.com/hg/
>
>
> Description:
> png: speed up opaque RGBA encoding
>
> start:
> png.BenchmarkEncodePaletted           50          44772820 ns/op
> png.BenchmarkEncodeRGBOpaque          10         208395900 ns/op
> png.BenchmarkEncodeRGBA                5         331088000 ns/op
>
> remove interface method calls:
> png.BenchmarkEncodePaletted           50          44722880 ns/op
> png.BenchmarkEncodeRGBOpaque          10         139042600 ns/op
> png.BenchmarkEncodeRGBA                5         334033600 ns/op
>
> flate inline min/max():
> png.BenchmarkEncodePaletted           50          40631180 ns/op
> png.BenchmarkEncodeRGBOpaque          10         124894900 ns/op
> png.BenchmarkEncodeRGBA                5         312099000 ns/op
>
> after adler change:
> png.BenchmarkEncodePaletted           50          40181760 ns/op
> png.BenchmarkEncodeRGBOpaque          20         121781950 ns/op
> png.BenchmarkEncodeRGBA                5         313890800 ns/op
>
> Please review this at http://codereview.appspot.com/4432077/
>
> Affected files:
>  M src/pkg/compress/flate/deflate.go
>  M src/pkg/image/png/writer.go
>  M src/pkg/image/png/writer_test.go
>
>
> Index: src/pkg/compress/flate/deflate.go
> ===================================================================
> --- a/src/pkg/compress/flate/deflate.go
> +++ b/src/pkg/compress/flate/deflate.go
> @@ -143,10 +143,18 @@
>                        d.blockStart = math.MaxInt32
>                }
>                for i, h := range d.hashHead {
> -                       d.hashHead[i] = max(h-wSize, -1)
> +                       v := h - wSize
> +                       if -1 > v {
> +                               v = -1
> +                       }
> +                       d.hashHead[i] = v
>                }
>                for i, h := range d.hashPrev {
> -                       d.hashPrev[i] = max(h-wSize, -1)
> +                       v := -h - wSize
> +                       if -1 > v {
> +                               v = -1
> +                       }
> +                       d.hashPrev[i] = v
>                }
>        }
>        count, err := d.r.Read(d.window[d.windowEnd:])
> @@ -177,10 +185,19 @@
>  // Try to find a match starting at index whose length is greater than
> prevSize.
>  // We only look at chainCount possibilities before giving up.
>  func (d *compressor) findMatch(pos int, prevHead int, prevLength int,
> lookahead int) (length, offset int, ok bool) {
> -       win := d.window[0 : pos+min(maxMatchLength, lookahead)]
> +       // min(maxMatchLength, lookahead)
> +       minMatchLook := maxMatchLength
> +       if lookahead < minMatchLook {
> +               minMatchLook = lookahead
> +       }
> +
> +       win := d.window[0 : pos+minMatchLook]
>
>        // We quit when we get a match that's at least nice long
> -       nice := min(d.niceMatch, len(win)-pos)
> +       nice := len(win) - pos
> +       if d.niceMatch < nice {
> +               nice = d.niceMatch
> +       }
>
>        // If we've got a match that's good enough, only look in 1/4 the
> chain.
>        tries := d.maxChainLength
> @@ -344,9 +361,12 @@
>                }
>                prevLength := length
>                prevOffset := offset
> -               minIndex := max(index-maxOffset, 0)
>                length = minMatchLength - 1
>                offset = 0
> +               minIndex := index - maxOffset
> +               if minIndex < 0 {
> +                       minIndex = 0
> +               }
>
>                if chainHead >= minIndex &&
>                        (isFastDeflate && lookahead > minMatchLength-1 ||
> Index: src/pkg/image/png/writer.go
> ===================================================================
> --- a/src/pkg/image/png/writer.go
> +++ b/src/pkg/image/png/writer.go
> @@ -263,7 +263,12 @@
>        defer zw.Close()
>
>        bpp := 0 // Bytes per pixel.
> +
> +       // Used by fast paths for common image types
>        var paletted *image.Paletted
> +       var rgba *image.RGBA
> +       rgba, _ = m.(*image.RGBA)
> +
>        switch cb {
>        case cbG8:
>                bpp = 1
> @@ -303,12 +308,24 @@
>                                cr[0][x+1] = c.Y
>                        }
>                case cbTC8:
> -                       for x := b.Min.X; x < b.Max.X; x++ {
> -                               // We have previously verified that the
> alpha value is fully opaque.
> -                               r, g, b, _ := m.At(x, y).RGBA()
> -                               cr[0][3*x+1] = uint8(r >> 8)
> -                               cr[0][3*x+2] = uint8(g >> 8)
> -                               cr[0][3*x+3] = uint8(b >> 8)
> +                       // We have previously verified that the alpha value
> is fully opaque.
> +                       cr0 := cr[0]
> +                       if rgba != nil {
> +                               yoff := y * rgba.Stride
> +                               xoff := 3 * b.Min.X
> +                               for _, color := range rgba.Pix[yoff+b.Min.X
> : yoff+b.Max.X] {
> +                                       cr0[xoff+1] = color.R
> +                                       cr0[xoff+2] = color.G
> +                                       cr0[xoff+3] = color.B
> +                                       xoff += 3
> +                               }
> +                       } else {
> +                               for x := b.Min.X; x < b.Max.X; x++ {
> +                                       r, g, b, _ := m.At(x, y).RGBA()
> +                                       cr0[3*x+1] = uint8(r >> 8)
> +                                       cr0[3*x+2] = uint8(g >> 8)
> +                                       cr0[3*x+3] = uint8(b >> 8)
> +                               }
>                        }
>                case cbP8:
>                        rowOffset := y * paletted.Stride
> Index: src/pkg/image/png/writer_test.go
> ===================================================================
> --- a/src/pkg/image/png/writer_test.go
> +++ b/src/pkg/image/png/writer_test.go
> @@ -88,3 +88,32 @@
>                Encode(buffer, img)
>        }
>  }
> +
> +func BenchmarkEncodeRGBOpaque(b *testing.B) {
> +       b.StopTimer()
> +       img := image.NewRGBA(640, 480)
> +       // Set all pixels to 0xFF alpha to force opaque mode.
> +       bo := img.Bounds()
> +       for y := bo.Min.Y; y < bo.Max.Y; y++ {
> +               for x := bo.Min.X; x < bo.Max.X; x++ {
> +                       img.Set(x, y, image.RGBAColor{0, 0, 0, 255})
> +               }
> +       }
> +       b.StartTimer()
> +       buffer := new(bytes.Buffer)
> +       for i := 0; i < b.N; i++ {
> +               buffer.Reset()
> +               Encode(buffer, img)
> +       }
> +}
> +
> +func BenchmarkEncodeRGBA(b *testing.B) {
> +       b.StopTimer()
> +       img := image.NewRGBA(640, 480)
> +       b.StartTimer()
> +       buffer := new(bytes.Buffer)
> +       for i := 0; i < b.N; i++ {
> +               buffer.Reset()
> +               Encode(buffer, img)
> +       }
> +}
>
>
>

[r, 2011-04-28 06:06:26]

LGTM, but maybe let nigel have a look.

thanks for putting the numbers in the CL.  

can you please mention in the CL desc what sort of machine the benchmarks ran
on?

http://codereview.appspot.com/4432077/diff/3/src/pkg/compress/flate/deflate.go
File src/pkg/compress/flate/deflate.go (right):

http://codereview.appspot.com/4432077/diff/3/src/pkg/compress/flate/deflate.g...
src/pkg/compress/flate/deflate.go:147: if -1 > v {
please don't write C-style ifs. v < -1 is much nicer to read and you can't make
the C mistake in Go.

http://codereview.appspot.com/4432077/diff/3/src/pkg/compress/flate/deflate.g...
src/pkg/compress/flate/deflate.go:188: // min(maxMatchLength, lookahead)
delete this line. the code is plenty clear
i have no problem with inlining min/max. i almost never bother with the function
form anyway. ifs are cool!

http://codereview.appspot.com/4432077/diff/3/src/pkg/image/png/writer_test.go
File src/pkg/image/png/writer_test.go (right):

http://codereview.appspot.com/4432077/diff/3/src/pkg/image/png/writer_test.go...
src/pkg/image/png/writer_test.go:114: buffer := new(bytes.Buffer)
might as well move the allocation up one line. in the other function too.

[bradfitz, 2011-04-28 06:36:34]

http://codereview.appspot.com/4432077/diff/3/src/pkg/compress/flate/deflate.go
File src/pkg/compress/flate/deflate.go (right):

http://codereview.appspot.com/4432077/diff/3/src/pkg/compress/flate/deflate.g...
src/pkg/compress/flate/deflate.go:147: if -1 > v {
On 2011/04/28 06:06:26, r wrote:
> please don't write C-style ifs. v < -1 is much nicer to read and you can't
make
> the C mistake in Go.

Done.

http://codereview.appspot.com/4432077/diff/3/src/pkg/compress/flate/deflate.g...
src/pkg/compress/flate/deflate.go:188: // min(maxMatchLength, lookahead)
On 2011/04/28 06:06:26, r wrote:
> delete this line. the code is plenty clear
> i have no problem with inlining min/max. i almost never bother with the
function
> form anyway. ifs are cool!

Done.

http://codereview.appspot.com/4432077/diff/3/src/pkg/image/png/writer_test.go
File src/pkg/image/png/writer_test.go (right):

http://codereview.appspot.com/4432077/diff/3/src/pkg/image/png/writer_test.go...
src/pkg/image/png/writer_test.go:114: buffer := new(bytes.Buffer)
On 2011/04/28 06:06:26, r wrote:
> might as well move the allocation up one line. in the other function too.

Done.

[bradfitz, 2011-04-28 06:36:46]

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

Please take another look.

[r, 2011-04-28 07:17:05]

LGTM

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

I'll wait for Nigel too.

I also haven't tested an actual image with this and I'm not sure how
comprehensive the writer tests are.
I don't trust myself to not have screwed something up.

On Thu, Apr 28, 2011 at 12:17 AM, <r@golang.org> wrote:

> LGTM
>
>
>
> http://codereview.appspot.com/4432077/
>

[rsc, 2011-04-28 11:51:39]

Please use b.SetBytes in the benchmark.  Then you will get
some MB/s times too, which are likely to be easier to compare.

[nigeltao, 2011-05-02 09:05:50]

LGTM.

http://codereview.appspot.com/4432077/diff/10004/src/pkg/image/png/writer.go
File src/pkg/image/png/writer.go (right):

http://codereview.appspot.com/4432077/diff/10004/src/pkg/image/png/writer.go#...
src/pkg/image/png/writer.go:315: xoff := 3 * b.Min.X
Add a +1 here and subtract 1 on lines 317-319?

[bradfitz, 2011-05-02 14:25:41]

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

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

[bradfitz, 2011-05-02 14:26:04]

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

png: speed up opaque RGBA encoding

With Linux/8g on a 2006 Mac Mini (1.66 GHz Intel Core Duo,
2KB L1, 2MB L2, 2G main memory), GOMAXPROCS unset:

start:
png.BenchmarkEncodePaletted	      50	  44772820 ns/op
png.BenchmarkEncodeRGBOpaque	      10	 208395900 ns/op
png.BenchmarkEncodeRGBA		       5	 331088000 ns/op

remove interface method calls:
png.BenchmarkEncodePaletted	      50	  44722880 ns/op
png.BenchmarkEncodeRGBOpaque	      10	 139042600 ns/op
png.BenchmarkEncodeRGBA		       5	 334033600 ns/op

flate inline min/max():
png.BenchmarkEncodePaletted	      50	  40631180 ns/op
png.BenchmarkEncodeRGBOpaque	      10	 124894900 ns/op
png.BenchmarkEncodeRGBA		       5	 312099000 ns/op

after adler change:
png.BenchmarkEncodePaletted	      50	  40181760 ns/op
png.BenchmarkEncodeRGBOpaque	      20	 121781950 ns/op
png.BenchmarkEncodeRGBA		       5	 313890800 ns/op

In comparison to 121 ms on this 2006 machine, on my
Core2 Duo 2.66 GHz laptop, the final BenchmarkEncodeRGBOpaque
runs in 27 ms. (these are all for 640x480 images)

R=nigeltao, rsc, r
CC=golang-dev
http://codereview.appspot.com/4432077