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

[Michal Hocko]

On Thu 09-01-20 09:56:23, Greg KH wrote:
> 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?

Which means that if you have to call it N times then it is O(N^2) and
that is the case here because you are adding N memblocks. See
memory_dev_init
  for each memblock
    add_memory_block
      init_memory_block
        find_memory_block_by_id # checks all existing devices
        register_memory
	  device_register # add new device
  
In this particular case find_memory_block_by_id is called mostly to make
sure we are no re-registering something multiple times which shouldn't
happen so it sucks to spend a lot of time on that. We might think of
removing that for boot time but who knows what kind of surprises we
might see from crazy HW setups.
 
> 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.

The main question is whether replacing the linked list with a radix tree
in the generic code is something more meaningful.
-- 
Michal Hocko
SUSE Labs