On 6/9/21 3:09 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 > > [floor, last_alloc + nb_user * cache_size + 1]. > > where 'cache_size' is the number of ID in each per-user > cache. It is defined as 'ID_FPOOL_CACHE_SIZE' to 64. > > * 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 allocator is designed to scale reasonably well in multithread > 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-id-fpool benchmark 10000 1 > Benchmarking n=10000 on 1 thread. > type\thread: 1 Avg > id-fpool new: 1 1 ms > id-fpool del: 1 1 ms > id-fpool mix: 2 2 ms > id-fpool rnd: 2 2 ms > id-pool new: 4 4 ms > id-pool del: 2 2 ms > id-pool mix: 6 6 ms > id-pool rnd: 431 431 ms > > $ ./tests/ovstest test-id-fpool benchmark 100000 1 > Benchmarking n=100000 on 1 thread. > type\thread: 1 Avg > id-fpool new: 2 2 ms > id-fpool del: 2 2 ms > id-fpool mix: 3 3 ms > id-fpool rnd: 4 4 ms > id-pool new: 12 12 ms > id-pool del: 5 5 ms > id-pool mix: 16 16 ms > id-pool rnd: 10000+ -1 ms > > $ ./tests/ovstest test-id-fpool benchmark 1000000 1 > Benchmarking n=1000000 on 1 thread. > type\thread: 1 Avg > id-fpool new: 15 15 ms > id-fpool del: 12 12 ms > id-fpool mix: 34 34 ms > id-fpool rnd: 48 48 ms > id-pool new: 276 276 ms > id-pool del: 286 286 ms > id-pool mix: 448 448 ms > id-pool rnd: 10000+ -1 ms > > Running only a performance test on the fast pool: > > $ ./tests/ovstest test-id-fpool perf 1000000 1 > Benchmarking n=1000000 on 1 thread. > type\thread: 1 Avg > id-fpool new: 15 15 ms > id-fpool del: 12 12 ms > id-fpool mix: 34 34 ms > id-fpool rnd: 47 47 ms > > $ ./tests/ovstest test-id-fpool perf 1000000 2 > Benchmarking n=1000000 on 2 threads. > type\thread: 1 2 Avg > id-fpool new: 11 11 11 ms > id-fpool del: 10 10 10 ms > id-fpool mix: 24 24 24 ms > id-fpool rnd: 30 30 30 ms > > $ ./tests/ovstest test-id-fpool perf 1000000 4 > Benchmarking n=1000000 on 4 threads. > type\thread: 1 2 3 4 Avg > id-fpool new: 9 11 11 10 10 ms > id-fpool del: 5 6 6 5 5 ms > id-fpool mix: 16 16 16 16 16 ms > id-fpool rnd: 20 20 20 20 20 ms > > Signed-off-by: Gaetan Rivet <[email protected]> > --- > lib/automake.mk | 2 + > lib/id-fpool.c | 279 +++++++++++++++++++ > lib/id-fpool.h | 66 +++++ > tests/automake.mk | 1 + > tests/library.at | 4 + > tests/test-id-fpool.c | 615 ++++++++++++++++++++++++++++++++++++++++++ > 6 files changed, 967 insertions(+) > create mode 100644 lib/id-fpool.c > create mode 100644 lib/id-fpool.h > create mode 100644 tests/test-id-fpool.c > Reviewed-by: Maxime Coquelin <[email protected]> Thanks, Maxime _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
