Revision 8f5bbad392b904d1f5b7e9f4ee262f339d999056 authored by Damian Sawicki on 13 June 2024, 08:41:41 UTC, committed by Dylan Reimerink on 15 June 2024, 08:22:04 UTC
This commit adds alternative implementations of methods of ImmSet: * InsertNew(xs ...T) * DeleteNew(xs ...T) * UnionNew(s2 ImmSet[T]) * DifferenceNew(s2 ImmSet[T]) and benchmarks these implementations agains the existing ones. Benchmarking results: * for Insert, the proposed method becomes faster already with the container of size 1000, and then it performed 10x faster for size 10,000 and 100x faster for size 100,000; * for Delete, the proposed method becomes faster already with the container of size 1000, and then it performed ~5x faster for size 10,000; * for Difference, the proposed method was already 4x faster for size 100, and then it performed 7x faster for size 1000, 35x times faster for size 10,000, and 193x faster for size 100,000; * for Union, the proposed method performs slightly faster, but gains do not visibly grow with increasing size. Theoretically, the proposed solutions have improved computational complexity: * the complexity of Insert is O(len(s.xs)*len(xs)), and the complexity of InsertNew is O(len(s.xs)+len(xs)); * the complexity of Delete is O(len(s.xs)*len(xs)), and the complexity of DeleteNew is O(len(s.xs)+len(xs)); * the complexity of Difference is O(len(s.xs)*len(s2.xs)) because it uses Delete internally, and the complexity of DifferenceNew O(len(s.xs)+len(s2.xs)); * the complexity of Union is harder to estimate: it involves sorting a slice of size n=len(s.xs)+len(s2.xs), but this slice is a concatenation of two sorted slices, so most likely this does not lead to the usual O(n*log(n)) complexity; of course, it is at least O(n); the complexity of UnionNew is O(n). Signed-off-by: Damian Sawicki <dsawicki@google.com>
1 parent 5aa52b0
SECURITY-INSIGHTS.yml
header:
schema-version: '1.0.0'
expiration-date: '2025-01-26T01:00:00.000Z'
last-updated: '2024-01-26'
last-reviewed: '2024-01-26'
project-url: https://github.com/cilium/cilium
license: https://github.com/cilium/cilium/blob/main/LICENSE
project-lifecycle:
status: active
bug-fixes-only: false
core-maintainers:
- https://github.com/cilium/cilium/blob/main/MAINTAINERS.md
roadmap: https://docs.cilium.io/en/stable/community/roadmap
contribution-policy:
accepts-pull-requests: true
accepts-automated-pull-requests: true
dependencies:
third-party-packages: true
dependencies-lists:
- https://github.com/cilium/cilium/blob/main/go.mod
sbom:
- sbom-format: SPDX
sbom-url: https://docs.cilium.io/en/stable/configuration/sbom
distribution-points:
- https://github.com/cilium/cilium
- https://hub.docker.com/u/cilium
- https://quay.io/organization/cilium
documentation:
- https://docs.cilium.io/en/stable/
security-assessments:
- auditor-name: ADA Logics
auditor-url: https://adalogics.com
auditor-report: https://github.com/cilium/cilium.io/blob/main/Security-Reports/CiliumSecurityAudit2022.pdf
report-year: 2022
- auditor-name: ADA Logics
auditor-url: https://adalogics.com
auditor-report: https://github.com/cilium/cilium.io/blob/main/Security-Reports/CiliumFuzzingAudit2022.pdf
report-year: 2022
security-contacts:
- type: email
value: security@cilium.io
security-testing:
- tool-type: sca
tool-name: Mend Renovate
tool-url: https://www.mend.io/renovate
tool-version: latest
integration:
ad-hoc: false
ci: true
before-release: true
- tool-type: fuzzer
tool-name: OSS-Fuzz
tool-url: https://github.com/google/oss-fuzz
tool-version: latest
integration:
ad-hoc: false
ci: true
before-release: true
- tool-type: sast
tool-name: Grype
tool-url: https://github.com/anchore/grype
tool-version: latest
integration:
ad-hoc: false
ci: true
before-release: true
vulnerability-reporting:
accepts-vulnerability-reports: true
security-policy: https://github.com/cilium/cilium/security
Computing file changes ...
