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

[Boqun Feng <boqun.feng@gmail.com>]

On Tue, May 20, 2025 at 06:05:52AM -0700, Alice Ryhl wrote:
> On Tue, May 20, 2025 at 5:56 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> >
> > On Tue, May 20, 2025 at 05:42:51AM -0700, Alice Ryhl wrote:
> > > On Mon, May 19, 2025 at 10:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > >
> > > > On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote:
> > > > > On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > > > >
> > > > > > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > > > > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> 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
> > > > > >
> > > > > > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> > > > >
> > > > > We need the smallest ID without a value, not the smallest ID in use.
> > > > >
> > > >
> > > > Ok, but it shouldn't be hard to write a Rust function that search that,
> > > > right? My point was mostly the Rust rbtree binding can do O(log n)
> > > > search. I have no idea about "even so, should we try something like Jann
> > > > suggested". And I think your other reply basically says no.
> > >
> > > We would need to store additional data in the r/b tree to know whether
> > > to go left or right, so it would be somewhat tricky. We don't have an
> >
> > Hmm... I'm confused, I thought you can implement a search like that by
> > doing what RBTree::raw_entry() does except that when Ordering::Equal you
> > always go left or right (depending on whether you want to get an unused
> > ID less or greater than a key value), i.e. you always search until you
> > get an Vacant entry. Why do you need store additional data for that?
> > Maybe I'm missing something here?
> 
> Let's say you're at the root node of an r/b tree, and you see that the
> root node has id 17, the left node has id 8, and the right node has id
> 25. Do you go left or right?
> 

I went to check what commit 15d9da3f818c actually did and I understand
what you mean now ;-) In your case, the rbtree cannot have nodes with
the same key. If Jann can provide the O(log n) search that could help in
this case, I'm happy to learn about it ;-)

Regards,
Boqun

> Alice