Message-Id: <274ba6bb-8027-4972-9ae2-db46844d528f@app.fastmail.com>
Date: Fri, 30 Aug 2024 12:00:53 +0200
From: "David Rheinsberg" <david@...dahead.eu>
To: "Alice Ryhl" <aliceryhl@...gle.com>
Cc: "Matt Gilbride" <mattgilbride@...gle.com>,
 "Miguel Ojeda" <ojeda@...nel.org>, "Alex Gaynor" <alex.gaynor@...il.com>,
 "Wedson Almeida Filho" <wedsonaf@...il.com>,
 "Boqun Feng" <boqun.feng@...il.com>, "Gary Guo" <gary@...yguo.net>,
 Björn Roy Baron <bjorn3_gh@...tonmail.com>,
 "Benno Lossin" <benno.lossin@...ton.me>,
 "Andreas Hindborg" <a.hindborg@...sung.com>,
 "Greg Kroah-Hartman" <gregkh@...uxfoundation.org>,
 Arve Hjønnevåg <arve@...roid.com>,
 "Todd Kjos" <tkjos@...roid.com>, "Martijn Coenen" <maco@...roid.com>,
 "Joel Fernandes" <joel@...lfernandes.org>,
 "Carlos Llamas" <cmllamas@...gle.com>,
 "Suren Baghdasaryan" <surenb@...gle.com>,
 "Christian Brauner" <brauner@...nel.org>, "Rob Landley" <rob@...dley.net>,
 "Davidlohr Bueso" <dave@...olabs.net>,
 "Michel Lespinasse" <michel@...pinasse.org>, rust-for-linux@...r.kernel.org,
 linux-kernel@...r.kernel.org
Subject: Re: [PATCH v12 0/5] Red-black tree abstraction needed by Rust Binder

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@...dahead.eu> 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

Powered by blists - more mailing lists