slices: new standard library package based on x/exp/slices #57433

ianlancetaylor · 2022-12-21T22:54:48Z

In #45955 I proposed a new slices package in the standard library. After considerable discussion there and in discussion #47203 we settled on an API and added the experimental package golang.org/x/exp/slices.

We now have experience with this package in practice. pkg.go.dev reports that it is imported by 1,541 other packages. I propose that it is now time to move this package into the standard library for the 1.21 release.

Doing this doesn't mean that we can't add more functions to the standard library slices package later. Any such additions should be suggested in their own separate proposal.

The specific API that we will put into the standard library appears below.

This description of the API refers to constraints.Ordered in a few places; if the constraints package is not present in the standard library, that reference will be replaced by an unexported constraint with the same set of types.

Note that we should either accept or reject #57348 before we accept this proposal. If we accept #57348, the appropriate change will be made here.

I'm not aware of any other proposal to modify the existing slices package API. There are a few proposals to add new functions to the slices package (at least #52434, #53987, #54768, #56353); those proposals can move from x/exp/slices to just plain slices.

Proposed API:

// Equal reports whether two slices are equal: the same length and all
// elements equal. If the lengths are different, Equal returns false.
// Otherwise, the elements are compared in increasing index order, and the
// comparison stops at the first unequal pair.
// Floating point NaNs are not considered equal.
func Equal[E comparable](s1, s2 []E) bool

// EqualFunc reports whether two slices are equal using a comparison
// function on each pair of elements. If the lengths are different,
// EqualFunc returns false. Otherwise, the elements are compared in
// increasing index order, and the comparison stops at the first index
// for which eq returns false.
func EqualFunc[E1, E2 any](s1 []E1, s2 []E2, eq func(E1, E2) bool) bool

// Compare compares the elements of s1 and s2.
// The elements are compared sequentially, starting at index 0,
// until one element is not equal to the other.
// The result of comparing the first non-matching elements is returned.
// If both slices are equal until one of them ends, the shorter slice is
// considered less than the longer one.
// The result is 0 if s1 == s2, -1 if s1 < s2, and +1 if s1 > s2.
// Comparisons involving floating point NaNs are ignored.
func Compare[E constraints.Ordered](s1, s2 []E) int

// CompareFunc is like Compare but uses a comparison function
// on each pair of elements. The elements are compared in increasing
// index order, and the comparisons stop after the first time cmp
// returns non-zero.
// The result is the first non-zero result of cmp; if cmp always
// returns 0 the result is 0 if len(s1) == len(s2), -1 if len(s1) < len(s2),
// and +1 if len(s1) > len(s2).
func CompareFunc[E1, E2 any](s1 []E1, s2 []E2, cmp func(E1, E2) int) int

// Index returns the index of the first occurrence of v in s,
// or -1 if not present.
func Index[E comparable](s []E, v E) int

// IndexFunc returns the first index i satisfying f(s[i]),
// or -1 if none do.
func IndexFunc[E any](s []E, f func(E) bool) int

// Contains reports whether v is present in s.
func Contains[E comparable](s []E, v E) bool

// ContainsFunc reports whether at least one
// element e of s satisfies f(e).
func ContainsFunc[E any](s []E, f func(E) bool) bool

// Insert inserts the values v... into s at index i,
// returning the modified slice.
// In the returned slice r, r[i] == v[0].
// Insert panics if i is out of range.
// This function is O(len(s) + len(v)).
func Insert[S ~[]E, E any](s S, i int, v ...E) S

// Delete removes the elements s[i:j] from s, returning the modified slice.
// Delete panics if s[i:j] is not a valid slice of s.
// Delete modifies the contents of the slice s; it does not create a new slice.
// Delete is O(len(s)-j), so if many items must be deleted, it is better to
// make a single call deleting them all together than to delete one at a time.
// Delete might not modify the elements s[len(s)-(j-i):len(s)]. If those
// elements contain pointers you might consider zeroing those elements so that
// objects they reference can be garbage collected.
func Delete[S ~[]E, E any](s S, i, j int) S

// Replace replaces the elements s[i:j] by the given v, and returns the
// modified slice. Replace panics if s[i:j] is not a valid slice of s.
func Replace[S ~[]E, E any](s S, i, j int, v ...E) S

// Clone returns a copy of the slice.
// The elements are copied using assignment, so this is a shallow clone.
func Clone[S ~[]E, E any](s S) S

// Compact replaces consecutive runs of equal elements with a single copy.
// This is like the uniq command found on Unix.
// Compact modifies the contents of the slice s; it does not create a new slice.
// When Compact discards m elements in total, it might not modify the elements
// s[len(s)-m:len(s)]. If those elements contain pointers you might consider
// zeroing those elements so that objects they reference can be garbage collected.
func Compact[S ~[]E, E comparable](s S) S

// CompactFunc is like Compact but uses a comparison function.
func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S

// Grow increases the slice's capacity, if necessary, to guarantee space for
// another n elements. After Grow(n), at least n elements can be appended
// to the slice without another allocation. If n is negative or too large to
// allocate the memory, Grow panics.
func Grow[S ~[]E, E any](s S, n int) S

// Clip removes unused capacity from the slice, returning s[:len(s):len(s)].
func Clip[S ~[]E, E any](s S) S

// Sort sorts a slice of any ordered type in ascending order.
// Sort may fail to sort correctly when sorting slices of floating-point
// numbers containing Not-a-number (NaN) values.
// Use slices.SortFunc(x, func(a, b float64) bool {return a < b || (math.IsNaN(a) && !math.IsNaN(b))})
// instead if the input may contain NaNs.
func Sort[E constraints.Ordered](x []E)

// SortFunc sorts the slice x in ascending order as determined by the less function.
// This sort is not guaranteed to be stable.
//
// SortFunc requires that less is a strict weak ordering.
// See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings.
func SortFunc[E any](x []E, less func(a, b E) bool)

// SortStableFunc sorts the slice x while keeping the original order of equal
// elements, using less to compare elements.
func SortStableFunc[E any](x []E, less func(a, b E) bool)

// IsSorted reports whether x is sorted in ascending order.
func IsSorted[E constraints.Ordered](x []E) bool

// IsSortedFunc reports whether x is sorted in ascending order, with less as the
// comparison function.
func IsSortedFunc[E any](x []E, less func(a, b E) bool) bool

// BinarySearch searches for target in a sorted slice and returns the position
// where target is found, or the position where target would appear in the
// sort order; it also returns a bool saying whether the target is really found
// in the slice. The slice must be sorted in increasing order.
func BinarySearch[E constraints.Ordered](x []E, target E) (int, bool)

// BinarySearchFunc works like BinarySearch, but uses a custom comparison
// function. The slice must be sorted in increasing order, where "increasing" is
// defined by cmp. cmp(a, b) is expected to return an integer comparing the two
// parameters: 0 if a == b, a negative number if a < b and a positive number if
// a > b.
func BinarySearchFunc[E any](x []E, target E, cmp func(E, E) int) (int, bool)

The text was updated successfully, but these errors were encountered:

Merovius · 2022-12-21T23:04:29Z

Note that we should either accept or reject #57348 before we accept this proposal. If we accept #57348, the appropriate change will be made here.

Out of interest: Is there code which would compile with the current version but would stop compiling with my proposal? I can't really think of how that would be the case, because any code using slices.BinarySearchFunc should just be inferred to two identical type arguments, no? [edit] I mean, I said on that proposal that it's not backwards compatible, as if it's self-explanatory, so I must've thought of something, but I can't remember what… [/edit]

fzipp · 2022-12-21T23:11:27Z

it is imported by 1,541 other packages

Usage statistics per function would be interesting. If there's a function that isn't used at all, that could be a sign that it's not necessary.

Merovius · 2022-12-21T23:14:36Z

I don't know if it has been brought up, but Contains fits into the family None/Any/All - if we had all three, it would be Any. I've recently found myself needing All a couple of times. I bring this up not to suggest adding the others, but because I can't think of how I'd name the others if we stick with the name Contains.

I also find it a bit of a rough edge that it's sometimes less func(a, b T) bool and sometimes cmp func(a, b T) int. If I want a slice of things which can both be sorted and searched (and let's be honest, anything that needs to be searched will have to be sorted first) I'll have to write two, mostly redundant functions.

fzipp · 2022-12-21T23:21:12Z

I don't know if it has been brought up, but Contains fits into the family None/Any/All - if we had all three, it would be Any.

I think it was discussed in #53983

Merovius · 2022-12-21T23:47:20Z

Fair enough.

ianlancetaylor · 2022-12-22T00:48:00Z

Is there code which would compile with the current version but would stop compiling with my proposal?

I had to think about it, but I think the answer is yes:

    f := slices.BinarySearchFunc[int]

We can't infer the second type argument in the absence of any actual arguments.

ghost · 2022-12-22T03:07:27Z

It's a pity we can't have func SortFunc[E any, EP E | *E](x []E, less func(a, b EP) bool). It can be kind of expensive to pass largish elements by value.

earthboundkid · 2022-12-22T06:30:59Z

Can we get a decision on #52427 before this is merged, to nail down the constraints package issue?

andig · 2022-12-22T06:32:02Z

It's a pity we can't have func SortFunc[E any, EP E | *E](x []E, less func(a, b EP) bool). It can be kind of expensive to pass largish elements by value.

Isn‘t only the header passed by value? Then size shouldn‘t make a difference regarding performance.

ericlagergren · 2022-12-22T07:09:18Z

It's a pity we can't have func SortFunc[E any, EP E | *E](x []E, less func(a, b EP) bool). It can be kind of expensive to pass largish elements by value.

Isn‘t only the header passed by value? Then size shouldn‘t make a difference regarding performance.

Not the slice, the comparison function.

fzipp · 2022-12-22T07:34:33Z

Why is there a stable variant of SortFunc, but not of Sort?

Edit: I think I found the answer. It's because only value types can satisfy constraints.Ordered.

Merovius · 2022-12-22T09:14:52Z

@fzipp Arguably there should be.

As usually, the special case are floating point numbers, where distinguishable elements can still compare as equal. Distinguishing the stable/unstable sorting result requires using math.Signbit in this case or might require math.Float64bits for NaN, but they can be distinguished.

But it seems very much a corner case and people who care can then still result to SortStableFunc.

For all other types satisfying constraints.Ordered, the stable/unstable sorting result will always be indistinguishable.

gophun · 2022-12-22T09:52:17Z

We now have experience with this package in practice.

I would have liked to hear more experience reports from people who have used this package. But maybe the silence just means they're happy so far.

Merovius · 2022-12-22T13:22:15Z

@gophun

I've been using the slices package over the last year or so whenever I thought of it. In particular, I've been using it a bunch for Advent of Code over the last three weeks. That's a small sample and it's code for a specific kind of problem, but OTOH it's all fresh code from scratch, so it's probably the most representative sample I have at hand for how I write code "right now". The TL;DR is that I use or could use almost all of its API and I use it quite frequently (which also feels true for my day job).

Stats/Details

Grepping through the source, I call:

  4 Clone
  4 Index
  2 Sort
  3 SortFunc
  3 SortStableFunc

I would have used slices.BinarySearchFunc 5 times, if #57348 was accepted. That's ~20 calls in ~2700 SLOC, which is a decent amount. It's also one of the most-imported Go project packages in that codebase:

  1 	"crypto/sha1"
  1 	"encoding/base64"
  1 	"encoding/binary"
  1 	"encoding/json"
  1 	"golang.org/x/net/publicsuffix"
  1 	"image"
  1 	"image/color"
  1 	"image/png"
  1 	"io/fs"
  1 	"net/http"
  1 	"net/http/cookiejar"
  1 	"net/url"
  1 	"reflect"
  1 	"regexp"
  1 	"sort"
  1 	"sync"
  2 	"context"
  2 	"path/filepath"
  2 	"testing"
  2 	"time"
  2 	"unicode/utf8"
  3 	"bufio"
  4 	"bytes"
  5 	"flag"
  5 	"golang.org/x/exp/constraints"
  6 	"strconv"
  9 -->	"golang.org/x/exp/slices"
 10 	"io"
 10 	"strings"
 12 	"errors"
 21 	"log"
 22 	"os"
 30 	"fmt"

Looking at the API, I probably would have used Delete, Insert and Replace for one problem and Clip in at least one place, if I had thought of them. I also know that I've written versions of Compact and Grow a couple of times in the past.

APIs I haven't used and don't remember needing are Compare*, Contains* and IsSorted*, but there's also significant personal preference in that.

One thing I've been missing a couple of times are Map and Filter, but I think it makes sense to delay those until we solve iteration.

Overall, I find myself reaching for slices quite frequently and I use most of its API occasionally, with a decent bias towards the *Func variants. I think an interesting contrast is golang.org/x/exp/maps, which I don't seem to be using much, if at all.

adonovan · 2022-12-22T14:57:36Z

Can we also add the in-place Reverse([]T) function? It's a common three-liner.

adonovan · 2022-12-22T19:27:57Z

We could also produce a set of vet analyzers that can suggest fixes that would safely transform pre-generic code using explicit allocations/loops into calls to these new functions.

DeedleFake · 2022-12-22T19:44:18Z

We could also produce a set of vet analyzers that can suggest fixes that would safely transform pre-generic code using explicit allocations/loops into calls to these new functions.

That feels like it could get a bunch of false positives. That could be annoying if they show up in go test runs.

adonovan · 2022-12-22T19:56:46Z

We could also produce a set of vet analyzers that can suggest fixes that would safely transform pre-generic code using explicit allocations/loops into calls to these new functions.

That feels like it could get a bunch of false positives. That could be annoying if they show up in go test runs.

Sorry, I meant vet analyzer here as a shorthand for golang.org/x/tools/go/analysis analyzers, along with a standalone tool that one could apply as desired to your codebase; I didn't mean they would actually be in the vet tool.

AndrewHarrisSPU · 2022-12-22T21:07:17Z

I would have liked to hear more experience reports from people who have used this package. But maybe the silence just means they're happy so far.

I think the slices package has chosen the right focus. Go slices have quirks; it's really nice to have the operations slices provides, with implementation that is plainly tuned to (in-)variants particular to the slice data structure.

Eventually, I think it's really natural to want backed-by-slices, generics-oriented versions of what e.g. container/heap, container/ring do, or stacks/queues, or multi-dimensional slices, etc., etc., but it feels right that slices doesn't get into this.

Aceix · 2022-12-22T21:44:54Z

This is good but what of a C++ STL equivalent, but with chain-able methods for functional programming feel

earthboundkid · 2022-12-22T21:47:57Z

The one function I find myself still regularly missing is the equivalent of maps.DeleteFunc. I understand why slices.Filter isn’t in the package (yet?), but an in place filter would be helpful.

ianlancetaylor · 2022-12-22T22:02:02Z

I think it will be best if suggestions for new functions in the slices package go into separate proposals. Whether or not we add new functions to the slices package does not affect whether the slices package will go into the standard library. Similarly, whether or not the slices package goes into the standard library does not affect whether we add new functions. Thanks.

dsnet · 2022-12-22T23:48:48Z

Usage statistics per function would be interesting. If there's a function that isn't used at all, that could be a sign that it's not necessary.

@fzipp, scanning the latest module of all publicly known modules on 2022-10-01, the usage stats are as follows:

Function	Count
Contains	1481
Clone	531
Sort	433
Equal	404
SortFunc	336
Index	190
IndexFunc	166
Delete	145
Insert	82
BinarySearch	60
SortStableFunc	42
EqualFunc	41
Clip	38
Compact	37
IsSorted	36
Grow	29
BinarySearchFunc	26
Compare	20
IsSortedFunc	18
Replace	10
CompactFunc	5
CompareFunc	3
ContainsFunc	1

I find it ironic that the most used function is Contains, while the least used function is it's sibling ConrtainsFunc.

ianlancetaylor · 2022-12-22T23:52:30Z

ContainsFunc was only added to the package on December 5, so it's not that surprising that it's not used very often.

hherman1 · 2022-12-23T01:21:08Z

Replace seems borderline underused for inclusion here.

bobg · 2023-02-09T18:51:28Z

Probably a little late for this suggestion, but how about Python-style negative indexes, as in https://pkg.go.dev/github.com/bobg/go-generics/slices?

earthboundkid · 2023-02-09T19:28:05Z

@bobg, See #53510.

seankhliao · 2023-02-09T19:29:45Z

negative indices would be a language change, most recently declined in #33359

gopherbot · 2023-02-10T21:54:33Z

Change https://go.dev/cl/467417 mentions this issue: slices: new package

DeedleFake · 2023-02-10T22:13:53Z

@seankhliao I'm apathetic about negative indices myself, but I think he meant just for the functions in this package, not in general. Then you could do things like slices.Delete(s, -3, -2) to remove the penultimate element, for example.

beoran · 2023-02-11T01:46:09Z

I think negative indexes at're an example of wanting to be "too clever" . It's better to use the length of the slice.

l :=len(s)
slices.Delete(s, len-3, len-2)

Expresses more clearly what we mean

natefinch · 2023-02-16T15:27:29Z

I just wanted to say thank you to whoever added the ,bool to the return value of the binary search functions. Figuring out how to use sort.Search correctly was an ordeal.

ianlancetaylor · 2023-02-16T19:44:49Z

I believe it was first suggested by @rsc in #50340 (comment).

ghost · 2023-02-18T14:57:27Z

// BinarySearch searches for target in a sorted slice and returns the position
// where target is found, or the position where target would appear in the
// sort order; it also returns a bool saying whether the target is really found
// in the slice. The slice must be sorted in increasing order.
func BinarySearch[E constraints.Ordered](x []E, target E) (int, bool)

increasing order

Non-decreasing, maybe?

This copies parts of x/exp/slices into the standard library. We omit all functions that depend on constraints.Ordered, and the Func variants of all such functions. In particular this omits the various Sort and Search functions. Fixes golang#57433 Change-Id: I3c28f4c2e6bd1e3c9ad70e120a0dd68065388f77 Reviewed-on: https://go-review.googlesource.com/c/go/+/467417 Run-TryBot: Ian Lance Taylor <iant@golang.org> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Eli Bendersky <eliben@google.com> Run-TryBot: Ian Lance Taylor <iant@google.com> Reviewed-by: Ian Lance Taylor <iant@google.com> Auto-Submit: Ian Lance Taylor <iant@google.com>

gopherbot · 2023-05-04T11:35:42Z

Change https://go.dev/cl/492576 mentions this issue: all: use slices.Equal to simplify code

#57433 added slices.Equal, using it can reduce the amount of code Change-Id: I70d14b6c4c24da641a34ed36c900d9291033f526 Reviewed-on: https://go-review.googlesource.com/c/go/+/492576 Reviewed-by: Than McIntosh <thanm@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Run-TryBot: Ian Lance Taylor <iant@google.com> Reviewed-by: Ian Lance Taylor <iant@google.com> Auto-Submit: Ian Lance Taylor <iant@google.com> Run-TryBot: shuang cui <imcusg@gmail.com>

This copies parts of x/exp/slices into the standard library. We omit all functions that depend on constraints.Ordered, and the Func variants of all such functions. In particular this omits the various Sort and Search functions. Fixes golang#57433 Change-Id: I3c28f4c2e6bd1e3c9ad70e120a0dd68065388f77 Reviewed-on: https://go-review.googlesource.com/c/go/+/467417 Run-TryBot: Ian Lance Taylor <iant@golang.org> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Eli Bendersky <eliben@google.com> Run-TryBot: Ian Lance Taylor <iant@google.com> Reviewed-by: Ian Lance Taylor <iant@google.com> Auto-Submit: Ian Lance Taylor <iant@google.com>

ianlancetaylor added the Proposal label Dec 21, 2022

gopherbot added this to the Proposal milestone Dec 21, 2022

This was referenced Dec 21, 2022

slices: new package to provide generic slice functions #45955

Closed

slices: add Sort, SortStable, IsSorted, BinarySearch, and func variants #47619

Closed

ianlancetaylor added the generics Issue is related to generics label Dec 21, 2022

rsc added Proposal-Accepted and removed Proposal-FinalCommentPeriod labels Feb 9, 2023

uablrek mentioned this issue Feb 13, 2023

Fix target changes on LB Nordix/Meridio#363

Merged

12 tasks

gopherbot closed this as completed in 1e9925f Feb 13, 2023

bobg mentioned this issue Feb 21, 2023

Add slices.Any, slices.None bobg/go-generics#2

Closed

crisman mentioned this issue Apr 17, 2023

x/exp/slices: BinarySearchFunc slice sort undefined #59685

Closed

ianlancetaylor mentioned this issue May 9, 2023

slices: add sorting and comparison functions #60091

Closed

dmitshur modified the milestones: Backlog, Go1.21 May 30, 2023

mknyszek mentioned this issue Jun 1, 2023

api: audit for Go 1.21 #60560

Closed

AlexanderYastrebov mentioned this issue Jun 12, 2023

Replace NLBs on subnets change zalando-incubator/kube-ingress-aws-controller#610

Open

David-Mao mentioned this issue Jul 5, 2023

slices: make Clone preallocate and copy instead of solely invoking append #61186

Closed

arran4 mentioned this issue Aug 6, 2023

feature: Exposes isExecutable to the user twpayne/chezmoi#3153

Closed

hamidzr mentioned this issue Aug 17, 2023

chore: upgrade go 1.20 to 1.21 determined-ai/determined#7657

Merged

4 tasks

earthboundkid mentioned this issue Sep 20, 2023

cmd/vet: warn when ignoring the return value of slices.Delete and friends #62729

Closed

acheong08 mentioned this issue Oct 17, 2023

Fix go version issue in test pitabwire/natspubsub#8

Closed

slices: new standard library package based on x/exp/slices #57433

slices: new standard library package based on x/exp/slices #57433

Comments

ianlancetaylor commented Dec 21, 2022

Merovius commented Dec 21, 2022 • edited

fzipp commented Dec 21, 2022

Merovius commented Dec 21, 2022

fzipp commented Dec 21, 2022 • edited

Merovius commented Dec 21, 2022

ianlancetaylor commented Dec 22, 2022

ghost commented Dec 22, 2022 • edited by ghost

earthboundkid commented Dec 22, 2022

andig commented Dec 22, 2022

ericlagergren commented Dec 22, 2022

fzipp commented Dec 22, 2022 • edited

Merovius commented Dec 22, 2022 • edited

gophun commented Dec 22, 2022

Merovius commented Dec 22, 2022

adonovan commented Dec 22, 2022

adonovan commented Dec 22, 2022

DeedleFake commented Dec 22, 2022

adonovan commented Dec 22, 2022

AndrewHarrisSPU commented Dec 22, 2022 • edited

Aceix commented Dec 22, 2022

earthboundkid commented Dec 22, 2022

ianlancetaylor commented Dec 22, 2022

dsnet commented Dec 22, 2022

ianlancetaylor commented Dec 22, 2022

hherman1 commented Dec 23, 2022

bobg commented Feb 9, 2023

earthboundkid commented Feb 9, 2023

seankhliao commented Feb 9, 2023

gopherbot commented Feb 10, 2023

DeedleFake commented Feb 10, 2023 • edited

beoran commented Feb 11, 2023

natefinch commented Feb 16, 2023

ianlancetaylor commented Feb 16, 2023

ghost commented Feb 18, 2023

gopherbot commented May 4, 2023

Merovius commented Dec 21, 2022 •

edited

fzipp commented Dec 21, 2022 •

edited

ghost commented Dec 22, 2022 •

edited by ghost

fzipp commented Dec 22, 2022 •

edited

Merovius commented Dec 22, 2022 •

edited

AndrewHarrisSPU commented Dec 22, 2022 •

edited

DeedleFake commented Feb 10, 2023 •

edited