Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Date:   Mon, 10 Feb 2020 21:44:55 +0000
From:   Luis Chamberlain <mcgrof@kernel.org>
To:     Davidlohr Bueso <dave@stgolabs.net>
Cc:     akpm@linux-foundation.org, linux-kernel@vger.kernel.org,
        broonie@kernel.org, alex.williamson@redhat.com,
        Davidlohr Bueso <dbueso@suse.de>
Subject: Re: [PATCH 1/5] lib/rbtree: introduce linked-list rbtree interface
Message-ID: <20200210214455.GO11244@42.do-not-panic.com>
References: <20200207180305.11092-1-dave@stgolabs.net>
 <20200207180305.11092-2-dave@stgolabs.net>
 <20200210200712.GM11244@42.do-not-panic.com>
 <20200210212832.2i2i3kbybhk2rcee@linux-p48b>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20200210212832.2i2i3kbybhk2rcee@linux-p48b>
User-Agent: Mutt/1.10.1 (2018-07-13)
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On Mon, Feb 10, 2020 at 01:28:32PM -0800, Davidlohr Bueso wrote:
> On Mon, 10 Feb 2020, Luis Chamberlain wrote:
> > > 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.
> 
> I don't think we want an all or nothing approach

I'm not suggesting all or nothing for all rb tree users, I'm suggesting
an all or nothing approach to users of a *new* API. That is, users would
still need to be converted over, and *iff* the new kconfig entry is
enabled would the two pointers be added / used, otherwise we'd fallback
to the default current boring rbtree.

> as different users in the
> kernel have different needs and some users are simply unable to deal with
> enlarging data structures, while others have no problem.

The approach would allow distros which are not yet sure if two pointers
are worth it yet to continue to chug on as they used to, but also allow
them to explore this prospect in a flexible way.

  Luis