Messages in this thread | ![/](/images/icornerl.gif) | | Subject | Re: [PATCH v3] drivers/base/memory.c: cache blocks in radix tree to accelerate lookup | From | David Hildenbrand <> | Date | Wed, 8 Jan 2020 16:23:04 +0100 |
| |
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
| ![\](/images/icornerr.gif) |