Revision - 8f5bbad - Add and benchmark alternative immset methods

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

Files
Changes

Permalinks

MAINTAINERS.md

# Maintainers

See [Governance](https://github.com/cilium/community/blob/main/GOVERNANCE.md) for
governance, commit, and vote guidelines as well as committer responsibilities.
Everybody listed is a committer as per governance definition. See the 
[Contributor Ladder](https://github.com/cilium/community/blob/main/CONTRIBUTOR-LADDER.md)
to learn how to level up through the project.

## Cilium Committers

 * [Aditi Ghag] (Isovalent)
 * [Alexandre Perrin] (Isovalent)
 * [André Martins] (Isovalent)
 * [Beatriz Martínez] (Isovalent)
 * [Bill Mulligan] (Isovalent)
 * [Bruno M. Custódio] (Isovalent)
 * [Casey Callendrello] (Isovalent)
 * [Chance Zibolski] (Isovalent)
 * [Chris Tarazi] (Isovalent)
 * [Daniel Borkmann] (Isovalent)
 * [Dan Wendlandt] (Isovalent)
 * [Deepesh Pathak]
 * [Dylan Reimerink] (Isovalent)
 * [Gilberto Bertin] (Isovalent)
 * [Glib Smaga] (Isovalent)
 * [Hemanth Malla] (Datadog)
 * [Ian Vernon]
 * [Jarno Rajahalme] (Isovalent)
 * [Joe Stringer] (Isovalent)
 * [John Fastabend] (Isovalent)
 * [Julian Wiedmann] (Isovalent)
 * [Jussi Mäki] (Isovalent)
 * [Kornilios Kourtis] (Isovalent)
 * [Laurent Bernaille] (Datadog)
 * [Liz Rice] (Isovalent)
 * [Lorenz Bauer] (Isovalent)
 * [Louis DeLosSantos] (Isovalent)
 * [Maciej Kwiek] (Isovalent)
 * [Martynas Pumputis] (Isovalent)
 * [Michal Rostecki] (Deepfence)
 * [Michi Mutsuzaki] (Isovalent)
 * [Natália Réka Ivánkó] (Isovalent)
 * [Nathan Sweet] (Isovalent)
 * [Nick Young] (Isovalent)
 * [Nicolas Busseneau] (Isovalent)
 * [Nirmoy Das] (AMD)
 * [Paul Chaignon] (Isovalent)
 * [Quentin Monnet] (Isovalent)
 * [Robin Hahling] (Isovalent)
 * [Sebastian Wicki] (Isovalent)
 * [Tam Mach] (Isovalent)
 * [Thomas Graf] (Isovalent)
 * [Timo Beckers] (Isovalent)
 * [Tobias Klauser] (Isovalent)
 * [Tom Hadlaw] (Isovalent)
 * [Vlad Ungureanu] (Palantir)
 * [Weilong Cui] (Google)
 * [Yongkun Gui] (Google)
 * [Yutaro Hayakawa] (Isovalent)

## Cilium & Hubble Emeritus Committers

We would like to acknowledge previous committers and their huge contributions to our collective success:

 * [Eloy Coto] (Red Hat)
 * [Ilya Dmitrichenko] (Docker)
 * [Ray Bejjani]
 * [Tom Payne]
 * [Zang Li] (Google)


Please see the AUTHORS file for the full list of contributors to the Cilium
project.

[Aditi Ghag]: https://github.com/aditighag
[Alexandre Perrin]: https://github.com/kaworu
[André Martins]: https://github.com/aanm
[Beatriz Martínez]: https://github.com/b3a-dev
[Bill Mulligan]: https://github.com/xmulligan
[Bruno M. Custódio]: https://github.com/bmcustodio
[Casey Callendrello]: https://github.com/squeed
[Chance Zibolski]: https://github.com/chancez
[Chris Tarazi]: https://github.com/christarazi
[Daniel Borkmann]: https://github.com/borkmann
[Dan Wendlandt]: https://github.com/danwent
[Deepesh Pathak]: https://github.com/fristonio
[Dylan Reimerink]: https://github.com/dylandreimerink
[Eloy Coto]: https://github.com/eloycoto
[Gilberto Bertin]: https://github.com/jibi
[Glib Smaga]: https://github.com/glibsm
[Hemanth Malla]: https://github.com/hemanthmalla
[Ian Vernon]: https://github.com/ianvernon
[Ilya Dmitrichenko]: https://github.com/errordeveloper
[Jarno Rajahalme]: https://github.com/jrajahalme
[Joe Stringer]: https://github.com/joestringer
[John Fastabend]: https://github.com/jrfastab
[Julian Wiedmann]: https://github.com/julianwiedmann
[Jussi Mäki]: https://github.com/joamaki
[Kornilios Kourtis]: https://github.com/kkourt
[Laurent Bernaille]: https://github.com/lbernail
[Liz Rice]: https://github.com/lizrice
[Lorenz Bauer]: https://github.com/lmb
[Louis DeLosSantos]: https://github.com/ldelossa
[Maciej Kwiek]: https://github.com/nebril
[Martynas Pumputis]: https://github.com/brb
[Michal Rostecki]: https://github.com/vadorovsky
[Michi Mutsuzaki]: https://github.com/michi-covalent
[Natália Réka Ivánkó]: https://github.com/sharlns
[Nathan Sweet]: https://github.com/nathanjsweet
[Nick Young]: https://github.com/youngnick
[Nicolas Busseneau]: https://github.com/nbusseneau
[Nirmoy Das]: https://github.com/nirmoy
[Paul Chaignon]: https://github.com/pchaigno
[Quentin Monnet]: https://github.com/qmonnet
[Ray Bejjani]: https://github.com/raybejjani
[Robin Hahling]: https://github.com/rolinh
[Sebastian Wicki]: https://github.com/gandro
[Tam Mach]: https://github.com/sayboras
[Thomas Graf]: https://github.com/tgraf
[Timo Beckers]: https://github.com/ti-mo
[Tobias Klauser]: https://github.com/tklauser
[Tom Hadlaw]: https://github.com/tommyp1ckles
[Tom Payne]: https://github.com/twpayne
[Vlad Ungureanu]: https://github.com/ungureanuvladvictor
[Weilong Cui]: https://github.com/Weil0ng
[Yongkun Gui]: https://github.com/anfernee
[Yutaro Hayakawa]: https://github.com/YutaroHayakawa
[Zang Li]: https://github.com/lzang

Showing with 0 additions and 0 deletions (0 / 0 diffs computed)

Computing file changes ...