orderedIDSet.add scanned the entire existing slice for every inserted ID,
so building a Collection was quadratic in the number of packages sharing an
index key. This is most visible in idsByType: package types are few, so that
index accumulates nearly every package in the SBOM into a single set, and
each Add rescans it.
Keep the ordered slice (ordering and dedup semantics are unchanged) and add
a hash index for membership checks. The index is only built once a set grows
beyond a small threshold, so the many single-element sets held by idsByName
and idsByPath do not pay for a map, while the large idsByType sets get
constant-time lookups.
BenchmarkCollectionAdd (Apple M2 Pro), packages sharing one type:
packages before after speedup
1,000 1.37 ms 0.76 ms 1.8x
10,000 100.31 ms 9.80 ms 10.2x
50,000 2,423.79 ms 34.46 ms 70.3x
The tradeoff is memory: sets past the threshold allocate an index map,
about 14% more bytes at 50,000 packages, with allocation counts unchanged.
Signed-off-by: Oleksandr Vodotiiets <61548316+avodotiiets@users.noreply.github.com>
Oleksandr Vodotiiets