Skip to main content

Browse the archive

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 
Add and benchmark alternative immset methods
 
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
Raw File
CODE_OF_CONDUCT.md 
## Community Code of Conduct v1.0

This is Code of Conduct is based on the [CNCF Code of
Conduct](https://github.com/cncf/foundation/blob/main/code-of-conduct.md).
See the referred document for translated versions into different languages. The
text below is modified with Cilium community specific contact details.

### Contributor Code of Conduct

As contributors and maintainers of this project, and in the interest of fostering
an open and welcoming community, we pledge to respect all people who contribute
through reporting issues, posting feature requests, updating documentation,
submitting pull requests or patches, and other activities.

We are committed to making participation in this project a harassment-free experience for
everyone, regardless of level of experience, gender, gender identity and expression,
sexual orientation, disability, personal appearance, body size, race, ethnicity, age,
religion, or nationality.

Examples of unacceptable behavior by participants include:

* The use of sexualized language or imagery
* Personal attacks
* Trolling or insulting/derogatory comments
* Public or private harassment
* Publishing others' private information, such as physical or electronic addresses,
 without explicit permission
* Other unethical or unprofessional conduct.

Project maintainers have the right and responsibility to remove, edit, or reject
comments, commits, code, wiki edits, issues, and other contributions that are not
aligned to this Code of Conduct. By adopting this Code of Conduct, project maintainers
commit themselves to fairly and consistently applying these principles to every aspect
of managing this project. Project maintainers who do not follow or enforce the Code of
Conduct may be permanently removed from the project team.

This code of conduct applies both within project spaces and in public spaces
when an individual is representing the project or its community.

Instances of abusive, harassing, or otherwise unacceptable behavior may be
reported by contacting the code of conduct team via 
[conduct@cilium.io](mailto:conduct@cilium.io).

This Code of Conduct is adapted from the Contributor Covenant
(http://contributor-covenant.org), version 1.2.0, available at
http://contributor-covenant.org/version/1/2/0/
back to top