Re: [RFC PATCH 3/4] rust/drm: Add DRM Jobqueue

[Alice Ryhl <aliceryhl@google.com>]

On Wed, Feb 11, 2026 at 02:53:49PM +0100, Philipp Stanner wrote:
> On Wed, 2026-02-11 at 12:52 +0000, Alice Ryhl wrote:
> > 
> > Yes, many people assume "list widely used in kernel" implies "list is a
> > good idea". Unfortunately it is not the case.
> > 
> > > > This applies to the red/black tree too, by the way.
> > > 
> > > Can't fully follow, you mean that RB trees are supposedly overused,
> > > too?
> > 
> > When I first suggested adding red/black tree abstractions in Rust
> > several years ago I was told by Greg that I couldn't do it because the
> > red/black tree was deprecated and no new users should be added.
> 
> Do you have a link or sth?

I could not easily find it again, sorry. It's been several years now
since that discussion.

> First time in my life that I hear that RB trees shouldn't be used. If
> something is deprecated for good one would hope that's obvious.

I'm not sure what the current status is ... it may have been somewhat
walked back and is now a "some people do not like rb trees" rather than
a deprecation.

> What's the justification? Should everyone use the B-Tree?
> RB trees are super widely used in CS. 

The justification is that every time you follow a pointer, it costs a
cache miss which is really expensive. Using an xarray or hashtable or
vector is much cheaper under most circumstances.

RB trees are used widely in CS because they are one of the simplest data
structures that provide O(log n) lookup. Such analysis usually does not
care about constant factors.

Alice