Re: [PATCH 1/5] lib/rbtree: introduce linked-list rbtree interface

[Luis Chamberlain]

On Fri, Feb 07, 2020 at 10:03:01AM -0800, Davidlohr Bueso wrote:
> When doing in-order tree traversals, the rb_next() and rb_prev() helpers can
> be sub-optimal as plain node representations incur in extra pointer chasing
> up the tree to compute the corresponding node. This can impact negatively
> in performance when traversals are a common thing. This, for example, is what
> we do in our vm already to efficiently manage VMAs.
> 
> This interface provides branchless O(1)

I think including the word "branchless" does injustice to the
optimization, just O(1) sells it to me more to how I read the code.
Why is the "branchless" prefix needed here?

> access to the first node as well as
> both its in-order successor and predecessor. This is done at the cost of higher
> memory footprint: mainly additional prev and next pointers for each node. Such
> benefits can be seen in this table showing the amount of cycles it takes to
> do a full tree traversal:
> 
>    +--------+--------------+-----------+
>    | #nodes | plain rbtree | ll-rbtree |
>    +--------+--------------+-----------+
>    |     10 |          138 |        24 |
>    |    100 |        7,200 |       425 |
>    |   1000 |       17,000 |     8,000 |
>    |  10000 |      501,090 |   222,500 |
>    +--------+--------------+-----------+

Sold, however I wonder if we can have *one new API* where based on just one
Kconfig you either get the two pointers or not, the performance gain
then would only be observed if this new kconfig entry is enabled. The
benefit of this is that we don't shove the performance benefit down
all user's throughts but rather this can be decided by distributions
and system integrators.

> diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
> index 523d54b60087..fe38fb257931 100644
> --- a/Documentation/rbtree.txt
> +++ b/Documentation/rbtree.txt
> @@ -5,6 +5,7 @@ Red-black Trees (rbtree) in Linux
>  
>  :Date: January 18, 2007
>  :Author: Rob Landley <rob@xxxxxxxxxxx>
> +         Davidlohr Bueso <dave@xxxxxxxxxxxx>
>  
>  What are red-black trees, and what are they for?
>  ------------------------------------------------
> @@ -226,6 +227,79 @@ trees::
>  				 struct rb_augment_callbacks *);
>  
>  
> +Linked-list rbtrees
> +-------------------
> +
> +When doing in-order tree traversals, the rb_next() and rb_prev() helpers can
> +be sub-optimal as plain node representations incur in extra pointer chasing
> +up the tree to compute the corresponding node. This can have a negative impact
> +in latencies in scenarios where tree traversals are not rare. This interface
> +provides branchless O(1) access to the first node as well as both its in-order
> +successor and predecessor. This is done at the cost of higher memory footprint:
> +mainly additional prev and next pointers for each node, essentially duplicating
> +the tree data structure. While there are other node representations that optimize
> +getting such pointers without bloating the nodes as much, such as keeping a
> +parent pointer or threaded trees where the nil prev/next pointers are recycled;
> +both incurring in higher runtime penalization for common modification operations
> +as well as any rotations.
> +
> +As with regular rb_root structure, linked-list rbtrees are initialized to be
> +empty via::
> +
> +  struct llrb_root mytree = LLRB_ROOT;
> +
> +Insertion and deletion are defined by:
> +
> +  void llrb_insert(struct llrb_root *, struct llrb_node *, struct llrb_node *);
> +  void llrb_erase(struct llrb_node *, struct llrb_root *);
> +
> +The corresponding helpers needed to iterate through a tree are the following,
> +equivalent to an optimized version of the regular rbtree version:
> +
> +  struct llrb_node *llrb_first(struct llrb_root *tree);
> +  struct llrb_node *llrb_next(struct rb_node *node);
> +  struct llrb_node *llrb_prev(struct rb_node *node);
> +
> +
> +Inserting data into a Linked-list rbtree
> +----------------------------------------
> +
> +Because llrb trees can exist anywhere regular rbtrees, the steps are similar.
> +The search for insertion differs from the regular search in two ways. First
> +the caller must keep track of the previous node,

can you explain here why, even though its clear in the code: its because
we need to pass it as a parameter when the new node is inserted into the
rb tree.

Also, what about a selftest for this?

Reviewed-by: Luis Chamberlain <mcgrof@xxxxxxxxxx>   

  Luis