Re: [PATCH v12 0/5] Red-black tree abstraction needed by Rust Binder

[David Rheinsberg]

Hi

On Mon, Aug 26, 2024, at 11:56 AM, Alice Ryhl wrote:
> On Mon, Aug 26, 2024 at 11:15 AM David Rheinsberg <david@xxxxxxxxxxxx> wrote:
>> On Thu, Aug 22, 2024, at 6:37 PM, Matt Gilbride wrote:
>> > "This RFC uses the kernel's red-black tree for key/value mappings, but we
>> > are aware that the red-black tree is deprecated. We did this to make the
>> > performance comparison more fair, since C binder also uses rbtree for
>> > this. We intend to replace these with XArrays instead. That said, we
>> > don't think that XArray is a good fit for the range allocator, and we
>> > propose to continue using the red-black tree for the range allocator."
>>
>> (I might have missed this in previous versions of the patchset, so let me know if this has been answered before.)
>>
>> 1) Have you had any chance to compare this (performance wise) to the intrusive version used by the C Binder implementation? I assume the allocations are negligible, but tree-traversal should be significantly faster with intrusive trees when keys are next to the rb-node (e.g., binder range allocator, or ref/node lookup based on u64). With the allocating style, you likely double the number of cache-lines you load during a traversal, don't you?
>> We have been trying hard to keep the intrusive style, but never really measured the performance. So in case you do have numbers / experience, I would love to hear about it.
>
> The performance numbers are okay, see the linked RFC for numbers. But
> it's a known area of improvement.

The measurements in that RFC where about overall Binder performance, that's why I asked whether the abstractions where measured without the Binder code. But fair enough, seems like it did not affect overall module performance.

>> 2) Similar to 1), what is the reason to avoid the intrusive style? Is this just to simplify the API and keep it close to what rust-std does? Is the intention of this RFC to move towards an allocating style, or is work on the intrusive abstraction still welcome? I guess for compatibility to C-code, we still need the intrusive helpers, and likely for a long time.
>
> Ultimately, the reason is that the red/black tree is one of the very
> first abstractions that were written in the Rust for Linux project. We
> had not yet figured out how to correctly do intrusive structures at
> the time, and I have not taken the time to rewrite it with intrusive
> support. That said, we do know how to do it now: see the workqueue [1]
> and the linked list [2] for examples of how to do intrusive data
> structures.

Right, fair enough!

>> 3) I know that Matthew has spent significant time converting users to xarray, yet I have not seen any real deprecation of rbtrees. Especially when keys are user controlled or sparse, I do not see how xarray is a suitable replacement. Did I miss some discussions there? Or are you just referring to the general recommendation to consider xarray?
>
> Ah yes, the xarray doesn't work for every case. But I believe we can
> replace the red/black tree with a hash table instead in those cases.
> There are cases where xarray is a good fit, e.g. when the key is a
> thread id. Also for the u32 ids of remote nodes, as their values are
> controlled by the kernel. But for locally owned nodes, we would want a
> hash table instead.
>
> There's only really one case where I don't see any replacement to the
> red/black tree, and that is the range allocator. In C Binder, it uses
> a complex data structure where the nodes are intertwined between two
> rb trees and a linked list. Rust Binder also uses red/black trees
> here.

We need an ordered structure with user-controlled keys, so yeah, hashmaps and xarray are out (at least without secondary structures to help), that's why we always used rb-tree, and it worked fine.

Thanks for the answers!
David