From 659ad3492b913c9033d47cb406ac5754780875b6 Mon Sep 17 00:00:00 2001 From: Ian Rogers Date: Fri, 9 Feb 2024 19:17:41 -0800 Subject: perf maps: Switch from rbtree to lazily sorted array for addresses Maps is a collection of maps primarily sorted by the starting address of the map. Prior to this change the maps were held in an rbtree requiring 4 pointers per node. Prior to reference count checking, the rbnode was embedded in the map so 3 pointers per node were necessary. This change switches the rbtree to an array lazily sorted by address, much as the array sorting nodes by name. 1 pointer is needed per node, but to avoid excessive resizing the backing array may be twice the number of used elements. Meaning the memory overhead is roughly half that of the rbtree. For a perf record with "--no-bpf-event -g -a" of true, the memory overhead of perf inject is reduce fom 3.3MB to 3MB, so 10% or 300KB is saved. Map inserts always happen at the end of the array. The code tracks whether the insertion violates the sorting property. O(log n) rb-tree complexity is switched to O(1). Remove slides the array, so O(log n) rb-tree complexity is degraded to O(n). A find may need to sort the array using qsort which is O(n*log n), but in general the maps should be sorted and so average performance should be O(log n) as with the rbtree. An rbtree node consumes a cache line, but with the array 4 nodes fit on a cache line. Iteration is simplified to scanning an array rather than pointer chasing. Overall it is expected the performance after the change should be comparable to before, but with half of the memory consumed. To avoid a list and repeated logic around splitting maps, maps__merge_in is rewritten in terms of maps__fixup_overlap_and_insert. maps_merge_in splits the given mapping inserting remaining gaps. maps__fixup_overlap_and_insert splits the existing mappings, then adds the incoming mapping. By adding the new mapping first, then re-inserting the existing mappings the splitting behavior matches. Signed-off-by: Ian Rogers Acked-by: Namhyung Kim Cc: K Prateek Nayak Cc: James Clark Cc: Vincent Whitchurch Cc: Alexey Dobriyan Cc: Colin Ian King Cc: Changbin Du Cc: Masami Hiramatsu Cc: Song Liu Cc: Leo Yan Cc: Athira Rajeev Cc: Liam Howlett Cc: Artem Savkov Cc: bpf@vger.kernel.org Signed-off-by: Namhyung Kim Link: https://lore.kernel.org/r/20240210031746.4057262-2-irogers@google.com --- tools/perf/util/map.c | 1 + 1 file changed, 1 insertion(+) (limited to 'tools/perf/util/map.c') diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c index 7a785a47467e..14a5ea70d81e 100644 --- a/tools/perf/util/map.c +++ b/tools/perf/util/map.c @@ -168,6 +168,7 @@ struct map *map__new(struct machine *machine, u64 start, u64 len, if (dso == NULL) goto out_delete; + assert(!dso->kernel); map__init(result, start, start + len, pgoff, dso); if (anon || no_dso) { -- cgit