linux-kernel - Re: [PATCH -next 0/5] rbtree: optimize frequent tree walks

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20200209174632.9c7b6ff20567853c05e5ee58@linux-foundation.org>
Date:   Sun, 9 Feb 2020 17:46:32 -0800
From:   Andrew Morton <akpm@...ux-foundation.org>
To:     Davidlohr Bueso <dave@...olabs.net>
Cc:     linux-kernel@...r.kernel.org, mcgrof@...nel.org,
        broonie@...nel.org, alex.williamson@...hat.com
Subject: Re: [PATCH -next 0/5] rbtree: optimize frequent tree walks

On Fri,  7 Feb 2020 10:03:00 -0800 Davidlohr Bueso <dave@...olabs.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?