Add a package for slices utilities #25069

pippolo84 · 2023-04-23T10:56:51Z

Add a package with utilities to deduplicate and deduplicate-and-sort slices of any type.

Currently, the Cilium codebase uses multiple (but very similar) approaches to deduplicate slices in different packages, like in pkg/ip, pkg/fqdn and operator/pkg/model/translation.

The PR adds a separate package to be used throughout the codebase for deduplicate elements in a slice, with 3 different functions that should cover all the current needs:

Unique: deduplication of a slice of any comparable type, preserving the ordering and modifying the slice in place.
SortedUnique: sorting and deduplication of a slice of constraints.Ordered type elements, operating in place.
SortedUniqueFunc: like SortedUnique, but usable also on composite types and/or with user-customized comparison logic.

The Unique function uses an optimization for small slices inspired by previous function KeepUniqueNames from pkg/fqdn.

sayboras

Thanks a lot ✔️

christarazi

❤️ this. Nice work! A few comments about benchmarks results below.

Also, did you perform an exhaustive scan on the rest of the code for other potential places where we'd need to convert them over to the new API?

christarazi · 2023-04-25T00:19:18Z

pkg/slices/slices_test.go

+// name          old time/op    new time/op    delta
+// Unique/96-8     3.17µs ± 9%    4.83µs ±15%  +52.50%  (p=0.008 n=5+5)
+// Unique/128-8    4.97µs ± 5%    5.95µs ± 2%  +19.83%  (p=0.008 n=5+5)
+// Unique/160-8    7.20µs ±12%    7.33µs ± 1%     ~     (p=0.690 n=5+5)
+// Unique/192-8    9.29µs ± 3%    9.07µs ± 2%     ~     (p=0.151 n=5+5)
+// Unique/256-8    15.4µs ± 4%    11.2µs ± 2%  -27.56%  (p=0.008 n=5+5)
+// ...
+//
+// After 192 elements, the map based approach becomes more efficient.


Can you include results for memory just so we can get an overall sense of the performance?

Added memory results, too.
I pointed out in the comment that, since the number of allocations from the loop algorithm is always 0, benchstat reports +Inf when comparing the two. But the info in the previous two columns (old alloc/op and new alloc/op) should be enough to highlight the allocations performed by the map approach:

... name old alloc/op new alloc/op delta Unique/96-8 0.00B 1474.00B ± 2% +Inf% (p=0.008 n=5+5) Unique/128-8 0.00B 3100.00B ± 0% +Inf% (p=0.008 n=5+5) Unique/160-8 0.00B 3113.20B ± 0% +Inf% (p=0.008 n=5+5) Unique/192-8 0.00B 3143.20B ± 0% +Inf% (p=0.008 n=5+5) Unique/256-8 0.00B 6178.00B ± 0% +Inf% (p=0.008 n=5+5) name old allocs/op new allocs/op delta Unique/96-8 0.00 3.20 ±38% +Inf% (p=0.008 n=5+5) Unique/128-8 0.00 2.00 ± 0% +Inf% (p=0.008 n=5+5) Unique/160-8 0.00 3.00 ± 0% +Inf% (p=0.016 n=5+4) Unique/192-8 0.00 4.00 ± 0% +Inf% (p=0.008 n=5+5) Unique/256-8 0.00 2.00 ± 0% +Inf% (p=0.008 n=5+5)

christarazi · 2023-04-25T00:20:30Z

pkg/ip/ip_test.go

-func (s *IPTestSuite) BenchmarkKeepUniqueIPs(c *C) {
-	size := 1000
-	ipsOrig := make([]net.IP, 0, size)
-	for i := 0; i < size; i++ {
-		ipsOrig = append(ipsOrig, net.IPv4(byte(i>>24), byte(i>>16), byte(i>>8), byte(i>>0)))
-	}
-	ips := make([]net.IP, 0, len(ipsOrig))
-
-	copy(ips, ipsOrig)
-	for i := 0; i < c.N; i++ {
-		c.StopTimer()
-		rand.Shuffle(len(ips), func(i, j int) {
-			ips[i], ips[j] = ips[j], ips[i]
-		})
-		c.StartTimer()
-
-		KeepUniqueIPs(ips)
-	}
-}


I'm actually curious to see what the difference in benchmark results were between the old KeepUniqueIPs and the new SortedUniqueFunc.

Here they are (I used the new benchmark to compare the old and the new function to see the differences while scaling the slice size):

name old time/op new time/op delta KeepUniqueIPs/96-8 17.2µs ±34% 15.6µs ±29% ~ (p=0.421 n=5+5) KeepUniqueIPs/128-8 24.5µs ± 5% 23.8µs ± 3% ~ (p=0.151 n=5+5) KeepUniqueIPs/160-8 31.2µs ± 8% 29.8µs ± 2% -4.47% (p=0.032 n=5+5) KeepUniqueIPs/192-8 37.2µs ± 4% 36.2µs ± 2% ~ (p=0.056 n=5+5) KeepUniqueIPs/256-8 50.6µs ± 1% 48.6µs ± 0% -4.04% (p=0.008 n=5+5) KeepUniqueIPs/512-8 108µs ± 3% 105µs ± 1% -3.27% (p=0.008 n=5+5) KeepUniqueIPs/1024-8 235µs ± 1% 225µs ± 0% -4.26% (p=0.008 n=5+5) name old alloc/op new alloc/op delta KeepUniqueIPs/96-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/128-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/160-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/192-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/256-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/512-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/1024-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) name old allocs/op new allocs/op delta KeepUniqueIPs/96-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/128-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/160-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/192-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/256-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/512-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/1024-8 3.00 ± 0% 3.00 ± 0% ~ (all equal)

Awesome, thanks. It would be great to have them in the commit msg IMO

jrajahalme · 2023-04-26T05:23:07Z

/test

Job 'Cilium-PR-K8s-1.27-kernel-net-next' failed:

Click to show.

Test Name

K8sDatapathServicesTest Checks N/S loadbalancing with L7 policy Tests NodePort with L7 Policy from outside

Failure Output

FAIL: Can not connect to service "http://192.168.56.12:30562" from outside cluster (2/10)

Jenkins URL: https://jenkins.cilium.io/job/Cilium-PR-K8s-1.27-kernel-net-next/147/

If it is a flake and a GitHub issue doesn't already exist to track it, comment /mlh new-flake Cilium-PR-K8s-1.27-kernel-net-next so I can create one.

Then please upload the Jenkins artifacts to that issue.

pippolo84 · 2023-04-26T10:38:56Z

Force-pushed to address #25069 (comment), only the test comment has been changed:

 // Unique/160-8    7.20µs ±12%    7.33µs ± 1%     ~     (p=0.690 n=5+5)
 // Unique/192-8    9.29µs ± 3%    9.07µs ± 2%     ~     (p=0.151 n=5+5)
 // Unique/256-8    15.4µs ± 4%    11.2µs ± 2%  -27.56%  (p=0.008 n=5+5)
-// ...
+
+// name          old alloc/op   new alloc/op   delta
+// Unique/96-8      0.00B       1474.00B ± 2%    +Inf%  (p=0.008 n=5+5)
+// Unique/128-8     0.00B       3100.00B ± 0%    +Inf%  (p=0.008 n=5+5)
+// Unique/160-8     0.00B       3113.20B ± 0%    +Inf%  (p=0.008 n=5+5)
+// Unique/192-8     0.00B       3143.20B ± 0%    +Inf%  (p=0.008 n=5+5)
+// Unique/256-8     0.00B       6178.00B ± 0%    +Inf%  (p=0.008 n=5+5)
+
+// name          old allocs/op  new allocs/op  delta
+// Unique/96-8       0.00           3.20 ±38%    +Inf%  (p=0.008 n=5+5)
+// Unique/128-8      0.00           2.00 ± 0%    +Inf%  (p=0.008 n=5+5)
+// Unique/160-8      0.00           3.00 ± 0%    +Inf%  (p=0.016 n=5+4)
+// Unique/192-8      0.00           4.00 ± 0%    +Inf%  (p=0.008 n=5+5)
+// Unique/256-8      0.00           2.00 ± 0%    +Inf%  (p=0.008 n=5+5)
 //
 // After 192 elements, the map based approach becomes more efficient.
+// Regarding the memory, the number of allocations for the double loop algorithm is always 0,
+// that's why benchstat is reporting "+Inf%" in the delta column.
+// The relevant differences between the two approaches in terms of memory are shown in the previous
+// two columns.
 func BenchmarkUnique(b *testing.B) {
        var benchCases = [...]int{96, 128, 160, 192, 256, 512, 1024}

pippolo84 · 2023-04-26T10:55:17Z

Also, did you perform an exhaustive scan on the rest of the code for other potential places where we'd need to convert them over to the new API?

After another scan I found several other potential candidates:

func countUniqueIPsecKeys() int
func (i *defaultTranslator) Translate(model *model.Model)
func getService(m *model.Model) *corev1.Service
func exportedUniqueStructTypes(v reflect.Value, m map[reflect.Type]struct{}, s map[uintptr]struct{})
func (s *ServiceCache) UniqueServiceFrontends() FrontendList
func (s *Service) UniquePorts() map[uint16]bool
func ValidIPs(podStatus slim_corev1.PodStatus) []string
func (c *DaemonConfig) populateDevices(vp *viper.Viper)
func (s *SSHMeta) BpfLBList(noDuplicates bool) (map[string][]string, error)
func failIfContainsBadLogMsg(logs, label string, blacklist map[string][]string)

I think I can convert these in one or more follow up PRs. WDYT?

christarazi · 2023-04-26T17:23:15Z

I think I can convert these in one or more follow up PRs. WDYT?

Sounds reasonable.

pippolo84 · 2023-04-27T08:23:48Z

Force-pushed to add the benchmark results to the commit message as suggested by #25069 (comment).
No changes to the code.

Add a package with common utilities to work on slices of any type. Currently, functions to deduplicate and deduplicate with sorting are added. Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

Change KeepUnique* functions to wrap `slices.SortedUniqueFunc` from pkg/slices. The tests are kept since they are useful to verify the logic of the custom less and eq functions passed to `slices.SortedUniqueFunc`. Instead, the old benchmark for KeepUniqueIPs is removed in favor of the one already present in pkg/slices that fulfill the same purpose. Here the results after running the new benchmark against the old version and the new one of KeepUniqueIPs: name old time/op new time/op delta KeepUniqueIPs/96-8 17.2µs ±34% 15.6µs ±29% ~ (p=0.421 n=5+5) KeepUniqueIPs/128-8 24.5µs ± 5% 23.8µs ± 3% ~ (p=0.151 n=5+5) KeepUniqueIPs/160-8 31.2µs ± 8% 29.8µs ± 2% -4.47% (p=0.032 n=5+5) KeepUniqueIPs/192-8 37.2µs ± 4% 36.2µs ± 2% ~ (p=0.056 n=5+5) KeepUniqueIPs/256-8 50.6µs ± 1% 48.6µs ± 0% -4.04% (p=0.008 n=5+5) KeepUniqueIPs/512-8 108µs ± 3% 105µs ± 1% -3.27% (p=0.008 n=5+5) KeepUniqueIPs/1024-8 235µs ± 1% 225µs ± 0% -4.26% (p=0.008 n=5+5) name old alloc/op new alloc/op delta KeepUniqueIPs/96-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/128-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/160-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/192-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/256-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/512-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) KeepUniqueIPs/1024-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) name old allocs/op new allocs/op delta KeepUniqueIPs/96-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/128-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/160-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/192-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/256-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/512-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) KeepUniqueIPs/1024-8 3.00 ± 0% 3.00 ± 0% ~ (all equal) Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

Use helpers from pkg/slices to deduplicate names slice. Remove the old test and benchmark for the no more used KeepUniqueNames. Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

Avoid the addition of package level code and instead rely on the common helpers available in pkg/slices. Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

pippolo84 · 2023-04-27T08:31:36Z

/test

Job 'Cilium-PR-K8s-1.26-kernel-net-next' failed:

Click to show.

Test Name

K8sDatapathConfig Check BPF masquerading with ip-masq-agent VXLAN

Failure Output

FAIL: Error deleting resource /home/jenkins/workspace/Cilium-PR-K8s-1.26-kernel-net-next/src/github.com/cilium/cilium/test/k8s/manifests/l3-policy-demo.yaml: Cannot retrieve "cilium-2rl8l"'s policy revision: cannot get policy revision: ""

Jenkins URL: https://jenkins.cilium.io/job/Cilium-PR-K8s-1.26-kernel-net-next/1944/

If it is a flake and a GitHub issue doesn't already exist to track it, comment /mlh new-flake Cilium-PR-K8s-1.26-kernel-net-next so I can create one.

Then please upload the Jenkins artifacts to that issue.

pippolo84 · 2023-04-27T12:26:15Z

/mlh new-flake Cilium-PR-K8s-1.26-kernel-net-next

👍 created #25163

pippolo84 · 2023-04-27T12:26:26Z

/test-1.26-net-next

pippolo84 requested review from a team as code owners April 23, 2023 10:56

pippolo84 requested review from thorn3r and jrajahalme April 23, 2023 10:56

maintainer-s-little-helper bot added the dont-merge/needs-release-note-label The author needs to describe the release impact of these changes. label Apr 23, 2023

pippolo84 added the release-note/misc This PR makes changes that have no direct user impact. label Apr 23, 2023

maintainer-s-little-helper bot removed the dont-merge/needs-release-note-label The author needs to describe the release impact of these changes. label Apr 23, 2023

pippolo84 added area/misc Impacts miscellaneous areas of the code not otherwise owned by another area. dont-merge/needs-release-note-label The author needs to describe the release impact of these changes. labels Apr 23, 2023

maintainer-s-little-helper bot removed the dont-merge/needs-release-note-label The author needs to describe the release impact of these changes. label Apr 23, 2023

sayboras approved these changes Apr 24, 2023

View reviewed changes

pippolo84 added the affects/v1.13 This issue affects v1.13 branch label Apr 24, 2023

christarazi approved these changes Apr 25, 2023

View reviewed changes

christarazi added kind/enhancement This would improve or streamline existing functionality. kind/performance There is a performance impact of this. sig/agent Cilium agent related. labels Apr 25, 2023

jrajahalme approved these changes Apr 26, 2023

View reviewed changes

pippolo84 force-pushed the pr/pippolo84/add-slice-utilities branch from 29eca2e to 2a003ec Compare April 26, 2023 10:38

ti-mo approved these changes Apr 26, 2023

View reviewed changes

pippolo84 force-pushed the pr/pippolo84/add-slice-utilities branch from 2a003ec to 8f90050 Compare April 27, 2023 08:23

pippolo84 added 3 commits April 27, 2023 10:26

pkg/slices: Add slices utility package

c42b79d

Add a package with common utilities to work on slices of any type. Currently, functions to deduplicate and deduplicate with sorting are added. Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

fqdn: Use slices helpers to remove duplicated names

78382d7

Use helpers from pkg/slices to deduplicate names slice. Remove the old test and benchmark for the no more used KeepUniqueNames. Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

ingress: Use slices helpers to remove duplicates

e3d9832

Avoid the addition of package level code and instead rely on the common helpers available in pkg/slices. Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

pippolo84 force-pushed the pr/pippolo84/add-slice-utilities branch from 8f90050 to e3d9832 Compare April 27, 2023 08:26

pippolo84 added the ready-to-merge This PR has passed all tests and received consensus from code owners to merge. label Apr 27, 2023

christarazi merged commit eb356a8 into cilium:main Apr 27, 2023
56 checks passed

sayboras mentioned this pull request Apr 29, 2023

gateway-api: Add support for TLSRoute #25106

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add a package for slices utilities #25069

Add a package for slices utilities #25069

pippolo84 commented Apr 23, 2023

sayboras left a comment

christarazi left a comment

christarazi Apr 25, 2023

pippolo84 Apr 26, 2023

christarazi Apr 25, 2023

pippolo84 Apr 26, 2023

christarazi Apr 26, 2023

jrajahalme commented Apr 26, 2023 •

edited by maintainer-s-little-helper bot

Test Name

Failure Output

pippolo84 commented Apr 26, 2023

pippolo84 commented Apr 26, 2023

christarazi commented Apr 26, 2023

pippolo84 commented Apr 27, 2023

pippolo84 commented Apr 27, 2023 •

edited by maintainer-s-little-helper bot

Test Name

Failure Output

pippolo84 commented Apr 27, 2023 •

edited by maintainer-s-little-helper bot

pippolo84 commented Apr 27, 2023

Add a package for slices utilities #25069

Add a package for slices utilities #25069

Conversation

pippolo84 commented Apr 23, 2023

sayboras left a comment

Choose a reason for hiding this comment

christarazi left a comment

Choose a reason for hiding this comment

christarazi Apr 25, 2023

Choose a reason for hiding this comment

pippolo84 Apr 26, 2023

Choose a reason for hiding this comment

christarazi Apr 25, 2023

Choose a reason for hiding this comment

pippolo84 Apr 26, 2023

Choose a reason for hiding this comment

christarazi Apr 26, 2023

Choose a reason for hiding this comment

jrajahalme commented Apr 26, 2023 • edited by maintainer-s-little-helper bot

Test Name

Failure Output

pippolo84 commented Apr 26, 2023

pippolo84 commented Apr 26, 2023

christarazi commented Apr 26, 2023

pippolo84 commented Apr 27, 2023

pippolo84 commented Apr 27, 2023 • edited by maintainer-s-little-helper bot

Test Name

Failure Output

pippolo84 commented Apr 27, 2023 • edited by maintainer-s-little-helper bot

pippolo84 commented Apr 27, 2023

jrajahalme commented Apr 26, 2023 •

edited by maintainer-s-little-helper bot

pippolo84 commented Apr 27, 2023 •

edited by maintainer-s-little-helper bot

pippolo84 commented Apr 27, 2023 •

edited by maintainer-s-little-helper bot