FAQ
Reviewers: bradfitz, khr1,

Message:
Hello bradfitz@golang.org, khr@google.com (cc:
golang-dev@googlegroups.com),

I'd like you to review this change to
https://khr%40golang.org@code.google.com/p/go/


Description:
compress/flate: faster version of forwardCopy

benchmark old ns/op new ns/op delta
BenchmarkDecodeDigitsSpeed1e4 197767 203490 +2.89%
BenchmarkDecodeDigitsSpeed1e5 1873969 1912761 +2.07%
BenchmarkDecodeDigitsSpeed1e6 18922760 19021056 +0.52%
BenchmarkDecodeDigitsDefault1e4 194975 197054 +1.07%
BenchmarkDecodeDigitsDefault1e5 1704262 1719988 +0.92%
BenchmarkDecodeDigitsDefault1e6 16618354 16351957 -1.60%
BenchmarkDecodeDigitsCompress1e4 195281 194626 -0.34%
BenchmarkDecodeDigitsCompress1e5 1694364 1702372 +0.47%
BenchmarkDecodeDigitsCompress1e6 16463347 16492126 +0.17%
BenchmarkDecodeTwainSpeed1e4 200653 200127 -0.26%
BenchmarkDecodeTwainSpeed1e5 1861385 1759632 -5.47%
BenchmarkDecodeTwainSpeed1e6 18255769 17186679 -5.86%
BenchmarkDecodeTwainDefault1e4 189080 185157 -2.07%
BenchmarkDecodeTwainDefault1e5 1559222 1461465 -6.27%
BenchmarkDecodeTwainDefault1e6 14792125 13879051 -6.17%
BenchmarkDecodeTwainCompress1e4 188881 185151 -1.97%
BenchmarkDecodeTwainCompress1e5 1537031 1456945 -5.21%
BenchmarkDecodeTwainCompress1e6 14805972 13405094 -9.46%

Please review this at https://codereview.appspot.com/9425046/

Affected files:
    M src/pkg/compress/flate/copy.go
    M src/pkg/compress/flate/copy_test.go
    M src/pkg/compress/flate/inflate.go


Index: src/pkg/compress/flate/copy.go
===================================================================
--- a/src/pkg/compress/flate/copy.go
+++ b/src/pkg/compress/flate/copy.go
@@ -6,12 +6,27 @@

   // forwardCopy is like the built-in copy function except that it always
goes
   // forward from the start, even if the dst and src overlap.
-func forwardCopy(dst, src []byte) int {
- if len(src) > len(dst) {
- src = src[:len(dst)]
+// equivalent to:
+// for i := 0; i < n; i++ {
+// mem[dst+i] = mem[src+i]
+// }
+func forwardCopy(mem []byte, dst, src, n int) {
+ if dst <= src {
+ copy(mem[dst:dst+n], mem[src:src+n])
+ return
    }
- for i, x := range src {
- dst[i] = x
+ for {
+ if dst >= src+n {
+ copy(mem[dst:dst+n], mem[src:src+n])
+ return
+ }
+ // There is some forward overlap. The destination
+ // will be filled with a repeated pattern of mem[src:src+k].
+ // We copy one instance of the pattern here, then repeat.
+ // Each time around this loop k will double.
+ k := dst - src
+ copy(mem[dst:dst+k], mem[src:src+k])
+ n -= k
+ dst += k
    }
- return len(src)
   }
Index: src/pkg/compress/flate/copy_test.go
===================================================================
--- a/src/pkg/compress/flate/copy_test.go
+++ b/src/pkg/compress/flate/copy_test.go
@@ -30,10 +30,12 @@
    }
    for _, tc := range testCases {
     b := []byte("0123456789")
- dst := b[tc.dst0:tc.dst1]
- src := b[tc.src0:tc.src1]
- n := forwardCopy(dst, src)
- got := string(dst[:n])
+ n := tc.dst1 - tc.dst0
+ if tc.src1-tc.src0 < n {
+ n = tc.src1 - tc.src0
+ }
+ forwardCopy(b, tc.dst0, tc.src0, n)
+ got := string(b[tc.dst0 : tc.dst0+n])
     if got != tc.want {
      t.Errorf("dst=b[%d:%d], src=b[%d:%d]: got %q, want %q",
       tc.dst0, tc.dst1, tc.src0, tc.src1, got, tc.want)
Index: src/pkg/compress/flate/inflate.go
===================================================================
--- a/src/pkg/compress/flate/inflate.go
+++ b/src/pkg/compress/flate/inflate.go
@@ -511,7 +511,7 @@
     if x := len(f.hist) - p; n > x {
      n = x
     }
- forwardCopy(f.hist[f.hp:f.hp+n], f.hist[p:p+n])
+ forwardCopy(f.hist[:], f.hp, p, n)
     p += n
     f.hp += n
     f.copyLen -= n


--

---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

  • Brad Fitzpatrick at May 17, 2013 at 10:19 pm
    I defer to others on this.


    On Fri, May 17, 2013 at 3:16 PM, wrote:

    Reviewers: bradfitz, khr1,

    Message:
    Hello bradfitz@golang.org, khr@google.com (cc:
    golang-dev@googlegroups.com),

    I'd like you to review this change to
    https://khr%40golang.org@code.**google.com/p/go/<http://40golang.org@code.google.com/p/go/>


    Description:
    compress/flate: faster version of forwardCopy

    benchmark old ns/op new ns/op delta
    BenchmarkDecodeDigitsSpeed1e4 197767 203490 +2.89%
    BenchmarkDecodeDigitsSpeed1e5 1873969 1912761 +2.07%
    BenchmarkDecodeDigitsSpeed1e6 18922760 19021056 +0.52%
    BenchmarkDecodeDigitsDefault1e**4 194975 197054 +1.07%
    BenchmarkDecodeDigitsDefault1e**5 1704262 1719988 +0.92%
    BenchmarkDecodeDigitsDefault1e**6 16618354 16351957 -1.60%
    BenchmarkDecodeDigitsCompress1**e4 195281 194626 -0.34%
    BenchmarkDecodeDigitsCompress1**e5 1694364 1702372 +0.47%
    BenchmarkDecodeDigitsCompress1**e6 16463347 16492126 +0.17%
    BenchmarkDecodeTwainSpeed1e4 200653 200127 -0.26%
    BenchmarkDecodeTwainSpeed1e5 1861385 1759632 -5.47%
    BenchmarkDecodeTwainSpeed1e6 18255769 17186679 -5.86%
    BenchmarkDecodeTwainDefault1e4 189080 185157 -2.07%
    BenchmarkDecodeTwainDefault1e5 1559222 1461465 -6.27%
    BenchmarkDecodeTwainDefault1e6 14792125 13879051 -6.17%
    BenchmarkDecodeTwainCompress1e**4 188881 185151 -1.97%
    BenchmarkDecodeTwainCompress1e**5 1537031 1456945 -5.21%
    BenchmarkDecodeTwainCompress1e**6 14805972 13405094 -9.46%

    Please review this at https://codereview.appspot.**com/9425046/<https://codereview.appspot.com/9425046/>

    Affected files:
    M src/pkg/compress/flate/copy.go
    M src/pkg/compress/flate/copy_**test.go
    M src/pkg/compress/flate/**inflate.go


    Index: src/pkg/compress/flate/copy.go
    ==============================**==============================**=======
    --- a/src/pkg/compress/flate/copy.**go
    +++ b/src/pkg/compress/flate/copy.**go
    @@ -6,12 +6,27 @@

    // forwardCopy is like the built-in copy function except that it always
    goes
    // forward from the start, even if the dst and src overlap.
    -func forwardCopy(dst, src []byte) int {
    - if len(src) > len(dst) {
    - src = src[:len(dst)]
    +// equivalent to:
    +// for i := 0; i < n; i++ {
    +// mem[dst+i] = mem[src+i]
    +// }
    +func forwardCopy(mem []byte, dst, src, n int) {
    + if dst <= src {
    + copy(mem[dst:dst+n], mem[src:src+n])
    + return
    }
    - for i, x := range src {
    - dst[i] = x
    + for {
    + if dst >= src+n {
    + copy(mem[dst:dst+n], mem[src:src+n])
    + return
    + }
    + // There is some forward overlap. The destination
    + // will be filled with a repeated pattern of
    mem[src:src+k].
    + // We copy one instance of the pattern here, then repeat.
    + // Each time around this loop k will double.
    + k := dst - src
    + copy(mem[dst:dst+k], mem[src:src+k])
    + n -= k
    + dst += k
    }
    - return len(src)
    }
    Index: src/pkg/compress/flate/copy_**test.go
    ==============================**==============================**=======
    --- a/src/pkg/compress/flate/copy_**test.go
    +++ b/src/pkg/compress/flate/copy_**test.go
    @@ -30,10 +30,12 @@
    }
    for _, tc := range testCases {
    b := []byte("0123456789")
    - dst := b[tc.dst0:tc.dst1]
    - src := b[tc.src0:tc.src1]
    - n := forwardCopy(dst, src)
    - got := string(dst[:n])
    + n := tc.dst1 - tc.dst0
    + if tc.src1-tc.src0 < n {
    + n = tc.src1 - tc.src0
    + }
    + forwardCopy(b, tc.dst0, tc.src0, n)
    + got := string(b[tc.dst0 : tc.dst0+n])
    if got != tc.want {
    t.Errorf("dst=b[%d:%d], src=b[%d:%d]: got %q, want
    %q",
    tc.dst0, tc.dst1, tc.src0, tc.src1, got,
    tc.want)
    Index: src/pkg/compress/flate/**inflate.go
    ==============================**==============================**=======
    --- a/src/pkg/compress/flate/**inflate.go
    +++ b/src/pkg/compress/flate/**inflate.go
    @@ -511,7 +511,7 @@
    if x := len(f.hist) - p; n > x {
    n = x
    }
    - forwardCopy(f.hist[f.hp:f.hp+**n], f.hist[p:p+n])
    + forwardCopy(f.hist[:], f.hp, p, n)
    p += n
    f.hp += n
    f.copyLen -= n

    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Nigeltao at May 18, 2013 at 5:32 pm
    LGTM.

    CC'ing Raph Levien, since we were just talking yesterday about
    optimizing flate.


    https://codereview.appspot.com/9425046/diff/6002/src/pkg/compress/flate/copy.go
    File src/pkg/compress/flate/copy.go (right):

    https://codereview.appspot.com/9425046/diff/6002/src/pkg/compress/flate/copy.go#newcode9
    src/pkg/compress/flate/copy.go:9: // equivalent to:
    Make this a complete sentence:

    // It is equivalent to:

    https://codereview.appspot.com/9425046/

    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Nigel Tao at May 18, 2013 at 5:52 pm
    Out of curiousity, can we also get a benchcmp for image/png?

    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Brad Fitzpatrick at May 18, 2013 at 8:32 pm

    On Sat, May 18, 2013 at 10:52 AM, Nigel Tao wrote:

    Out of curiousity, can we also get a benchcmp for image/png?
    benchmark old ns/op new ns/op delta
    BenchmarkPaeth 5 5 +2.69%
    BenchmarkDecodeGray 1292058 1207025 -6.58%
    BenchmarkDecodeNRGBAGradient 5471073 4603122 -15.86%
    BenchmarkDecodeNRGBAOpaque 4765816 4036000 -15.31%
    BenchmarkDecodePaletted 1037492 853686 -17.72%
    BenchmarkDecodeRGB 5302434 4470217 -15.69%
    BenchmarkEncodeGray 7289243 6146824 -15.67%
    BenchmarkEncodeNRGBOpaque 21253587 18765274 -11.71%
    BenchmarkEncodeNRGBA 22622053 22235804 -1.71%
    BenchmarkEncodePaletted 6098935 6292153 +3.17%
    BenchmarkEncodeRGBOpaque 18819536 19607316 +4.19%
    BenchmarkEncodeRGBA 50199860 50570850 +0.74%

    benchmark old MB/s new MB/s speedup
    BenchmarkDecodeGray 50.72 54.30 1.07x
    BenchmarkDecodeNRGBAGradient 47.91 56.95 1.19x
    BenchmarkDecodeNRGBAOpaque 55.01 64.95 1.18x
    BenchmarkDecodePaletted 63.17 76.77 1.22x
    BenchmarkDecodeRGB 49.44 58.64 1.19x
    BenchmarkEncodeGray 42.14 49.98 1.19x
    BenchmarkEncodeNRGBOpaque 57.82 65.48 1.13x
    BenchmarkEncodeNRGBA 54.32 55.26 1.02x
    BenchmarkEncodePaletted 50.37 48.82 0.97x
    BenchmarkEncodeRGBOpaque 65.29 62.67 0.96x
    BenchmarkEncodeRGBA 24.48 24.30 0.99x

    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Brad Fitzpatrick at May 18, 2013 at 8:32 pm
    processor : 7
    vendor_id : GenuineIntel
    cpu family : 6
    model : 30
    model name : Intel(R) Core(TM) i7 CPU 860 @ 2.80GHz
    stepping : 5
    microcode : 0x3
    cpu MHz : 1200.000
    cache size : 8192 KB




    2013/5/18 Brad Fitzpatrick <bradfitz@golang.org>

    On Sat, May 18, 2013 at 10:52 AM, Nigel Tao wrote:

    Out of curiousity, can we also get a benchcmp for image/png?
    benchmark old ns/op new ns/op delta
    BenchmarkPaeth 5 5 +2.69%
    BenchmarkDecodeGray 1292058 1207025 -6.58%
    BenchmarkDecodeNRGBAGradient 5471073 4603122 -15.86%
    BenchmarkDecodeNRGBAOpaque 4765816 4036000 -15.31%
    BenchmarkDecodePaletted 1037492 853686 -17.72%
    BenchmarkDecodeRGB 5302434 4470217 -15.69%
    BenchmarkEncodeGray 7289243 6146824 -15.67%
    BenchmarkEncodeNRGBOpaque 21253587 18765274 -11.71%
    BenchmarkEncodeNRGBA 22622053 22235804 -1.71%
    BenchmarkEncodePaletted 6098935 6292153 +3.17%
    BenchmarkEncodeRGBOpaque 18819536 19607316 +4.19%
    BenchmarkEncodeRGBA 50199860 50570850 +0.74%

    benchmark old MB/s new MB/s speedup
    BenchmarkDecodeGray 50.72 54.30 1.07x
    BenchmarkDecodeNRGBAGradient 47.91 56.95 1.19x
    BenchmarkDecodeNRGBAOpaque 55.01 64.95 1.18x
    BenchmarkDecodePaletted 63.17 76.77 1.22x
    BenchmarkDecodeRGB 49.44 58.64 1.19x
    BenchmarkEncodeGray 42.14 49.98 1.19x
    BenchmarkEncodeNRGBOpaque 57.82 65.48 1.13x
    BenchmarkEncodeNRGBA 54.32 55.26 1.02x
    BenchmarkEncodePaletted 50.37 48.82 0.97x
    BenchmarkEncodeRGBOpaque 65.29 62.67 0.96x
    BenchmarkEncodeRGBA 24.48 24.30 0.99x
    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Khr at May 18, 2013 at 10:28 pm
    *** Submitted as
    https://code.google.com/p/go/source/detail?r=bd653e485f1d ***

    compress/flate: faster version of forwardCopy

    benchmark old ns/op new ns/op delta
    BenchmarkDecodeDigitsSpeed1e4 197767 203490 +2.89%
    BenchmarkDecodeDigitsSpeed1e5 1873969 1912761 +2.07%
    BenchmarkDecodeDigitsSpeed1e6 18922760 19021056 +0.52%
    BenchmarkDecodeDigitsDefault1e4 194975 197054 +1.07%
    BenchmarkDecodeDigitsDefault1e5 1704262 1719988 +0.92%
    BenchmarkDecodeDigitsDefault1e6 16618354 16351957 -1.60%
    BenchmarkDecodeDigitsCompress1e4 195281 194626 -0.34%
    BenchmarkDecodeDigitsCompress1e5 1694364 1702372 +0.47%
    BenchmarkDecodeDigitsCompress1e6 16463347 16492126 +0.17%
    BenchmarkDecodeTwainSpeed1e4 200653 200127 -0.26%
    BenchmarkDecodeTwainSpeed1e5 1861385 1759632 -5.47%
    BenchmarkDecodeTwainSpeed1e6 18255769 17186679 -5.86%
    BenchmarkDecodeTwainDefault1e4 189080 185157 -2.07%
    BenchmarkDecodeTwainDefault1e5 1559222 1461465 -6.27%
    BenchmarkDecodeTwainDefault1e6 14792125 13879051 -6.17%
    BenchmarkDecodeTwainCompress1e4 188881 185151 -1.97%
    BenchmarkDecodeTwainCompress1e5 1537031 1456945 -5.21%
    BenchmarkDecodeTwainCompress1e6 14805972 13405094 -9.46%
    BenchmarkPaeth 4 4 -0.89%
    BenchmarkDecodeGray 964679 937244 -2.84%
    BenchmarkDecodeNRGBAGradient 3753769 3646416 -2.86%
    BenchmarkDecodeNRGBAOpaque 3165856 2981300 -5.83%
    BenchmarkDecodePaletted 713950 691984 -3.08%
    BenchmarkDecodeRGB 3051718 2924260 -4.18%

    R=nigeltao, bradfitz
    CC=golang-dev, raph
    https://codereview.appspot.com/9425046


    https://codereview.appspot.com/9425046/

    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-dev @
categoriesgo
postedMay 17, '13 at 10:16p
activeMay 18, '13 at 10:28p
posts7
users3
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase