Re: [PATCH v3] drivers/base/memory.c: cache blocks in radix tree to accelerate lookup

[Michal Hocko <mhocko@kernel.org>]

On Wed 08-01-20 14:36:48, David Hildenbrand wrote:
> On 07.01.20 22:48, Michal Hocko wrote:
> > [Cc Andrew]
> > 
> > On Tue 17-12-19 13:32:38, Scott Cheloha wrote:
> >> Searching for a particular memory block by id is slow because each block
> >> device is kept in an unsorted linked list on the subsystem bus.
> > 
> > Noting that this is O(N^2) would be useful.
> > 
> >> Lookup is much faster if we cache the blocks in a radix tree.
> > 
> > While this is really easy and straightforward, is there any reason why
> > subsys_find_device_by_id has to use such a slow lookup? I suspect nobody
> > simply needed a more optimized data structure for that purpose yet.
> > Would it be too hard to use radix tree for all lookups rather than
> > adding a shadow copy for memblocks?
> 
> As reply to v1/v2 I argued that this is really only needed if there are
> many devices. So far that seems to be applicable to the memory subsystem
> mostly. No need to waste space on all other subsystems IMHO.

How much space are we talking about? Radix tree (resp. xarray) is a
small data structure and even when we have to allocate nodes dynamically
this doesn't sound like a huge overhead (especially with a small id
space). I might be missing something of course because I am not familiar
with this part the driver model and I would be interested what
maintainers think about that.

> As you said, right now it's easy and straightforward, if we find out
> other subsystems need it we can generalize/factor out.

I will not really push for that but it is almost always better to
improve a common infrastructure rather than build up a dedicated
workarouns in some users. Especially when there are no strong arguments
for that.
-- 
Michal Hocko
SUSE Labs