code review 117290043: image/png: use branch-free abs function

image/png: use branch-free abs function

benchmark                        old ns/op     new ns/op     delta       
BenchmarkPaeth                   5.06          6.02          +18.97%     
BenchmarkDecodeGray              1010551       956911        -5.31%      
BenchmarkDecodeNRGBAGradient     3877813       3754160       -3.19%      
BenchmarkDecodeNRGBAOpaque       3194058       3079094       -3.60%      
BenchmarkDecodePaletted          699243        700211        +0.14%      
BenchmarkDecodeRGB               2835733       2692120       -5.06%      
BenchmarkDecodeInterlacing       3651805       3563124       -2.43%      
BenchmarkEncodeGray              4399183       4404113       +0.11%      
BenchmarkEncodeNRGBOpaque        13323627      13306485      -0.13%      
BenchmarkEncodeNRGBA             15840092      15751188      -0.56%      
BenchmarkEncodePaletted          4396622       4404373       +0.18%      
BenchmarkEncodeRGBOpaque         13320475      13279189      -0.31%      
BenchmarkEncodeRGBA              36898392      36781002      -0.32%

[ruiu, 2014-07-29 04:05:54]

Hello nigeltao@golang.org (cc: golang-codereviews@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go

[ruiu, 2014-07-29 04:08:20]

I'm not very happy about copy-and-pasting CL 107340047 but have no idea
better than doing this.


On Mon, Jul 28, 2014 at 9:05 PM, <ruiu@google.com> wrote:

> Reviewers: nigeltao,
>
> Message:
> Hello nigeltao@golang.org (cc: golang-codereviews@googlegroups.com),
>
> I'd like you to review this change to
> https://code.google.com/p/go
>
>
> Description:
> image/png: use branch-free abs function
>
> benchmark                        old ns/op     new ns/op     delta
>
> BenchmarkPaeth                   5.06          6.02          +18.97%
>
> BenchmarkDecodeGray              1010551       956911        -5.31%
>
> BenchmarkDecodeNRGBAGradient     3877813       3754160       -3.19%
>
> BenchmarkDecodeNRGBAOpaque       3194058       3079094       -3.60%
>
> BenchmarkDecodePaletted          699243        700211        +0.14%
>
> BenchmarkDecodeRGB               2835733       2692120       -5.06%
>
> BenchmarkDecodeInterlacing       3651805       3563124       -2.43%
>
> BenchmarkEncodeGray              4399183       4404113       +0.11%
>
> BenchmarkEncodeNRGBOpaque        13323627      13306485      -0.13%
>
> BenchmarkEncodeNRGBA             15840092      15751188      -0.56%
>
> BenchmarkEncodePaletted          4396622       4404373       +0.18%
>
> BenchmarkEncodeRGBOpaque         13320475      13279189      -0.31%
>
> BenchmarkEncodeRGBA              36898392      36781002      -0.32%
>
> Please review this at https://codereview.appspot.com/117290043/
>
> Affected files (+25, -24 lines):
>   M src/pkg/image/png/paeth.go
>   M src/pkg/image/png/paeth_test.go
>
>
> Index: src/pkg/image/png/paeth.go
> ===================================================================
> --- a/src/pkg/image/png/paeth.go
> +++ b/src/pkg/image/png/paeth.go
> @@ -4,6 +4,21 @@
>
>  package png
>
> +// intSize is either 32 or 64.
> +const intSize = 32 << (^uint(0) >> 63)
> +
> +func abs(x int) int {
> +       // m := -1 if x < 0. m := 0 otherwise.
> +       m := x >> (intSize - 1)
> +
> +       // In two's complement representation, the negative number
> +       // of any number (except the smallest one) can be computed
> +       // by flipping all the bits and add 1. This is faster than
> +       // code with a branch.
> +       // See Hacker's Delight, section 2-4.
> +       return (x ^ m) - m
> +}
> +
>  // paeth implements the Paeth filter function, as per the PNG
> specification.
>  func paeth(a, b, c uint8) uint8 {
>         // This is an optimized version of the sample code in the PNG spec.
> @@ -16,16 +31,9 @@
>         pc := int(c)
>         pa := int(b) - pc
>         pb := int(a) - pc
> -       pc = pa + pb
> -       if pa < 0 {
> -               pa = -pa
> -       }
> -       if pb < 0 {
> -               pb = -pb
> -       }
> -       if pc < 0 {
> -               pc = -pc
> -       }
> +       pc = abs(pa + pb)
> +       pa = abs(pa)
> +       pb = abs(pb)
>         if pa <= pb && pa <= pc {
>                 return a
>         } else if pb <= pc {
> @@ -44,16 +52,9 @@
>                         b = int(pdat[j])
>                         pa = b - c
>                         pb = a - c
> -                       pc = pa + pb
> -                       if pa < 0 {
> -                               pa = -pa
> -                       }
> -                       if pb < 0 {
> -                               pb = -pb
> -                       }
> -                       if pc < 0 {
> -                               pc = -pc
> -                       }
> +                       pc = abs(pa + pb)
> +                       pa = abs(pa)
> +                       pb = abs(pb)
>                         if pa <= pb && pa <= pc {
>                                 // No-op.
>                         } else if pb <= pc {
> Index: src/pkg/image/png/paeth_test.go
> ===================================================================
> --- a/src/pkg/image/png/paeth_test.go
> +++ b/src/pkg/image/png/paeth_test.go
> @@ -10,7 +10,7 @@
>         "testing"
>  )
>
> -func abs(x int) int {
> +func slowAbs(x int) int {
>         if x < 0 {
>                 return -x
>         }
> @@ -21,9 +21,9 @@
>  // It is a straight port of the sample code in the PNG spec, section 9.4.
>  func slowPaeth(a, b, c uint8) uint8 {
>         p := int(a) + int(b) - int(c)
> -       pa := abs(p - int(a))
> -       pb := abs(p - int(b))
> -       pc := abs(p - int(c))
> +       pa := slowAbs(p - int(a))
> +       pb := slowAbs(p - int(b))
> +       pc := slowAbs(p - int(c))
>         if pa <= pb && pa <= pc {
>                 return a
>         } else if pb <= pc {
>
>
>

[nigeltao, 2014-07-29 04:28:23]

LGTM.

[nigeltao, 2014-07-29 04:29:33]

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

image/png: use branch-free abs function

benchmark                        old ns/op     new ns/op     delta
BenchmarkPaeth                   5.06          6.02          +18.97%
BenchmarkDecodeGray              1010551       956911        -5.31%
BenchmarkDecodeNRGBAGradient     3877813       3754160       -3.19%
BenchmarkDecodeNRGBAOpaque       3194058       3079094       -3.60%
BenchmarkDecodePaletted          699243        700211        +0.14%
BenchmarkDecodeRGB               2835733       2692120       -5.06%
BenchmarkDecodeInterlacing       3651805       3563124       -2.43%
BenchmarkEncodeGray              4399183       4404113       +0.11%
BenchmarkEncodeNRGBOpaque        13323627      13306485      -0.13%
BenchmarkEncodeNRGBA             15840092      15751188      -0.56%
BenchmarkEncodePaletted          4396622       4404373       +0.18%
BenchmarkEncodeRGBOpaque         13320475      13279189      -0.31%
BenchmarkEncodeRGBA              36898392      36781002      -0.32%

LGTM=nigeltao
R=nigeltao
CC=golang-codereviews
https://codereview.appspot.com/117290043

Committer: Nigel Tao <nigeltao@golang.org>

[gobot, 2014-07-29 04:31:14]

This CL appears to have broken the linux-386-387 builder.
See http://build.golang.org/log/33e057ec87cf705d5c479f18f5b53a018264c315

[dave_cheney.net, 2014-07-29 04:47:04]

cmd/gc
<built-in>:0:0: internal compiler error: Segmentation fault
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-4.8/README.Bugs> for instructions.
The bug is not reproducible, so it is likely a hardware or OS problem.
go tool dist: FAILED: gcc -Wall -Wstrict-prototypes -Wextra -Wunused
-Wno-sign-compare -Wno-missing-braces -Wno-parentheses
-Wno-unknown-pragmas -Wno-switch -Wno-comment
-Wno-missing-field-initializers -Werror -fno-common -ggdb -pipe
-Wuninitialized -O2 -fmessage-length=0 -c -m32 -I
/tmp/gobuilder/linux-386-387-d4f4fb0e307c/go/include -I
/tmp/gobuilder/linux-386-387-d4f4fb0e307c/go/src/cmd/gc -o
$WORK/align.o /tmp/gobuilder/linux-386-387-d4f4fb0e307c/go/src/cmd/gc/align.c
Build complete, duration 1m8.986552959s. Result: error: exit status 1


I think you win a prize or something.



On Tue, Jul 29, 2014 at 2:31 PM, <gobot@golang.org> wrote:

> This CL appears to have broken the linux-386-387 builder.
> See http://build.golang.org/log/33e057ec87cf705d5c479f18f5b53a018264c315
>
>
> https://codereview.appspot.com/117290043/
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-codereviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-codereviews+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

[ruiu, 2014-07-29 04:47:16]

GCC failed with an internal compiler error. Unlikely to related to this CL
but seems pretty weird. Hardware failure?


On Mon, Jul 28, 2014 at 9:31 PM, <gobot@golang.org> wrote:

> This CL appears to have broken the linux-386-387 builder.
> See http://build.golang.org/log/33e057ec87cf705d5c479f18f5b53a018264c315
>
> https://codereview.appspot.com/117290043/
>

[minux, 2014-07-29 21:56:43]

I think this function is potentially useful in a lot of places, could we
add that to a internal package? e.g. internal/math.

[ruiu, 2014-07-29 22:36:36]

There are indeed several dozen occurrences of the pattern "if (x < 0) { x =
-x }" in the standard library, but none of them except this seems to be in
a performance critical path. We probably don't need branch-less abs
function there.

On the other hand, abs(x) is just more readable than the if pattern, so it
may worth doing for the sake of that. Also if we have the package we could
add new utility functions such as saturation arithmetic ones there. I
honestly don't know what we should do. WDYT.

On Tue, Jul 29, 2014 at 2:56 PM, minux <minux@golang.org> wrote:

> I think this function is potentially useful in a lot of places, could we
> add that to a internal package? e.g. internal/math.
>