On 4/12/21 5:19 PM, Gaetan Rivet wrote:
> The current id-pool module is slow to allocate the
> next valid ID, and can be optimized when restricting
> some properties of the pool.
>
> Those restrictions are:
>
> * No ability to add a random ID to the pool.
>
> * A new ID is no more the smallest possible ID. It is
> however guaranteed to be in the range of
> [base, next_id]. Multiple users of the pool are
> registered, each with a thread-local cache for
> better scalability and the next_id is one after the
> latest ID added to any user cache.
> The allocation range can be written as:
>
> [base, last_alloc + nb-user * cache-size + 1].
>
> * A user should never free an ID that is not allocated.
> No checks are done and doing so will duplicate the spurious
> ID. Refcounting or other memory management scheme should
> be used to ensure an object and its ID are only freed once.
>
> This pool is designed to scale reasonably well in multi-thread
> setup. As it is aimed at being a faster replacement to the
> current id-pool, a benchmark has been implemented alongside
> unit tests.
>
> The benchmark is composed of 4 rounds: 'new', 'del', 'mix', and 'rnd'.
> Respectively
>
> + 'new': only allocate IDs
> + 'del': only free IDs
> + 'mix': allocate, sequential free, then allocate ID.
> + 'rnd': allocate, random free, allocate ID.
>
> Randomized freeing is done by swapping the latest allocated ID with any
> from the range of currently allocated ID, which is reminiscent of the
> Fisher-Yates shuffle. This evaluates freeing non-sequential IDs,
> which is the more natural use-case.
>
> For this specific round, the id-pool performance is such that a timeout
> of 10 seconds is added to the benchmark:
>
> $ ./tests/ovstest test-seq-pool benchmark 10000 1
> Benchmarking n=10000 on 1 thread.
> type\thread: 1 Avg
> seq-pool new: 1 1 ms
> seq-pool del: 0 0 ms
> seq-pool mix: 1 1 ms
> seq-pool rnd: 1 1 ms
> id-pool new: 0 0 ms
> id-pool del: 1 1 ms
> id-pool mix: 1 1 ms
> id-pool rnd: 1201 1201 ms
>
> $ ./tests/ovstest test-seq-pool benchmark 100000 1
> Benchmarking n=100000 on 1 thread.
> type\thread: 1 Avg
> seq-pool new: 2 2 ms
> seq-pool del: 5 5 ms
> seq-pool mix: 5 5 ms
> seq-pool rnd: 5 5 ms
> id-pool new: 8 8 ms
> id-pool del: 5 5 ms
> id-pool mix: 11 11 ms
> id-pool rnd: 10000+ ****** ms
>
> $ ./tests/ovstest test-seq-pool benchmark 1000000 1
> Benchmarking n=1000000 on 1 thread.
> type\thread: 1 Avg
> seq-pool new: 23 23 ms
> seq-pool del: 49 49 ms
> seq-pool mix: 53 53 ms
> seq-pool rnd: 53 53 ms
> id-pool new: 190 190 ms
> id-pool del: 173 173 ms
> id-pool mix: 273 273 ms
> id-pool rnd: 10042+ ****** ms
>
> $ ./tests/ovstest test-seq-pool benchmark 1000000 2
> Benchmarking n=1000000 on 2 threads.
> type\thread: 1 2 Avg
> seq-pool new: 40 39 39 ms
> seq-pool del: 33 33 33 ms
> seq-pool mix: 89 91 90 ms
> seq-pool rnd: 146 151 148 ms
> id-pool new: 485 485 485 ms
> id-pool del: 541 542 541 ms
> id-pool mix: 550 600 575 ms
> id-pool rnd: 10048+ 10003+ ****** ms
>
> $ ./tests/ovstest test-seq-pool benchmark 1000000 4
> Benchmarking n=1000000 on 4 threads.
> type\thread: 1 2 3 4 Avg
> seq-pool new: 40 39 40 40 39 ms
> seq-pool del: 24 28 28 30 27 ms
> seq-pool mix: 60 63 69 69 65 ms
> seq-pool rnd: 195 197 202 202 199 ms
> id-pool new: 478 471 482 485 479 ms
> id-pool del: 474 469 467 474 471 ms
> id-pool mix: 558 558 611 545 568 ms
> id-pool rnd: 10121+ 10076+ 10030+ 10167+ ****** ms
>
> Signed-off-by: Gaetan Rivet <[email protected]>
> Reviewed-by: Eli Britstein <[email protected]>
> ---
> lib/automake.mk | 2 +
> lib/seq-pool.c | 198 +++++++++++++++
> lib/seq-pool.h | 66 +++++
> tests/automake.mk | 1 +
> tests/library.at | 5 +
> tests/test-seq-pool.c | 543 ++++++++++++++++++++++++++++++++++++++++++
> 6 files changed, 815 insertions(+)
> create mode 100644 lib/seq-pool.c
> create mode 100644 lib/seq-pool.h
> create mode 100644 tests/test-seq-pool.c
>
Reviewed-by: Maxime Coquelin <[email protected]>
Thanks,
Maxime
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
