This came up in the discussion of #55358 and prior discussions. It would be nice to have a simple, generic way to concatenate a slice of slices.
Here's the proposed signature:
func Concat[S ~[]E, E any](dst S, slices ...S) S
Usage:
// Join slices into a new slice
a := []int{ 1, 2, 3 }
b := []int{ 4, 5, 6 }
c := slices.Concat(nil, a, b)
// c == int{ 1, 2, 3, 4, 5, 6 }
// overwrite an existing slice
a = slices.Concat(a[:0], c[0:1], c[2:3], c[4:5])
// a == int{ 1, 3, 5 }
Comment From: rittneje
a := []int{1, 2, 3}
b := []int{4}
c := slices.Concat(a[:2], b, a[2:])
What is the value of c? Depending on the order of events weird things could happen.
For example, consider the following (perhaps naive) implementation:
func Concat[S ~[]E, E any](dst S, slices ...S) S {
for _, s := range slices {
dst = append(dst, s...)
}
return dst
}
This will result in c being [1 2 4 4] which is probably unexpected.
Comment From: ericlagergren
Isn't append already generic?
Comment From: earthboundkid
Isn't
appendalready generic?
Append can't concatenate multiple slices. This means you need to jump through hoops to precalculate the capacity and to make a one-liner you end up with awkward things like append(s1, append(s2, s3...)...).
Comment From: earthboundkid
This will result in c being [1 2 4 4] which is probably unexpected.
I think it's only worth doing Concat if it does one shot preallocation, like
func Concat[S ~[]E, E any](dst S, ss ...S) S {
c := 0
for _, s := range ss {
c += cap(s)
}
dst = Grow(dst, c)
for _, s := range ss {
dst = append(dst, s...)
}
return dst
}
If you run this, you get 1, 2, 4, 3.
Comment From: rittneje
@carlmjohnson I don't think it should use cap as that could greatly overestimate the size requirement. For example, slices.Concat(nil, make([]int, 0, 1000)) should not grow the dest to 1000 elements.
Really it should be len, but that still causes problems. https://go.dev/play/p/zb1d-MhD6Pj
Comment From: earthboundkid
😅 You're right!
Comment From: earthboundkid
I think at a certain point, if the user is clobbering the slice they are reading from, it's a user error. You can probably make up an example using slices.Insert that is confusing too.
Comment From: rittneje
@carlmjohnson It would be all too easy for someone not to realize that the first parameter is special in that regard, especially because it isn't in other languages that have similar APIs. And due to the nature of append/slices.Grow it will sometimes appear to work the way they expect, meaning they might not even notice the problem until it causes some production incident.
What if it were a method instead of a function, to reinforce the fact that the first parameter is actually the output buffer?
type Buffer[T any] []T
func (buf Buffer[T]) Concat(ss ...[]T) Buffer[T] {
size := 0
for _, s := range ss {
size += len(s)
}
if size == 0 {
return buf
}
buf = Grow(buf, len(buf)+size)
for _, s := range ss {
buf = append(buf, s...)
}
return buf
}
(This type name is just for example purposes.)
Then it would be slices.Buffer[int](a).Concat(b, c). For people who don't care to optimize it, they can call slices.Buffer[int](nil).Concat(a, b, c).
Comment From: earthboundkid
The objection to destination slices already applies to several functions in exp/slices: Insert, Delete, the upcoming Replace, and arguably Grow and Clip (although not as confusing as the others). If you think it's causing bugs, you should open an issue to make a v2 of the package before the current slices API gets into the standard library.
Comment From: rittneje
Yes, it is possible to break them, but it is a bit more contrived. https://go.dev/play/p/4lLBHhxrfdN
Regardless, adding a typedef with methods does not itself necessitate a v2. It just means some (or all) of the existing functions would presumably be deprecated.
Comment From: AndrewHarrisSPU
I feel like two versions of concatenation could make sense - a minimally complicated, more variadic 'Append'-like concatenation, and a profligately eager, maximally allocating 'Collect'-ing concatenation: https://go.dev/play/p/13N05VZPjwS
Comment From: earthboundkid
I don't think it makes sense to have two very similar concatenation functions.
Comment From: DeedleFake
Especially because the Append() case could be handled by allowing multiple spread operations in variadic arguments, such as append(s, a..., b..., c...).
Comment From: rittneje
@DeedleFake The Go language spec defines a... to reuse the backing slice rather than copying. Allowing multiple spread operations could not preserve this essential behavior.
Comment From: DeedleFake
It could, but only for the case of a single spread operator being used. It doesn't seem that different to me to just having multiple elements without using the spread operator.
Comment From: AndrewHarrisSPU
I don't think it makes sense to have two very similar concatenation functions.
The edit distance in LOC from append(...) to a variation with copy-then-append, or clone-then-append, isn't large. I do think they are not at all similar in terms of actual behavior, the invariants broken or preserved, algorithmic uses etc. That said I think it'd be fair enough to just have the append-like behavior in slices (a different take on Collect in an iter package would be more interesting.)
I think what I'm trying to suggest is that, on a first glance Concat can read either way. To me, I'd expect the Collect-like behavior from a slices.Concat. FWIW, there are only a few uses of a func concat or a method concat in the standard library (plus one in x/exp/slog); they all maintain the "no clobbering" invariant, mostly by slice copying rather than slice growing.
Comment From: rittneje
It could, but only for the case of a single spread operator being used. It doesn't seem that different to me to just having multiple elements without using the spread operator.
It cannot.
func foo(x ...int) {
// ...
}
a := []int{1, 2, 3}
b := []int{4, 5, 6}
foo(a..., b...) // cannot work
Within foo, the type of x is []int, which means it must be a standard slice backed by a single contiguous array. Thus there is no way to pass both a... and b... without copying at least one of them.
With regards to the original proposal, I think naming it something like AppendAll would be better, as that would at least suggest that it has analogous behavior to built-in append as far as the first parameter goes.
Comment From: DeedleFake
Thus there is no way to pass both a... and b... without copying at least one of them.
Right, that's what I said. It wouldn't change anything for existing cases where only a single spread operator is used, which is all that's currently legal.
Comment From: ianlancetaylor
Discussion about passing both a... and b... should perhaps go to #18605 rather than here. Thanks.
Comment From: zigo101
concat should be built-in to get the most out of it.
Otherwise, the implementation is hard to be performant, even correct.
Comment From: aclements
I think we should consider this proposal together with #4096, since these are two different solutions to the same problem.
Personally, I would much prefer to have #4096, since that feels like a natural and ergonomic extension to the way people already concatenate multiple slices. While we can do this with a generic function, doing so creates two different ways to do almost the same thing, where neither subsumes the other. It also has some (probably slight) performance disadvantages compared to doing it directly in append.
Comment From: rsc
This proposal has been added to the active column of the proposals project and will now be reviewed at the weekly proposal review meetings. — rsc for the proposal review group
Comment From: randall77
Concat suffers from the issue of having a slice in slices alias dst. As described here: https://github.com/golang/go/issues/56353#issuecomment-1285979414
This was fixed for slices.{Insert,Replace}, but it is tricky. See CL 494817. I'm not sure how you would handle that overlapping in general.
Comment From: earthboundkid
Maybe Concat should just always make a new slice. func Concat[S ~[]T, T any](ss ...S) S. I think I would be okay with that. It's simpler without dst, and reusing an existing slice does seem to be a tricky corner case.
Comment From: rsc
It does sound like an always-allocating Concat is a lot simpler to understand. Is it also useful enough? I think for most cases that I can think of, I'd be happy with the always-allocating form.
Are there any objections to a Concat that always allocates?
Comment From: randall77
Should the signature of Concat be
func Concat[S ~[]E, E any](dst S, slices ...S) S
or
func Concat[S ~[]E, E any](dst S, slices ...[]E) S
?
I think it might only matter if you do:
type S1 []int
type S2 []int
var s1 S1
var s2 S2
s1 = Concat[S1, int](s1, s2)
The former signature would not allow this code, the latter signature will. I don't know whether that's a good or bad thing.
There doesn't seem to be any direct analog already in slices, although we do tend to use []E instead of S where we can. But see #60546.
Comment From: gopherbot
Change https://go.dev/cl/500175 mentions this issue: slices: implement Concat
Comment From: randall77
I hacked up a CL which does the right thing when calling Concat on input slices that alias each other. It isn't too horrible, see the CL for details.
Comment From: earthboundkid
400 lines and a call to unsafe is a sort of a lot of work. 😆
Comment From: hherman1
What the right thing is sounds like a detail worthy of being in the api/docs
Comment From: zigo101
Maybe the signature should be
func Concat[S ~[]E, S2 ~[]E, E any](dst S, slices ...S2) S
to allow
type S1 []int
type S2 []int
var s1 S1
var s2 S2
var ss = []S2{s2}
_ = Concat(s1, ss...)
Comment From: rsc
Wow, thanks for working all that out Keith. From an API standpoint it seems much less error-prone to have the Concat that always allocates and have users use that. That suggestion had 5 thumbs up 1 thumb down.
How do people feel about:
func Concat[S ~[]E, E any](slices ...S) S
(This Concat always allocates a fresh result and copies the slices in.)
Comment From: zigo101
A non-builtin Concat function will unnecessarily reset the elements allocated in the make call (for most cases).
A builtin one can avoid this performance problem. And a builtin one can support some special needs:
- concat a string and a byte slice into a new byte slice.
- even concat arbitrary strings and byte slices into a new string or byte slice. The result type is the same as the first argument. We can pass a blank string or byte slice as the first argument when needed to determine the result type.
Comment From: earthboundkid
It looks like this sample program of concating a string with some other bytes only does one alloc.
23905 seems like it could be addressed through a compiler optimization that notices make([]T) followed by an unconditional overwrite. That would be better than a new built in because it would make old code faster without a rewrite to use a new builtin.
The slices package doesn't accept strings, so you couldn't write slices.Concat("a", "b", "c"). It would be the same as strings.Join([]string{"a", "b", "c"}, "") though, so it doesn't strike me as a big problem.
Comment From: zigo101
It looks like this sample program of concating a string with some other bytes only does one alloc.
[]byte(aStr) will allocate on stack if len(aStr) <= 32. That is a small optimization made in the current gc implementation.
https://github.com/golang/go/issues/23905 seems like it could be addressed through a compiler optimization that notices make([]T) followed by an unconditional overwrite. That would be better than a new built in because it would make old code faster without a rewrite to use a new builtin.
If this is possible, then that is great.
The slices package doesn't accept strings, so you couldn't write slices.Concat("a", "b", "c"). It would be the same as strings.Join([]string{"a", "b", "c"}, "") though, so it doesn't strike me as a big problem.
True, but sometimes, we need to concat hybrid arguments of strings and byte slices with a high performance demand (without unnecessarily element duplication and element resetting). That is why a builtin concat is preferred.
Comment From: rsc
A builtin concat still has to zero the backing store (if it contains pointers) because of GC. We don't make things builtins just to optimize them.
Comment From: rsc
Will move to likely accept but let's wait for Go 1.22 to submit it.
Comment From: rsc
Based on the discussion above, this proposal seems like a likely accept. — rsc for the proposal review group
Comment From: zigo101
A builtin concat still has to zero the backing store (if it contains pointers) because of GC.
True. But at least making it buitlin is not harmful (for the pointer cases). And for most cases, the elements don't contain pointers.
We don't make things builtins just to optimize them.
Surely, it is not a fatal problem not to make it builtin. :) It is just a problem that people will feel Go builtin slice manipulations are incomplete.
Comment From: rsc
No change in consensus, so accepted. 🎉 This issue now tracks the work of implementing the proposal. — rsc for the proposal review group
Comment From: gopherbot
Change https://go.dev/cl/504882 mentions this issue: slices: add Concat
Comment From: 6543
https://go.dev/play/p/TA-aYz8ZGUV
Comment From: 6543
well this should impl. the proposed api: #61817
correct me if I did messed up somewhere :)
Comment From: gopherbot
Change https://go.dev/cl/516656 mentions this issue: slices: add Concat
Comment From: fzipp
@6543 There is already an implementation; see the linked change list in comment https://github.com/golang/go/issues/56353#issuecomment-1601724189
Comment From: 6543
@fzipp yes but it does not implement the proposed api and looks stale
Comment From: earthboundkid
It implements the approved API. It's not stale, just waiting for the Go release cycle: https://github.com/golang/go/wiki/Go-Release-Cycle
Comment From: zigo101
Maybe this function should be specially optimized, just like maps.Clone? https://docs.go101.org/std/src/maps/maps.go.html#line-41
Comment From: earthboundkid
If you have a performance improvement to benchmark, that can be a new issue.
Comment From: zigo101
It is impossible to write normal benchmarks without hacking the runtime code. Someone ever hacked it.
There is no need to create a new issue.
Comment From: justinhwang
@ianlancetaylor / @earthboundkid could one of you elaborate on what this comment means and why we shouldn't be using make here?
https://go-review.googlesource.com/c/go/+/504882/3..6/src/slices/slices.go#b510
Since we don't make any promises about the capacity, I recommend
newslice := Grow[S](nil, size)That should lift the capacity up to the next size class.
Comment From: earthboundkid
If it used make there, the capacity would be exactly the combined size of the slices, but we want it to be rounded up to the next size class, so people don't rely on len(s) == cap(s) being true, and box ourselves into a corner.
Comment From: justinhwang
If it used
makethere, the capacity would be exactly the combined size of the slices, but we want it to be rounded up to the next size class, so people don't rely on len(s) == cap(s) being true, and box ourselves into a corner.
Still not quite following, what do we mean by rounded up to the next size class? Do we mean:
cap(Grow[S](nil, size)) != size
Comment From: earthboundkid
Sometimes, yes. See here for background on size classes: https://dave.cheney.net/2021/01/05/a-few-bytes-here-a-few-there-pretty-soon-youre-talking-real-memory
Comment From: OhJuhun
@earthboundkid I also don't quite understand why slices.Grow should be used instead of make in this case. I tested it with Go 1.22 using the link you provided, and contrary to what the post claims, this code does not allocate memory.
func BenchmarkSortStrings(b *testing.B) {
s := []string{"heart", "lungs", "brain", "kidneys", "pancreas"}
b.ReportAllocs()
for i := 0; i < b.N; i++ {
sort.Strings(s)
}
}
Therefore, I believe that this post is no longer valid.
In this case, make seems to be superior in terms of performance, and there doesn't seem to be a significant difference in readability either. Can you explain in more detail why slices.Grow should be used in this scenario please?
Comment From: earthboundkid
This is a closed issue. Your benchmark is invalid because sort.Strings isn't relevant to slices.Concat and the slice is sorted after the first loop. If you can make a change with better performance, submit the change with a benchmark from benchstat.
Comment From: zigo101
@OhJuhun
It looks the APIs in the slices package try to round up memory size to the next class size, except strings.Repeat. Honestly, I don't understand the cause of the inconsistency.
The current design of the slices package lacks of custom configurations:
- whether or not round up to the next memory class size.
- whether or not zero freed-up elements (in
Delete,ReplaceandCompactetc) - whether or not keep element order (such as in
Delete) - ...
Because of these facts, the slices package doesn't satisfy the needs of all cases.
So sometimes, you might need to write your own implementations.