Re: [PATCH v4 16/23] perf maps: Optimize tail insertion and small-append sorting

[Namhyung Kim <namhyung@kernel.org>]

On Fri, Nov 13, 2026 at 09:17:27AM -0800, Ian Rogers wrote:
> User-space map insertions (from /proc/pid/maps synthesis, runtime
> PERF_RECORD_MMAP2, and jitdump) and BPF ksymbol registrations all flow
> through maps__fixup_overlap_and_insert() -> first_ending_after().
> Currently first_ending_after() has a fast-path check for the first map
> (maps_by_address[0]), but no fast-path check for the last map
> (maps_by_address[high]). Because /proc/pid/maps entries are synthesized
> in ascending address order, every synthesized mapping starts at or after
> maps_by_address[high]'s end, yet currently executes the full O(log N)
> binary search loop. Add a tail check in first_ending_after() so
> non-overlapping ascending insertions complete in O(1).
> 
> Additionally, track the sorted prefix lengths (nr_maps_by_address_sorted
> and nr_maps_by_name_sorted) in struct maps:
> - In __maps__sort_by_address() and maps__sort_by_name(), when the
>   unsorted tail is small (k <= 8) or the total map count is small
>   (n <= 64), binary-insert the newly appended maps into the sorted
>   prefix instead of re-running qsort() over the entire array. This
>   avoids O(N^2 log N) re-sorting when maps__find_by_name() is called
>   repeatedly between single-map maps__insert() calls in
>   dso__process_kernel_symbol() and dso__split_kallsyms().
> - In maps__by_address_index() and maps__by_name_index(), binary-search
>   the known-sorted prefix before scanning only the unsorted tail.
> - Add a unit test in tools/perf/tests/maps.c covering the tail
>   fast-path and incremental binary-insertion sort.
> 
> Using 'perf bench internals maps':
> 
>   Before:
>     Average ascending insert + lookup: 63.370 usec (+- 0.476 usec)
>     Average append + lookup: 7477.450 usec (+- 20.829 usec)
>   After (-6.9% ascending, -98.7% append):
>     Average ascending insert + lookup: 58.970 usec (+- 0.609 usec)
>     Average append + lookup: 96.670 usec (+- 1.353 usec)
> 
> Signed-off-by: Ian Rogers <irogers@google.com>
> ---
[SNIP] 
> diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c
> index f808df2fe77b..98401fdd0e51 100644
> --- a/tools/perf/util/maps.c
> +++ b/tools/perf/util/maps.c
> @@ -1,6 +1,7 @@
>  // SPDX-License-Identifier: GPL-2.0
>  #include <errno.h>
>  #include <stdlib.h>
> +#include <linux/kernel.h>
>  #include <linux/zalloc.h>
>  #include "debug.h"
>  #include "dso.h"
> @@ -56,6 +57,16 @@ DECLARE_RC_STRUCT(maps) {
>  	 * maps_by_name.
>  	 */
>  	unsigned int	 nr_maps_allocated;
> +	/**
> +	 * @nr_maps_by_address_sorted: number of leading entries in
> +	 * maps_by_address that are known to be sorted.
> +	 */
> +	unsigned int	 nr_maps_by_address_sorted;
> +	/**
> +	 * @nr_maps_by_name_sorted: number of leading entries in maps_by_name
> +	 * that are known to be sorted.
> +	 */
> +	unsigned int	 nr_maps_by_name_sorted;

Can they be shorter like nr_{addr,name}_sorted?  Sorry for the naming
argument but I generally prefer short names.  As it has 'maps' in the
struct name, probably we can skip it.

Thanks,
Namhyung