/test

I'm assuming this was discussed, but did you consider extending the key of the Trie with the clusterID bits instead of having a map of Tries? What's the tradeoff there?

Excellent question, TBH we didn't think about this. My hunch is that we almost always end up in a scenario where:

• the number of prefixes in the ipcache is high
• the number of keys of the CIDRTrieMap (i.e: the number of clusters) is almost always 1 or << number of CIDRs

With these assumptions (one or very few keys in the map), I think that prepending the clusterID bits to each CIDRTrie key (that is, to each upserted CIDR) might be less efficient compared to the map overhead. But I didn't run any benchmark to confirm this.

One possible improvement to the current "bare" map might be to extend this:

to have a map type optimized to store a single mapping.

Running the existing BenchmarkInjectLabels benchmark to compare the CIDRTrieMap in a single cluster scenario against the previous CIDRTrie shows that with the map we are ~8% slower:

                │   old.txt   │               new.txt               │
                │   sec/op    │    sec/op     vs base               │
InjectLabels-24   9.343µ ± 2%   10.079µ ± 4%  +7.88% (p=0.000 n=10)

                │   old.txt    │            new.txt             │
                │     B/op     │     B/op      vs base          │
InjectLabels-24   6.501Ki ± 1%   6.317Ki ± 4%  ~ (p=0.218 n=10)

                │  old.txt   │            new.txt             │
                │ allocs/op  │ allocs/op   vs base            │
InjectLabels-24   57.00 ± 0%   57.00 ± 0%  ~ (p=1.000 n=10) ¹
¹ all samples are equal

/test

It looks like this PR needs a rebase to make CI happy.

With these assumptions (one or very few keys in the map), I think that prepending the clusterID bits to each CIDRTrie key (that is, to each upserted CIDR) might be less efficient compared to the map overhead. But I didn't run any benchmark to confirm this.

There's the aspect of constructing the key which you'll pay for the additional bits - but that's identical in the map of trie variant. In the actual Trie I think they'd matter very little:

• in the single cluster case, the only change would be that the topmost node would have its prefix extended
• in the multi cluster case, you'd branch at most sizeof(clusterid) times before getting to the same trie the hash map maps to.

Speaking of, what's the actual number of bits in the clusterID in the DP? would it be feasible to store an array of pointers instead of a proper map, with trivial indexing?

Speaking of, what's the actual number of bits in the clusterID in the DP?

IIRC the type is a u16, although currently only either 8 (default) or 9 (extended clustermesh) bits can be used.

• in the single cluster case, the only change would be that the topmost node would have its prefix extended

IIUC your proposal, we'll end storing a copy of the key (a cmtypes.PrefixCluster instance) inside each trie node for each upsertion. Thus we'll have 4 more bytes for each node (since clusterID is a uint32):

Speaking of, what's the actual number of bits in the clusterID in the DP? would it be feasible to store an array of pointers instead of a proper map, with trivial indexing?

IIRC the type is a u16, although currently only either 8 (default) or 9 (extended clustermesh) bits can be used.

It is a uint32 actually:

But if 9 bits only are used we could have a [512]*CIDRTrie inner type. I can also rely on the cmtypes.ClusterIDExt511 constant. I'll try to implement this variant too and run the above benchmark against it. 👍

IIRC the type is a u16, although currently only either 8 (default) or 9 (extended clustermesh) bits can be used.

It is a uint32 actually:

Yeah, I was referring to the datapath. Not sure if it even matters at the end of the day though in terms of space usage, considering alignment and alike.

Yeah, I was referring to the datapath. Not sure if it even matters at the end of the day though in terms of space usage, considering alignment and alike.

Ok, let's go ahead with this approach, then. We can still rework this in the future with the ideas we discussed above 👍

/test

• ci-e2e-upgrade is hitting CI: Cilium E2E Upgrade: no-interrupted-connections #37520
• ci-ipsec-upgrade is hitting CI: Cilium E2E Upgrade (ci-e2e-upgrade): Found unexpected packet drops: "No mapping for NAT masquerade" #38466