slices: low performance from common misuse of Delete

[earthboundkid]

Problem:

A quick search for slices.Delete on SourceGraph shows that many calls to slices.Delete are preceded by a call to slices.Index. This is often done in a loop, leading to needlessly terrible performance.

Possible solutions:

• Remove Delete from the standard library slices package.
• Accept and add slices: add DeleteFunc #54768 before slices is added to the standard library.

[dmitshur]

CC @ianlancetaylor, @eliben.

[ianlancetaylor]

Can you link to a couple of places? Thanks.

I'm fine with adding DeleteFunc but I don't see how it makes sense to remove Delete. The function's doc comment is even careful to explain its performance.

[earthboundkid]

https://sourcegraph.com/search?q=context:global+slices.Delete+lang:go+&patternType=standard&sm=1&groupBy=repo

I'm just going to do cursory reviews of the first handful of examples:

• pkg/bgpv1/gobgp/reconcile.go Has comment "Loop over announcements in reverse order so we can delete entries without effecting iteration." This is inefficient because it repeatedly moves tail elements in the case where there are many elements to delete.
• pkg/bgpv1/gobgp/routermgr.go Does the same thing
• operator/pkg/lbipam/lbipam.go Does the same thing
• operator/pkg/lbipam/range_store.go Unclear from context if this is problematic. Might be okay.
• tools/utils/misc.go Has "RemoveAll" utility which loops through with Delete.
• There are some false positive string matches in Kubernetes
• internal/service/emr/cluster.go Not totally clear how it's being used, but it's in a double nested loop, which is a bad sign to begin with.
• internal/filtering/rewrite/storage.go False positive string match
• vendor/github.com/jesseduffield/generics/slices/slices.go Okay. Just a utility to pass i and i+1 to slices.Remove.
• internal/types/document.go Okay
• service/worker/scheduler/workflow.go Okay
• vendor/github.com/jesseduffield/generics/slices/delegated_slices.go Just a wrapper function.
• vendor/github.com/containers/image/v5/manifest/docker_schema1.go "backwards loop so that we keep the remaining indexes after removing items"
• tools/cmd/unicode_input/main.go Okay
• modules/distributor/forwarder/manager_test.go Doesn't seem to do any work slices.Delete(o.tenantIDToForwarders["testTenantID"], idx, idx)
• internal/service/elbv2/listener_test.go Okay
• internal/service/elbv2/listener_rule_test.go Okay
• pkg/plugins/runtime/k8s/controllers/cni_taint_controller.go Unclear from context. Probably okay.
• exp/orderbook/edges.go Okay
• cmd/gitserver/server/vcs_packages_syncer_test.go In a loop. Would be better served by slices.DeleteFunc.
• vendor/github.com/containers/image/v5/manifest/docker_schema1.go Repeat. Bad.
• detector.go In a loop. Looks bad.
• gi/winlists.go Okay
• core/internal/testutils/evmtest/evmtest.go Seems okay
• internal/cmd/ssh.go In a loop. Seems bad.

Around a quarter of examples seem to be misuses, and many examples are some variant of i := slices.Index(s, something); if i != -1 { s = slices.Delete(s, i, i+1) }.

[rsc]

Closing as duplicate of #54768.