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

Oh, and please note (as discussed in v1 or v2 of this patch as well)
that the lookup is also performed in walk_memory_blocks() for each
memory block in the range, e.g., via link_mem_sections() on system boot.
There we have O(N^2) as well.

--
Thanks,

David / dhildenb

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