On 1/31/23 17:21, Mark Michelson wrote:
> Using a bitmap makes the id-pool use less memory and be more
> cache-friendly. It theoretically should be faster since hashes do not
> have to be computed.
>
> This takes the approach of expanding the bitmap when necessary rather
> than allocating the entire space at once. This makes the approach less
> memory-intensive for id pools with a large theoretical maximum number of
> values.
>
> Signed-off-by: Mark Michelson <[email protected]>
> ---
> lib/id-pool.c | 110 +++++++++++++++++++-------------------------------
> 1 file changed, 41 insertions(+), 69 deletions(-)
>
> diff --git a/lib/id-pool.c b/lib/id-pool.c
> index 69910ad08..b24c681b6 100644
> --- a/lib/id-pool.c
> +++ b/lib/id-pool.c
> @@ -17,25 +17,20 @@
>
> #include <config.h>
> #include "id-pool.h"
> -#include "openvswitch/hmap.h"
> -#include "hash.h"
> +#include "bitmap.h"
>
> -struct id_node {
> - struct hmap_node node;
> - uint32_t id;
> -};
> +#define ID_POOL_BASE_ALLOC 64
>
> struct id_pool {
> - struct hmap map;
> + unsigned long *bitmap;
> + uint32_t bitmap_size; /* Current highest offset the bitmap can hold */
> uint32_t base; /* IDs in the range of [base, base + n_ids). */
> uint32_t n_ids; /* Total number of ids in the pool. */
> - uint32_t next_free_id; /* Possible next free id. */
> };
Hi, Mark. Thanks for the patch!
This is definitely an interesting idea. I have a couple of thoughts around it.
First is, I think, at some point the size of a bitmap will surpass the size
of an actual hash map, depending on how may IDs we have allocated and then
freed. But that will require us to continuously allocate a huge amount of IDs
first and then free them, so that doesn't seem to be an issue after all as
we'll likely hit memory limitations first.
Second is about performance. We have a benchmark for different implementations
of the ID pool in tests/test-id-fpool.c. If we ignore the concurrency parts,
we can use it to compare performance of the simple id-pool before and after.
So, I did. The results for 500K IDs are below.
Before:
$ ./tests/ovstest test-id-fpool benchmark 500000 1
Benchmarking n=500000 on 1 thread.
type\thread: 1 Avg
id-pool new: 109 109 ms
id-pool del: 112 112 ms
id-pool mix: 196 196 ms
id-pool rnd: 10000+ -1 ms
After:
$ ./tests/ovstest test-id-fpool benchmark 500000 1
Benchmarking n=500000 on 1 thread.
type\thread: 1 Avg
id-pool new: 879 879 ms
id-pool del: 10 10 ms
id-pool mix: 1722 1722 ms
id-pool rnd: 1354 1354 ms
There is a clear win in the performance of random add/del case. Current
implementation is not even able to finish the test, while bitmap shows
a fair performance.
However, there is a noticeable degradation in sequential allocation ('new')
and a mixed workload ('mix'). This is caused by execution of a bitmap
scan over 500K elements on each call, and that turns out to be slow at a
certain scale.
My guess, is that we can significantly improve performance by keeping the
'next_free_id' logic intact, so we don't need to perform a full scan every
single time. What do you think?
Best regards, Ilya Maximets.
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
