lkml.org 
[lkml]   [2020]   [Jan]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH v3] drivers/base/memory.c: cache blocks in radix tree to accelerate lookup
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?
--
Michal Hocko
SUSE Labs

\
 
 \ /
  Last update: 2020-01-09 09:50    [W:0.124 / U:4.492 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site