FAQ
What's the best way to grow a slice by a given size a priori (when the data
you want to append is not yet available)?

I first wondered when I read go.crypto/nacl/secretbox<https://code.google.com/p/go/source/browse/nacl/secretbox/secretbox.go?repo=crypto&r=30e766a96bf10b896121ceff74b404a65ceecda3&spec=svn.crypto.983a4287662a87c2b0990e5796c5d788bc2608e7#64>,
where out = append(out, 0) is called in a loop.
To me, that seems to be the worst way to do it.

I see two additional ways: append & make and make & copy.
Example: http://play.golang.org/p/PP_RI_WKbJ

The make & copy way is pretty obvious, but it's longer and optimizing it in
the compiler is probably harder.
I prefer the append way, but it allocates a new slice it discards
immediately.

So... append in a loop, make & copy or append & make - or something else?

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

Search Discussions

  • Gerard at Apr 23, 2013 at 2:02 pm
    If the cap of the slice is large enough, then append doesn't allocate new
    memory. See goplay <http://play.golang.org/p/qt8pyb-0e3>


    Op dinsdag 23 april 2013 15:37:26 UTC+2 schreef Arne Hormann het volgende:
    What's the best way to grow a slice by a given size a priori (when the
    data you want to append is not yet available)?

    I first wondered when I read go.crypto/nacl/secretbox<https://code.google.com/p/go/source/browse/nacl/secretbox/secretbox.go?repo=crypto&r=30e766a96bf10b896121ceff74b404a65ceecda3&spec=svn.crypto.983a4287662a87c2b0990e5796c5d788bc2608e7#64>,
    where out = append(out, 0) is called in a loop.
    To me, that seems to be the worst way to do it.

    I see two additional ways: append & make and make & copy.
    Example: http://play.golang.org/p/PP_RI_WKbJ

    The make & copy way is pretty obvious, but it's longer and optimizing it
    in the compiler is probably harder.
    I prefer the append way, but it allocates a new slice it discards
    immediately.

    So... append in a loop, make & copy or append & make - or something else?
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Arne Hormann at Apr 23, 2013 at 2:09 pm
    I know - but that's not always the case. Sometimes I want to start with a
    small slice and only grow it incrementally when needed.
    Coincidentially, that's the scenario I'm interested in.

    Am Dienstag, 23. April 2013 16:02:34 UTC+2 schrieb Gerard:
    If the cap of the slice is large enough, then append doesn't allocate new
    memory. See goplay <http://play.golang.org/p/qt8pyb-0e3>


    Op dinsdag 23 april 2013 15:37:26 UTC+2 schreef Arne Hormann het volgende:
    What's the best way to grow a slice by a given size a priori (when the
    data you want to append is not yet available)?

    I first wondered when I read go.crypto/nacl/secretbox<https://code.google.com/p/go/source/browse/nacl/secretbox/secretbox.go?repo=crypto&r=30e766a96bf10b896121ceff74b404a65ceecda3&spec=svn.crypto.983a4287662a87c2b0990e5796c5d788bc2608e7#64>,
    where out = append(out, 0) is called in a loop.
    To me, that seems to be the worst way to do it.

    I see two additional ways: append & make and make & copy.
    Example: http://play.golang.org/p/PP_RI_WKbJ

    The make & copy way is pretty obvious, but it's longer and optimizing it
    in the compiler is probably harder.
    I prefer the append way, but it allocates a new slice it discards
    immediately.

    So... append in a loop, make & copy or append & make - or something else?
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Maxim Khitrov at Apr 23, 2013 at 2:45 pm
    First, depending on your exact performance requirements, you may be
    better off with a linked list or a slice of slices. That would
    eliminate the extra copy operations.

    If you do need just once slice, you can still use append without
    creating a temporary slice (grow3):

    http://play.golang.org/p/jMGLmaxUTt

    I think this is what secretbox is trying to do. In my benchmarks, this
    version is significantly faster than the other two. It relies on the
    fact that append doubles the slice capacity on each reallocation. It
    might also benefit from a few other optimizations, such as growing the
    array in place if there is sufficient free memory after it.

    Another example is bytes.Buffer, which uses make & copy:

    http://tip.golang.org/src/pkg/bytes/buffer.go#L77
    On Tue, Apr 23, 2013 at 10:09 AM, Arne Hormann wrote:
    I know - but that's not always the case. Sometimes I want to start with a
    small slice and only grow it incrementally when needed.
    Coincidentially, that's the scenario I'm interested in.

    Am Dienstag, 23. April 2013 16:02:34 UTC+2 schrieb Gerard:
    If the cap of the slice is large enough, then append doesn't allocate new
    memory. See goplay


    Op dinsdag 23 april 2013 15:37:26 UTC+2 schreef Arne Hormann het volgende:
    What's the best way to grow a slice by a given size a priori (when the
    data you want to append is not yet available)?

    I first wondered when I read go.crypto/nacl/secretbox, where out =
    append(out, 0) is called in a loop.
    To me, that seems to be the worst way to do it.

    I see two additional ways: append & make and make & copy.
    Example: http://play.golang.org/p/PP_RI_WKbJ

    The make & copy way is pretty obvious, but it's longer and optimizing it
    in the compiler is probably harder.
    I prefer the append way, but it allocates a new slice it discards
    immediately.

    So... append in a loop, make & copy or append & make - or something else?
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Julien Schmidt at Apr 24, 2013 at 1:40 pm
    I tried an approach based on Maxim's grow3:

    Here is the current code (with debug output):
    // grow buffer if necessary
    if need > len(b.buf) {
    fmt.Printf("REFILL len=%d, need=%d \r\n", len(b.buf), need)
    for cap(b.buf) < need {
    b.buf = append(b.buf[:cap(b.buf)], 0)
    fmt.Printf("APPENDED cap=%d \r\n", cap(b.buf))
    }
    b.buf = b.buf[:cap(b.buf)]
    fmt.Printf("END len=%d, need=%d \r\n", len(b.buf), need)
    }
    *need* is the new size we need, *b.buf* is the buffer so *len(b.buf)* is
    the current size.

    Here is the debug output from a test:
    REFILL len=4096, need=1048551
    APPENDED cap=5120
    APPENDED cap=6400
    APPENDED cap=8000
    APPENDED cap=10000
    APPENDED cap=12500
    APPENDED cap=15625
    APPENDED cap=19531
    APPENDED cap=24413
    APPENDED cap=30516
    APPENDED cap=38145
    APPENDED cap=47681
    APPENDED cap=59601
    APPENDED cap=74501
    APPENDED cap=93126
    APPENDED cap=116407
    APPENDED cap=145508
    APPENDED cap=181885
    APPENDED cap=227356
    APPENDED cap=284195
    APPENDED cap=355243
    APPENDED cap=444053
    APPENDED cap=555066
    APPENDED cap=693832
    APPENDED cap=867290
    APPENDED cap=1084112
    END len=1084112, need=1048551

    Any suggestions how this could be optimized?
    On Tuesday, April 23, 2013 4:45:05 PM UTC+2, Maxim Khitrov wrote:

    First, depending on your exact performance requirements, you may be
    better off with a linked list or a slice of slices. That would
    eliminate the extra copy operations.

    If you do need just once slice, you can still use append without
    creating a temporary slice (grow3):

    http://play.golang.org/p/jMGLmaxUTt

    I think this is what secretbox is trying to do. In my benchmarks, this
    version is significantly faster than the other two. It relies on the
    fact that append doubles the slice capacity on each reallocation. It
    might also benefit from a few other optimizations, such as growing the
    array in place if there is sufficient free memory after it.

    Another example is bytes.Buffer, which uses make & copy:

    http://tip.golang.org/src/pkg/bytes/buffer.go#L77
    On Tue, Apr 23, 2013 at 10:09 AM, Arne Hormann wrote:
    I know - but that's not always the case. Sometimes I want to start with a
    small slice and only grow it incrementally when needed.
    Coincidentially, that's the scenario I'm interested in.

    Am Dienstag, 23. April 2013 16:02:34 UTC+2 schrieb Gerard:
    If the cap of the slice is large enough, then append doesn't allocate
    new
    memory. See goplay


    Op dinsdag 23 april 2013 15:37:26 UTC+2 schreef Arne Hormann het
    volgende:
    What's the best way to grow a slice by a given size a priori (when the
    data you want to append is not yet available)?

    I first wondered when I read go.crypto/nacl/secretbox, where out =
    append(out, 0) is called in a loop.
    To me, that seems to be the worst way to do it.

    I see two additional ways: append & make and make & copy.
    Example: http://play.golang.org/p/PP_RI_WKbJ

    The make & copy way is pretty obvious, but it's longer and optimizing
    it
    in the compiler is probably harder.
    I prefer the append way, but it allocates a new slice it discards
    immediately.

    So... append in a loop, make & copy or append & make - or something
    else?
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/groups/opt_out.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Julien Schmidt at Apr 24, 2013 at 1:54 pm
    I'm now tending to use grow2 instead. I'm writing a benchmark now...
    On Wednesday, April 24, 2013 3:40:34 PM UTC+2, Julien Schmidt wrote:

    I tried an approach based on Maxim's grow3:

    Here is the current code (with debug output):
    // grow buffer if necessary
    if need > len(b.buf) {
    fmt.Printf("REFILL len=%d, need=%d \r\n", len(b.buf), need)
    for cap(b.buf) < need {
    b.buf = append(b.buf[:cap(b.buf)], 0)
    fmt.Printf("APPENDED cap=%d \r\n", cap(b.buf))
    }
    b.buf = b.buf[:cap(b.buf)]
    fmt.Printf("END len=%d, need=%d \r\n", len(b.buf), need)
    }
    *need* is the new size we need, *b.buf* is the buffer so *len(b.buf)* is
    the current size.

    Here is the debug output from a test:
    REFILL len=4096, need=1048551
    APPENDED cap=5120
    APPENDED cap=6400
    APPENDED cap=8000
    APPENDED cap=10000
    APPENDED cap=12500
    APPENDED cap=15625
    APPENDED cap=19531
    APPENDED cap=24413
    APPENDED cap=30516
    APPENDED cap=38145
    APPENDED cap=47681
    APPENDED cap=59601
    APPENDED cap=74501
    APPENDED cap=93126
    APPENDED cap=116407
    APPENDED cap=145508
    APPENDED cap=181885
    APPENDED cap=227356
    APPENDED cap=284195
    APPENDED cap=355243
    APPENDED cap=444053
    APPENDED cap=555066
    APPENDED cap=693832
    APPENDED cap=867290
    APPENDED cap=1084112
    END len=1084112, need=1048551

    Any suggestions how this could be optimized?
    On Tuesday, April 23, 2013 4:45:05 PM UTC+2, Maxim Khitrov wrote:

    First, depending on your exact performance requirements, you may be
    better off with a linked list or a slice of slices. That would
    eliminate the extra copy operations.

    If you do need just once slice, you can still use append without
    creating a temporary slice (grow3):

    http://play.golang.org/p/jMGLmaxUTt

    I think this is what secretbox is trying to do. In my benchmarks, this
    version is significantly faster than the other two. It relies on the
    fact that append doubles the slice capacity on each reallocation. It
    might also benefit from a few other optimizations, such as growing the
    array in place if there is sufficient free memory after it.

    Another example is bytes.Buffer, which uses make & copy:

    http://tip.golang.org/src/pkg/bytes/buffer.go#L77

    On Tue, Apr 23, 2013 at 10:09 AM, Arne Hormann <arneh...@gmail.com>
    wrote:
    I know - but that's not always the case. Sometimes I want to start with a
    small slice and only grow it incrementally when needed.
    Coincidentially, that's the scenario I'm interested in.

    Am Dienstag, 23. April 2013 16:02:34 UTC+2 schrieb Gerard:
    If the cap of the slice is large enough, then append doesn't allocate
    new
    memory. See goplay


    Op dinsdag 23 april 2013 15:37:26 UTC+2 schreef Arne Hormann het
    volgende:
    What's the best way to grow a slice by a given size a priori (when
    the
    data you want to append is not yet available)?

    I first wondered when I read go.crypto/nacl/secretbox, where out =
    append(out, 0) is called in a loop.
    To me, that seems to be the worst way to do it.

    I see two additional ways: append & make and make & copy.
    Example: http://play.golang.org/p/PP_RI_WKbJ

    The make & copy way is pretty obvious, but it's longer and optimizing
    it
    in the compiler is probably harder.
    I prefer the append way, but it allocates a new slice it discards
    immediately.

    So... append in a loop, make & copy or append & make - or something
    else?
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts...@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Chris dollin at Apr 24, 2013 at 2:00 pm

    On 24 April 2013 14:40, Julien Schmidt wrote:

    I tried an approach based on Maxim's grow3:

    Here is the current code (with debug output):
    // grow buffer if necessary
    if need > len(b.buf) {
    fmt.Printf("REFILL len=%d, need=%d \r\n", len(b.buf), need)
    for cap(b.buf) < need {
    b.buf = append(b.buf[:cap(b.buf)], 0)
    fmt.Printf("APPENDED cap=%d \r\n", cap(b.buf))
    }
    b.buf = b.buf[:cap(b.buf)]
    fmt.Printf("END len=%d, need=%d \r\n", len(b.buf), need)
    }
    *need* is the new size we need, *b.buf* is the buffer so *len(b.buf)* is
    the current size.

    Here is the debug output from a test:
    ...
    Any suggestions how this could be optimized?
    If you don't know what the elements are, but do know how many you
    need, the grow2() version makes the most sense to me.

    If the allocated size is going to be beig enough, you can
    still add the elements using append() so that len() is not
    misleading.

    Chris

    --
    Chris "allusive" Dollin

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Maxim Khitrov at Apr 24, 2013 at 2:02 pm
    grow3 works well when the extra requested space is less than the
    current capacity. When you need to more than double the existing
    capacity, the make & copy approach is likely to be faster. Here's an
    example:

    http://play.golang.org/p/sLHRRReVvI
    On Wed, Apr 24, 2013 at 9:40 AM, Julien Schmidt wrote:
    I tried an approach based on Maxim's grow3:

    Here is the current code (with debug output):
    // grow buffer if necessary
    if need > len(b.buf) {
    fmt.Printf("REFILL len=%d, need=%d \r\n", len(b.buf), need)
    for cap(b.buf) < need {
    b.buf = append(b.buf[:cap(b.buf)], 0)
    fmt.Printf("APPENDED cap=%d \r\n", cap(b.buf))
    }
    b.buf = b.buf[:cap(b.buf)]
    fmt.Printf("END len=%d, need=%d \r\n", len(b.buf), need)
    }
    need is the new size we need, b.buf is the buffer so len(b.buf) is the
    current size.

    Here is the debug output from a test:
    REFILL len=4096, need=1048551
    APPENDED cap=5120
    APPENDED cap=6400
    APPENDED cap=8000
    APPENDED cap=10000
    APPENDED cap=12500
    APPENDED cap=15625
    APPENDED cap=19531
    APPENDED cap=24413
    APPENDED cap=30516
    APPENDED cap=38145
    APPENDED cap=47681
    APPENDED cap=59601
    APPENDED cap=74501
    APPENDED cap=93126
    APPENDED cap=116407
    APPENDED cap=145508
    APPENDED cap=181885
    APPENDED cap=227356
    APPENDED cap=284195
    APPENDED cap=355243
    APPENDED cap=444053
    APPENDED cap=555066
    APPENDED cap=693832
    APPENDED cap=867290
    APPENDED cap=1084112
    END len=1084112, need=1048551

    Any suggestions how this could be optimized?
    On Tuesday, April 23, 2013 4:45:05 PM UTC+2, Maxim Khitrov wrote:

    First, depending on your exact performance requirements, you may be
    better off with a linked list or a slice of slices. That would
    eliminate the extra copy operations.

    If you do need just once slice, you can still use append without
    creating a temporary slice (grow3):

    http://play.golang.org/p/jMGLmaxUTt

    I think this is what secretbox is trying to do. In my benchmarks, this
    version is significantly faster than the other two. It relies on the
    fact that append doubles the slice capacity on each reallocation. It
    might also benefit from a few other optimizations, such as growing the
    array in place if there is sufficient free memory after it.

    Another example is bytes.Buffer, which uses make & copy:

    http://tip.golang.org/src/pkg/bytes/buffer.go#L77
    On Tue, Apr 23, 2013 at 10:09 AM, Arne Hormann wrote:
    I know - but that's not always the case. Sometimes I want to start with
    a
    small slice and only grow it incrementally when needed.
    Coincidentially, that's the scenario I'm interested in.

    Am Dienstag, 23. April 2013 16:02:34 UTC+2 schrieb Gerard:
    If the cap of the slice is large enough, then append doesn't allocate
    new
    memory. See goplay


    Op dinsdag 23 april 2013 15:37:26 UTC+2 schreef Arne Hormann het
    volgende:
    What's the best way to grow a slice by a given size a priori (when the
    data you want to append is not yet available)?

    I first wondered when I read go.crypto/nacl/secretbox, where out =
    append(out, 0) is called in a loop.
    To me, that seems to be the worst way to do it.

    I see two additional ways: append & make and make & copy.
    Example: http://play.golang.org/p/PP_RI_WKbJ

    The make & copy way is pretty obvious, but it's longer and optimizing
    it
    in the compiler is probably harder.
    I prefer the append way, but it allocates a new slice it discards
    immediately.

    So... append in a loop, make & copy or append & make - or something
    else?
    --
    You received this message because you are subscribed to the Google
    Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send
    an
    email to golang-nuts...@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Julien Schmidt at Apr 24, 2013 at 2:27 pm

    On Wednesday, April 24, 2013 4:02:12 PM UTC+2, Maxim Khitrov wrote:
    grow3 works well when the extra requested space is less than the
    current capacity.
    That was also my impression.

    When you need to more than double the existing
    capacity, the make & copy approach is likely to be faster. Here's an
    example:

    http://play.golang.org/p/sLHRRReVvI
    This looks really nice! I think I'll skip the benchmark and stick to that
    code.

    In the current use-case this code part is not really performance critical.
    It's more a general interest. Maybe I'll write a benchmark some time later
    to find the exact point where append gets more expensive.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Julien Schmidt at Jun 2, 2013 at 1:19 pm
    First of all, the built-in append function has not same characteristics as
    the example Append-function in Go at
    http://golang.org/doc/effective_go.html#slices. You often read, that append
    would double the size when it must reallocate, which is not entirely true.
    The slice is currently growed by factor 1.25 if the size is greater than
    1024: http://code.google.com/p/go/source/browse/src/pkg/runtime/slice.c#208

    Also I decided to run a benchmark. The (heavily copy-pasted)
    source: http://play.golang.org/p/xMWTHiu9JY

    Results:

    System: Intel i5-2500K @ 3.30 GHz, 8192 MB RAM, Windows 7 x64

    PASS
    BenchmarkGrowAppend1 50000 32121 ns/op 10240 B/op 1
    allocs/op
    BenchmarkGrowMake1 50000 32101 ns/op 9471 B/op 1
    allocs/op
    BenchmarkGrowAppend4 50000 32261 ns/op 10240 B/op 1
    allocs/op
    BenchmarkGrowMake4 50000 31961 ns/op 9471 B/op 1
    allocs/op
    BenchmarkGrowAppend64 50000 31721 ns/op 10240 B/op 1
    allocs/op
    BenchmarkGrowMake64 50000 32241 ns/op 9471 B/op 1
    allocs/op
    BenchmarkGrowAppend256 50000 31861 ns/op 10240 B/op 1
    allocs/op
    BenchmarkGrowMake256 50000 31981 ns/op 9471 B/op 1
    allocs/op
    BenchmarkGrowAppend1024 50000 32241 ns/op 10240 B/op 1
    allocs/op
    BenchmarkGrowMake1024 50000 32121 ns/op 10239 B/op 1
    allocs/op
    BenchmarkGrowAppend4096 10000 130507 ns/op 50688 B/op 6
    allocs/op
    BenchmarkGrowMake4096 100000 21841 ns/op 11601 B/op 1
    allocs/op
    BenchmarkGrowAppend16384 10000 264215 ns/op 146688 B/op 12
    allocs/op
    BenchmarkGrowMake16384 1000000 1372 ns/op 20480 B/op 1
    allocs/op
    BenchmarkGrowAppend65536 5000 576232 ns/op 454912 B/op 21
    allocs/op
    BenchmarkGrowMake65536 50000 66623 ns/op 79872 B/op 2
    allocs/op
    BenchmarkGrowAppend262144 2000 1049059 ns/op 1577216 B/op 33
    allocs/op
    BenchmarkGrowMake262144 50000 73044 ns/op 276480 B/op 2
    allocs/op
    ok command-line-arguments 110.262s


    Same system, Linux (Ubuntu 12.04) @ VirtualBox VM with 2048 MB RAM, 2 CPU
    Cores [VT-x/AMD-V, Nested Paging and PAE/NX enabled]

    testing: warning: no tests to run
    PASS
    BenchmarkGrowAppend1 200000 12270 ns/op 5181 B/op 1
    allocs/op
    BenchmarkGrowMake1 500000 7012 ns/op 4352 B/op 1
    allocs/op
    BenchmarkGrowAppend4 100000 16431 ns/op 5242 B/op 1
    allocs/op
    BenchmarkGrowMake4 500000 6958 ns/op 4352 B/op 1
    allocs/op
    BenchmarkGrowAppend64 100000 16332 ns/op 5242 B/op 1
    allocs/op
    BenchmarkGrowMake64 500000 7048 ns/op 4352 B/op 1
    allocs/op
    BenchmarkGrowAppend256 100000 16635 ns/op 5242 B/op 1
    allocs/op
    BenchmarkGrowMake256 500000 7032 ns/op 4352 B/op 1
    allocs/op
    BenchmarkGrowAppend1024 200000 7847 ns/op 5120 B/op 1
    allocs/op
    BenchmarkGrowMake1024 200000 11910 ns/op 5175 B/op 1
    allocs/op
    BenchmarkGrowAppend4096 50000 43127 ns/op 30607 B/op 4
    allocs/op
    BenchmarkGrowMake4096 200000 11180 ns/op 8192 B/op 1
    allocs/op
    BenchmarkGrowAppend16384 50000 70581 ns/op 106342 B/op 8
    allocs/op
    BenchmarkGrowMake16384 200000 12060 ns/op 20480 B/op 1
    allocs/op
    BenchmarkGrowAppend65536 10000 220643 ns/op 371557 B/op 13
    allocs/op
    BenchmarkGrowMake65536 50000 37278 ns/op 70313 B/op 1
    allocs/op
    BenchmarkGrowAppend262144 5000 556190 ns/op 1441009 B/op 20
    allocs/op
    BenchmarkGrowMake262144 50000 59496 ns/op 267776 B/op 1
    allocs/op
    ok command-line-arguments 124.845s

    So the extra case-differentiation currently doesn't make sense. If you know
    that that the underlying array must be reallocated, it is better to use
    just make.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Chris dollin at Apr 23, 2013 at 2:47 pm

    On 23 April 2013 15:09, Arne Hormann wrote:

    I know - but that's not always the case. Sometimes I want to start with a
    small slice and only grow it incrementally when needed.

    The first use of append [1] on a full slice will grow the slice
    *by a multiplicative factor*, so the resulting slice has room
    to append additonal elements.

    Chris


    [1] Well, an append that appends 1 or more items.
    --
    Chris "allusive" Dollin

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Julien Schmidt at Apr 23, 2013 at 2:20 pm
    Assume that the slice / buffer length is always the full capacity.
    On Tuesday, April 23, 2013 4:02:34 PM UTC+2, Gerard wrote:

    If the cap of the slice is large enough, then append doesn't allocate new
    memory. See goplay <http://play.golang.org/p/qt8pyb-0e3>


    Op dinsdag 23 april 2013 15:37:26 UTC+2 schreef Arne Hormann het volgende:
    What's the best way to grow a slice by a given size a priori (when the
    data you want to append is not yet available)?

    I first wondered when I read go.crypto/nacl/secretbox<https://code.google.com/p/go/source/browse/nacl/secretbox/secretbox.go?repo=crypto&r=30e766a96bf10b896121ceff74b404a65ceecda3&spec=svn.crypto.983a4287662a87c2b0990e5796c5d788bc2608e7#64>,
    where out = append(out, 0) is called in a loop.
    To me, that seems to be the worst way to do it.

    I see two additional ways: append & make and make & copy.
    Example: http://play.golang.org/p/PP_RI_WKbJ

    The make & copy way is pretty obvious, but it's longer and optimizing it
    in the compiler is probably harder.
    I prefer the append way, but it allocates a new slice it discards
    immediately.

    So... append in a loop, make & copy or append & make - or something else?
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Arne Hormann at Apr 23, 2013 at 2:30 pm

    From an off-list response:
    What makes you think it discards it [the underlying array] immediately?
    Taken my play example: the slice you have is len == 16, in append you make
    another slice with len == 16. The slice you get is len == 32.
    If there's no free space after the first slice, append has to allocate a
    new slice with len == 32 and copy the contents of the first and second
    slice into it.
    The second slice - the make([]byte, 16) in append - was allocated but
    discarded as it'll never be used. Still, the memory in it was zeroed and
    copied, which is a waste.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Chris dollin at Apr 23, 2013 at 2:55 pm

    On 23 April 2013 15:24, Arne Hormann wrote:

    From an off-list response:
    What makes you think it discards it [the underlying array] immediately?
    Taken my play example: the slice you have is len == 16, in append you make
    another slice with len == 16. The slice you get is len == 32.
    If there's no free space after the first slice, append has to allocate a
    new slice with len == 32 and copy the contents of the first and second
    slice into it.
    The second slice - the make([]byte, 16) in append - was allocated but
    discarded as it'll never be used. Still, the memory in it was zeroed and
    copied, which is a waste.
    Oh, /that/ slice, the second argument slice for append. SIlly of me: I was
    focussed on the first argument / result slice.

    But why make the slice bigger with irrelevant values (the "wasted zeroes")
    rather than the values you want to append to it?

    [Note that this is a place where escape analysis could spot that the
    second argument slice need not be heap allocated, and the zeroing
    and copying is pretty much a given if you're going to make a slice
    bigger ...]

    Chris

    --
    Chris "allusive" Dollin

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Arne Hormann at Apr 23, 2013 at 3:14 pm

    Am Dienstag, 23. April 2013 16:55:20 UTC+2 schrieb chris dollin:
    On 23 April 2013 15:24, Arne Hormann <arneh...@gmail.com <javascript:>>wrote:
    From an off-list response:
    What makes you think it discards it [the underlying array] immediately?
    Taken my play example: the slice you have is len == 16, in append you
    make another slice with len == 16. The slice you get is len == 32.
    If there's no free space after the first slice, append has to allocate a
    new slice with len == 32 and copy the contents of the first and second
    slice into it.
    The second slice - the make([]byte, 16) in append - was allocated but
    discarded as it'll never be used. Still, the memory in it was zeroed and
    copied, which is a waste.
    Oh, /that/ slice, the second argument slice for append. SIlly of me: I was
    focussed on the first argument / result slice.

    But why make the slice bigger with irrelevant values (the "wasted zeroes")
    rather than the values you want to append to it?
    This originally came up during a review of the go-sql-driver/mysql zero
    copy buffer <https://github.com/go-sql-driver/mysql/pull/55>. I don't know
    the values before they are read.
    It's hard to know before how large the largest column ever fetched will be
    - doubling the buffer size is probably fine, but it should allocate as
    little memory as possible and not allocate in more than step.
    Speed is probably more important than memory (Julien's call), so I guess
    append for doubling will be the way to go.
    I just want to make sure the implementation uses the best way to do it.

    [Note that this is a place where escape analysis could spot that the
    second argument slice need not be heap allocated, and the zeroing
    and copying is pretty much a given if you're going to make a slice
    bigger ...]
    That's exactly what I meant when I wrote copy & make is probably harder to
    optimize - the make-case for append should be pretty easy.

    >

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Roger peppe at Apr 23, 2013 at 5:04 pm
    I'd do something like this:


    // grow returns a slice with the same contents as slice
    // but with a capacity at least as large as newCap.
    func grow(slice []byte, newCap int) []byte {
         if cap(slice) >= newCap {
             return slice
         }
         newSlice := make([]byte, len(slice), newCap)
         copy(newSlice, slice)
         return newSlice
    }


    On 23 April 2013 16:14, Arne Hormann wrote:


    Am Dienstag, 23. April 2013 16:55:20 UTC+2 schrieb chris dollin:
    On 23 April 2013 15:24, Arne Hormann wrote:

    From an off-list response:
    What makes you think it discards it [the underlying array] immediately?
    Taken my play example: the slice you have is len == 16, in append you
    make another slice with len == 16. The slice you get is len == 32.
    If there's no free space after the first slice, append has to allocate a
    new slice with len == 32 and copy the contents of the first and second slice
    into it.
    The second slice - the make([]byte, 16) in append - was allocated but
    discarded as it'll never be used. Still, the memory in it was zeroed and
    copied, which is a waste.

    Oh, /that/ slice, the second argument slice for append. SIlly of me: I was
    focussed on the first argument / result slice.

    But why make the slice bigger with irrelevant values (the "wasted zeroes")
    rather than the values you want to append to it?

    This originally came up during a review of the go-sql-driver/mysql zero copy
    buffer. I don't know the values before they are read.
    It's hard to know before how large the largest column ever fetched will be -
    doubling the buffer size is probably fine, but it should allocate as little
    memory as possible and not allocate in more than step.
    Speed is probably more important than memory (Julien's call), so I guess
    append for doubling will be the way to go.
    I just want to make sure the implementation uses the best way to do it.
    [Note that this is a place where escape analysis could spot that the
    second argument slice need not be heap allocated, and the zeroing
    and copying is pretty much a given if you're going to make a slice
    bigger ...]

    That's exactly what I meant when I wrote copy & make is probably harder to
    optimize - the make-case for append should be pretty easy.

    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Gerard at Apr 24, 2013 at 7:56 am
    Thinking about it once more, I would like to mention two things:

        1. I think that clear code is more important than micro-optimisation,
        especially with todays processor power.
        2. If you really want to know the answer, perform benchmark tests (with
        actual data and 32/64 bit environment and Go1.1).

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Hotei at Apr 24, 2013 at 1:57 pm
    There's nothing magic about the append function. If the current append
    doesn't suit your purpose it's trivial to write your own and have it grow
    your slices by whatever increment percentage you want, including a sliding
    scale percentage if that's useful.
    On Tuesday, April 23, 2013 9:37:26 AM UTC-4, Arne Hormann wrote:

    What's the best way to grow a slice by a given size a priori (when the
    data you want to append is not yet available)?

    I first wondered when I read go.crypto/nacl/secretbox<https://code.google.com/p/go/source/browse/nacl/secretbox/secretbox.go?repo=crypto&r=30e766a96bf10b896121ceff74b404a65ceecda3&spec=svn.crypto.983a4287662a87c2b0990e5796c5d788bc2608e7#64>,
    where out = append(out, 0) is called in a loop.
    To me, that seems to be the worst way to do it.

    I see two additional ways: append & make and make & copy.
    Example: http://play.golang.org/p/PP_RI_WKbJ

    The make & copy way is pretty obvious, but it's longer and optimizing it
    in the compiler is probably harder.
    I prefer the append way, but it allocates a new slice it discards
    immediately.

    So... append in a loop, make & copy or append & make - or something else?
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Chris dollin at Apr 24, 2013 at 2:01 pm

    On 24 April 2013 14:57, Hotei wrote:

    There's nothing magic about the append function.

    Apart from its polymorphic type.

    Chris

    --
    Chris "polymorph self" Dollin

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

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedApr 23, '13 at 1:42p
activeJun 2, '13 at 1:19p
posts19
users7
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase