Skip to content

Conversation

jrajahalme
Copy link
Member

@jrajahalme jrajahalme commented Sep 4, 2024

Store single owners directly in the MapStateEntry and switch to a map only when more than one owner is needed. This is done with the new ifset.Set.

Instead of a map of MapStateOwner interfaces, the Owners member of MapStateEntry is now a ifset.Set, which can hold a single interface value directly, or a more in a map. The new ifset.Set type uses an unexported memberMap type for its internal map, so the Set can hold any interface values (including empty interface value nil).

With this change the BenchmarkRegenerateCIDRDenyPolicyRules benchmark runs ~11% faster and uses ~15% less memory with ~9% less allocs than with the prior map only version.

@jrajahalme jrajahalme added sig/policy Impacts whether traffic is allowed or denied based on user-defined policies. dont-merge/preview-only Only for preview or testing, don't merge it. release-note/misc This PR makes changes that have no direct user impact. labels Sep 4, 2024
@jrajahalme jrajahalme requested review from a team as code owners September 4, 2024 17:27
@jrajahalme jrajahalme marked this pull request as draft September 4, 2024 17:27
@jrajahalme jrajahalme force-pushed the policy-reduce-allocs-tracking-mapstate-owners branch 2 times, most recently from 53a4733 to 0174f2b Compare September 9, 2024 16:05
@jrajahalme
Copy link
Member Author

/test

@jrajahalme jrajahalme force-pushed the policy-reduce-allocs-tracking-mapstate-owners branch from 0174f2b to 512c729 Compare September 30, 2024 10:27
@jrajahalme jrajahalme marked this pull request as ready for review September 30, 2024 10:28
Copy link
Member

@nebril nebril left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice! Two nitpicks left inline.

@jrajahalme jrajahalme force-pushed the policy-reduce-allocs-tracking-mapstate-owners branch from 512c729 to 176137b Compare October 1, 2024 07:47
@jrajahalme jrajahalme removed the dont-merge/preview-only Only for preview or testing, don't merge it. label Oct 1, 2024
@jrajahalme
Copy link
Member Author

/test

@jrajahalme jrajahalme force-pushed the policy-reduce-allocs-tracking-mapstate-owners branch from 176137b to db9b949 Compare October 3, 2024 06:14
@jrajahalme
Copy link
Member Author

Rebased to absorb the visibility annotation removal.

@jrajahalme
Copy link
Member Author

/test

@jrajahalme jrajahalme removed request for a team October 4, 2024 12:58
Copy link
Member

@pippolo84 pippolo84 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Did a first pass and currently trying to better understand the scope of the new Set data structure. Left some questions inline.

@maintainer-s-little-helper maintainer-s-little-helper bot added ready-to-merge This PR has passed all tests and received consensus from code owners to merge. labels Oct 4, 2024
@pippolo84 pippolo84 removed the ready-to-merge This PR has passed all tests and received consensus from code owners to merge. label Oct 4, 2024
@pippolo84
Copy link
Member

I don't know why the "ready-to-merge" label has been added since I just commented without acking the PR. 🤔
Anyway, I removed it.

@maintainer-s-little-helper 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 Oct 5, 2024
@jrajahalme jrajahalme added dont-merge/blocked Another PR must be merged before this one. and removed ready-to-merge This PR has passed all tests and received consensus from code owners to merge. labels Oct 5, 2024
@jrajahalme jrajahalme force-pushed the policy-reduce-allocs-tracking-mapstate-owners branch from db9b949 to 46f4441 Compare October 5, 2024 14:23
@jrajahalme
Copy link
Member Author

/test

@jrajahalme jrajahalme requested a review from pippolo84 October 5, 2024 14:31
@jrajahalme
Copy link
Member Author

ci-runtime hit by #35055

Copy link
Member

@pippolo84 pippolo84 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks, this looks better. 🙏
I've take a deeper look at the last two commits and left some additional feedback.

MapStateEntry.Merge need not be exported.

Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
MapState keeps separate maps for allows and denies. There is no need to
delete a key with a known entry value from both maps, as we can observe
if the entry is a delete or an allow entry.

Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
Add new generic container type set.Set optimized for cases where there
typically is only one value in the set. A singular member is stored
separately, while sets with more members use a map to store them.

Set is not a refecence value, like a map is, so whenever a Set is stored
by value (e.g., in a map as a value rather than via a pointer), the value
must be updated when the Set changes from holding n/one to multiple and
from multiple to n/one values.

Due to this added complexity the Set should only be used in cases where
there typically is at most one value, and the associated reduction in
allocations is critical for performance or for memory use.

The singular value is stored by reference in order to avoid the need for
an additional boolean field to tell if the singlular value member is
occupied or not. This saves about 10% of memory due to the 'set.Set'
itself being smaller and has roughly the same performance as an inline
value, when tested for interface member types.

Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
Use the new 'set.Set' to store owners in MapStateEntry.

Extend MapStateEntry.String() to output the owners, dependents, and
listener priority. This eases unit test debugging going forward.

With this change the BenchmarkRegenerateCIDRDenyPolicyRules benchmark
runs ~10% faster and uses ~15% less memory with ~9% less allocs than with
the prior map only version.

Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
@jrajahalme jrajahalme force-pushed the policy-reduce-allocs-tracking-mapstate-owners branch from 46f4441 to 9143174 Compare October 8, 2024 09:57
@jrajahalme
Copy link
Member Author

/test

Copy link
Member

@pippolo84 pippolo84 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks! 💯

@jrajahalme jrajahalme removed the dont-merge/blocked Another PR must be merged before this one. label Oct 8, 2024
@jrajahalme jrajahalme enabled auto-merge October 8, 2024 11:20
@jrajahalme jrajahalme added this pull request to the merge queue Oct 8, 2024
@maintainer-s-little-helper 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 Oct 8, 2024
Merged via the queue into cilium:main with commit 8418dbb Oct 8, 2024
63 checks passed
@jrajahalme jrajahalme deleted the policy-reduce-allocs-tracking-mapstate-owners branch October 8, 2024 12:18
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
ready-to-merge This PR has passed all tests and received consensus from code owners to merge. release-note/misc This PR makes changes that have no direct user impact. sig/policy Impacts whether traffic is allowed or denied based on user-defined policies.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants