code review 14419054: spec: clarify re-use of underlying arrays in slice oper...

spec: clarify re-use of underlying arrays in slice operations

Please note the slight rewording for append: The spec now
requires that append reuses the underlying array if it is
sufficiently large. Per majority sentiment.

This is technically a language change but the current
implementation always worked this way.

Fixes issue 5818.
Fixes issue 5180.

[gri, 2013-10-09 22:54:39]

Hello rsc@golang.org, iant@golang.org, r@golang.org, ken@golang.org (cc:
golang-dev@googlegroups.com),

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

[r, 2013-10-09 23:00:25]

LGTM but wait for others

https://codereview.appspot.com/14419054/diff/6001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/6001/doc/go_spec.html#newcode5356
doc/go_spec.html:5356: The resulting slice may refer to a different underlying
array then <code>s</code>.
s/then/than/

[gri, 2013-10-09 23:05:24]

PTAL

https://codereview.appspot.com/14419054/diff/6001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/6001/doc/go_spec.html#newcode5356
doc/go_spec.html:5356: The resulting slice may refer to a different underlying
array then <code>s</code>.
On 2013/10/09 23:00:26, r wrote:
> s/then/than/

Done.

[iant, 2013-10-10 00:00:43]

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html#newcode893
doc/go_spec.html:893: it, so these two examples result in the same slice:
This sounds weird to me.  They don't actually result in the *same* *slice*. 
Both operations allocate an array and then slice it and the result is in some
sense equivalent but the slices are not the same.

[minux1, 2013-10-10 00:41:30]

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html#newcode5356
doc/go_spec.html:5356: The resulting slice may refer to a different underlying
array than <code>s</code>.
i don't understand why we remove the implementation restriction.
why allocate a new backing array and copy all the data instead of reuse
a sufficiently large original backing array?

i think it's a Go idiom to pre-allocate a backing array for a slice, and
then append to it in a loop.

Removing the restriction makes this idiom very inefficient (instead of
allocating O(N) memory, it might allocate up to O(N^2) memory, not to
mention the excessive copying overhead incurred during the process.)

Am I missing something?

[gri, 2013-10-10 00:54:10]

PTAL

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html#newcode893
doc/go_spec.html:893: it, so these two examples result in the same slice:
On 2013/10/10 00:00:43, iant wrote:
> This sounds weird to me.  They don't actually result in the *same* *slice*. 
> Both operations allocate an array and then slice it and the result is in some
> sense equivalent but the slices are not the same.

This was old language, existed before. I had noticed it and planned to change
it, but then forgot.

Fixed.

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html#newcode5356
doc/go_spec.html:5356: The resulting slice may refer to a different underlying
array than <code>s</code>.
On 2013/10/10 00:41:30, minux wrote:
> i don't understand why we remove the implementation restriction.
> why allocate a new backing array and copy all the data instead of reuse
> a sufficiently large original backing array?
> 
> i think it's a Go idiom to pre-allocate a backing array for a slice, and
> then append to it in a loop.
> 
> Removing the restriction makes this idiom very inefficient (instead of
> allocating O(N) memory, it might allocate up to O(N^2) memory, not to
> mention the excessive copying overhead incurred during the process.)
> 
> Am I missing something?

This is _not_ removing an implementation restriction (nowhere does it say
"implementation restriction"...).

Also, we have never required this. The resulting slice _may_ refer to a
different underlying array, but doesn't have to - the word "may" is crucial
here.

I don't think we want to _require_ that the underlying array be re-used. Code
that explicitly relies on this feature must know that the slice is large enough
before calling append (otherwise the code couldn't rely on it). Thus, that code
can always be written w/o the use of append (explicit indexing into existing
slice or use of copy).

[iant, 2013-10-10 00:58:40]

On 2013/10/10 00:41:30, minux wrote:

> >
https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html#newcode5356
> > doc/go_spec.html:5356: The resulting slice may refer to a different
underlying
> > array than <code>s</code>.
> i don't understand why we remove the implementation restriction.
> why allocate a new backing array and copy all the data instead of reuse
> a sufficiently large original backing array?
> 
> i think it's a Go idiom to pre-allocate a backing array for a slice, and
> then append to it in a loop.
> 
> Removing the restriction makes this idiom very inefficient (instead of
> allocating O(N) memory, it might allocate up to O(N^2) memory, not to
> mention the excessive copying overhead incurred during the process.)
> 
> Am I missing something?

I don't think we are actually changing anything in the spec.  If we are changing
something, then what we are changing is a requirement that the implementation
always reuse the existing backing array if there is space.  Of course in most
cases the implementation will reuse the existing array, and of course it will
always be the case that appending in a loop will be efficient.  But for example
if you write
    a := make([]byte, 0, 1)
    a = append(a, 'b')
then I think it is OK if the implementation guesses that more append calls are
coming and preemptively creates a new, larger, backing array.

[iant, 2013-10-10 00:59:12]

LGTM

[minux1, 2013-10-10 01:04:21]

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html#newcode5356
doc/go_spec.html:5356: The resulting slice may refer to a different underlying
array than <code>s</code>.
On 2013/10/10 00:54:10, gri wrote:
> I don't think we want to _require_ that the underlying array be re-used. Code
> that explicitly relies on this feature must know that the slice is large
enough
> before calling append (otherwise the code couldn't rely on it). Thus, that
code
> can always be written w/o the use of append (explicit indexing into existing
> slice or use of copy).
yes, the code that relies on append reusing the array could be rewritten.
but my point is the loop append idiom is sufficient widespread, we probably
shouldn't loose the requirement here.

also, consider what if you don't know exactly the amount of storage to be used,
now we can determine a typical value, say, N, and preallocate a slice with cap
N, and then do a loop append.

if we change to don't rely on this restriction, the loop will be more
complicated, as it has to keep track of cap(s) and len(s), and use simple
indexing assignment or append depends on the order of len(s) and cap(s).

Is there any optimization opportunity that will be missed when we enforce the
array reuse implementation restriction?

PS: ok, i chose the wrong word. it's not implementation restriction. but the
original wording does imply to reuse the storage if it's enough. so this change
actually removes that implication.

[minux1, 2013-10-10 01:13:36]

On Wed, Oct 9, 2013 at 8:58 PM, <iant@golang.org> wrote:

> I don't think we are actually changing anything in the spec.  If we are
> changing something, then what we are changing is a requirement that the
> implementation always reuse the existing backing array if there is
> space.  Of course in most cases the implementation will reuse the
> existing array, and of course it will always be the case that appending
> in a loop will be efficient.  But for example if you write
>     a := make([]byte, 0, 1)
>     a = append(a, 'b')
> then I think it is OK if the implementation guesses that more append
> calls are coming and preemptively creates a new, larger, backing array.
>
i expect this to be a surprise to the programmer, i've allocated enough
space, why allocate more?

if there are further appends to a, then this optimization of course is
plausible, but if written as is, i'd rather make a use the available space.

could we do some experiments before this change?
let's modify the runtime to do optimization like this, and see if there are
real world breakages?

to me, this change does remove one (however implicit) guarantee, and
thus goes against the Go 1 stability guarantee.

just my 2 cents.

[gri, 2013-10-10 01:14:22]

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/12001/doc/go_spec.html#newcode5356
doc/go_spec.html:5356: The resulting slice may refer to a different underlying
array than <code>s</code>.
On 2013/10/10 01:04:21, minux wrote:
> On 2013/10/10 00:54:10, gri wrote:
> > I don't think we want to _require_ that the underlying array be re-used.
Code
> > that explicitly relies on this feature must know that the slice is large
> enough
> > before calling append (otherwise the code couldn't rely on it). Thus, that
> code
> > can always be written w/o the use of append (explicit indexing into existing
> > slice or use of copy).
> yes, the code that relies on append reusing the array could be rewritten.
> but my point is the loop append idiom is sufficient widespread, we probably
> shouldn't loose the requirement here.
> 
> also, consider what if you don't know exactly the amount of storage to be
used,
> now we can determine a typical value, say, N, and preallocate a slice with cap
> N, and then do a loop append.
> 
> if we change to don't rely on this restriction, the loop will be more
> complicated, as it has to keep track of cap(s) and len(s), and use simple
> indexing assignment or append depends on the order of len(s) and cap(s).
> 
> Is there any optimization opportunity that will be missed when we enforce the
> array reuse implementation restriction?
> 
> PS: ok, i chose the wrong word. it's not implementation restriction. but the
> original wording does imply to reuse the storage if it's enough. so this
change
> actually removes that implication.

Sorry, I didn't mean to be facetious.

I still maintain that we do not want to _require_ this. Of course, a sensible
implementation will use the underlying array. Note that the previous wording
didn't say re-use is required. Is was unclear.

The new wording does not require it either, but it clear about it.

Making it a requirement would be a change to the spec. That's ok, but that's not
the intent of this CL.

[minux1, 2013-10-10 01:21:47]

On Wed, Oct 9, 2013 at 9:14 PM, <gri@golang.org> wrote:

> sensible implementation will use the underlying array. Note that the
> previous wording didn't say re-use is required. Is was unclear.
>
> The new wording does not require it either, but it clear about it.


> Making it a requirement would be a change to the spec. That's ok, but
> that's not the intent of this CL.
>
ok, i see. making the spec more clear is the way to go. I just pose the
question
as clearly i read something unintended from the spec, and i wonder if others
are also get the same.

[kortschak, 2013-10-10 01:45:59]

https://codereview.appspot.com/14419054/diff/13001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/13001/doc/go_spec.html#newcode5357
doc/go_spec.html:5357: For instance, if the capacity of <code>s</code> is not
large enough to fit the additional
I don't think this yet addresses the concern raised in Issue 5180. It would if
s/For instance, if/For instance, iff/ though. I know that you have addresses
this in that issue, but like minux, I think the idiom depending on this
behaviour is very widely used and probably expected by most gophers.

[gri, 2013-10-10 05:35:56]

https://codereview.appspot.com/14419054/diff/13001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/13001/doc/go_spec.html#newcode5357
doc/go_spec.html:5357: For instance, if the capacity of <code>s</code> is not
large enough to fit the additional
On 2013/10/10 01:45:59, kortschak wrote:
> I don't think this yet addresses the concern raised in Issue 5180. It would if
> s/For instance, if/For instance, iff/ though. I know that you have addresses
> this in that issue, but like minux, I think the idiom depending on this
> behaviour is very widely used and probably expected by most gophers.

The spec should not prescribe a specific implementation if not absolutely
necessary, hence the _may_. Of course any sensible implementation _will_ (at the
moment) reuse the underlying array if there's enough capacity since that is
(usually) the most efficient approach. Furthermore, it's a very straight-forward
approach, which is another reason why there's no need to prescribe it (it's a
different story if it were difficult to achieve with so much code that relies on
it for efficiency - we don't have that case).

It's important that it's not prescribed, though. Here's a (admittedly somewhat
contrived, but illustrative) example why: A future smarter compiler might
optimize the statement

copy(dst, append(src, x))

such that the generated code directly copies the result of append(src, x) into
dst, _without_ storing that intermediate result in the underlying array of src,
even if there would be enough space for it. If we require append to _always_
reuse the underlying array independent of context, we give up this optimization
(and others that we might not be thinking about now). We don't want to restrict
implementations this way.

Furthermore, code that _does_ rely on the result of append reusing the
underlying array if there's enough space should be explicit about it by not
using append in these cases. That code _must_ know that space is available and
so _can_ use easy alternatives to append (say, copy).

In short, requiring re-use when possible is a mistake. Any sensible
implementation should be free to choose the best possible approach.

[rog, 2013-10-10 10:04:28]

I appreciate the arguments for keeping this undefined, but I
couldn't guarantee that I haven't written some code along
these kinds of lines in the past:

For example, I might easily write this, and I doubt
I'd have called it out in a code review:

// fill populates the given slice with values from the given map. The
// slice and the map are of the same length.
func fill(xs []int, m map[string]int) {
    xs := xs[:0]
    for _, x := range m {
        xs = append(xs, x)
    }
}

rather than this:

func fill(xs []int, m map[string]int) {
    i := 0
    for _, x := range m {
        xs[i] = x
        i++
    }
}

If a compiler *were* to implement different behaviour in
this respect, I suspect it could lead to some very subtle
breakages. I'd prefer to have it defined, even if it
leads to some potential inefficiencies in the future.

The copy(dst, append(src, x)) optimisation will still be
possible in some circumstances, I think.

On 10 October 2013 06:35,  <gri@golang.org> wrote:
>
> https://codereview.appspot.com/14419054/diff/13001/doc/go_spec.html
> File doc/go_spec.html (right):
>
>
https://codereview.appspot.com/14419054/diff/13001/doc/go_spec.html#newcode5357
> doc/go_spec.html:5357: For instance, if the capacity of <code>s</code>
> is not large enough to fit the additional
> On 2013/10/10 01:45:59, kortschak wrote:
>>
>> I don't think this yet addresses the concern raised in Issue 5180. It
>
> would if
>>
>> s/For instance, if/For instance, iff/ though. I know that you have
>
> addresses
>>
>> this in that issue, but like minux, I think the idiom depending on
>
> this
>>
>> behaviour is very widely used and probably expected by most gophers.
>
>
> The spec should not prescribe a specific implementation if not
> absolutely necessary, hence the _may_. Of course any sensible
> implementation _will_ (at the moment) reuse the underlying array if
> there's enough capacity since that is (usually) the most efficient
> approach. Furthermore, it's a very straight-forward approach, which is
> another reason why there's no need to prescribe it (it's a different
> story if it were difficult to achieve with so much code that relies on
> it for efficiency - we don't have that case).
>
> It's important that it's not prescribed, though. Here's a (admittedly
> somewhat contrived, but illustrative) example why: A future smarter
> compiler might optimize the statement
>
> copy(dst, append(src, x))
>
> such that the generated code directly copies the result of append(src,
> x) into dst, _without_ storing that intermediate result in the
> underlying array of src, even if there would be enough space for it. If
> we require append to _always_ reuse the underlying array independent of
> context, we give up this optimization (and others that we might not be
> thinking about now). We don't want to restrict implementations this way.
>
> Furthermore, code that _does_ rely on the result of append reusing the
> underlying array if there's enough space should be explicit about it by
> not using append in these cases. That code _must_ know that space is
> available and so _can_ use easy alternatives to append (say, copy).
>
> In short, requiring re-use when possible is a mistake. Any sensible
> implementation should be free to choose the best possible approach.
>
>
> https://codereview.appspot.com/14419054/
>
> --
>
> ---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.

[gri, 2013-10-10 16:25:08]

I'd argue that the fill function should return the filled slice. The
comment does say that the slice and map are of the same length (capacity
rather, for the slice), but there's no check in that code that that's true.
So this may have silently failed if there's a bug elsewhere.

Once you add the respective checks to the code, it becomes easier to not
rely on it.

The purpose of this CL is make it clearer that something that happens to be
true for some implementations shouldn't be relied on in the first place. I
think once that's become part of the mindset when operating with append,
code like this is more likely to raise eyebrows.

- gri


On Thu, Oct 10, 2013 at 3:04 AM, roger peppe <rogpeppe@gmail.com> wrote:

> I appreciate the arguments for keeping this undefined, but I
> couldn't guarantee that I haven't written some code along
> these kinds of lines in the past:
>
> For example, I might easily write this, and I doubt
> I'd have called it out in a code review:
>
> // fill populates the given slice with values from the given map. The
> // slice and the map are of the same length.
> func fill(xs []int, m map[string]int) {
>     xs := xs[:0]
>     for _, x := range m {
>         xs = append(xs, x)
>     }
> }
>
> rather than this:
>
> func fill(xs []int, m map[string]int) {
>     i := 0
>     for _, x := range m {
>         xs[i] = x
>         i++
>     }
> }
>
> If a compiler *were* to implement different behaviour in
> this respect, I suspect it could lead to some very subtle
> breakages. I'd prefer to have it defined, even if it
> leads to some potential inefficiencies in the future.
>
> The copy(dst, append(src, x)) optimisation will still be
> possible in some circumstances, I think.
>
> On 10 October 2013 06:35,  <gri@golang.org> wrote:
> >
> > https://codereview.appspot.com/14419054/diff/13001/doc/go_spec.html
> > File doc/go_spec.html (right):
> >
> >
>
https://codereview.appspot.com/14419054/diff/13001/doc/go_spec.html#newcode5357
> > doc/go_spec.html:5357: For instance, if the capacity of <code>s</code>
> > is not large enough to fit the additional
> > On 2013/10/10 01:45:59, kortschak wrote:
> >>
> >> I don't think this yet addresses the concern raised in Issue 5180. It
> >
> > would if
> >>
> >> s/For instance, if/For instance, iff/ though. I know that you have
> >
> > addresses
> >>
> >> this in that issue, but like minux, I think the idiom depending on
> >
> > this
> >>
> >> behaviour is very widely used and probably expected by most gophers.
> >
> >
> > The spec should not prescribe a specific implementation if not
> > absolutely necessary, hence the _may_. Of course any sensible
> > implementation _will_ (at the moment) reuse the underlying array if
> > there's enough capacity since that is (usually) the most efficient
> > approach. Furthermore, it's a very straight-forward approach, which is
> > another reason why there's no need to prescribe it (it's a different
> > story if it were difficult to achieve with so much code that relies on
> > it for efficiency - we don't have that case).
> >
> > It's important that it's not prescribed, though. Here's a (admittedly
> > somewhat contrived, but illustrative) example why: A future smarter
> > compiler might optimize the statement
> >
> > copy(dst, append(src, x))
> >
> > such that the generated code directly copies the result of append(src,
> > x) into dst, _without_ storing that intermediate result in the
> > underlying array of src, even if there would be enough space for it. If
> > we require append to _always_ reuse the underlying array independent of
> > context, we give up this optimization (and others that we might not be
> > thinking about now). We don't want to restrict implementations this way.
> >
> > Furthermore, code that _does_ rely on the result of append reusing the
> > underlying array if there's enough space should be explicit about it by
> > not using append in these cases. That code _must_ know that space is
> > available and so _can_ use easy alternatives to append (say, copy).
> >
> > In short, requiring re-use when possible is a mistake. Any sensible
> > implementation should be free to choose the best possible approach.
> >
> >
> > https://codereview.appspot.com/14419054/
> >
> > --
> >
> > ---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.
>

[rog, 2013-10-10 18:42:38]

On 10 October 2013 17:25, Robert Griesemer <gri@golang.org> wrote:
> I'd argue that the fill function should return the filled slice. The comment
> does say that the slice and map are of the same length (capacity rather, for
> the slice), but there's no check in that code that that's true. So this may
> have silently failed if there's a bug elsewhere.

I agree that the fill function should return the filled slice (and
I would almost certainly write it that way).

But I can't guarantee that something like this code doesn't exist
in the wild, so I'm worried that changing something this fundamental
will probably break existing code in subtle and hard to diagnose
ways, something that would be hard to countenance, given the
usual Go compatibility guarantees.

> The purpose of this CL is make it clearer that something that happens to be
> true for some implementations shouldn't be relied on in the first place. I
> think once that's become part of the mindset when operating with append,
> code like this is more likely to raise eyebrows.

Isn't it a bit late for that?

[rsc, 2013-10-10 18:50:43]

FWIW I agree with Minux and Roger: we should define (if we haven't already)
that append only reallocates when there was not enough capacity in the
original slice.

[peterGo, 2013-10-10 19:16:23]

As a practical matter, it's important for Go performance to minimize 
allocations. For slices, it often helps to make reasonable capacity 
estimates. For example,

package main

import "fmt"

func main() {
    estimate, actual := 50, 42
    a := make([]int, 0, estimate)
    for i := 0; i < actual; i++ {
        a = append(a, 42)
    }
    fmt.Println(len(a), cap(a))
}

Output:

42 50

The append function should only reallocate the underlying array if the 
capacity is insufficient.

Peter

On Wednesday, October 9, 2013 6:54:40 PM UTC-4, gri wrote:
>
> Reviewers: rsc, iant, r, ken2, 
>
> Message: 
> Hello r...@golang.org <javascript:>, ia...@golang.org <javascript:>, 
> r...@golang.org <javascript:>, k...@golang.org <javascript:> (cc: 
> golan...@googlegroups.com <javascript:>), 
>
> I'd like you to review this change to 
> https://code.google.com/p/go 
>
>
> Description: 
> spec: clarify re-use of underlying arrays in slice operations 
>
> Documents the status quo; not a language change. That said, 
> please note the slight rewording for append, where the old 
> language (almost) implied that the underlying array is shared 
> if large enough. The slight rewording makes it clear that we 
> do not require that property. 
>
> Fixes issue 5818. 
>
> Please review this at https://codereview.appspot.com/14419054/ 
>
> Affected files (+17, -24 lines): 
>    M doc/go_spec.html 
>
>
> Index: doc/go_spec.html 
> =================================================================== 
> --- a/doc/go_spec.html 
> +++ b/doc/go_spec.html 
> @@ -1,6 +1,6 @@ 
>   <!--{ 
>           "Title": "The Go Programming Language Specification", 
> -        "Subtitle": "Version of Oct 7, 2013", 
> +        "Subtitle": "Version of Oct 9, 2013", 
>           "Path": "/ref/spec" 
>   }--> 
>
> @@ -839,7 +839,7 @@ 
>   <h3 id="Slice_types">Slice types</h3> 
>
>   <p> 
> -A slice is a descriptor for a contiguous segment of an array and 
> +A slice is a descriptor for a contiguous segment of an <i>underlying   
> array</i> and 
>   provides access to a numbered sequence of elements from that array. 
>   A slice type denotes the set of all slices of arrays of its element 
> type. 
>   The value of an uninitialized slice is <code>nil</code>. 
> @@ -879,26 +879,18 @@ 
>   made using the built-in function 
>   <a href="#Making_slices_maps_and_channels"><code>make</code></a>, 
>   which takes a slice type 
> -and parameters specifying the length and optionally the capacity: 
> -</p> 
> - 
> -<pre> 
> -make([]T, length) 
> +and parameters specifying the length and optionally the capacity. 
> +A slice created with <code>make</code> always allocates a new, hidden 
> array 
> +to which the returned slice value refers. That is, executing 
> +</p> 
> + 
> +<pre> 
>   make([]T, length, capacity) 
>   </pre> 
>
>   <p> 
> -A call to <code>make</code> allocates a new, hidden array to which the   
> returned 
> -slice value refers. That is, executing 
> -</p> 
> - 
> -<pre> 
> -make([]T, length, capacity) 
> -</pre> 
> - 
> -<p> 
> -produces the same slice as allocating an array and slicing it, so these   
> two examples 
> -result in the same slice: 
> +produces the same slice as allocating an array and <a   
> href="#Slice_expressions">slicing</a> 
> +it, so these two examples result in the same slice: 
>   </p> 
>
>   <pre> 
> @@ -910,8 +902,8 @@ 
>   Like arrays, slices are always one-dimensional but may be composed to   
> construct 
>   higher-dimensional objects. 
>   With arrays of arrays, the inner arrays are, by construction, always the 
>   
> same length; 
> -however with slices of slices (or arrays of slices), the lengths may vary 
>   
> dynamically. 
> -Moreover, the inner slices must be allocated individually (with   
> <code>make</code>). 
> +however with slices of slices (or arrays of slices), the inner lengths 
> may   
> vary dynamically. 
> +Moreover, the inner slices must be initialized individually. 
>   </p> 
>
>   <h3 id="Struct_types">Struct types</h3> 
> @@ -2707,7 +2699,8 @@ 
>
>   <p> 
>   If the sliced operand of a valid slice expression is a <code>nil</code> 
>   
> slice, the result 
> -is a <code>nil</code> slice. 
> +is a <code>nil</code> slice. Otherwise, the result shares its underlying 
>   
> array with the 
> +operand. 
>   </p> 
>
>   <h4>Full slice expressions</h4> 
> @@ -5360,10 +5353,10 @@ 
>   </pre> 
>
>   <p> 
> -If the capacity of <code>s</code> is not large enough to fit the 
> additional 
> +The resulting slice may refer to a different underlying array then   
> <code>s</code>. 
> +For instance, if the capacity of <code>s</code> is not large enough to 
> fit   
> the additional 
>   values, <code>append</code> allocates a new, sufficiently large slice 
> that   
> fits 
> -both the existing slice elements and the additional values. Thus, the   
> returned 
> -slice may refer to a different underlying array. 
> +both the existing slice elements and the additional values. 
>   </p> 
>
>   <pre> 
>
>
>

[gri, 2013-10-11 21:37:17]

Any other input? r? iant?

I remain unconvinced that defining that append must re-use the underlying
array if there's enough space is the right thing to do (the spec never said
it is required and good code shouldn't rely on undocumented features).

But I'll bow to overarching sentiment if everybody agrees (after all, we
cannot simply shutdown this place...).

- gri


On Thu, Oct 10, 2013 at 11:50 AM, Russ Cox <rsc@golang.org> wrote:

> FWIW I agree with Minux and Roger: we should define (if we haven't
> already) that append only reallocates when there was not enough capacity in
> the original slice.
>
>

[kortschak, 2013-10-13 22:39:20]

On 2013/10/11 21:37:17, gri wrote:
> Any other input? r? iant?
> 
> I remain unconvinced that defining that append must re-use the underlying
> array if there's enough space is the right thing to do (the spec never said
> it is required and good code shouldn't rely on undocumented features).
> 
> But I'll bow to overarching sentiment if everybody agrees (after all, we
> cannot simply shutdown this place...).
> 
> - gri

Is there are simple way to specify that it might not re-use if the the non-reuse
is not observable, for example in your example above, 'copy(dst, append(src,
x))'?

[gri, 2013-10-14 18:14:43]

On 2013/10/13 22:39:20, kortschak wrote:
> On 2013/10/11 21:37:17, gri wrote:
> > Any other input? r? iant?
> > 
> > I remain unconvinced that defining that append must re-use the underlying
> > array if there's enough space is the right thing to do (the spec never said
> > it is required and good code shouldn't rely on undocumented features).
> > 
> > But I'll bow to overarching sentiment if everybody agrees (after all, we
> > cannot simply shutdown this place...).
> > 
> > - gri
> 
> Is there are simple way to specify that it might not re-use if the the
non-reuse
> is not observable, for example in your example above, 'copy(dst, append(src,
> x))'?

In the example given, the re-use _is_ observable if the spec says so (the
underlying array of src would be changed as a result of the append). That's
exactly the point. If the re-use is not observable, the compiler is already free
to optimize within the confines of the spec.

[gri, 2013-10-16 00:26:17]

Hello rsc@golang.org, iant@golang.org, r@golang.org, ken@golang.org,
minux.ma@gmail.com, dan.kortschak@adelaide.edu.au, rogpeppe@gmail.com,
go.peter.90@gmail.com (cc: golang-dev@googlegroups.com),

Please take another look.

[gri, 2013-10-16 00:30:36]

FYI: This is now rephrasing the contentious bit in append: It leaves what
was there before but now makes it mandatory for append to reuse the
underlying array if it is large enough. Per majority sentiment.
- gri


On Tue, Oct 15, 2013 at 5:26 PM, <gri@golang.org> wrote:

> Hello rsc@golang.org, iant@golang.org, r@golang.org, ken@golang.org,
> minux.ma@gmail.com, dan.kortschak@adelaide.edu.au, rogpeppe@gmail.com,
> go.peter.90@gmail.com (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
>
https://codereview.appspot.**com/14419054/<https://codereview.appspot.com/144...
>

[minux1, 2013-10-16 00:36:15]

thank you. LGTM.

[r, 2013-10-16 22:51:26]

LGTM

[iant, 2013-10-16 22:57:52]

LGTM

https://codereview.appspot.com/14419054/diff/22001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/22001/doc/go_spec.html#newcode5358
doc/go_spec.html:5358: array that fits both the existing slice elements and the
additional values.
In the case where a new array is allocated, are we going to say anything about
what happens to the old array?  That is, is the old array guaranteed to be
unchanged in that case?

[gri, 2013-10-16 23:09:15]

https://codereview.appspot.com/14419054/diff/22001/doc/go_spec.html
File doc/go_spec.html (right):

https://codereview.appspot.com/14419054/diff/22001/doc/go_spec.html#newcode5358
doc/go_spec.html:5358: array that fits both the existing slice elements and the
additional values.
On 2013/10/16 22:57:52, iant wrote:
> In the case where a new array is allocated, are we going to say anything about
> what happens to the old array?  That is, is the old array guaranteed to be
> unchanged in that case?

I was trying to avoid that.

If people rely on that, they should write their own append.

[rsc, 2013-10-16 23:15:47]

LGTM

[gri, 2013-10-16 23:16:58]

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

spec: clarify re-use of underlying arrays in slice operations

Please note the slight rewording for append: The spec now
requires that append reuses the underlying array if it is
sufficiently large. Per majority sentiment.

This is technically a language change but the current
implementation always worked this way.

Fixes issue 5818.
Fixes issue 5180.

R=rsc, iant, r, ken, minux.ma, dan.kortschak, rogpeppe, go.peter.90
CC=golang-dev
https://codereview.appspot.com/14419054