Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proposal: add a "merge" built-in function to join several slices. #23905

Closed
dotaheor opened this issue Feb 18, 2018 · 20 comments
Closed

Proposal: add a "merge" built-in function to join several slices. #23905

dotaheor opened this issue Feb 18, 2018 · 20 comments
Labels
LanguageChange Proposal v2 A language change or incompatible library change
Milestone

Comments

@dotaheor
Copy link

dotaheor commented Feb 18, 2018

The problem

Sometime, we need to insert a slice (call it x) into another (call it y) at the index i of y.
If the capacity of y is large enough to accept all elements of x, then things would simple.

func insert1(y, x []T, i int) []T {
	s := y[:len(s)+len(x)]
	copy(s[i+len(x):], s[i:])
	copy(s[i:], x)
	return s
}

However, the capacity of y is not large enough to accept all elements of x,
we must use make to allocate a new slice which is large enough to accept all elements of x and y.

func insert2(y, x []T, i int) []T {
	s := make([]T, 0, len(x)+len(y))
	s = append(s, y[:i]...)
	s = append(s, x...)
	s = append(s, y[i:]...)
	return s
}

The problem here is that the make function will clear all allocated bytes,
which is not essential for this case.

The proposal

So I propose a merge (or join, or concat) built-in function to merge several slices.

func merge(slices ...[][]T) []T

so that we can call

merge(y[:i], elements, y[i:])

which will be more efficient than the insert2 function.

@gopherbot gopherbot added this to the Proposal milestone Feb 18, 2018
@as
Copy link
Contributor

as commented Feb 18, 2018

Append already reuses the array if the bytes fit in the destination.

@josharian
Copy link
Contributor

Duplicate of #18605, I believe.

@dotaheor
Copy link
Author

@as
append is only useful to merge two slices.

@dotaheor
Copy link
Author

dotaheor commented Feb 18, 2018

@josharian
looks #18605 is about expanding variadic argument manners.
This proposal is to get a way to merge multiple slices into a new allocated slice without zeroing the new slice when it is allocated.

@josharian
Copy link
Contributor

@dotaheor if you could do append(s, y[:i]..., x..., y[i:]...) then you would get all of this, with no new built-ins. And that's what #18605 is about it.

@dotaheor
Copy link
Author

Ah, yes.

@dotaheor
Copy link
Author

dotaheor commented Feb 18, 2018

But, with the manner append(s, y[:i]..., x..., y[i:]...), y[:i] and x and y[i:] will be merged into one slice as the variadic parameter of the append function, then the new merged parameter will be merged again with the first parameter of the append function. There will be two allocations. My proposal will only make one allocation.

@josharian
Copy link
Contributor

There’s no reason I see that it would have to be implemented that way.

@dotaheor
Copy link
Author

dotaheor commented Feb 18, 2018

Ok, it would be great if that change can satisfy this need.

@bradfitz bradfitz added LanguageChange v2 A language change or incompatible library change labels Feb 18, 2018
@bradfitz
Copy link
Contributor

Or we just do this in library code once we have generics (#15292).

@dotaheor
Copy link
Author

dotaheor commented Feb 18, 2018

@bradfitz generic is not helpful for this problem.
The core of this issue is to avoid the make function zeroing a just allocated memory.
Surely, it not possible for a make_without_zeroing proposal to get approved.
So I propose the merge function instead, it may be not only useful for the case in my first comment.

@andlabs
Copy link
Contributor

andlabs commented Feb 28, 2018

So why not a grow function instead, that acts like realloc in C? Then you could do more than merge (which would be grow+copy).

@dotaheor
Copy link
Author

dotaheor commented Mar 1, 2018

@andlabs grow still needs to zero new elements, which is unnecessary.

@dotaheor
Copy link
Author

dotaheor commented Mar 1, 2018

But I think that sometimes we really need a grow function (which doesn't zero old elements if a new underlying memory block is allocated), or an assureSliceCap function.
We can't implement a grow in the most efficient way by using make, copy and append.

@bcmills
Copy link
Contributor

bcmills commented Mar 3, 2018

The core of this issue is to avoid the make function zeroing a just allocated memory.

You don't need a language change for that. You just need a compiler optimization that infers regions of slices that are unconditionally overwritten, which should be fairly straightforward for the simple case of appending a sequence of slices.

@dotaheor
Copy link
Author

dotaheor commented Mar 3, 2018

It would be great that a compiler optimization can achieve the goal of a merge function.
I think it is possible at least for some scenarios.

@ianlancetaylor
Copy link
Contributor

This can be done either via #18605, or via generics, or via a compiler optimization. We're not going to accept this as a builtin function directly.

@dotaheor
Copy link
Author

ok, I hope there is a tangible solution in planning to resolve this inefficiency problem,
and to fix the Go slice manipulation completeness problem.

@andlabs
Copy link
Contributor

andlabs commented Apr 25, 2018

I do have to wonder, and I forget if anyone said this at all in this thread, if the cost of zero-initializing is really significant enough to optimize it away. (This means actual experiments and benchmarks to confirm or deny this.)

@golang golang locked as resolved and limited conversation to collaborators Apr 25, 2018
@josharian
Copy link
Contributor

I do have to wonder, and I forget if anyone said this at all in this thread, if the cost of zero-initializing is really significant enough to optimize it away.

The current compiler spends about 15% of its execution time zero initializing new allocations.

I doubt that much of that can be optimized away, but the answer is yes: It matters.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
LanguageChange Proposal v2 A language change or incompatible library change
Projects
None yet
Development

No branches or pull requests

8 participants