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

[Greg Kroah-Hartman]

On Thu, Jan 09, 2020 at 09:49:55AM +0100, Michal Hocko wrote:
> On Tue 07-01-20 22:48:04, 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?
> 
> Greg, Rafael, this seems to be your domain. Do you have any opinion on
> this?

No one has cared about the speed of that call as it has never been on
any "fast path" that I know of.  And it should just be O(N), isn't it
just walking the list of devices in order?

If the "memory subsystem" wants a faster lookup for their objects,
there's nothing stopping you from using your own data structure for the
pointers to the objects if you want.  Just be careful about the lifetime
rules.

thanks,

greg k-h