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

[David Hildenbrand]

On 08.01.20 15:21, Michal Hocko wrote:
> 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.

It's still wasted space even if it's not necessary in the common case.

> 
>> 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.

Yes, if it's worth for the common case :)

I don't really care in the and either, however, this seems to be the
easiest solution for now - IMHO.

-- 
Thanks,

David / dhildenb