Subject: Re: libkern's rb tree
To: Joerg Sonnenberger <>
From: SODA Noriyuki <>
List: tech-kern
Date: 10/19/2007 11:49:46
>>>>> On Fri, 19 Oct 2007 03:05:28 +0200,
      Joerg Sonnenberger <> said:

> Splay trees are also a lot worse for the CPU caches due to the constant
> modifications.

That's not always true, it depends on the access pattern of the
If there is high locality in the application, splay tree may be
more cache-friendly than redblack tree.

> The operations on splay trees are only cheap on average, individual
> operations can be O(n).

But usually that isn't a problem, because amortised cost is O(log(N)),
and average cost is often more cheaper than redblack tree.

> That makes it not very attractive for a number of important use
> cass. Splay trees are only attractive if a high locality of access is
> expected and IMO many cases just don't satisfy that property.

At least benchmarking is needed to determine which is better.