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

[David Hildenbrand]

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.

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

-- 
Thanks,

David / dhildenb