Messages in this thread | | | Subject | Re: [PATCH v4] drivers/base/memory.c: cache blocks in radix tree to accelerate lookup | From | David Hildenbrand <> | Date | Wed, 15 Jan 2020 20:09:48 +0100 |
| |
On 09.01.20 22:25, Scott Cheloha wrote: > Searching for a particular memory block by id is an O(n) operation > because each memory block's underlying device is kept in an unsorted > linked list on the subsystem bus. > > We can cut the lookup cost to O(log n) if we cache the memory blocks in > a radix tree. With a radix tree cache in place both memory subsystem > initialization and memory hotplug run palpably faster on systems with a > large number of memory blocks. > > Signed-off-by: Scott Cheloha <cheloha@linux.ibm.com> > Acked-by: David Hildenbrand <david@redhat.com> > Acked-by: Nathan Lynch <nathanl@linux.ibm.com> > Acked-by: Michal Hocko <mhocko@suse.com>
Soooo,
I just learned that radix trees are nowadays only a wrapper for xarray (for quite a while already!), and that the xarray interface shall be used in new code.
include/linux/radix-tree.h:
/* Keep unconverted code working */ #define radix_tree_root xarray [...]
Do we want to convert this code before sending it to Linus'? (resend this patch, or a fixup on top)
-- Thanks,
David / dhildenb
| |