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

[Alice Ryhl]

On Mon, May 19, 2025 at 3:51 PM Jann Horn <jannh@xxxxxxxxxx> wrote:
>
> On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@xxxxxxxxxx> wrote:
> > This is a port of the Binder data structure introduced in commit
> > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > Rust.
>
> Stupid high-level side comment:
>
> That commit looks like it changed a simple linear rbtree scan (which
> is O(n) with slow steps) into a bitmap thing. A more elegant option
> might have been to use an augmented rbtree, reducing the O(n) rbtree
> scan to an O(log n) rbtree lookup, just like how finding a free area
> used to work in MM code... That would let you drop that ID pool bitmap
> entirely. But I guess actually wiring up an augmented rbtree into Rust
> would be very annoying too.

If we're talking approaches to avoid the bitmap entirely, it would
probably be easier to replace the rb tree with xarray than to use an
augmented one.

Alice