Design of append()

[szt...@gmail.com]

Hi,

I wonder whether someone here would be able to explain to me the rationale for append() being the way it is. The idiomatic way for appending a new element to a slice seems to be this:

type X struct {

        Foo int

}

slice := []X{X{1}, X{2}, X{3}}

slice = append(slice, X{4})

But if X is a larger struct, this is somewhat inefficient, since the object has to be allocated first somewhere on the heap, just to be copied a moment after to the end of the array underlying the slice. To avoid this, the way I understand it, the slice capacity has to be checked manually, the slice potentially has to be expanded, then you have to take a pointer to an empty cell in the slices array and allocate the new object directly there. So to initialize a new struct directly using the underlying array you have to write this:

slice := []X{X{1}, X{2}}

l := len(slice)

if(l == cap(slice)) {

        nslice := make([]X, cap(slice)*2)

        copy(nslice, slice)

        slice = nslice

}

slice = slice[0:l+1]

x := &slice[l]

x.Foo = 4

Maybe the compiler optimizes it, maybe commonly the performance penalty isn't big, but I still do wonder how do the Go concepts fit together in the end. Is providing a primitive that would allow to directly initialize a new object at the end of the slice somehow not possible or leading to problems? Even just conceptually, that would seem to make more sense to me, so I wonder what am I missing out. I am trying to understand the design of the language, not trying to criticize anything... Another thing I wonder about is why append is a non-destructive operation, or at least why aren't there two versions like a non-destructive "concat" and destructive "append" based on passing a pointer to the slice.

Cheers,

Jarosław Rzeszótko

[Francesc Campoy Flores]

Hi Jaroslaw,

You should read http://blog.golang.org/slices

--
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.

--

--

Francesc Campoy

http://campoy.cat

[Dave Cheney]

On Wed, Jan 15, 2014 at 6:14 AM, <szt...@gmail.com> wrote:

Hi,

I wonder whether someone here would be able to explain to me the rationale for append() being the way it is. The idiomatic way for appending a new element to a slice seems to be this:

type X struct {

        Foo int

}

slice := []X{X{1}, X{2}, X{3}}

slice = append(slice, X{4})

But if X is a larger struct, this is somewhat inefficient, since the object has to be allocated first somewhere on the heap,

Not true, http://play.golang.org/p/l_TMBD4bMm

 

just to be copied a moment after to the end of the array underlying the slice. To avoid this, the way I understand it, the slice capacity has to be checked manually, the slice potentially has to be expanded, then you have to take a pointer to an empty cell in the slices array and allocate the new object directly there. So to initialize a new struct directly using the underlying array you have to write this:

slice := []X{X{1}, X{2}}

l := len(slice)

if(l == cap(slice)) {

        nslice := make([]X, cap(slice)*2)

        copy(nslice, slice)

        slice = nslice

}

slice = slice[0:l+1]

x := &slice[l]

x.Foo = 4

Maybe the compiler optimizes it, maybe commonly the performance penalty isn't big, but I still do wonder how do the Go concepts fit together in the end. Is providing a primitive that would allow to directly initialize a new object at the end of the slice somehow not possible or leading to problems? Even just conceptually, that would seem to make more sense to me, so I wonder what am I missing out. I am trying to understand the design of the language, not trying to criticize anything... Another thing I wonder about is why append is a non-destructive operation, or at least why aren't there two versions like a non-destructive "concat" and destructive "append" based on passing a pointer to the slice.

Cheers,

Jarosław Rzeszótko

[minux]

On Tue, Jan 14, 2014 at 2:14 PM, <szt...@gmail.com> wrote:

I wonder whether someone here would be able to explain to me the rationale for append() being the way it is. The idiomatic way for appending a new element to a slice seems to be this:

type X struct {

        Foo int

}

slice := []X{X{1}, X{2}, X{3}}

slice = append(slice, X{4})

But if X is a larger struct, this is somewhat inefficient, since the object has to be allocated first somewhere on the heap, just to be copied a moment

for the gc toolchain, X{4} is not allocated on the heap first and then copied to slice as you said.

it's allocated on the stack and then copied directly to its final place (two copies at this time,

but nothing prevents the future compilers to optimize this case into copying directly into

its final position)

(the compiler is capable to expand append inline for simple cases like this).

after to the end of the array underlying the slice. To avoid this, the way I understand it, the slice capacity has to be checked manually, the slice potentially has to be expanded, then you have to take a pointer to an empty cell in the slices array and allocate the new object directly there. So to initialize a new struct directly using the underlying array you have to write this:

slice := []X{X{1}, X{2}}

l := len(slice)

if(l == cap(slice)) {

        nslice := make([]X, cap(slice)*2)

        copy(nslice, slice)

        slice = nslice

}

slice = slice[0:l+1]

x := &slice[l]

x.Foo = 4

if slice = append(slice, X{4}) could be optimized to this code, why write it out yourself?

also, append has some heuristic in determine the best way to expand a larger backing array

for the new slice, so please don't reinvent the wheel.

[szt...@gmail.com]

Hi,

Please understand that I am not having a practical problem of any kind, I read "Effective Go" and the slices documentation, I understand the intended way to expand slices is to use append, and the example I posted is only meant to illustrate the issue, I am not reinventing anything. Being interested in programming languages in the abstract, I just wonder if at any point in the language evolution was there a primitive considered that would allow allocation directly using the slices underlying memory. Whether the compiler can always detect and safely optimize this is questionable. Also, thanks for pointing out it's allocated on the stack, but it doesn't change the core point that there is a copy made (By the way, if it's allocated on the stack, what happens if the function returns a pointer to the struct? The struct is moved to the heap on function return?)

Cheers,
Jarosław Rzeszótko

[andrey mirtchovski]

the slice's underlying memory is already allocated up to capacity. if
you want to use it, just use it. there's no magic involved and none
needed.

[szt...@gmail.com]

Hi,

Dynamically extending a slice without making extra copies is clumsy. My question is: is it clumsy because any direct way would have disadvantages, or is there a good way to make it not clumsy. It's not even necessarily a proposal for Go, just a general language design question. Please stop responding with truisms if you don't know the answer to my question.

Cheers,
Jarosław Rzeszótko

[DisposaBoy]

I suggest you explain the actual issue better. so far all I'm seeing you type are things that are either not true or suggesting some lack of understanding about append, slices and arrays on your part. I also detect a bit of annoyance in your tone and for me personally, that's a sign that I should leave the conversation if I were already in it. Just sayin'

[andrey mirtchovski]

> Dynamically extending a slice without making extra copies is clumsy.

a "slice" in go is a fixed-size data structure. "extending a slice"
carries as much meaning as "extending a byte" does: very little. when
you say "extending a slice", in order to extract a meaningful
question, everybody in the Go community takes it to mean "extending
the array underlying the slice". this is what append does quite
successfully. in the context that you're talking about, if you have
capacity to add more elements you can simply do so:

http://play.golang.org/p/2moflTf8fX

in the context that you're alluding to: the ability to just append new
elements at any memory location you wish, I don't think this is
possible in any language. even in written ones eventually the
whitespace runs out.

[andrey mirtchovski]

again, repeating Francesc, all of this is explained very eloquently here

http://blog.golang.org/slices

[szt...@gmail.com]

Hi,

I have said exactly one thing that might not be true, that the copy is allocated on the heap, while it seems to be allocated on the stack, which changes nothing about my argument that an unnecessary copy is being made. I am not sure where do you think I am misunderstanding slices or arrays?

I just hypothetically would want to put a new struct element directly in the array underlying the slice, without doing an unnecessary copy. append() is pass-by-value so it makes a copy and is no-good for this purpose. I can't in general assume that the array underlying the slice has the capacity for one more element, so I end up with the snippet I posted earlier:

slice := []X{X{1}, X{2}}

l := len(slice)

if(l == cap(slice)) {

        nslice := make([]X, cap(slice)*2)

        copy(nslice, slice)

        slice = nslice

}

slice = slice[0:l+1]

x := &slice[l]

x.Foo = 4

Once again: this is NOT a practical question, I am using append() for my Go programs. I am interested in whether alternative approaches were tried out and whether this issue has been at all considered at one point in the language evolution. The call-by-value signature of append suggests that even once you have in your hand a pointer to a struct, which could be used to directly copy the struct from whereever it is currently into the array underlying the slice, there is an extra copy made on the stack first. It might be optimized away to some extent by the compiler, but it still makes the semantics conceptually unclear.

Cheers,
Jarosław Rzeszótko

[szt...@gmail.com]

Hi,

By extending the slice I mean:

slice = slice[0:len(slice+1)]

I know technically the slice is copied, I also still think "extending the slice" is a perfectly reasonable name for this operation.

Nothing prevents one from having a primitive like append that ensures that the underlying array has enough capacity by moving it to a new memory location if necessary, but, for example, returns a pointer to the next "empty" element instead of taking a value as argument. I am interested in considerations that were at play here, I have read the standard documents you are pointing out, I don't see where they describe this issue, or, for example, why elements are passed to append by value.

Cheers,
Jarosław Rzeszótko

[Abhijit Kadam]

I think what he means is avoid the creation of temporary X{4}  that is created and copied to slice's array, and not directly about slice design or how efficiently slice stores the data. The compiler, can it foresee and optimize it. This optimization can be done later as append is builtin function and still no impact on the api and slice design. Just recompile the code. Is it?

[andrey mirtchovski]

> I think what he means is avoid the creation of temporary X{4} that is
> created and copied to slice's array

if the underlying array has the capacity to accept "X{4}" at any
location then that memory is already allocated and the only way to
initialize it to a non-zero element is either to set the appropriate
fields explicitly or to copy a whole struct en masse.

[andrey mirtchovski]

my suggestion is to step away from structs and illustrate the desired
behaviour with simple built-in types (byte is a good example). show,
using a slice of bytes, exactly what you think the problem is and how
you would like it to behave. please note where you think a reference
to a byte should be passed, and where the byte itself.

if there are other languages that do what you want please give them as
an example.

[Abhijit Kadam]

I think he knows copy en masse happens and he is expecting former option (set  appropriate fields explicitly). This is interesting as it is imperative to me that the check for capacity code would be in append function and by that time the temporary is already created and passed to it. 

Also I see no major problem with current behavior.  

[szt...@gmail.com]

Hi,

Exactly, thank you for putting in the effort to understand the question and choosing a wise interpretation and not the most naive one. That's the whole point, it's not like setting the fields explicitly and doing a copy are equivalent - the struct can potentially be large and have a large initialization cost, that will then be paid twice with the current implementation of append. I think it would potentially be interesting to be able to initialize the struct directly in the memory in which it will later be stored.

Cheers,
Jarosław Rzeszótko

[Dave Cheney]

Copying memory is essentially free, compared to garbage collecting the heap. This is a non issue. 

--

[Gustavo Niemeyer]

> W dniu środa, 15 stycznia 2014 09:36:10 UTC+1 użytkownik Abhijit Kadam
> napisał:

> Exactly, thank you for putting in the effort to understand the question and
> choosing a wise interpretation and not the most naive one. That's the whole
> point, it's not like setting the fields explicitly and doing a copy are
> equivalent - the struct can potentially be large and have a large
> initialization cost, that will then be paid twice with the current
> implementation of append. I think it would potentially be interesting to be
> able to initialize the struct directly in the memory in which it will later
> be stored.

I understand where you're coming from, but we're already *able* to do
that, in the sense that the current interface of append can be
improved when/if that becomes relevant. It sounds like you're thinking
of append as just a function provided by the runtime, but even today
it's already not. The logic of append is handled at compile time, and
is partially inlined into the call site, so it can already do clever
tricks based on its parameters.

Another relevant point in that context is that if you ever find such a
special case that requires so much tuning, you can also just implement
the best possible logic for your specific case. The append built-in is
a nice convenience, but it's not mandatory.


gustavo @ http://niemeyer.net

[szt...@gmail.com]

Hi,

It bothers me conceptually more than practically. In fact, I think that in the semantics of Go, adding another element to a slice in this scenario requires making not one but *two* unnecessary copies - the first one because you have to allocate the element somewhere before passing it to append, and another one because append requires the element to be appended to be passed by value. Of course, I understand that append is not internally simply a function, that what really happens might be different, and that compilers might optimize some of this away, but it still bothers me that such a simple operation is so hard to understand well. Also, some of this memory might be essentially blocked until the function terminates. I am wondering if from the perspective of a language designer there is a cleaner set of concepts that would be superior, or if another approach would come with serious problems of its own.

Cheers,
Jarosław Rzeszótko

[szt...@gmail.com]

I think the natural way to append a new element to a slice would be with a function like this:

package main

type X struct {
    Data [5000]int
}

func Push(slice []X) (nslice []X, nstruct *X) {
    l := len(slice)
    nslice = slice
    if(l == cap(slice)) {
        nslice = make([]X, l, cap(slice)*2)
        copy(nslice, slice)
    }
    nslice = nslice[0:l+1]
    return nslice, &nslice[l]
}

func main() {
    slice := make([]X, 0, 10)

    var x *X
    slice, x = Push(slice)
    for j := 0; j < 5000; j++ {
        x.Data[j] = j
    }
}

Why not have such "push" primitive that would not have to be manually added for every type, in addition to the existing "append", and why not make "append" function signature (which as far as I understand is anyway just sugar for whatever happens underneath in the go internals) indicate pass-by-reference for the elements appended? That would make things both conceptually cleaner and more efficient. Are there any downsides of this approach?

Cheers,
Jarosław Rzeszótko

[Gustavo Niemeyer]

On Wed, Jan 15, 2014 at 10:36 AM, <szt...@gmail.com> wrote:
> It bothers me conceptually more than practically. In fact, I think that in

(...)

> function, that what really happens might be different, and that compilers
> might optimize some of this away, but it still bothers me that such a simple
> operation is so hard to understand well.

The operation is conceptually very simple, as you point out, and it's
easy to optimize if necessary. It also looks like you don't really
have an actual issue. Hard to empathize with the goose-chasing.


gustavo @ http://niemeyer.net

[szt...@gmail.com]

Hi,

You can look at a language without looking at the compiler, and the concepts still mean things. Pass-by-value still is pass-by-value, and stack allocation still is stack allocation, so whatever the compiler does, this program:

slice := []X{X{1}, X{2}, X{3}}

slice = append(slice, X{4})

Still says "allocate two unnecessary copies just to initialize a new element in the array". How is this conceptually simple? If I learn the concepts of a language, I want to think in terms of those concepts, and not learn compiler internals by heart. In fact, if the compiler optimizes something contrary to the actual function signature, that strikes me as a rather ugly approach. For a language that takes pride in simplicity and intellectual elegance, this is a strange attitude.

The compiler does not optimize this currently by the way (I benchmarked two alternative approaches and there is around 20% execution time penalty in using append as opposed to directly using the arrays memory), and it is questionable whether all the differences between the two approaches in terms of memory usage and execution time can be resolved by compiler optimizations. But this is a minor point in comparision to the conceptual weirdness of using append() (for adding a completely new element, it makes more sense for adding elements already allocated some place else).

Cheers,
Jarosław Rzeszótko

[Jan Mercl]

On Wed, Jan 15, 2014 at 2:44 PM, <szt...@gmail.com> wrote:
> Still says "allocate two unnecessary copies just to initialize a new element
> in the array".

Have you seen the actual, default optimization level produced machine
code that actually ends in the binary and saw where it "allocates two
unnecessary copies"? If so, then please open a new issue[0] with a
copy of the relevant part of the disassembler output of the repro
case, thank you.

[0]: https://code.google.com/p/go/issues/entry?template=Defect%20report%20from%20user

-j

[szt...@gmail.com]

Hi,

This is not an issue with the compiler but with the language. Why should the compiler "optimize" a pass by value to a pass by reference? Have you at all read what I wrote?

Cheers,
Jarosław Rzeszótko

[Jan Mercl]

On Wed, Jan 15, 2014 at 3:02 PM, <szt...@gmail.com> wrote:
> This is not an issue with the compiler but with the language. Why should the
> compiler "optimize" a pass by value to a pass by reference? Have you at all
> read what I wrote?

Yes, I have read what you wrote and I don't think your assumptions
about allocating two unnecessary copies are correct. AFAICS, nowhere
the language specifies anything which would imply "allocating two
unnecessary copies" for the OP code. Where do you see such requirement
in the specs?

-j

[Gustavo Niemeyer]

On Wed, Jan 15, 2014 at 12:02 PM, <szt...@gmail.com> wrote:
> This is not an issue with the compiler but with the language. Why should the
> compiler "optimize" a pass by value to a pass by reference?

The language specification defines the semantics of what is happening,
not how it is happening. The compiler is free to implement those exact
semantics in whatever way it pleases. So it's not even about
pass-by-value vs. pass-by-reference.. the value can easily never exist
in memory.. in fact, the compiler is free to trash the whole logic if
it finds it irrelevant for the outcome of the program.

If you find that unreasonable, you'll end up programming in assembly,
and even there it's pretty hard to tell exactly what the runtime
performance characteristics will really look like in a modern
processor.

> Have you at all read what I wrote?

Jan merely asked you where do you see the duplicated value, in the
generated code. If you want to brainstorm potential
micro-optimizations, you should be ready for that sort of question.


gustavo @ http://niemeyer.net

[szt...@gmail.com]

Hi,

I specifically mentioned I don't mean the compiler, I don't know what the compiler does in detail, but it for sure doesn't generate equivalent assembly for the two cases I have posted. I don't know if there is a detailed enough spec of Go anywhere to substantiate it, but when I say:

x := X{}

It means "Allocate an instance of X on the stack of the current procedure". When I then say:

append(slice, x)

And the signature of append is:

func append(slice []Type, elems ...Type) []Type

so that elems are passed by value and not by reference, a copy of "x" has to be made on the stack frame for append. So you have "x" on the stack for whatever procedure you are in, "x" on the stack frame for append, and finally "x" lands in the array underlying the slice, so the only place where you really wanted it in. Those are just the good old semantics of function calls and of call-by-value vs call-by-reference. It's irrelevant what the compiler does, in a language with the semantics of Go appending a new element efficiently looks like my Push() I posted earlier. Push() might have other problems, I don't know if it's feasible as a practical proposal, all I was hoping for is an informed discussion of the rationale behind append(), and so far I am getting a lot of pointers to Go tutorials instead.

Cheers,
Jarosław Rzeszótko

[chris 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...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--
Chris "allusive" Dollin

[szt...@gmail.com]

Hi,

I don't want to discuss micro-optimizations, and in the first sentence of what he responded to I said I am not referring to the compiler, so how exactly do you think I should politely respond to a follow up question about the assembly code generated?

What you say about semantics doesn't make any sense to me. The concept of a pointer is rather low-level and refers to whether you want to copy a value or just pass the address. Why would you design a builtin function giving it a signature indicating it will copy its arguments values, and then change the compiler so it is actually takes pointers?

Cheers,
Jarosław Rzeszótko

[Volker Dobler]

Am Mittwoch, 15. Januar 2014 15:23:13 UTC+1 schrieb szt...@gmail.com:

I specifically mentioned I don't mean the compiler, I don't know what the compiler does in detail, but it for sure doesn't generate equivalent assembly for the two cases I have posted. I don't know if there is a detailed enough spec of Go anywhere to substantiate it, but when I say:

x := X{}

It means "Allocate an instance of X on the stack of the current procedure".

Sorry, but no, this is _not_ the meaning of x := X{}

The meaning is more like "declare x to be the zero value of type X".

If this instance does get allocated and if: where is nowhere

specified. E.g. if x escapes than it _cannot_ (and won't be)

allocated on the stack.

When I then say:

append(slice, x)

And the signature of append is:

func append(slice []Type, elems ...Type) []Type

so that elems are passed by value and not by reference, a copy of "x" has to be made on the stack frame for append. So you have "x" on the stack for whatever procedure you are in, "x" on the stack frame for append, and finally "x" lands in the array underlying the slice, so the only place where you really wanted it in. Those are just the good old semantics of function calls and of call-by-value vs call-by-reference. It's irrelevant what the compiler does, in a language with the semantics of Go appending a new element efficiently looks like my Push() I posted earlier. Push() might have other problems, I don't know if it's feasible as a practical proposal, all I was hoping for is an informed discussion of the rationale behind append(), and so far I am getting a lot of pointers to Go tutorials instead.

The argument breaks if the assumptions are wrong.

V. 

[Ian Lance Taylor]

On Wed, Jan 15, 2014 at 6:23 AM, <szt...@gmail.com> wrote:
>
> I specifically mentioned I don't mean the compiler, I don't know what the
> compiler does in detail, but it for sure doesn't generate equivalent
> assembly for the two cases I have posted. I don't know if there is a
> detailed enough spec of Go anywhere to substantiate it, but when I say:
>
> x := X{}
>
> It means "Allocate an instance of X on the stack of the current procedure".
> When I then say:
>
> append(slice, x)
>
> And the signature of append is:
>
> func append(slice []Type, elems ...Type) []Type
>
> so that elems are passed by value and not by reference, a copy of "x" has to
> be made on the stack frame for append. So you have "x" on the stack for
> whatever procedure you are in, "x" on the stack frame for append, and
> finally "x" lands in the array underlying the slice, so the only place where
> you really wanted it in. Those are just the good old semantics of function
> calls and of call-by-value vs call-by-reference. It's irrelevant what the
> compiler does, in a language with the semantics of Go appending a new
> element efficiently looks like my Push() I posted earlier. Push() might have
> other problems, I don't know if it's feasible as a practical proposal, all I
> was hoping for is an informed discussion of the rationale behind append(),
> and so far I am getting a lot of pointers to Go tutorials instead.

It sounds like you want the C++11 emplace method. That method is a
useful addition to C++ because it avoids the copy constructor. Go
does not have copy constructors, so the use case for Go is much less
compelling.

In fact, since Go doesn't have constructors at all, there is no way to
express what you want in Go. There is no way to say "turn this memory
location into this value" without expressing it as a copy. Of course
in many cases the copy will not actually occur. But conceptually it
must always be a copy.

That said, when you say that "x := X{}" means "allocate an instance of
X on the stack of the current procedure" you are not describing the
situation accurately. "x := X{}" just means "create a new X named x".
The compiler can and will generate code that does things other than
putting an instance of X on the stack. Sometimes it will put an
instance of X on the heap. Sometimes it won't create any instance of
X at all. Sometimes it will create some fields of X but not others.
And in principle it might sometimes create X in a newly-appended
array, though I'm not aware of any Go compilers that actually
implement that optimization.

Ian

[chris dollin]

On 15 January 2014 14:23, <szt...@gmail.com> wrote:

. I don't know if there is a detailed enough spec of Go anywhere to substantiate it, but when I say:

x := X{}

It means "Allocate an instance of X on the stack of the current procedure".

It does not, for several reasons.

One is that the *language* doesn't have a stack or a heap; those are

implementation tactics for finding locations. `x := X{}` means something

more like `bind x to some X-shaped location initialised with its zero value`.

The second is that if x has its address taken, explicitly (&) or implicitly

(used in a closure), then the location it binds to must continue to exist

even when the function it happens in has terminated, unless references
to that location no longer exist. This is usually done by taking the

location from the (a) heap. Stack allocation is an implementation optimisation
available if references to x's location no longer exist.

The third is that an implementation is free to rearrange, ignore, pushed,
filed, stamped, or renumbered anything that doesn't affect the external
effects of the program. When you say `x := X{}` the instruction to the

implementation is "behave /as if/ you allocated a new zeroed X-shaped location,

we'll call it x". Whether or not an extra copy or seventeen, or none, takes place

is free for the implementation to decide.

When I then say:

append(slice, x)

And the signature of append is:

func append(slice []Type, elems ...Type) []Type

so that elems are passed by value and not by reference, a copy of "x" has to be made on the stack frame for append.

No; the compiler is only obliged to generate code that has the same

/visible effect/ as taking a copy of x, etc. The output assembly code doesn't
count as a visible effect.

This is not unique to Go.

| all I was hoping for is an informed discussion of the rationale behind append(),

It's useful functionality that got written out long-hand lots of times before
append was added to the language, it's efficient (enough), optimisation

opportunities are available when required, and its easy to explain.

Chris

--
Chris "allusive" Dollin

[szt...@gmail.com]

Hi,

Why? How is there any copy made in my Push() implementation? You only end up with an uninitialized piece of memory for a moment, but that's true anyway in Go a lot of times, since it doesn't force you to initialize structs, and then you fill it out with the values.
 

That said, when you say that "x := X{}" means "allocate an instance of
X on the stack of the current procedure" you are not describing the
situation accurately.  "x := X{}" just means "create a new X named x".
The compiler can and will generate code that does things other than
putting an instance of X on the stack.  Sometimes it will put an
instance of X on the heap.  Sometimes it won't create any instance of
X at all.  Sometimes it will create some fields of X but not others.
And in principle it might sometimes create X in a newly-appended
array, though I'm not aware of any Go compilers that actually
implement that optimization.

Ian

Okay, that's a point, but in practice it likely still has to be allocated either on the heap or on the stack, and then has to be copied as it is passed by value to append, and then finally copied to the array. So while this is valid it doesn't sound like a strong enough argument to favour something like append() over something like Push().

Cheers,
Jarosław Rzeszótko

[szt...@gmail.com]

Hi,

W dniu środa, 15 stycznia 2014 15:45:28 UTC+1 użytkownik chris dollin napisał:

| all I was hoping for is an informed discussion of the rationale behind append(),

It's useful functionality that got written out long-hand lots of times before
append was added to the language, it's efficient (enough), optimisation

opportunities are available when required, and its easy to explain.

Chris

It is not easy to explain, as long as you want to understand what's going on, as illustrated by this discussion. You could use the existing semantics of the language to express a function for creating a new element directly in the array with much simpler semantics and that would work efficiently without any extra compiler support. As said, whether it's allocated on the heap or on the stack doesn't change the fact that two copies are being made, and that the compiler will at all be able to optimize it.

Cheers,
Jarosław Rzeszótko

[Jan Mercl]

On Wed, Jan 15, 2014 at 3:23 PM, <szt...@gmail.com> wrote:
> x := X{}
>
> It means "Allocate an instance of X on the stack of the current procedure".

Its sematics are ("it means"): _Declare_ a variable x in current scope
and _initialize_ it with value X{}. Observable effects are: Now x can
be used as an operand in expressions and its value, until overwtitten
eventually, will be X{}. BTW, those effects can be sometimes provided
without ever allocating a home for x when a smart compiler kicks in.

Nowhere in the specs is ever stack or heap mentioned. The compiler is
free to put the variable in a register, if it fits there, for example.
Or maybe on the stack, if the compiler cannot optimize x's completely
"home" away, which it sometimes can as mentioned above.

As the code explicitly asks to declare x and initialize x - there's no
doubt that any eventual allocation, register or stack, is
"unnecessary". One down.

> When I then say:
>
> append(slice, x)
>
> And the signature of append is:
>
> func append(slice []Type, elems ...Type) []Type
>
> so that elems are passed by value and not by reference, a copy of "x" has to
> be made on the stack frame for append. So you have "x" on the stack for
> whatever procedure you are in, "x" on the stack frame for append, and
> finally "x" lands in the array underlying the slice, so the only place where
> you really wanted it in. Those are just the good old semantics of function
> calls and of call-by-value vs call-by-reference.

Nowhere in the specs is this implementation detail mandated. I don't
know how other compilers, but I'm aware of compilers which, for code

f(a, b)

evaluate a and b on the stack and then call f. There's, in the general
case, no need to copy a or b if they are just literals or when the
compiler can deduce that x (above) is used only as an argument to f
(or append or whatever) as discussed earlier.

If a or b are, say local variables being still "live" after f
completes, than the semantics of pass by value do require, in the
first approximation, a copy to the f's invocation record. However,
there's nothing "unnecessary" in such copying as that what "pass by
value" is about. Second down.

Let's return to the OP code and its claim about "allocate two
unnecessary copies":

type X struct {
Foo int

}

slice := []X{X{1}, X{2}, X{3}}
slice = append(slice, X{4})

From the above discussion I conclude: Nothing in the specs prevents
the compiler to create just _one_ instance of the literal value X{4},
be it register or stack. That one value must exist at some point
anyway (it gets passed to append), so it's necessary/inevitable to
have it somewhere. (Modulo having an autogenerated specialized version
of append for appending X{}, which is in theory also possible.)

-j

[Gustavo Niemeyer]

On Wed, Jan 15, 2014 at 12:35 PM, <szt...@gmail.com> wrote:
> I don't want to discuss micro-optimizations, and in the first sentence of
> what he responded to I said I am not referring to the compiler, so how
> exactly do you think I should politely respond to a follow up question about
> the assembly code generated?

Hopefully with patience and respect, as some of us have been doing.
Note that in the message Jan responded to, you are in fact clearly
discussing a compiler micro-optimization ("The compiler does not
optimize this currently by the way (I benchmarked ..."). Communication
is hard, and it gets even harder when it gets to such meta-levels.

> What you say about semantics doesn't make any sense to me.

That's understandable, but it is actually the case, so it's worth
pondering for a bit longer about the described idea. Language
compilers are free to implement their respective language
specification as necessary, and any non-toy compiler will optimize
obvious sweet spots. So there's a relevant line between "I want to
understand the semantics of what is happening" and "I want to
understand exactly how it is done". It's bad for a compiler to pretend
that a very expensive operation is cheap, and Go does well in that
regard. It's not bad for a compiler to take a simple operation and
make it simpler, though.


gustavo @ http://niemeyer.net

[chris dollin]

On 15 January 2014 14:53, <szt...@gmail.com> wrote:

Hi,

W dniu środa, 15 stycznia 2014 15:45:28 UTC+1 użytkownik chris dollin napisał:

| all I was hoping for is an informed discussion of the rationale behind append(),

It's useful functionality that got written out long-hand lots of times before
append was added to the language, it's efficient (enough), optimisation

opportunities are available when required, and its easy to explain.

Chris

It is not easy to explain, as long as you want to understand what's going on, as illustrated by this discussion.

It's easy to explain if what you want to understand is the /effect/ of calling

append, rather than detailed internal implementation choices. The effect is
defined; the implementation choices can vary.

Whether actual copying -- picking the bytes up from some location and
dropping them doen at another -- happens a lot, a bit, or not at all is at
the whim of the compiler and the accidents of the parameters passed.

 

You could use the existing semantics of the language to express a function for creating a new element directly in the array with much simpler semantics

Simpler semantcis, how? Such a function still needs to (possibly) allocate
a new bigger underlying array and someone still needs to copy the desired

appended value to the end of the revised slice array.

and that would work efficiently without any extra compiler support. As said, whether it's allocated on the heap or on the stack doesn't change the fact that two copies are being made

/may/ be being made.

[szt...@gmail.com]

Hi,

W dniu środa, 15 stycznia 2014 16:00:56 UTC+1 użytkownik Jan Mercl napisał:

On Wed, Jan 15, 2014 at 3:23 PM,  <szt...@gmail.com> wrote:
> x := X{}
>
> It means "Allocate an instance of X on the stack of the current procedure".

Its sematics are ("it means"): _Declare_ a variable x in current scope
and _initialize_ it with value X{}. Observable effects are: Now x can
be used as an operand in expressions and its value, until overwtitten
eventually, will be X{}. BTW, those effects can be sometimes provided
without ever allocating a home for x when a smart compiler kicks in.

Nowhere in the specs is ever stack or heap mentioned. The compiler is
free to put the variable in a register, if it fits there, for example.
Or maybe on the stack, if the compiler cannot optimize x's completely
"home" away, which it sometimes can as mentioned above.

As the code explicitly asks to declare x and initialize x - there's no
doubt that any eventual allocation, register or stack, is
"unnecessary". One down.

Yes, up to the last paragraph I agree with you, and I was wrong with this respect. But I insist that the two allocations still are unnecessary - I am in a sense forced to explicitly allocate X because that is what append() requires (and I don't won't to roll my own Push() for every type I want to use). And then there is another unnecessary allocation from the call by value, which nobody has addressed so far in any way I think.

> When I then say:
>
> append(slice, x)
>
> And the signature of append is:
>
> func append(slice []Type, elems ...Type) []Type
>
> so that elems are passed by value and not by reference, a copy of "x" has to
> be made on the stack frame for append. So you have "x" on the stack for
> whatever procedure you are in, "x" on the stack frame for append, and
> finally "x" lands in the array underlying the slice, so the only place where
> you really wanted it in. Those are just the good old semantics of function
> calls and of call-by-value vs call-by-reference.

Nowhere in the specs is this implementation detail mandated. I don't
know how other compilers, but I'm aware of compilers which, for code

   f(a, b)

evaluate a and b on the stack and then call f. There's, in the general
case, no need to copy a or b if they are just literals or when the
compiler can deduce that x (above) is used only as an argument to f
(or append or whatever) as discussed earlier.

If a or b are, say local variables being still "live" after f
completes, than the semantics of pass by value do require, in the
first approximation, a copy to the f's invocation record. However,
there's nothing "unnecessary" in such copying as that what "pass by
value" is about. Second down.

Here you are being unreasonable. I am asking about why append uses pass by value instead of pass by reference, and you are saying that the copying of the argument to append is fine because append uses pass by value. How is that addressing the issue? I have showed an alternative to append() for the particular usage scenario that avoids those problems.
 

Let's return to the OP code and its claim about "allocate two
unnecessary copies":

type X struct {
        Foo int
}

slice := []X{X{1}, X{2}, X{3}}
slice = append(slice, X{4})

From the above discussion I conclude: Nothing in the specs prevents
the compiler to create just _one_ instance of the literal value X{4},
be it register or stack. That one value must exist at some point
anyway (it gets passed to append), so it's necessary/inevitable to
have it somewhere. (Modulo having an autogenerated specialized version
of append for appending X{}, which is in theory also possible.)

-j

Except the compiler might not be able to decide whether this optimization is safe to do or not and how precisely to do it. I don't think anything in compiler optimization algorithms is as simple as you paint it.

Cheers,
Jarosław Rzeszótko

[szt...@gmail.com]

W dniu środa, 15 stycznia 2014 16:06:41 UTC+1 użytkownik chris dollin napisał:

On 15 January 2014 14:53, <szt...@gmail.com> wrote:

Hi,

W dniu środa, 15 stycznia 2014 15:45:28 UTC+1 użytkownik chris dollin napisał:

| all I was hoping for is an informed discussion of the rationale behind append(),

It's useful functionality that got written out long-hand lots of times before
append was added to the language, it's efficient (enough), optimisation

opportunities are available when required, and its easy to explain.

Chris

It is not easy to explain, as long as you want to understand what's going on, as illustrated by this discussion.

It's easy to explain if what you want to understand is the /effect/ of calling

append, rather than detailed internal implementation choices. The effect is
defined; the implementation choices can vary.

Whether actual copying -- picking the bytes up from some location and
dropping them doen at another -- happens a lot, a bit, or not at all is at
the whim of the compiler and the accidents of the parameters passed.

append() has a signature that indicates that it will copy the value, that's the point of having values and pointers in the language. If the compiler does something else, then in does so contrary to the semantics of the language.
 

 

You could use the existing semantics of the language to express a function for creating a new element directly in the array with much simpler semantics

Simpler semantcis, how? Such a function still needs to (possibly) allocate
a new bigger underlying array and someone still needs to copy the desired

appended value to the end of the revised slice array.

I illustrated it with my Push() function several posts earlier. You can initialize the struct directly using a pointer to the right piece of the underlying array.
 

and that would work efficiently without any extra compiler support. As said, whether it's allocated on the heap or on the stack doesn't change the fact that two copies are being made

/may/ be being made.

And likely are currently being made. Picking every nit to somehow prove me wrong doesn't make this dicussion more productive.

Cheers,
Jarosław Rzeszótko

[egon]

On Wednesday, January 15, 2014 5:15:43 PM UTC+2, szt...@gmail.com wrote:

W dniu środa, 15 stycznia 2014 16:06:41 UTC+1 użytkownik chris dollin napisał:

On 15 January 2014 14:53, <szt...@gmail.com> wrote:

Hi,

W dniu środa, 15 stycznia 2014 15:45:28 UTC+1 użytkownik chris dollin napisał:

| all I was hoping for is an informed discussion of the rationale behind append(),

It's useful functionality that got written out long-hand lots of times before
append was added to the language, it's efficient (enough), optimisation

opportunities are available when required, and its easy to explain.

Chris

It is not easy to explain, as long as you want to understand what's going on, as illustrated by this discussion.

It's easy to explain if what you want to understand is the /effect/ of calling

append, rather than detailed internal implementation choices. The effect is
defined; the implementation choices can vary.

Whether actual copying -- picking the bytes up from some location and
dropping them doen at another -- happens a lot, a bit, or not at all is at
the whim of the compiler and the accidents of the parameters passed.

append() has a signature that indicates that it will copy the value, that's the point of having values and pointers in the language. If the compiler does something else, then in does so contrary to the semantics of the language.

The compiler should only appear to be doing what the source tells it... If the compiler did exactly what the code says then it wouldn't be able to do any optimizations. It shouldn't matter what the compiler does as long as the code result is exactly the same.

[Ian Lance Taylor]

On Wed, Jan 15, 2014 at 6:48 AM, <szt...@gmail.com> wrote:
>
> W dniu środa, 15 stycznia 2014 15:40:54 UTC+1 użytkownik Ian Lance Taylor
> napisał:
>>

>> In fact, since Go doesn't have constructors at all, there is no way to
>> express what you want in Go. There is no way to say "turn this memory
>> location into this value" without expressing it as a copy. Of course
>> in many cases the copy will not actually occur. But conceptually it
>> must always be a copy.
>
>
> Why? How is there any copy made in my Push() implementation? You only end up
> with an uninitialized piece of memory for a moment, but that's true anyway
> in Go a lot of times, since it doesn't force you to initialize structs, and
> then you fill it out with the values.

That turns out not to be the case. There is no concept of
uninitialized memory in Go. All memory always holds a valid value for
its type. In implementation terms, what this means is that all memory
is initialized either by the zero value (which is always all zeros) or
by some other valid value.

>> That said, when you say that "x := X{}" means "allocate an instance of
>> X on the stack of the current procedure" you are not describing the
>> situation accurately. "x := X{}" just means "create a new X named x".
>> The compiler can and will generate code that does things other than
>> putting an instance of X on the stack. Sometimes it will put an
>> instance of X on the heap. Sometimes it won't create any instance of
>> X at all. Sometimes it will create some fields of X but not others.
>> And in principle it might sometimes create X in a newly-appended
>> array, though I'm not aware of any Go compilers that actually
>> implement that optimization.
>

> Okay, that's a point, but in practice it likely still has to be allocated
> either on the heap or on the stack, and then has to be copied as it is
> passed by value to append, and then finally copied to the array.

None of these statements is true in all cases. The append function is
part of the language, and not only is the generated code not required
to call a function in all cases, in actual fact for some compilers it
does not call a function in all cases.

Ian

[szt...@gmail.com]

Hi,

W dniu środa, 15 stycznia 2014 16:28:40 UTC+1 użytkownik Ian Lance Taylor napisał:

On Wed, Jan 15, 2014 at 6:48 AM,  <szt...@gmail.com> wrote:
>
> W dniu środa, 15 stycznia 2014 15:40:54 UTC+1 użytkownik Ian Lance Taylor
> napisał:
>>
>> In fact, since Go doesn't have constructors at all, there is no way to
>> express what you want in Go.  There is no way to say "turn this memory
>> location into this value" without expressing it as a copy.  Of course
>> in many cases the copy will not actually occur.  But conceptually it
>> must always be a copy.
>
>
> Why? How is there any copy made in my Push() implementation? You only end up
> with an uninitialized piece of memory for a moment, but that's true anyway
> in Go a lot of times, since it doesn't force you to initialize structs, and
> then you fill it out with the values.

That turns out not to be the case.  There is no concept of
uninitialized memory in Go.  All memory always holds a valid value for
its type.  In implementation terms, what this means is that all memory
is initialized either by the zero value (which is always all zeros) or
by some other valid value.

I meant an uninitialized struct, in the sense that the struct might require additional initialization (beyond the default zeroing) before it represents a semantically meaningful object. E.g. a memory of all zeros is not a valid value for the type:

struct Line {
  Point p1
  Point p2
}

Because two points make a line only if they are at distinct locations. So with Push() always, and with Go sometimes (because you can, but don't have to, discipline yourself and always pass in valid initial values as in Line{1,2,3,4}) you can end up with a pointer to something that is not a valid value for the type it represents.
 

>> That said, when you say that "x := X{}" means "allocate an instance of
>> X on the stack of the current procedure" you are not describing the
>> situation accurately.  "x := X{}" just means "create a new X named x".
>> The compiler can and will generate code that does things other than
>> putting an instance of X on the stack.  Sometimes it will put an
>> instance of X on the heap.  Sometimes it won't create any instance of
>> X at all.  Sometimes it will create some fields of X but not others.
>> And in principle it might sometimes create X in a newly-appended
>> array, though I'm not aware of any Go compilers that actually
>> implement that optimization.
>
> Okay, that's a point, but in practice it likely still has to be allocated
> either on the heap or on the stack, and then has to be copied as it is
> passed by value to append, and then finally copied to the array.

None of these statements is true in all cases.  The append function is
part of the language, and not only is the generated code not required
to call a function in all cases, in actual fact for some compilers it
does not call a function in all cases.

Ian

Allright, I agree, but why complicate the compiler if you can get something to work faster by expressing it more clearly using the existing language semantics more appropriately?

Cheers,
Jarosław Rzeszótko

[roger peppe]

On 15 January 2014 15:36, <szt...@gmail.com> wrote:
> Allright, I agree, but why complicate the compiler if you can get something
> to work faster by expressing it more clearly using the existing language
> semantics more appropriately?

What's not clear about this?

lines = append(lines, Line{
p0: start,
p1: end,
})

There's no need for the compiler to copy the new line at all - it's
totally free to append the new item, then fill it in from the initialisation
values.

If the appended value is a local variable that's not
used elsewhere, that's still possible.

[chris dollin]

On 15 January 2014 15:15, <szt...@gmail.com> wrote:

W dniu środa, 15 stycznia 2014 16:06:41 UTC+1 użytkownik chris dollin napisał:

On 15 January 2014 14:53, <szt...@gmail.com> wrote:

append() has a signature that indicates that it will copy the value,

The signature makes no difference; all Go function, append included,

pass by value. Sometimes the value is a pointer. That doesn't mean
that the value is copied; it means it must /behave as if/ the value is copied.
 

that's the point of having values and pointers in the language. If the compiler does something else, then in does so contrary to the semantics of the language.

That's not true, if you can't tell from the program's external effects that

"something else" has happened.

type T struct {A, B int}

func eg() {

    a := T{1, 2}

    b := T{3, 4}

    a.A += 1

    b.B += 1
}

An implementation is free to reorder the two declarations. It is free
to reorder the two assignments. It is free to delete all four statements.

Are these "something elses" contrary to the semantics of the language?

What about inlining? Is that contrary to the semantics of the language?

You could use the existing semantics of the language to express a function for creating a new element directly in the array with much simpler semantics

Simpler semantcis, how? Such a function still needs to (possibly) allocate
a new bigger underlying array and someone still needs to copy the desired

appended value to the end of the revised slice array.

I illustrated it with my Push() function several posts earlier. You can initialize the struct directly using a pointer to the right piece of the underlying array.

I don't see that the /semantics/ is any simpler.

and that would work efficiently without any extra compiler support. As said, whether it's allocated on the heap or on the stack doesn't change the fact that two copies are being made

/may/ be being made.

And likely are currently being made.

The significant thing is that it's /allowed/ to not make the copies you
insist /must/ be made.

(Also, Ian's posts.)

 

Chris

--
Chris "allusive" Dollin

[szt...@gmail.com]

Hi,

W dniu środa, 15 stycznia 2014 16:46:57 UTC+1 użytkownik chris dollin napisał:

On 15 January 2014 15:15, <szt...@gmail.com> wrote:

W dniu środa, 15 stycznia 2014 16:06:41 UTC+1 użytkownik chris dollin napisał:

On 15 January 2014 14:53, <szt...@gmail.com> wrote:

append() has a signature that indicates that it will copy the value,

The signature makes no difference; all Go function, append included,

pass by value. Sometimes the value is a pointer. That doesn't mean
that the value is copied; it means it must /behave as if/ the value is copied.
 

that's the point of having values and pointers in the language. If the compiler does something else, then in does so contrary to the semantics of the language.

That's not true, if you can't tell from the program's external effects that

"something else" has happened.

type T struct {A, B int}

func eg() {

    a := T{1, 2}

    b := T{3, 4}

    a.A += 1

    b.B += 1
}

An implementation is free to reorder the two declarations. It is free
to reorder the two assignments. It is free to delete all four statements.

Are these "something elses" contrary to the semantics of the language?

What about inlining? Is that contrary to the semantics of the language?

I think there is a huge difference of degree between inlining and "optimizing" a call-by-value to be in fact a call-by-reference. If you don't write things reasonably conforming to the semantics of the language, you can't just expect the compiler to be able to optimize it away, because you are then not giving the compiler the knowledge necessary to do it, see below.

You could use the existing semantics of the language to express a function for creating a new element directly in the array with much simpler semantics

Simpler semantcis, how? Such a function still needs to (possibly) allocate
a new bigger underlying array and someone still needs to copy the desired

appended value to the end of the revised slice array.

I illustrated it with my Push() function several posts earlier. You can initialize the struct directly using a pointer to the right piece of the underlying array.

I don't see that the /semantics/ is any simpler.

and that would work efficiently without any extra compiler support. As said, whether it's allocated on the heap or on the stack doesn't change the fact that two copies are being made

/may/ be being made.

And likely are currently being made.

The significant thing is that it's /allowed/ to not make the copies you
insist /must/ be made.

(Also, Ian's posts.)

Chris

--
Chris "allusive" Dollin

Those are valid points in general, but not necessarily completely valid here, replying to both you and rog here, the struct might require initialization in the form of an arbitrarily complicated algorithm, and I doubt a compiler can analyze precisely from which parts of your program this initialization algorithm consists of and then apply those parts directly to the arrays memory instead of applying it to whatever the program says to apply it to and then doing a copy, and in the process make sure that the transformation is completely safe to do. At the very least it's not a trivial optimization, while implementing something like Push() as a primitive is comparatively simple.

Cheers,
Jarosław Rzeszótko

[chris dollin]

On 15 January 2014 16:05, <szt...@gmail.com> wrote:

Hi,

W dniu środa, 15 stycznia 2014 16:46:57 UTC+1 użytkownik chris dollin napisał:

On 15 January 2014 15:15, <szt...@gmail.com> wrote:

W dniu środa, 15 stycznia 2014 16:06:41 UTC+1 użytkownik chris dollin napisał:

On 15 January 2014 14:53, <szt...@gmail.com> wrote:

append() has a signature that indicates that it will copy the value,

The signature makes no difference; all Go function, append included,

pass by value. Sometimes the value is a pointer. That doesn't mean
that the value is copied; it means it must /behave as if/ the value is copied.
 

that's the point of having values and pointers in the language. If the compiler does something else, then in does so contrary to the semantics of the language.

That's not true, if you can't tell from the program's external effects that

"something else" has happened.

type T struct {A, B int}

func eg() {

    a := T{1, 2}

    b := T{3, 4}

    a.A += 1

    b.B += 1
}

An implementation is free to reorder the two declarations. It is free
to reorder the two assignments. It is free to delete all four statements.

Are these "something elses" contrary to the semantics of the language?

What about inlining? Is that contrary to the semantics of the language?

I think there is a huge difference of degree between inlining and "optimizing" a call-by-value to be in fact a call-by-reference.

I don't. They're different kinds of optimisation, is all. (Not to mention I wouldn't

call what generating a reduced-copying append does making something a

call-by-reference, since that's really not what it is -- note that "call by reference"

has a specific meaning that doesn't just mean "pass a pointer".)

 

If you don't write things reasonably conforming to the semantics of the language, you can't just expect the compiler to be able to optimize it away, because you are then not giving the compiler the knowledge necessary to do it, see below.

That's generally true. It also doesn't apply to calls of append.

Those are valid points in general, but not necessarily completely valid here, replying to both you and rog here, the struct might require initialization in the form of an arbitrarily complicated algorithm, and I doubt a compiler can analyze precisely from which parts of your program this initialization algorithm consists of and then apply those parts directly to the arrays memory instead of applying it to whatever the program says to apply it to and then doing a copy, and in the process make sure that the transformation is completely safe to do.

Yes, sometimes the optimisation is too hard to do. "Mights" can be a
real fun-breaker.

 

At the very least it's not a trivial optimization, while implementing something like Push() as a primitive is comparatively simple.

That wasn't what people wanted in the times before append. It's no use

being efficient if you don't get used.

 

Chris

--
Chris "allusive" Dollin

[szt...@gmail.com]

Hi,

W dniu środa, 15 stycznia 2014 17:15:51 UTC+1 użytkownik chris dollin napisał:

At the very least it's not a trivial optimization, while implementing something like Push() as a primitive is comparatively simple.

That wasn't what people wanted in the times before append. It's no use

being efficient if you don't get used.

 

Chris

--
Chris "allusive" Dollin

If this is simply "what people wanted", then I don't have any more questions.

Cheers,
Jarosław Rzeszótko

[chris dollin]

On 15 January 2014 16:20, <szt...@gmail.com> wrote:

Hi,

W dniu środa, 15 stycznia 2014 17:15:51 UTC+1 użytkownik chris dollin napisał:

That wasn't what people wanted in the times before append. It's no use

being efficient if you don't get used.

If this is simply "what people wanted", then I don't have any more questions.

My (imperfect) recollection is that options around append-like things

got discussed a lot and the current append was the outcome as

something (a) generic (b) convenient to use (c) ok performance and

optimisation possibilities. It wasn't just blind "we want this".

[Andy Balholm]

On Wednesday, January 15, 2014 8:05:41 AM UTC-8, szt...@gmail.com wrote:

the struct might require initialization in the form of an arbitrarily complicated algorithm

Struct literals in Go (unlike C++) never require arbitrarily complicated initialization. The initialization is never more than copying the relevant bytes.

[szt...@gmail.com]

Hi,

I said *the struct* might require initialization, it might not be a struct literal, in fact it might not even be a struct, the same applies to arrays. The struct literal case can probably indeed be optimized more easily.

Cheers,
Jarosław Rzeszótko

[Niklas Schnelle]

Why do you think append would be conceptually more efficient with pass-by-reference? Say we are appending to a float64 slice, then copying 8 bytes into a true

float array (that's backing the slice) will result in a much faster accessible []float64 than the reference based []*float64 that would be the only way if append() would use 

pass-by-reference in the C sense of passing a pointer.

[szt...@gmail.com]

Hi,

The signature of append is this:

func append(slice []Type, elems ...Type) []Type

All arguments are non-pointer values, and I think this signature was meant to suggest that none of the elems will be modified by append, because the appends *function body* will just copy the element to the underlying array. But this is what the go specification says about function calls:

"In a function call, the function value and arguments are evaluated in the usual order. After they are evaluated, the parameters of the call are passed by value to the function and the called function begins execution."

So it is conceptually wrong to use a non-pointer value argument to suggest that there will be a copy made in the function *body*, the copy takes place before function execution. A call-by-value means making a copy on the stack of the function called, before the function is at all executed, if you at all care about keeping clear semantics. So append to stay efficient and conceptually clear should take pointers for the elements to be appended, so if you are appending an array of float64, *[]float64, a pointer to an array of float64, not a stack-copy of an array of float64. To express more specifically what happens to the appended elements, append should really take a pointer to a constant, but Go doesn't have const as I understand. In general, as said earlier, I think append should only handle concatenating elements already allocated earlier, and there should be a new primitive that would, just like append, ensure the array underlying the slices has room for one more element, reallocate to a new memory place if needed, and return a pointer to the next "free" element of the array. This is the best way to express the idea of adding a new element to a slice using the zoo of concepts Go has.

The current approach wastes time, space, and is confusing the concepts of the language.

Cheers,
Jarosław Rzeszótko

[minux]

On Thu, Jan 16, 2014 at 1:21 AM, <szt...@gmail.com> wrote:

W dniu czwartek, 16 stycznia 2014 00:46:40 UTC+1 użytkownik Niklas Schnelle napisał:

Why do you think append would be conceptually more efficient with pass-by-reference? Say we are appending to a float64 slice, then copying 8 bytes into a true

float array (that's backing the slice) will result in a much faster accessible []float64 than the reference based []*float64 that would be the only way if append() would use 

pass-by-reference in the C sense of passing a pointer.

Hi,

The signature of append is this:

func append(slice []Type, elems ...Type) []Type

This is only a conceptual signature for append, append is a compiler builtin function, which

means that the compiler can blend the normal rules. 

All arguments are non-pointer values, and I think this signature was meant to suggest that none of the elems will be modified by append, because the appends *function body* will just copy the element to the underlying array. But this is what the go specification says about function calls:

"In a function call, the function value and arguments are evaluated in the usual order. After they are evaluated, the parameters of the call are passed by value to the function and the called function begins execution."

you're still mixing the semantics of one statement and the actual implementation of that statement.

as long as the behavior visible to the user is the same, the implementation is free to do whatever it want.

Also, as I said above, append is not a normal function (you can't define your own append in Go, so this

paragraph actually might not describe what happens when you call the builtin function append.

So it is conceptually wrong to use a non-pointer value argument to suggest that there will be a copy made in the function

you keep mention conceptually. conceptually everything must be allocated on heap, how does that sound?

it's actually an optimization to allocate object on stack when it doesn't escape.

So why you analyze the performance of a conceptual thing? Discussing performance implicitly means

an implementation, and having an implementation means give concrete meanings to all concepts.

*body*, the copy takes place before function execution. A call-by-value means making a copy on the stack of the function called, before the function is at all executed, if you at all care about keeping clear semantics. So append to stay efficient 

and conceptually clear should take pointers for the elements to be appended, so if you are appending an array of float64, *[]float64, a pointer to an array of float64, not a stack-copy of an array of float64. To express more specifically what happens to the appended elements, append should really take a pointer to a constant, but Go doesn't have const as I understand. In general, as said earlier, I think append should only handle concatenating elements already allocated earlier, and there should be a new primitive that would, just like append, ensure the array underlying the slices has room for one more element, reallocate to a new memory place if needed, and return a pointer to the next "free" element of the array. This is the best way to express the idea of adding a new element to a slice using the zoo of concepts Go has.

because you based all this arguments on false assumptions, they are false.

The current approach wastes time, space, and is confusing the concepts of the language.

the Push you mentioned isn't better, besides it's much harder to use.

for example, how to do append(s, a1, a2, a3)?

do you need to Push multiple times? Or have a Push that can return any number of pointers?

How you could write that line in terms of your Push?

[szt...@gmail.com]

Hi,

W dniu czwartek, 16 stycznia 2014 07:47:57 UTC+1 użytkownik minux napisał:

On Thu, Jan 16, 2014 at 1:21 AM, <szt...@gmail.com> wrote:

W dniu czwartek, 16 stycznia 2014 00:46:40 UTC+1 użytkownik Niklas Schnelle napisał:

Why do you think append would be conceptually more efficient with pass-by-reference? Say we are appending to a float64 slice, then copying 8 bytes into a true

float array (that's backing the slice) will result in a much faster accessible []float64 than the reference based []*float64 that would be the only way if append() would use 

pass-by-reference in the C sense of passing a pointer.

Hi,

The signature of append is this:

func append(slice []Type, elems ...Type) []Type

This is only a conceptual signature for append, append is a compiler builtin function, which

means that the compiler can blend the normal rules. 

The conceptual signature should still make sense when you for a moment forget that a compiler exists and just think on the level of the programming language as an abstract thing, it should adequately describe the semantics of append(). Why would append do a copy of each of elems before execution? And yet that's what the signature of append() says it does, according to go language spec. Are you saying the signature of append can say anything because it's a builtin and the compiler will anyway interpret it whatever way it wants?
 

All arguments are non-pointer values, and I think this signature was meant to suggest that none of the elems will be modified by append, because the appends *function body* will just copy the element to the underlying array. But this is what the go specification says about function calls:

"In a function call, the function value and arguments are evaluated in the usual order. After they are evaluated, the parameters of the call are passed by value to the function and the called function begins execution."

you're still mixing the semantics of one statement and the actual implementation of that statement.

as long as the behavior visible to the user is the same, the implementation is free to do whatever it want.

Also, as I said above, append is not a normal function (you can't define your own append in Go, so this

paragraph actually might not describe what happens when you call the builtin function append.

I am not mixing anything, that's how the signature of append describes what append does according to the language spec, if the compiler does something else, it only makes things even more messy to understand. In case of Go, language concepts happen to intersect with some implementation details, as you have seen the language spec explicitly mentions that a copy is being made before function body execution.
 

So it is conceptually wrong to use a non-pointer value argument to suggest that there will be a copy made in the function

you keep mention conceptually. conceptually everything must be allocated on heap, how does that sound?

it's actually an optimization to allocate object on stack when it doesn't escape.

Pointer and non-pointer values are concepts of the language, the heap is not, neither is the stack, it's not even mentioned once in the spec.
 

So why you analyze the performance of a conceptual thing? Discussing performance implicitly means

an implementation, and having an implementation means give concrete meanings to all concepts.

*body*, the copy takes place before function execution. A call-by-value means making a copy on the stack of the function called, before the function is at all executed, if you at all care about keeping clear semantics. So append to stay efficient 

and conceptually clear should take pointers for the elements to be appended, so if you are appending an array of float64, *[]float64, a pointer to an array of float64, not a stack-copy of an array of float64. To express more specifically what happens to the appended elements, append should really take a pointer to a constant, but Go doesn't have const as I understand. In general, as said earlier, I think append should only handle concatenating elements already allocated earlier, and there should be a new primitive that would, just like append, ensure the array underlying the slices has room for one more element, reallocate to a new memory place if needed, and return a pointer to the next "free" element of the array. This is the best way to express the idea of adding a new element to a slice using the zoo of concepts Go has.

because you based all this arguments on false assumptions, they are false.

No, they are not false, you guys just keep using this "appeal to compiler" to justify a language flaw. It's unbelievably irritating, because A) this is a flaw regardless of whatever the compiler does, B) the compiler does not optimize this currently, and might never be able to for 100% of the cases, as was discussed.
 

The current approach wastes time, space, and is confusing the concepts of the language.

the Push you mentioned isn't better, besides it's much harder to use.

for example, how to do append(s, a1, a2, a3)?

do you need to Push multiple times? Or have a Push that can return any number of pointers?

How you could write that line in terms of your Push?

I have already mentioned that you should distinguish between the case of concatenating slices, for which append with a pointer argument for elems would be OK, and the case of initializing a new element in the slice. Push() is meant to fix the issues append() has with the latter case.

Cheers,
Jarosław Rzeszótko

[Jesse McNelis]

On Thu, Jan 16, 2014 at 6:05 PM, <szt...@gmail.com> wrote:

Hi,

W dniu czwartek, 16 stycznia 2014 07:47:57 UTC+1 użytkownik minux napisał:

On Thu, Jan 16, 2014 at 1:21 AM, <szt...@gmail.com> wrote:

W dniu czwartek, 16 stycznia 2014 00:46:40 UTC+1 użytkownik Niklas Schnelle napisał:

Why do you think append would be conceptually more efficient with pass-by-reference? Say we are appending to a float64 slice, then copying 8 bytes into a true

float array (that's backing the slice) will result in a much faster accessible []float64 than the reference based []*float64 that would be the only way if append() would use 

pass-by-reference in the C sense of passing a pointer.

Hi,

The signature of append is this:

func append(slice []Type, elems ...Type) []Type

This is only a conceptual signature for append, append is a compiler builtin function, which

means that the compiler can blend the normal rules. 

The conceptual signature should still make sense when you for a moment forget that a compiler exists and just think on the level of the programming language as an abstract thing, it should adequately describe the semantics of append(). Why would append do a copy of each of elems before execution? And yet that's what the signature of append() says it does, according to go language spec. Are you saying the signature of append can say anything because it's a builtin and the compiler will anyway interpret it whatever way it wants?

append() works like every other function in Go. It's pass-by-value.

The Go spec says that calling append() will copy each of the parameters.

I don't understand why this concerns you so much. Copying is a really fast operation and you're copying small things.

If T is very large then you'd probably avoid append()ing to a []T because the copying of all the elements in []T would be very slow when you needed to extend the []T and you'd use a []*T instead or preallocate a much larger slice and just assign to the indices.

append() is simple and efficient for any sane use case. If it happens to be a bottleneck for you then it's trivial to avoid.

--
=====================
http://jessta.id.au

[minux]

On Thu, Jan 16, 2014 at 2:05 AM, <szt...@gmail.com> wrote:

W dniu czwartek, 16 stycznia 2014 07:47:57 UTC+1 użytkownik minux napisał:

The signature of append is this:

func append(slice []Type, elems ...Type) []Type

This is only a conceptual signature for append, append is a compiler builtin function, which

means that the compiler can blend the normal rules. 

The conceptual signature should still make sense when you for a moment forget that a compiler exists and just think on the level of the programming language as an abstract thing, it should adequately describe the semantics of append(). Why would append do a copy of each of elems before execution? And yet that's what the signature of append() says it does, according to go language spec. Are you saying the signature of append can say anything because it's a builtin and the compiler will anyway interpret it whatever way it wants?

the signature is just for reference how you can use append, not how append take those arguments

because it's a builtin function, not a normal function.

All arguments are non-pointer values, and I think this signature was meant to suggest that none of the elems will be modified by append, because the appends *function body* will just copy the element to the underlying array. But this is what the go specification says about function calls:

"In a function call, the function value and arguments are evaluated in the usual order. After they are evaluated, the parameters of the call are passed by value to the function and the called function begins execution."

you're still mixing the semantics of one statement and the actual implementation of that statement.

as long as the behavior visible to the user is the same, the implementation is free to do whatever it want.

Also, as I said above, append is not a normal function (you can't define your own append in Go, so this

paragraph actually might not describe what happens when you call the builtin function append.

I am not mixing anything, that's how the signature of append describes what append does according to the language spec,

also, that signature is actually not correct. because you can append a string to a byte slice.

if the compiler does something else, it only makes things even more messy to understand. In case of Go, language concepts happen to intersect with some implementation details, as you have seen the language spec explicitly mentions that a copy is being made before function body execution.

My point is you can't discuss performance of a language by looking at the spec.

Also, you are actually wrong to cite the function call section of the spec, because at the start

of that section, it says:

   "Given an expression f of function type F,"

Does append fits this requirement? what the function type of append?

Also, if it's a function, then you can assign to a variable, can you do this in Go?

    f := append

So it is conceptually wrong to use a non-pointer value argument to suggest that there will be a copy made in the function

you keep mention conceptually. conceptually everything must be allocated on heap, how does that sound?

it's actually an optimization to allocate object on stack when it doesn't escape.

Pointer and non-pointer values are concepts of the language, the heap is not, neither is the stack, it's not even mentioned once in the spec.
 

So why you analyze the performance of a conceptual thing? Discussing performance implicitly means

an implementation, and having an implementation means give concrete meanings to all concepts.

*body*, the copy takes place before function execution. A call-by-value means making a copy on the stack of the function called, before the function is at all executed, if you at all care about keeping clear semantics. So append to stay efficient 

and conceptually clear should take pointers for the elements to be appended, so if you are appending an array of float64, *[]float64, a pointer to an array of float64, not a stack-copy of an array of float64. To express more specifically what happens to the appended elements, append should really take a pointer to a constant, but Go doesn't have const as I understand. In general, as said earlier, I think append should only handle concatenating elements already allocated earlier, and there should be a new primitive that would, just like append, ensure the array underlying the slices has room for one more element, reallocate to a new memory place if needed, and return a pointer to the next "free" element of the array. This is the best way to express the idea of adding a new element to a slice using the zoo of concepts Go has.

because you based all this arguments on false assumptions, they are false.

No, they are not false, you guys just keep using this "appeal to compiler" to justify a language flaw. It's unbelievably

What is the flaw of append?

Performance? No, you can discuss the performance without making reference to an implementation,

and that's why we keep mention compiler here.

irritating, because A) this is a flaw regardless of whatever the compiler does, B) the compiler does not optimize this currently, and might never be able to for 100% of the cases, as was discussed.
 

The current approach wastes time, space, and is confusing the concepts of the language.

the Push you mentioned isn't better, besides it's much harder to use.

for example, how to do append(s, a1, a2, a3)?

do you need to Push multiple times? Or have a Push that can return any number of pointers?

How you could write that line in terms of your Push?

I have already mentioned that you should distinguish between the case of concatenating slices, for which append with a pointer argument for elems would be OK, and the case of initializing a new element in the slice. Push() is meant to fix the issues append() has with the latter case.

OK, let's discuss how you can use Push to write:

append(s1, X{1}, X{2})

Push as you proposed can only initialize one element, which IMO is the flaw.

(also, you failed to consider that allocating new slice already zeros the slice,

so it actually doesn't reduce the amount of unnecessary memory initialization,

be it zeroing or copying another non-zero value)

[szt...@gmail.com]

Hi,

append() is just intellectually ugly to me, that's all, and I am very surprised people here are defending it almost fanatically like it's a gift from the elders or something, I thought at least one person will simply agree with me that it isn't the best thing under the sun, even if the whole issue isn't a very big deal in most cases. Then you again invent this sort of circular argument, of the sort that was mentioned already, that append() is totally fine because if you would like to do LargeStruct[] then append() would make a copy and that's slow and you would avoid using append() then... I don't get it. You can't just preallocate a larger slice, because you might not know in advance how many elements you will want to add. In addition to wasting (not too much) time, append() also wastes space. Why do it wrong if you can do it right?

Cheers,
Jarosław Rzeszótko

[minux]

On Thu, Jan 16, 2014 at 2:26 AM, <szt...@gmail.com> wrote:

append() is just intellectually ugly to me, that's all, and I am very surprised people here are defending it almost fanatically like it's a gift from the elders or something, I thought at least one person will simply agree with me that it isn't the best thing under the sun, even if the whole issue isn't a very big deal in most cases. Then you again invent this sort of circular argument, of the sort that was mentioned already, that append() is totally fine because if you would like to do LargeStruct[] then append() would make a copy and that's slow and you would avoid using append() then... I don't get it. You can't just preallocate a larger slice, because you might not know in advance how many elements you will want to add. In addition to wasting (not too much) time, append() also wastes space. Why do it wrong if you can do it right?

By how? As already mentioned, your Push is just as bad (if not worse).

Also, how can you be sure (without compiler optimization), that initialize the pointer

returned from your Push doesn't need extra copying?

The spec doesn't say when you do:

  *p = X{1}

it must initialize *p directly, not allocate X{1} somewhere and then copy to *p.

(or put it another way, without proper compiler optimization, you simply can't

say Push is more efficient than append)

So if you disregard implementation here, I fail to see how Push could be

conceptually more efficient than append.

[szt...@gmail.com]

Hi,

W dniu czwartek, 16 stycznia 2014 08:24:17 UTC+1 użytkownik minux napisał:

On Thu, Jan 16, 2014 at 2:05 AM, <szt...@gmail.com> wrote:

W dniu czwartek, 16 stycznia 2014 07:47:57 UTC+1 użytkownik minux napisał:

The signature of append is this:

func append(slice []Type, elems ...Type) []Type

This is only a conceptual signature for append, append is a compiler builtin function, which

means that the compiler can blend the normal rules. 

The conceptual signature should still make sense when you for a moment forget that a compiler exists and just think on the level of the programming language as an abstract thing, it should adequately describe the semantics of append(). Why would append do a copy of each of elems before execution? And yet that's what the signature of append() says it does, according to go language spec. Are you saying the signature of append can say anything because it's a builtin and the compiler will anyway interpret it whatever way it wants?

the signature is just for reference how you can use append, not how append take those arguments

because it's a builtin function, not a normal function.

The spec says:

"The built-in functions do not have standard Go types, so they can only appear in call expressions; they cannot be used as function values."

And the "call expressions" section says, as I mentioned:

"In a function call, the function value and arguments are evaluated in the usual order. After they are evaluated, the parameters of the call are passed by value to the function and the called function begins execution."
 

All arguments are non-pointer values, and I think this signature was meant to suggest that none of the elems will be modified by append, because the appends *function body* will just copy the element to the underlying array. But this is what the go specification says about function calls:

"In a function call, the function value and arguments are evaluated in the usual order. After they are evaluated, the parameters of the call are passed by value to the function and the called function begins execution."

you're still mixing the semantics of one statement and the actual implementation of that statement.

as long as the behavior visible to the user is the same, the implementation is free to do whatever it want.

Also, as I said above, append is not a normal function (you can't define your own append in Go, so this

paragraph actually might not describe what happens when you call the builtin function append.

I am not mixing anything, that's how the signature of append describes what append does according to the language spec,

also, that signature is actually not correct. because you can append a string to a byte slice.

if the compiler does something else, it only makes things even more messy to understand. In case of Go, language concepts happen to intersect with some implementation details, as you have seen the language spec explicitly mentions that a copy is being made before function body execution.

My point is you can't discuss performance of a language by looking at the spec.

Also, you are actually wrong to cite the function call section of the spec, because at the start

of that section, it says:

   "Given an expression f of function type F,"

Does append fits this requirement? what the function type of append?

Also, if it's a function, then you can assign to a variable, can you do this in Go?

    f := append

That's what the spec says, see above.
 

So it is conceptually wrong to use a non-pointer value argument to suggest that there will be a copy made in the function

you keep mention conceptually. conceptually everything must be allocated on heap, how does that sound?

it's actually an optimization to allocate object on stack when it doesn't escape.

Pointer and non-pointer values are concepts of the language, the heap is not, neither is the stack, it's not even mentioned once in the spec.
 

So why you analyze the performance of a conceptual thing? Discussing performance implicitly means

an implementation, and having an implementation means give concrete meanings to all concepts.

The conceptual thing happens to refer to what the computer does.
 

*body*, the copy takes place before function execution. A call-by-value means making a copy on the stack of the function called, before the function is at all executed, if you at all care about keeping clear semantics. So append to stay efficient 

and conceptually clear should take pointers for the elements to be appended, so if you are appending an array of float64, *[]float64, a pointer to an array of float64, not a stack-copy of an array of float64. To express more specifically what happens to the appended elements, append should really take a pointer to a constant, but Go doesn't have const as I understand. In general, as said earlier, I think append should only handle concatenating elements already allocated earlier, and there should be a new primitive that would, just like append, ensure the array underlying the slices has room for one more element, reallocate to a new memory place if needed, and return a pointer to the next "free" element of the array. This is the best way to express the idea of adding a new element to a slice using the zoo of concepts Go has.

because you based all this arguments on false assumptions, they are false.

No, they are not false, you guys just keep using this "appeal to compiler" to justify a language flaw. It's unbelievably

What is the flaw of append?

Performance? No, you can discuss the performance without making reference to an implementation,

and that's why we keep mention compiler here.

The flaw is that the signature of append does not reflect the semantics of append. Another flaw is that with append() as the only primitive available for adding thing to the slice, it might never be possible to optimize the case of initializing a new element directly in the slice.
 

irritating, because A) this is a flaw regardless of whatever the compiler does, B) the compiler does not optimize this currently, and might never be able to for 100% of the cases, as was discussed.
 

The current approach wastes time, space, and is confusing the concepts of the language.

the Push you mentioned isn't better, besides it's much harder to use.

for example, how to do append(s, a1, a2, a3)?

do you need to Push multiple times? Or have a Push that can return any number of pointers?

How you could write that line in terms of your Push?

I have already mentioned that you should distinguish between the case of concatenating slices, for which append with a pointer argument for elems would be OK, and the case of initializing a new element in the slice. Push() is meant to fix the issues append() has with the latter case.

OK, let's discuss how you can use Push to write:

append(s1, X{1}, X{2})

Push as you proposed can only initialize one element, which IMO is the flaw.

(also, you failed to consider that allocating new slice already zeros the slice,

so it actually doesn't reduce the amount of unnecessary memory initialization,

be it zeroing or copying another non-zero value)

 

First of all, I have actually benchmarked Push() against append() and it is 20% faster. This is what happens when using append() (judging by its signature) to put a new element at the end of the underlying array:

- You have to allocate the struct somewhere before passing it to append (first unnecessary copy)

- You pass the struct by value to append (another unnecessary copy)

- Append moves the array to another memory location if necessary, zeroing the memory and copying the old array to a new place

- Finally the the struct is copied to its final destination

When using Push:

- The underlying array is moved to another memory location if necessary, zeroing the memory and copying the old array to a new place

- You get a pointer to the first free element

- You initialize the memory directly using the pointer

The zeroing happens both in Push() and in append(), and append() does two copies on top of that, judging by the signature, and judging by it's real world performance it definitely does something more because it's significantly slower.

Cheers,
Jarosław Rzeszótko

 

 

[szt...@gmail.com]

Hi,

In addition to what I just said in another post, you can use the pointer directly:

p.Field1 = 1
p.Field2 = "foo"
for i := 0; i < 100; i += 1 {
  p.Field3[i] = i
}
...

And it actually *is* more efficient.

Cheers,
Jarosław Rzeszótko

[Jan Mercl]

On Thu, Jan 16, 2014 at 8:26 AM, <szt...@gmail.com> wrote:
> append() is just intellectually ugly to me, that's all, and I am very
> surprised people here are defending it almost fanatically like it's a gift
> from the elders or something, I thought at least one person will simply

> agree with me ...

There's always a slight chance that no one agreeing with a claim might
indicate the claim is wrong.

-j

[szt...@gmail.com]

W dniu czwartek, 16 stycznia 2014 08:34:24 UTC+1 użytkownik minux napisał:

Here is foo.go:

package main

const loops = 100
const elements = 10000
const ints = 1000

type X struct {
    Data [ints]int
}

func Push(slice []X) (nslice []X, nstruct *X) {
    l := len(slice)
    nslice = slice
    if(l == cap(slice)) {
        nslice = make([]X, l, cap(slice)*2)
        copy(nslice, slice)
    }
    nslice = nslice[0:l+1]
    return nslice, &nslice[l]
}

func main() {
    for i := 0; i < loops; i++ {
        slice := make([]X, 0, elements)

        for j := 0; j < elements; j++ {            
            var x *X
            slice, x = Push(slice)
            for j := 0; j < ints; j++ {
                x.Data[j] = j
            }
        }
    }
}

And here is foo2.go:

package main

const loops = 100
const elements = 10000
const ints = 1000

type X struct {
    Data [ints]int
}

func main() {
    for i := 0; i < loops; i++ {
        slice := make([]X, 0, elements)

        for j := 0; j < elements; j++ {
            var x X
            for k := 0; k < ints; k++ {
                x.Data[k] = k
            }
            slice = append(slice, x)
        }
    }
}

foo.go is consistently 20-25% faster on my computer, when testing with "time go run foo.go" and "time go run foo2.go". The constants might need to be adjusted on another computer to make things fit in memory, but the relative difference should be about the same.

Cheers,
Jarosław Rzeszótko

[szt...@gmail.com]

Hi,

I am open to that possibility, but so far I am not convinced, I am not convinced that the compiler can optimize this away if there isn't another primitive introduced, and I am not convinced that append() has a signature that describes accurately what it does. It's a small little quirk, I am aware of this, but I was hoping for an informed technical discussion, whereas it seems to be more about proving oneself superior, or the Go language somehow exempt from criticism, e.g. if you point out a perceived flaw in the language, you get a knee-jerk reaction of being pointed to tutorials, accused of ignorance of basic facts etc.

Cheers,
Jarosław Rzeszótko

[RickyS]

I think that in the case of the straight-line code you gave us, the original slice should have been made with extra space, (see the make builtin) and then you should write directly to the next unused cell (near the end).    The slice variable has a constant size, it does not get bigger when you append to the slice.  The slice variable has a pointer, a length and a capacity.  It is small enough to be passed by value to a function.  So that the contents of the array are passed by reference when the slice is passed by value.

In more complex code, you can enquire of the capacity and length of the slice, and and find out whether you need to extend the slice before creating your "Fourth" structure.

Or you can extend an existing slice by as much as you want using something like this form:

a = append(a, make([]T, j)...)
Then your code can continue to enquire and place elements into the already-allocated space.

[szt...@gmail.com]

Hi,

You must separate the benchmark program from the types of real code that might be affected by the issue. In this benchmark I allocate the slice to be of constant length, and use append despite, to isolate out the impact of the mechanics of append with respect to growing the slice, and to only measure the impact of the way parameters are passed. The real problem is in the case where I don't know the number of elements that slice will have at compile time, but the benchmark gives more insight into the issue as it is. If you use for example loops=2, elements=2, and experiment with the largest possible value of ints with which the program will run correctly, you will also see that the version of append() runs out of memory before the version with Push() does.

Cheers,
Jarosław Rzeszótko

[Dan Kortschak]

Can you demonstrate this please?

[szt...@gmail.com]

Hi,

It's the same "benchmark" with different settings, so:

package main

const loops = 2
const elements = 2
const ints = 100 000 000

type X struct {
    Data [ints]int
}

func Push(slice []X) (nslice []X, nstruct *X) {
    l := len(slice)
    nslice = slice
    if(l == cap(slice)) {
        nslice = make([]X, l, cap(slice)*2)
        copy(nslice, slice)
    }
    nslice = nslice[0:l+1]
    return nslice, &nslice[l]
}

func main() {
    for i := 0; i < loops; i++ {
        slice := make([]X, 0, elements)

        for j := 0; j < elements; j++ {           
            var x *X
            slice, x = Push(slice)
            for j := 0; j < ints; j++ {
                x.Data[j] = j
            }
        }
    }
}

And:

package main

const loops = 2
const elements = 2
const ints = 100 000 000

type X struct {
    Data [ints]int
}

func main() {
    for i := 0; i < loops; i++ {
        slice := make([]X, 0, elements)

        for j := 0; j < elements; j++ {
            var x X
            for k := 0; k < ints; k++ {
                x.Data[k] = k
            }
            slice = append(slice, x)
        }
    }
}

ints = 100 000 000 is what it takes on my computer for the append() version to crash, while Push() continues to work, the setting will likely be different for someone else.

Cheers,
Jarosław Rzeszótko

[Dan Kortschak]

Yeah. You probably shouldn't be doing that with append. I find my bicycle causes me problems when I ride against traffic too.

--

[szt...@gmail.com]

Good your feeling good about yourself. But you do understand this is a benchmark that tries to isolate a single aspect and measure its performance impact? You typically do not know the size of the array to allocate it in advance. The same problem can easily happen in a real world scenario, but would not make for a fair benchmark.

Cheers,
Jarosław Rzeszótko

[Jan Mercl]

On Thu, Jan 16, 2014 at 10:13 AM, <szt...@gmail.com> wrote:
> Hi,
>
> It's the same "benchmark" with different settings, so:
>
> package main
>
> const loops = 2
> const elements = 2
> const ints = 100 000 000
>
>
> type X struct {
> Data [ints]int
> }

Okay, so now the argument is that passing a [100 million]integer array
by value is less efficient than passing a pointer to the same?

Please.

-j

[szt...@gmail.com]

Hi,

You people here kept saying that the compiler can optimize it away, that it's only pass-by-value at the signature level and what really happens is completely optimal, there is no way to do it faster etc., and now you are ridiculing my point by saying it's obvious it will be faster when passing a pointer? Yes, it is obvious, why is then the only concise primitive available for appending to an array doing it, when there is a way that is as concise and more space- and time- efficient? This is despicable.

Cheers,
Jarosław Rzeszótko

[szt...@gmail.com]

And Push() is not passing a pointer to the array, passing a pointer to the array to append would still be bad because the array would have to be allocated somewhere first, you want a primitive to let you create it exactly where it will later be stored.

Cheers,
Jarosław Rzeszótko

[Jan Mercl]

On Thu, Jan 16, 2014 at 10:36 AM, <szt...@gmail.com> wrote:
> You people here kept saying that the compiler can optimize it away, that
> it's only pass-by-value at the signature level and what really happens is
> completely optimal, there is no way to do it faster etc., and now you are
> ridiculing my point by saying it's obvious it will be faster when passing a
> pointer? Yes, it is obvious, why is then the only concise primitive
> available for appending to an array doing it, when there is a way that is as
> concise and more space- and time- efficient? This is despicable.

Show us _one_ well written piece of Go code which passes [100
million]int arrays by value to append and we could consider this
discussion rational again.

-j

[Dan Kortschak]

That's entirely untrue. In that example you know the size of the object at compile time; ints is a constant,... and it's ridiculously latge to be copying around. if you make foolish tests, you'll get meaningless answers.

[szt...@gmail.com]

Hi,

This answer is what is foolish. Do you suggest I create an "undeterministic benchmark" ? A benchmark by its nature is a simplification of a real situation, and the benchmark I posted measures what would happen if someone wrote a program, not knowing how many elements will be appended to a slice, and if someone else than proceeded to put into it a certain amount of structs of a certain size.

Cheers,
Jarosław Rzeszótko

[szt...@gmail.com]

Hi,

The benchmark has to fix certain numbers to be able to meaningfully compare between the two programs, if you just stop and think about it for just one minute before posting the next response about how I should use Go features better, you will easily see that the problem illustrated can occur in a real program. 95% of the time you don't know at compile time how many elements to allocate, and have to allocate a new larger array and copy the contents of the old one to the new as you go and encounter new inputs, so you use append. My benchmark measures how well append() handles such a scenario under the assumption that a certain number of elements of certain size are in effect finally appended. The point that in the benchmark program you could directly access the j-th element of the slice and initialize it is irrelevant, because the moment you do it the benchmark stops measuring anything interesting.

It's just glitch, it's already not worth the time this discussion took, but the kind of response I get here, it's just ridiculous. It's like an all time ongoing competition in who will first show the OP is an idiot who doesn't know how to use the language, without doing any serious attempt at understanding what's being said. It took away any sympathy I had for the Go language itself.

Cheers,
Jarosław Rzeszótko

[Konstantin Khomoutov]

On Thu, 16 Jan 2014 00:09:00 -0800 (PST)
szt...@gmail.com wrote:

> Here is foo.go:
[...]
> And here is foo2.go:
[...]

Here is append_test.go which contains both your code
(only modified to be "benchmarkable" by the `go test`)
and the code which appends a byte using both your "pass-by-reference"
approach and built-in append():

----8<----
package append

import "testing"

const elements = 10000
const ints = 1000

type X struct {
Data [ints]int
}

func PushX(slice []X) (nslice []X, nstruct *X) {

l := len(slice)
nslice = slice

if l == cap(slice) {

nslice = make([]X, l, cap(slice)*2)
copy(nslice, slice)
}
nslice = nslice[0 : l+1]
return nslice, &nslice[l]
}

func PushByte(slice []byte) (nslice []byte, nstruct *byte) {

l := len(slice)
nslice = slice

if l == cap(slice) {
nslice = make([]byte, l, cap(slice)*2)

copy(nslice, slice)
}
nslice = nslice[0 : l+1]
return nslice, &nslice[l]
}

func BenchmarkPushX(b *testing.B) {
for i := 0; i < b.N; i++ {

slice := make([]X, 0, elements)

for j := 0; j < elements; j++ {
var x *X

slice, x = PushX(slice)

for j := 0; j < ints; j++ {
x.Data[j] = j
}
}
}
}

func BenchmarkAppendX(b *testing.B) {
for i := 0; i < b.N; i++ {

slice := make([]X, 0, elements)

for j := 0; j < elements; j++ {
var x X
for k := 0; k < ints; k++ {
x.Data[k] = k
}
slice = append(slice, x)
}
}
}

func BenchmarkPushByte(b *testing.B) {
for i := 0; i < b.N; i++ {
slice := make([]byte, 0, elements)

for j := 0; j < elements; j++ {

var p *byte
slice, p = PushByte(slice)
*p = 0xff
}
}
}

func BenchmarkAppendByte(b *testing.B) {
for i := 0; i < b.N; i++ {
slice := make([]byte, 0, elements)

for j := 0; j < elements; j++ {

var b byte
b = 0xff
slice = append(slice, b)
}
}
}
----8<----

And here are the results:

append% go test -bench . -benchtime 10s
testing: warning: no tests to run
PASS
BenchmarkPushX 1000 28490870 ns/op
BenchmarkAppendX 500 36131226 ns/op
BenchmarkPushByte 200000 95168 ns/op
BenchmarkAppendByte 500000 57829 ns/op
ok append 102.651s

Calculating ratios:

append% bc -q
scale=2
28490870/36131226
.78
95168/57829
1.64
quit

Here's the runtime info:

append% go version
go version go1.2 linux/386

append% grep -i 'model name' /proc/cpuinfo
model name : Intel(R) Core(TM)2 Duo CPU E7500 @ 2.93GHz
model name : Intel(R) Core(TM)2 Duo CPU E7500 @ 2.93GHz

The end result is: you artifically demonstrated a pathological
case for which your custom approach works better.
I demonstrated you that appending bytes using stock append()
works faster, and doing this *is* very common.

What to take from this? "There's no silver bullet." [1]
Built-in append() works OK for a broad range of cases on
recent hardware. Basically every data type instances of which
has size <= unsafe.Sizeof(unitptr) will work faster with append()'s
"pass by value" than with yours "pass via pointer".
If you've profiled your program and identified append() is
a bottleneck, you either start to store pointers to objects
in your slice instead of objects themselves or write custom
code like you did.
I don't see anything wrong with this -- Go is way more closer
to C than to, say, C++ in this regard: what you see in the code
is what you get. This allows you to fine-tune your approach
to managing data rather than jump around the compiler trying
to hint it somehow to do that. You will see this approach in
Go almost everywhere: is strives to do simple things fast and
simple and complex things possible, trying to have no places
with hidden performance costs (with notable exceptions like GC
and type conversions from []byte to string). But again, [1].

Now can we pretty please end this discussion?

1. http://en.wikipedia.org/wiki/No_Silver_Bullet

[Jan Mercl]

On Thu, Jan 16, 2014 at 11:06 AM, <szt...@gmail.com> wrote:
>> Show us _one_ well written piece of Go code which passes [100
>> million]int arrays by value to append and we could consider this
>> discussion rational again.
>>
>> -j
>
>
> The benchmark has to fix certain numbers to be able to meaningfully compare
> between the two programs, if you just stop and think about it for just one
> minute before posting the next response about how I should use Go features
> better, you will easily see that the problem illustrated can occur in a real
> program.

Where can I see such "real" program? Do experienced Go programmers
really write code appending [100 million]int elements by value?

> 95% of the time you don't know at compile time how many elements to
> allocate, and have to allocate a new larger array and copy the contents of
> the old one to the new as you go and encounter new inputs, so you use
> append. My benchmark measures how well append() handles such a scenario
> under the assumption that a certain number of elements of certain size are
> in effect finally appended. The point that in the benchmark program you
> could directly access the j-th element of the slice and initialize it is
> irrelevant, because the moment you do it the benchmark stops measuring
> anything interesting.

I suggest to research using real Go code bases like for example the
stdlib. You'll find that elements of slices tend to be typically in
several orders of magnitude smaller than the unreal example of [100
million]int. Next step is to realize that the design of append is
optimized for the/such _majority_ of uses and it thus will not
necessarily scale to _every possible_ use. Yet another step would be,
in theory, that if append would have been designed for typical use of
appending a [100 million]int element, then it quite probably would
have been designed taking a element's pointer.

On the opposite, designing it taking a pointer would probably hurt
many, if not most of the cases where the element is really small. Like
byte or few bytes. Which you can see happening all over the code in
the wild. And if it's more than few bytes it's probably the case of
appending a []byte, so the value is just three words.

> It's just glitch, it's already not worth the time this discussion took, but
> the kind of response I get here, it's just ridiculous. It's like an all time
> ongoing competition in who will first show the OP is an idiot who doesn't
> know how to use the language, without doing any serious attempt at
> understanding what's being said. It took away any sympathy I had for the Go
> language itself.

I don't know why discussion "metadata" are being repeatedly discussed
by you, but I see others as focused on the technical side of the
"problem" as possible. I don't recall anyone else here is concerned
about something being 'ridiculous', about 'sympathy' and other
non-technical issues.

I, for one, think that the OP claims are technically wrong and the
later attempts to render them correct by unreal examples don't make it
any better. Also, I think that if you're gonna, by chance, code in Go
for some time, you'll find using append often; while it typically will
not be an unnecessary and/or avoidable bottleneck of your programs.

-j

[Nico]

Actually, I think a fairer comparison wouldn't use append(). See below:

package main

const loops = 2
const elements = 2
const ints = 100000000

type X struct {
Data [ints]int
}

func main() {
for i := 0; i < loops; i++ {
slice := make([]X, 0, elements)

for j := 0; j < elements; j++ {

slice = slice[:j+1]
x := &slice[j]

[Nico]

To be more clear the comparison you suggested is a case where I think
the use of append() is justified.

[Mateusz Czapliński]

On Thu, Jan 16, 2014 at 6:05 PM, <szt...@gmail.com> wrote:

The conceptual signature should still make sense when you for a moment forget that a compiler exists and just think on the level of the programming language as an abstract thing, it should adequately describe the semantics of append(). Why would append do a copy of each of elems before execution?

And why would it not? If I don't care about computer internals ("efficiency"), from mathematical point of view presence of intermediate copy is irrelevant to the result. If I *do* care about computer internals, I do care about *full depth* of the toolchain, including optimizations, I don't see why should I stop in the middle of the road; and then, copy by value may be often actually more efficient today, for example because of cache locality. Or may not. But I shall not care anyway until I actually measure this as performance bottleneck in a concrete real app; only then I shall search for possible optimizations.

append() is just intellectually ugly to me

append() is just intellectually pretty to me.

In real life, when I put a box on a stack of boxes, I tend to first stuff it and close it, and only then put it on top of the stack. I rarely do opposite (i.e. put the box on stack top, then fill, then close). This matches the current syntax of append() for me, and is intellectually simpler to me, also through separation of concerns and more "functional" approach.

Also, append() has some more advantages for me over Push as described above, including that I can easily, without necessity of intermediate values, express with it many things, including:

    vec = append(vec, Foo{
        Bar: "bar",
        Baz: "baz",
    }, Foo{
        Bar: "bar2",
        Baz: "baz2",
    })

and common slice operations (although they tend to often be overly verbose still): https://code.google.com/p/go-wiki/wiki/SliceTricks

I tried here to discuss with your concerns about "concept" as I could understand it (thus the "boxes" metaphor). I've seen also concerns about efficiency/optimizations/implementation - I'm not sure which of those are actually more important to you in this discussion; it might, I believe, be good idea for easier discussion to focus on one concern, if one is most important, or to list them all explicitly and separately.

Just my $0.02, anyway. I have no affiliation etc.

/M.

[szt...@gmail.com]

Hi,

W dniu czwartek, 16 stycznia 2014 11:40:03 UTC+1 użytkownik Konstantin Khomoutov napisał:

The end result is: you artifically demonstrated a pathological
case for which your custom approach works better.
I demonstrated you that appending bytes using stock append()
works faster, and doing this *is* very common.

Why do you say I demonstrated it "artifically"? I said all the time from the start it's just a little quirk, and I am curious about the rationale, and all the way until this point people have in various way denied it's at all an issue, and were pointing me to Go tutorials. In my opinion doing append() with individual bytes is much more common in low level library code than in user code. In user code you typically have slices of larger objects, and for that case, which I would argue is also very commond, append() wastes memory and time. I don't think it's that difficult to find real go programs that waste a fair bit of memory by coping structs to append().

What to take from this?  "There's no silver bullet." [1]
Built-in append() works OK for a broad range of cases on
recent hardware.  Basically every data type instances of which
has size <= unsafe.Sizeof(unitptr) will work faster with append()'s
"pass by value" than with yours "pass via pointer".
If you've profiled your program and identified append() is
a bottleneck, you either start to store pointers to objects
in your slice instead of objects themselves or write custom
code like you did.

 
That's getting much more reasonable that the rest of the discussion, but I am not sold on the fact that the case of size < sizeof(uniptr) is really so much more common. That's the kind of discussion I was hoping for.

Cheers,
Jarosław Rzeszótko

[szt...@gmail.com]

Hi,

W dniu czwartek, 16 stycznia 2014 11:43:27 UTC+1 użytkownik Jan Mercl napisał:

On Thu, Jan 16, 2014 at 11:06 AM,  <szt...@gmail.com> wrote:
>> Show us _one_ well written piece of Go code which passes [100
>> million]int arrays by value to append and we could consider this
>> discussion rational again.
>>
>> -j
>
>
> The benchmark has to fix certain numbers to be able to meaningfully compare
> between the two programs, if you just stop and think about it for just one
> minute before posting the next response about how I should use Go features
> better, you will easily see that the problem illustrated can occur in a real
> program.

Where can I see such "real" program? Do experienced Go programmers
really write code appending [100 million]int elements by value?

It's really clear that you want to somehow "win" the discussion and are not interested in a fair discussion of the tradeoffs, that I was hoping for. You have denied all the way until now this is at all an issue.
 

> 95% of the time you don't know at compile time how many elements to
> allocate, and have to allocate a new larger array and copy the contents of
> the old one to the new as you go and encounter new inputs, so you use
> append. My benchmark measures how well append() handles such a scenario
> under the assumption that a certain number of elements of certain size are
> in effect finally appended. The point that in the benchmark program you
> could directly access the j-th element of the slice and initialize it is
> irrelevant, because the moment you do it the benchmark stops measuring
> anything interesting.

I suggest to research using real Go code bases like for example the
stdlib. You'll find that elements of slices tend to be typically in
several orders of magnitude smaller than the unreal example of [100
million]int. Next step is to realize that the design of append is
optimized for the/such _majority_ of uses and it thus will not
necessarily scale to _every possible_ use. Yet another step would be,
in theory, that if append would have been designed for typical use of
appending a [100 million]int element, then it quite probably would
have been designed taking a element's pointer.

I used an extreme case to illustrate the issue. I don't see it as clear-cut that appending bytes is more common that appending larger structs. Do you think a 100MB of data going through append is so uncommon? Is it fine to throw away 100MB for the duration of the function?
 

On the opposite, designing it taking a pointer would probably hurt
many, if not most of the cases where the element is really small. Like
byte or few bytes. Which you can see happening all over the code in
the wild. And if it's more than few bytes it's probably the case of
appending a []byte, so the value is just three words.

Well, would it? The benchmark of appending bytes to the slices that was just posted seems artificial, because the byte is directly embedded in the source code, and likely the compiler optimizes it so the byte isn't copied.
 

> It's just glitch, it's already not worth the time this discussion took, but
> the kind of response I get here, it's just ridiculous. It's like an all time
> ongoing competition in who will first show the OP is an idiot who doesn't
> know how to use the language, without doing any serious attempt at
> understanding what's being said. It took away any sympathy I had for the Go
> language itself.

I don't know why discussion "metadata" are being repeatedly discussed
by you, but I see others as focused on the technical side of the
"problem" as possible. I don't recall anyone else here is concerned
about something being 'ridiculous', about 'sympathy' and other
non-technical issues.

I, for one, think that the OP claims are technically wrong and the
later attempts to render them correct by unreal examples don't make it
any better. Also, I think that if you're gonna, by chance, code in Go
for some time, you'll find using append often; while it typically will
not be an unnecessary and/or avoidable bottleneck of your programs.

I have heard by now that I am "riding my bicycle backwards", that I am "reinventing the wheel", been pointed to a bunch of Go tutorials, and it was denied that any issue at all exist unitl now. It took 80 responses to get someone to actually admit that there is a tradeoff in append(). That reflects rather poor on the culture around here.

Cheers,
Jarosław Rzeszótko

[Nico]

Correction:

To be more clear, the comparison you suggested is a case where I think
the use of append() is *not* justified.


Sorry about the noise.

[szt...@gmail.com]

Hi,

W dniu czwartek, 16 stycznia 2014 12:00:56 UTC+1 użytkownik Mateusz Czapliński napisał:

On Thu, Jan 16, 2014 at 6:05 PM, <szt...@gmail.com> wrote:

The conceptual signature should still make sense when you for a moment forget that a compiler exists and just think on the level of the programming language as an abstract thing, it should adequately describe the semantics of append(). Why would append do a copy of each of elems before execution?

And why would it not? If I don't care about computer internals ("efficiency"), from mathematical point of view presence of intermediate copy is irrelevant to the result. If I *do* care about computer internals, I do care about *full depth* of the toolchain, including optimizations, I don't see why should I stop in the middle of the road; and then, copy by value may be often actually more efficient today, for example because of cache locality. Or may not. But I shall not care anyway until I actually measure this as performance bottleneck in a concrete real app; only then I shall search for possible optimizations.

From mathematical point of view computations typically don't last any time, from a practical one they do. It's about the ease of which you can map the language concepts to what actually will happen. If the language has a concept of a pointer, the sense of which pretty much boils down to not making a copy on function call, and a concept of pass-by-value, I would like the signature of append to reflect what is being done and use a pointer. Much more importantly, as I have said many times by now, it probably is impossible to completely optimize this given the current semantics of append.

append() is just intellectually ugly to me

append() is just intellectually pretty to me.

In real life, when I put a box on a stack of boxes, I tend to first stuff it and close it, and only then put it on top of the stack. I rarely do opposite (i.e. put the box on stack top, then fill, then close). This matches the current syntax of append() for me, and is intellectually simpler to me, also through separation of concerns and more "functional" approach.

That's a fair point, but given the rest of Go, you are given the choice between a surface-level more intuitive but semantically somehow strange append(), and a more efficient and easier to understand to the last detail Push(). You can easily see by reading this discussing that understanding the details of append() is not at all easy.
 

Also, append() has some more advantages for me over Push as described above, including that I can easily, without necessity of intermediate values, express with it many things, including:

    vec = append(vec, Foo{
        Bar: "bar",
        Baz: "baz",
    }, Foo{
        Bar: "bar2",
        Baz: "baz2",
    })

and common slice operations (although they tend to often be overly verbose still): https://code.google.com/p/go-wiki/wiki/SliceTricks

I tried here to discuss with your concerns about "concept" as I could understand it (thus the "boxes" metaphor). I've seen also concerns about efficiency/optimizations/implementation - I'm not sure which of those are actually more important to you in this discussion; it might, I believe, be good idea for easier discussion to focus on one concern, if one is most important, or to list them all explicitly and separately.

Just my $0.02, anyway. I have no affiliation etc.

/M.

I am not suggesting removing append. I think perhaps having another primitive would be nice. And I was interested in the rationale for the design, and only now I got some reasonable answers.

Cheers,
Jarosław Rzeszótko

[Jan Mercl]

On Thu, Jan 16, 2014 at 12:17 PM, <szt...@gmail.com> wrote:

While I don't agree about the meta-discussion remarks (eg. Dan din't
wrote that _you_ are riding the bicycle backwards, that's simply not
true), let me just ignore that part.

Show us real code written by an experienced Go programmer which
demonstrates what the OP claims to be a problem. Unless such code
exists, such claim is by definition about a non problem. It's IMHO
that simple.

And showing us unreal code written only to demonstrate something which
doesn't actually happen in the wild is perhaps not going to convince
many.

-j

PS: Persons do not really win discussions. Truth may. Occasionally ;-)

[Gustavo Niemeyer]

On Thu, Jan 16, 2014 at 9:17 AM, <szt...@gmail.com> wrote:
> I have heard by now that I am "riding my bicycle backwards", that I am
> "reinventing the wheel", been pointed to a bunch of Go tutorials, and it was
> denied that any issue at all exist unitl now. It took 80 responses to get
> someone to actually admit that there is a tradeoff in append(). That
> reflects rather poor on the culture around here.

To me, on the contrary, it actually feels rather amazing how much
patience and respect most people have offered you while explaining
such a trivial point, while you clearly demonstrate unwillingness to
listen, to reflect, and lack of any trivial empathy. The fact the
group responds with reason to such attitude is remarkable.


gustavo @ http://niemeyer.net

[szt...@gmail.com]

Hi,

Take a look at src/pkg/go/parser/parser.go, e.g. those two functions:

// Consume a group of adjacent comments, add it to the parser's
// comments list, and return it together with the line at which
// the last comment in the group ends. A non-comment token or n
// empty lines terminate a comment group.
//
func (p *parser) consumeCommentGroup(n int) (comments *ast.CommentGroup, endline int) {
    var list []*ast.Comment
    endline = p.file.Line(p.pos)
    for p.tok == token.COMMENT && p.file.Line(p.pos) <= endline+n {
        var comment *ast.Comment
        comment, endline = p.consumeComment()
        list = append(list, comment)
    }

    // add comment group to the comments list
    comments = &ast.CommentGroup{List: list}
    p.comments = append(p.comments, comments)

    return
}

// Consume a comment and return it and the line on which it ends.
func (p *parser) consumeComment() (comment *ast.Comment, endline int) {
    // /*-style comments may end on a different line than where they start.
    // Scan the comment for '\n' chars and adjust endline accordingly.
    endline = p.file.Line(p.pos)
    if p.lit[1] == '*' {
        // don't use range here - no need to decode Unicode code points
        for i := 0; i < len(p.lit); i++ {
            if p.lit[i] == '\n' {
                endline++
            }
        }
    }

    comment = &ast.Comment{Slash: p.pos, Text: p.lit}
    p.next0()

    return
}

It uses slices of pointers all the way over, I guess to avoid the problems we have been discussing, or is there some other explanation? The problem is that the moment you start using arrays of pointers instead of arrays of values, you loose locality of reference, and with it performance. I started this discussion because I was wondering why there isn't any language that would let you use dynamic arrays but always allocate new things directly using the memory of the array, never via pointers. You can imagine rewriting this along those lines:

func (p *parser) consumeCommentGroup(n int) (comments *ast.CommentGroup, endline int) {
    var group *ast.CommentGroup
    endline = p.file.Line(p.pos)
    for p.tok == token.COMMENT && p.file.Line(p.pos) <= endline+n {
        group = Push(comments)
        endline = p.consumeComment(group)
    }

    return
}

// Consume a comment and return it and the line on which it ends.
func (p *parser) consumeComment(group *ast.CommentGroup) (endline int) {
    // /*-style comments may end on a different line than where they start.
    // Scan the comment for '\n' chars and adjust endline accordingly.
    endline = p.file.Line(p.pos)
    if p.lit[1] == '*' {
        // don't use range here - no need to decode Unicode code points
        for i := 0; i < len(p.lit); i++ {
            if p.lit[i] == '\n' {
                endline++
            }
        }
    }

    var comment *ast.Comment;
    comment = Push(group)
    comment.Slash = p.pos
    comment.Text = p.lit

    p.next0()

    return endline
}

It might not be very pretty, it might not be very good Go, I don't know, but I think it's worthwhile to consider the possibility of a language where you can do those kinds of processing while keeping locality of reference.

Cheers,
Jarosław Rzeszótko

[szt...@gmail.com]

Hi,

What point precisely was "explained" to me? I asked a reasonable question, and as I said it took 80 responses, many of which were full of snark while simultaneously demonstrating a lack of understanding of what's being talked about, until finally now some people admitted that it at all is a valid question and that there are some tradeoffs present. I don't know where I demonstrated "lack of trivial empathy", whatever trivial empathy is, because I didn't say anything about anyone personally, I was just asking, in response to those snarky comments, to try to read and understand before posting knee-jerk answers, that come off as there was some obligation to "defend" the language no matter what. Guess what, I am not "attacking" Go, I try to understand one aspect of it in more depth.

Cheers,
Jarosław Rzeszótko

[Volker Dobler]

Am Donnerstag, 16. Januar 2014 13:25:51 UTC+1 schrieb szt...@gmail.com:

What point precisely was "explained" to me?  [...] that there are some 

tradeoffs present [ ... ]  I try to understand one aspect of it [Go] in more depth.

Maybe you tried to hard and thought too much about some

tiny aspect most people do not consider to be worth thinking

about it in first place.

Life is a constant series of tradeoffs and most people do not

muse too much about tiny tradeoffs which are obvious only

in special, uncommon cases.

Append works the way it works, there is no metaphysical

hidden special meaning to it and yes, everything has tradeoffs.

You now know that append might or might not make a copy,

you know that almost everyone doesn't care about this copy.

You know that sometimes, even in typical situations a copy is

faster. And you know that most of us here think that performance

is important but any type of micro-optimisation is done after

fixing the big performance staff and only after measuring.

Append works fine, it is easy to grasp, most people like it

and most probably it was not designed to reflect some

special case optimizations but to be simple to the majority

of oblivious users who do not dream of cache coherence and

stuff like that. Append is append is append and nothing more.

Use it, replace it if it is a bottleneck in your app but do not

think too much about it, it is just not worth it.

V.

 

 

[szt...@gmail.com]

Hi,

That's not a bad summary, but I cannot help myself that I happened to have that thought that there might be a way to give users cache coherence, which seems to be sort of a big deal those days, without their thinking of it, and without making the high level language less pleasant to use. It seems no popular high level language does that very well currently, and it's entertaining to see how close Go might get to it. I don't think too many people saw my point in the end, unfortunately, and your summary sounds like the good old "worse is better" philosophy (http://en.wikipedia.org/wiki/Worse_is_better). In other words, never challenge the status quo, never think too deeply about anything, don't ask too detailed questions, the life pleasures await, after all.

Cheers,
Jarosław Rzeszótko

[Abhijit Kadam]

On Wednesday, January 15, 2014 2:25:41 PM UTC+5:30, szt...@gmail.com wrote:

Hi,

W dniu środa, 15 stycznia 2014 09:36:10 UTC+1 użytkownik Abhijit Kadam napisał:

On Wednesday, January 15, 2014 1:52:49 PM UTC+5:30, andrey mirtchovski wrote:

> I think what he means is avoid the creation of temporary X{4}  that is
> created and copied to slice's array

if the underlying array has the capacity to accept "X{4}" at any
location then that memory is already allocated and the only way to
initialize it to a non-zero element is either to set the appropriate
fields explicitly or to copy a whole struct en masse.

I think he knows copy en masse happens and he is expecting former option (set  appropriate fields explicitly). This is interesting as it is imperative to me that the check for capacity code would be in append function and by that time the temporary is already created and passed to it. 

Also I see no major problem with current behavior.  

Exactly, thank you for putting in the effort to understand the question and choosing a wise interpretation and not the most naive one. That's the whole point, it's not like setting the fields explicitly and doing a copy are equivalent - the struct can potentially be large and have a large initialization cost, that will then be paid twice with the current implementation of append. I think it would potentially be interesting to be able to initialize the struct directly in the memory in which it will later be stored.

Cheers,
Jarosław Rzeszótko

Lot has happened over this thread and me not in sync however wanted to put my thought on why I think no major problem: Small objects are efficiently copied 

and we put objects in array by value to have better data locality. So that when CPU pull the data and process it things are faster. However I would be careful

with storing big objects by value in vector and rather use pointers. This is because 1) if I have to do some operation on such objects like sort I would end up moving large objects  2) other devs might write code to copy elements by value from array(slice) and do operations on that. This would end by cpu pulling all data and only reading few fields. If not copy is made and specific fields are used by algorithm then because the object being large, data locality might not be effective as we are reading addresses too far from each other(cache misses still). 3) Large struct are hard to grasp (for humans) and programming may be difficult.

On append, because it is inbuilt function compiler can optimize it as required and wherever suitable.

 

[szt...@gmail.com]

Hi,

Thank you, some of those are very interesting points that I have completely missed in my considerations. 2) only depends on what mechanisms Go offers and encourages to use, and 3) is not universally applicable, the struct might be large not because it has a lot of fields, but just because it stores a lot of data, like a large matrix or something of this kind. I completely agree though that after a certain point the locality of reference might not be the case anyway, probably depending on the particular pattern of data usage. And the point about sorting is certainly very interesting for me, in that case it seems it seems you really have to go for an array of pointers instead.

Cheers,
Jarosław Rzeszótko

[DV]

From some purely abstract, 10,000 meter-above-sea-level point-of-view, I actually agree with you that perhaps append() is somewhat "ugly". Much like how the language gives maps, channels and slices special treatment with generic programming support without extending that courtesy to user-defined types. (Just, please, don't start another giant thread on that....)

They're both "ugly" if the standard of beauty is one of the LISP dialects or Haskell or whatever, but in the end, it doesn't matter. Go is a practical language, not an academically beautiful one, and that aspect actually appeals to a lot of people. 

I am not intimately familiar with Go compiler internals and the various optimizations it does, but here's what I *do* know:

1. Unless you're not writing pathologically bad code with a purpose, Go is very, very fast. In my experience, much faster than "beautiful" languages, and I say this as a person who *loves* him some LISP/Clojure. 

2. The people who are working on the Go team are very, very smart people. They really seem to know what they're doing. Unlike other "young" languages I won't mention here that re-invent themselves every 2 years, Go, excluding some miniature warts, is really showing how well thought out it actually is when it comes to real-world code. 

3. Relax, don't fight the language, learn and accept its idioms and constructs and everything will be ok. 

On Tuesday, January 14, 2014 12:14:05 PM UTC-7, szt...@gmail.com wrote:

Hi,

I wonder whether someone here would be able to explain to me the rationale for append() being the way it is. The idiomatic way for appending a new element to a slice seems to be this:

type X struct {

        Foo int

}

slice := []X{X{1}, X{2}, X{3}}

slice = append(slice, X{4})

But if X is a larger struct, this is somewhat inefficient, since the object has to be allocated first somewhere on the heap, just to be copied a moment after to the end of the array underlying the slice. To avoid this, the way I understand it, the slice capacity has to be checked manually, the slice potentially has to be expanded, then you have to take a pointer to an empty cell in the slices array and allocate the new object directly there. So to initialize a new struct directly using the underlying array you have to write this:

slice := []X{X{1}, X{2}}

l := len(slice)

if(l == cap(slice)) {

        nslice := make([]X, cap(slice)*2)

        copy(nslice, slice)

        slice = nslice

}

slice = slice[0:l+1]

x := &slice[l]

x.Foo = 4

Maybe the compiler optimizes it, maybe commonly the performance penalty isn't big, but I still do wonder how do the Go concepts fit together in the end. Is providing a primitive that would allow to directly initialize a new object at the end of the slice somehow not possible or leading to problems? Even just conceptually, that would seem to make more sense to me, so I wonder what am I missing out. I am trying to understand the design of the language, not trying to criticize anything... Another thing I wonder about is why append is a non-destructive operation, or at least why aren't there two versions like a non-destructive "concat" and destructive "append" based on passing a pointer to the slice.

Cheers,

Jarosław Rzeszótko

[Nico]

On 16/01/14 12:10, szt...@gmail.com wrote:
> It uses slices of pointers all the way over, I guess to avoid the
> problems we have been discussing, or is there some other explanation?

I don't think that is the only or main reason to use pointers there.

In Go everything is copied by value and when this becomes a problem, one
has to be explicit and use pointers.

I think you made a good insight by noticing this "issue" about using
append() with large objects, but one should also notice that this issue
is not limited to append(), it's also an issue with everything else in Go:
- maps of large objects
- range over a slice or a map of large objects
- using large objects as function arguments
- channels of large objects
- ...

[Abhijit Kadam]

Ok, good to know. About large objects consider 'email' entity once could possibly split it into efficiently copyable 'EmailHeader' struct and 'EmailBody'. 'EmailHeader' pointing(has pointer) to EmailBody. One would prefer to have  'EmailHeader' in slice and 'EmailBody' on heap. 'EmailBody' could be big object itself (depends) just like slice. So the question should be if I have a large buffalo size object constructed in memory than do we have data locality for that struct i.e. all fields packed together? If we have even larger elephant size object then probably we are reading files and there are other techniques like memory mapped files to deal it efficiently.

[Konstantin Khomoutov]

On Thu, 16 Jan 2014 03:09:59 -0800 (PST)
szt...@gmail.com wrote:

> > The end result is: you artifically demonstrated a pathological
> > case for which your custom approach works better.
> > I demonstrated you that appending bytes using stock append()
> > works faster, and doing this *is* very common.
>
> Why do you say I demonstrated it "artifically"?

As many people said earlier in this thread, it's hard to find
Go code written by a serious programmer that would use append()
in the context similar to that you have demonstrated -- that is,
with types instances of which are this large.
It does not render your testing code "wrong" (in whatever sense
you take it to be) it just demonstrates it's artifical.

If you're not convinced, here's another example: you might write a
piece of code (in whatever language you prefer) that would try to
allocate more than 3 GiB and run it on a commodity 32-bit OS --
it's oblidged to fail but then again typical programs working on 32-bit
systems do not try to allocate that much memory all at the same time.

> I said all the time from the start it's just a little quirk, and I am
> curious about the rationale, and all the way until this point people
> have in various way denied it's at all an issue,

I'm in the same camp with those people. I was just pleased that you
have finally turned to presenting hard data and then tried to present
another set of hard data demonstrating a case of using append() pretty
opposite to yours. That wasn't to defeat your point but rather to
demonstrate with numbers the use case append() is tailored for.

> and were pointing me to Go tutorials.

My opinion on this is that this was simply an escalation of emotions.
Many people have hard time fighting elitism in theirselves (me
included) which results in a fair share of "smart ass" responses, even
though they are technically correct in my eyes. Unfortunately I should
also note that you was good at provoking that elitism being quite
persistent (to not use another word, you know) even in the face of "OK,
where's the real use cases and measurements" requests.

Another problem was side-tracking of the thread to the discussion
of semantics of the specification. No one to blame here though --
I'd say this was inevitable beause of the nature of append() which is a
builtin.

> In my opinion doing append() with individual bytes is much more
> common in low level library code than in user code.
> In user code you typically have slices of larger objects, and for
> that case, which I would argue is also very commond, append() wastes
> memory and time. I don't think it's that difficult to find real go
> programs that waste a fair bit of memory by coping structs to
> append().

I disagree. I don't know your programming background but I think you
mistakenly perceive Go as being more high-level than it really is.
I reckon you turned a blind eye to the fact slices are the lowest-level
built-in device in Go to operate dynamic arrays. That's all there is
to them; they're not kind of the only blessed container type to use
for everything, they are just type-safe calloc()/realloc() wrapped in a
nice language idiom. Please think more about this. If you know C this
might help a lot. You might use slices directly -- and this is just
the right thing to do for many cases -- or you might use them to
implement some custom behaviour, like your Push() function.
Or you might use something completely other like the container/list
standard package. Or implement intrusive lists [2]. You're the
programmer after all and are supposed to program, that is to solve a
problem at hand in a best way possible. Here, the goal of doing proper
design of a language feature is to make it useful while not getting in
your way should you need something fancy, and in my opinion, slices are
done just right in this regard, including append(): they strike a good
balance between simplicity and usability. But this supposedly can only
be appreciated if you have seriously dabbled with languages both at
lower and higher levels than Go and understand where it fits this
spectrum.

Let's recap: slices provide the programmer with dynamic arrays
and have rather simple semantics to reason about. If a particular set
of requirements for managing data starts to look like being unfit for
using slices directly, a programmer might use certain techniques to
solve this problem -- storing in a slice pointers to values allocated
elsewhere or using in-place initialization like you've proposed.

> > What to take from this? "There's no silver bullet." [1]

[...]

> That's getting much more reasonable that the rest of the discussion,
> but I am not sold on the fact that the case of size < sizeof(uniptr)
> is really so much more common. That's the kind of discussion I was
> hoping for.

Thank you.

2. http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists

[szt...@gmail.com]

Hi,

W dniu czwartek, 16 stycznia 2014 16:42:00 UTC+1 użytkownik Konstantin Khomoutov napisał:

On Thu, 16 Jan 2014 03:09:59 -0800 (PST)
szt...@gmail.com wrote:

> > The end result is: you artifically demonstrated a pathological
> > case for which your custom approach works better.
> > I demonstrated you that appending bytes using stock append()
> > works faster, and doing this *is* very common.
>
> Why do you say I demonstrated it "artifically"?

As many people said earlier in this thread, it's hard to find
Go code written by a serious programmer that would use append()
in the context similar to that you have demonstrated -- that is,
with types instances of which are this large.
It does not render your testing code "wrong" (in whatever sense
you take it to be) it just demonstrates it's artifical.

If you're not convinced, here's another example: you might write a
piece of code (in whatever language you prefer) that would try to
allocate more than 3 GiB and run it on a commodity 32-bit OS --
it's oblidged to fail but then again typical programs working on 32-bit
systems do not try to allocate that much memory all at the same time.

I demonstrated an extreme case to illustrate the issue where it is clearly visible. It does not mean it does not happen in other scenarios, it's just not easy to come up with another example that would prove beyond doubt what happens. My simplistic way of thinking was this: a processor cache can hold even 8MB of data those days. So certainly one might imagine it makes sense to keep 8MB of data in a single struct, packed together, without a single pointer, to have this locality of reference thing. Imagine that then you have a loop and you pack 200 of those 8MB objects somewhere, one after another. append() generates a copy of each of those objects, and the copy might not get cleaned up for a while, so you are potentially wasting a few hundred MBs of memory for a while. If you don't want to have pointers, and don't want to use append, you end up rolling Push(), and you have to roll it for every type yourself, so I brought that up to discussion. And Push() is clunky, could you improve it, could you improve the language to make the efficiency issues be solved optimally without making the language harder to use or less flexible? Etc. I might be wrong, I just don't think it's trivial, and I think it's an interesting exercise to think of those issues, even if they turn out to no be that important in the end. It's more interesting if you step out for a while from being completely fixated only on Go and think of the general issues, I didn't want to participate in any language wars. I did now receive interesting responses for which I am grateful, and have certainly learnt things in the process.
 

> I said all the time from the start it's just a little quirk, and I am
> curious about the rationale, and all the way until this point people
> have in various way denied it's at all an issue,

I'm in the same camp with those people.  I was just pleased that you
have finally turned to presenting hard data and then tried to present
another set of hard data demonstrating a case of using append() pretty
opposite to yours.  That wasn't to defeat your point but rather to
demonstrate with numbers the use case append() is tailored for.

Frankly, I still don't understand that benchmark that shows append is better for small pieces of data, could you explain to me why it would be faster? This byte benchmark is somewhat artificial, because the bytes that are copied are byte literals, and the compiler could, at least hypothetically, easily optimize it to just a single MOV (conceptually, at least). I don't see how passing a single byte by value is, in general, different from passing it as a pointer, in the end it's anyway something like a MOV. What am I missing here?
 

I was hoping with small effort this approach could perhaps be extended to be valid for a wider variety of cases, without sacrificing anything. I actually view Go after this discussion to be higher level than I thought it is before, if you look at C, the great thing about it you can very easily interpret it in terms of what the computer does. A local variable goes on the stack, explicit allocation are on the heap, etc., you can easily almost see the assembly that will be generated, if you happen to have such a need. In Go this is no longer the case, and I wonder if the benefits those particular changes to C offer are worth it. Overall it's certainly an improvement over C, and overall I like the language a lot so far.

Cheers,
Jarosław Rzeszótko

[DisposaBoy]

This is one beautiful bridge you've built here sir. Full marks. full marks.