Re: [PATCH v8 5/5] rust: add dynamic ID pool abstraction for bitmap

[Yury Norov <yury.norov@gmail.com>]

On Wed, May 21, 2025 at 03:57:55AM +0000, Carlos Llamas wrote:
> On Mon, May 19, 2025 at 08:57:04PM -0400, Yury Norov wrote:
> > + Carlos Llamas

...

> > Carlos, can you please elaborate your motivation to switch to bitmaps?
> > Have you considered rb-trees with O(logn) lookup?
> 
> Yeah, we tried rb-trees. There was even a patch that implemented the
> augmented logic. See this:
> https://lore.kernel.org/all/20240917030203.286-1-ebpqwerty472123@gmail.com/
> IIRC, it just didn't make sense for our use case because of the extra
> memory bytes required for this solution. The performance ended up being
> the same (from my local testing).
> 
> I'm not certain of this but one potential factor is that the rb nodes
> are in-strucutre members allocated separately. This can lead to more
> cache misses when traversing them. I don't know how applicable this
> would be for the Rust implementation though. Take that with a grain of
> salt as I didn't actually look super close while running the tests.
> 
> I would also note, this whole logic wouldn't be required if userspace
> wasn't using these descriptor IDs as vector indexes. At some point this
> practice will be fixed and we can remove the "dbitmap" implementation.

Yeah, I expected to get this kind of feedback from real-world testing.
Your reply to the patch you mentioned above answers all my questions:

https://lore.kernel.org/all/ZwdWe_I2p3zD-v1O@google.com/

Let's stick to bitmaps unless someone shows clear benefit of using any
alternative approach, both in time and memory perspectives, supported
by testing.

Thanks,
Yury