lkml.org 
[lkml]   [2020]   [Feb]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH -next 0/5] rbtree: optimize frequent tree walks
On Fri,  7 Feb 2020 10:03:00 -0800 Davidlohr Bueso <dave@stgolabs.net> wrote:

> This series introduces the ll_rbtree interface to optimize rbtree users
> that incur in frequent in-order tree iterations (even full traversals).
> This can be seen as an abstraction to what is already done for dealing
> with VMAs (albeit non-augmented trees).
>
> Mainly, it trades off higher per-node memory footprint (two extra pointers)
> for minimal runtime overhead to gain O(1) brachless next and prev node
> pointers. See patch 1 for full details, but, for example, the following
> tables show the benefits vs the costs of using this new interface.
>
> +--------+--------------+-----------+
> | #nodes | plain rbtree | ll-rbtree |
> +--------+--------------+-----------+
> | 10 | 138 | 24 |
> | 100 | 7,200 | 425 |
> | 1000 | 17,000 | 8,000 |
> | 10000 | 501,090 | 222,500 |
> +--------+--------------+-----------+
>
> 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.
> The overhead of tree modifications can be seen in the following table, comparing
> cycles to insert+delete:
>
> +--------+--------------+------------------+-----------+
> | #nodes | plain rbtree | augmented rbtree | ll-rbtree |
> +--------+--------------+------------------+-----------+
> | 10 | 530 | 840 | 600 |
> | 100 | 7,100 | 14,200 | 7,800 |
> | 1000 | 265,000 | 370,000 | 205,200 |
> | 10000 | 4,400,000 | 5,500,000 | 4,200,000 |
> +--------+--------------+------------------+-----------+
>
>
> Patch 1 introduces the ll_rbtree machinery.
>
> Patches 2-5 convert users that might benefit from the new interface.
>
> Full details and justifications for the conversion are in each
> individual patch.
>
> I am Cc'ing some of the maintainers of the users I have converted to the whole
> series such that it can the numbers and interface details can be easily seen.
>
> Please consider for v5.7.

Seems that all the caller sites you've converted use a fairly small
number of rbnodes, so the additional storage shouldn't be a big
problem. Are there any other sites you're eyeing? If so, do you expect
any of those will use a significant amount of memory for the nodes?

And... are these patches really worth merging? Complexity is added,
but what end-user benefit can we expect?

\
 
 \ /
  Last update: 2020-02-10 02:47    [W:0.106 / U:0.300 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site