[golang-dev] code review 14419054: spec: clarify re-use of underlying arrays in slice oper... (issue 14419054)

On Wed, Oct 9, 2013 at 8:58 PM, 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.

On Wed, Oct 9, 2013 at 9:14 PM, 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.

On 10 October 2013 06:35, 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

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.

On Thu, Oct 10, 2013 at 3:04 AM, roger peppe 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 17:25, Robert Griesemer 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.

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>