Refactor set.SliceSubsetOf #25559

pippolo84 · 2023-05-19T15:23:27Z

pkg/set has a method to verify if a given slice is a subset of another. Being an utility function about slices, it is moved in the pkg/slices package.
Also, the method is modified to leverage type parameters, and broken down to expose the diff logic as a separate method, to higher the chances of being reused throughout the codebase.

The algorithm used for the new slices.Diff and slices.SubsetOf differ from the previous semantic in a detail: they do not consider duplicates. IOW, the input slices are treated as sets. This is fine with the current usage of the method and in case the opposite semantic will be needed in the future, it'll be possible to add a new method with a different algorithm.

jschwinger233

Thank you!

christarazi

Nice! Benchmarks between the new implementation and the one it replaces?

michi-covalent · 2023-05-23T19:16:08Z

/test

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

Click to show.

Test Name

K8sDatapathConfig High-scale IPcache Test ingress policy enforcement

Failure Output

FAIL: Expected command: kubectl exec -n kube-system cilium-k29fb -- bpftool map update pinned /sys/fs/bpf/tc/globals/cilium_world_cidrs4 key 0 0 0 0 0 0 0 0 value 1

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

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-05-24T16:29:09Z

Nice! Benchmarks between the new implementation and the one it replaces?

I've added a commit with a benchmark.
Here the results (I've also added this in the commit message):

    name                  old time/op    new time/op    delta
    SubsetOf/64-512-8       15.3µs ±35%    14.6µs ±27%      ~     (p=0.134 n=20+20)
    SubsetOf/128-512-8      24.4µs ± 5%    22.6µs ± 4%    -7.47%  (p=0.000 n=18+17)
    SubsetOf/256-2048-8     88.3µs ± 7%    81.0µs ± 6%    -8.28%  (p=0.000 n=18+19)
    SubsetOf/512-2048-8      110µs ± 5%      98µs ± 7%   -10.24%  (p=0.000 n=20+20)
    SubsetOf/1024-8192-8     358µs ± 4%     318µs ± 5%   -11.25%  (p=0.000 n=19+20)
    SubsetOf/2048-8192-8     469µs ± 5%     423µs ±10%    -9.72%  (p=0.000 n=20+19)
    
    name                  old alloc/op   new alloc/op   delta
    SubsetOf/64-512-8       28.7kB ± 0%    23.2kB ± 0%   -19.10%  (p=0.000 n=20+20)
    SubsetOf/128-512-8      28.8kB ± 0%    25.9kB ± 0%    -9.97%  (p=0.000 n=19+16)
    SubsetOf/256-2048-8      115kB ± 0%      92kB ± 0%   -19.62%  (p=0.000 n=19+20)
    SubsetOf/512-2048-8      115kB ± 0%     103kB ± 0%   -10.78%  (p=0.000 n=19+16)
    SubsetOf/1024-8192-8     459kB ± 0%     360kB ± 0%   -21.42%  (p=0.000 n=18+17)
    SubsetOf/2048-8192-8     460kB ± 0%     402kB ± 0%   -12.59%  (p=0.000 n=20+17)
    
    name                  old allocs/op  new allocs/op  delta
    SubsetOf/64-512-8         2.00 ± 0%      4.00 ± 0%  +100.00%  (p=0.000 n=20+20)
    SubsetOf/128-512-8        4.65 ±57%      5.55 ±28%   +19.35%  (p=0.028 n=20+20)
    SubsetOf/256-2048-8       2.00 ± 0%      4.00 ± 0%  +100.00%  (p=0.000 n=19+20)
    SubsetOf/512-2048-8       6.45 ±24%      7.75 ±10%   +20.16%  (p=0.000 n=20+16)
    SubsetOf/1024-8192-8      2.17 ±38%      4.00 ± 0%   +84.62%  (p=0.000 n=18+17)
    SubsetOf/2048-8192-8      8.65 ± 8%     10.00 ± 0%   +15.61%  (p=0.000 n=20+17)

The number of allocations increased, but the total amount of allocated memory lowered.
Also, there is an improvement in speed, due to the simpler semantic.

pippolo84 · 2023-05-24T16:30:56Z

/test

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

Click to show.

Test Name

K8sDatapathServicesTest Checks N/S loadbalancing With host policy Tests NodePort

Failure Output

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

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

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.

christarazi · 2023-05-25T20:48:15Z

Needs a rebase

pkg/set has a method to verify if a given slice is a subset of another. Being an utility function about slice, it is moved in the pkg/slices package. Also, the method is modified to leverage type parameters, and broken down to expose the diff logic as a separate method, to higher the chances of being reused throughout the codebase. Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

The only method exported has been superseded by slices.Subset so the package can be removed. Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

Add a benchmark to measure the performance of the SubsetOf function. Below the benchstat comparison of the current implementation against the old set.SliceSubsetOf: name old time/op new time/op delta SubsetOf/64-512-8 15.3µs ±35% 14.6µs ±27% ~ (p=0.134 n=20+20) SubsetOf/128-512-8 24.4µs ± 5% 22.6µs ± 4% -7.47% (p=0.000 n=18+17) SubsetOf/256-2048-8 88.3µs ± 7% 81.0µs ± 6% -8.28% (p=0.000 n=18+19) SubsetOf/512-2048-8 110µs ± 5% 98µs ± 7% -10.24% (p=0.000 n=20+20) SubsetOf/1024-8192-8 358µs ± 4% 318µs ± 5% -11.25% (p=0.000 n=19+20) SubsetOf/2048-8192-8 469µs ± 5% 423µs ±10% -9.72% (p=0.000 n=20+19) name old alloc/op new alloc/op delta SubsetOf/64-512-8 28.7kB ± 0% 23.2kB ± 0% -19.10% (p=0.000 n=20+20) SubsetOf/128-512-8 28.8kB ± 0% 25.9kB ± 0% -9.97% (p=0.000 n=19+16) SubsetOf/256-2048-8 115kB ± 0% 92kB ± 0% -19.62% (p=0.000 n=19+20) SubsetOf/512-2048-8 115kB ± 0% 103kB ± 0% -10.78% (p=0.000 n=19+16) SubsetOf/1024-8192-8 459kB ± 0% 360kB ± 0% -21.42% (p=0.000 n=18+17) SubsetOf/2048-8192-8 460kB ± 0% 402kB ± 0% -12.59% (p=0.000 n=20+17) name old allocs/op new allocs/op delta SubsetOf/64-512-8 2.00 ± 0% 4.00 ± 0% +100.00% (p=0.000 n=20+20) SubsetOf/128-512-8 4.65 ±57% 5.55 ±28% +19.35% (p=0.028 n=20+20) SubsetOf/256-2048-8 2.00 ± 0% 4.00 ± 0% +100.00% (p=0.000 n=19+20) SubsetOf/512-2048-8 6.45 ±24% 7.75 ±10% +20.16% (p=0.000 n=20+16) SubsetOf/1024-8192-8 2.17 ±38% 4.00 ± 0% +84.62% (p=0.000 n=18+17) SubsetOf/2048-8192-8 8.65 ± 8% 10.00 ± 0% +15.61% (p=0.000 n=20+17) Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

pippolo84 · 2023-05-29T08:19:28Z

Needs a rebase

👍

pippolo84 · 2023-05-29T08:50:39Z

/test

pippolo84 · 2023-05-29T12:25:08Z

CI is green and reviews are in, marking ready-to-merge.

pippolo84 added kind/enhancement This would improve or streamline existing functionality. release-note/misc This PR makes changes that have no direct user impact. sig/agent Cilium agent related. labels May 19, 2023

pippolo84 marked this pull request as ready for review May 19, 2023 16:20

pippolo84 requested review from a team as code owners May 19, 2023 16:20

pippolo84 requested a review from jschwinger233 May 19, 2023 16:20

pippolo84 force-pushed the pr/pippolo84/refactor-slice-subset-of branch from 6b2d602 to b306002 Compare May 20, 2023 16:14

jschwinger233 approved these changes May 22, 2023

View reviewed changes

christarazi reviewed May 23, 2023

View reviewed changes

michi-covalent approved these changes May 23, 2023

View reviewed changes

sayboras approved these changes May 24, 2023

View reviewed changes

pippolo84 force-pushed the pr/pippolo84/refactor-slice-subset-of branch from b306002 to d19e797 Compare May 24, 2023 16:17

christarazi approved these changes May 24, 2023

View reviewed changes

christarazi mentioned this pull request May 25, 2023

Fix bug with toServices policy where service backend churn left stale CIDR identities #25687

Merged

christarazi added the dont-merge/needs-rebase This PR needs to be rebased because it has merge conflicts. label May 25, 2023

pippolo84 force-pushed the pr/pippolo84/refactor-slice-subset-of branch from d19e797 to 64cc1c6 Compare May 29, 2023 08:18

pippolo84 added 5 commits May 29, 2023 10:19

pkg/modules: Use slices.SubsetOf instead of set.SliceSubsetOf

37d1274

Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

pkg/slices: Add package-level documentation

a262151

Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

pkg/set: Remove unused pkg

70d77da

The only method exported has been superseded by slices.Subset so the package can be removed. Signed-off-by: Fabio Falzoi <fabio.falzoi@isovalent.com>

pippolo84 force-pushed the pr/pippolo84/refactor-slice-subset-of branch from 64cc1c6 to 24e9e2f Compare May 29, 2023 08:19

pippolo84 added ready-to-merge This PR has passed all tests and received consensus from code owners to merge. and removed dont-merge/needs-rebase This PR needs to be rebased because it has merge conflicts. labels May 29, 2023

maintainer-s-little-helper bot removed the ready-to-merge This PR has passed all tests and received consensus from code owners to merge. label May 29, 2023

julianwiedmann approved these changes May 29, 2023

View reviewed changes

julianwiedmann merged commit a7a483a into cilium:main May 29, 2023
62 checks passed

maintainer-s-little-helper bot added the ready-to-merge This PR has passed all tests and received consensus from code owners to merge. label May 29, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Refactor set.SliceSubsetOf #25559

Refactor set.SliceSubsetOf #25559

pippolo84 commented May 19, 2023 •

edited

jschwinger233 left a comment

christarazi left a comment •

edited

michi-covalent commented May 23, 2023 •

edited by maintainer-s-little-helper bot

Test Name

Failure Output

pippolo84 commented May 24, 2023

pippolo84 commented May 24, 2023 •

edited by maintainer-s-little-helper bot

Test Name

Failure Output

christarazi commented May 25, 2023

pippolo84 commented May 29, 2023

pippolo84 commented May 29, 2023

pippolo84 commented May 29, 2023

Refactor set.SliceSubsetOf #25559

Refactor set.SliceSubsetOf #25559

Conversation

pippolo84 commented May 19, 2023 • edited

jschwinger233 left a comment

Choose a reason for hiding this comment

christarazi left a comment • edited

Choose a reason for hiding this comment

michi-covalent commented May 23, 2023 • edited by maintainer-s-little-helper bot

Test Name

Failure Output

pippolo84 commented May 24, 2023

pippolo84 commented May 24, 2023 • edited by maintainer-s-little-helper bot

Test Name

Failure Output

christarazi commented May 25, 2023

pippolo84 commented May 29, 2023

pippolo84 commented May 29, 2023

pippolo84 commented May 29, 2023

pippolo84 commented May 19, 2023 •

edited

christarazi left a comment •

edited

michi-covalent commented May 23, 2023 •

edited by maintainer-s-little-helper bot

pippolo84 commented May 24, 2023 •

edited by maintainer-s-little-helper bot