From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=74.125.82.70 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1795245453; b=uazDZwuag7vUaG8vDthbrhh/IE/IMZkvYKPTXNToFnAjJ5i/ToK/taM+FkMfYE+crlUc m9vhm5P31o528dcaHMXhz84VafMGuNIfL+uWFow+tV0SJuJVuy+kM387i8+/cAKL8OuPu lW2umHADaEW31/VwT3i2ynnQdN10PpDGmZNI6e5JJi1usnFDUwUQNxIQQAkNtAibHgvzJ qVCJZt0hxq2eTIM+7lvBj07BcavH8eQZsqkFpPK/n/rnERv90vc6K2gU7oVgstrbVYF1r r2y976q84hGbW/kohk8VhO3zq3nXdeXr28DmI1vkP+XqLLLRSEVhymkamAStTbAWMfg== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1795245453; h=DMARC-Filter:Received:DKIM-Signature:X-Google-DKIM-Signature: X-Forwarded-Encrypted:X-Gm-Message-State:X-Received:Date:In-Reply-To: Mime-Version:References:X-Mailer:Message-ID:Subject:From:To:Cc: Content-Type; bh=MHlNyxo+mafQ5vFC1JiNOwKYJbzxb2VMwl/G1pzxtY4=; b=juZqZCWtc2NR+i0BZjO+7Tt26z4bKIEbDI+kRR51ie7YaNTqQPHMjnEgkWFzmZptgPpE hkg3r4x+5dDDqJWNMPvQFEiM+DmGb85cMe7XE1yQxRQ3RYs6rvgA5qXvmoVWR0pOErWSy T95hgcLzw443NSpqAj6uq4k5e+S9m2RX+olqsO/IxZN7ovVRXuh146JgkU+AzdkKSDS8R 0xH27QNWVQc5BNPwJy5iwQZTz1FxdY3qcReb6Woky4SrruJ6Gvb+Q3eaaojAJtALu1eeH G1e/3/yEYt3AK4qSxWuRFR0Xl3s0iSzNlgpVY6iubfy9YCD0nff/6Na9QCQEBRVCSmw== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass header.d=google.com header.i=@google.com header.a=rsa-sha256 header.s=20260707 header.b=BF2XwRn8; arc=none smtp.remote-ip=74.125.82.70 Received: from mail-dl1-f70.google.com (mail-dl1-f70.google.com [74.125.82.70]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CE209606A332 for ; Sat, 21 Nov 2026 07:17:32 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.2 smtp.subspace.kernel.org CE209606A332 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.a=rsa-sha256 header.s=20260707 header.b=BF2XwRn8 Received: by mail-dl1-f70.google.com with SMTP id a92af1059eb24-1383723dfddso1741681c88.0 for ; Fri, 20 Nov 2026 23:17:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20260707; t=1795245452; x=1795850252; darn=vger.kernel.org; h=content-type:cc:to:from:subject:message-id:references:mime-version :in-reply-to:date:from:to:cc:subject:date:message-id:reply-to :content-type; bh=MHlNyxo+mafQ5vFC1JiNOwKYJbzxb2VMwl/G1pzxtY4=; b=BF2XwRn8Ppf3kZavS/Zy+efvXwHrhsbt5qLT7SG4Y3+XML3enH7Ob0VpMc8mQ+5xRq 9thTTmxaA2eWShX6LTvlyhdRMCk0X07GQ4CVqPZTqu0FBIbeJSU9YSwggGOa5Jl+Amx9 IH7Ndhm02E8QRi6hQeINEiDnkqVopKhmLvOVG4kf+z0pglBLCuTu4OiEgSkW1MO6i/aG JZUzXH/KAZdv3NrIhgUCdSgjSc77d0ip02+b1lkXaYmX3rxRSxanVjqdCdDHro7LINjz MLDSx9424zenax8hVbkDXBzVc7AWHDzy39M0VuAYRIHrgRER+GiY8QsbittknD1F7oXi BFvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1795245452; x=1795850252; h=content-type:cc:to:from:subject:message-id:references:mime-version :in-reply-to:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to:content-type; bh=MHlNyxo+mafQ5vFC1JiNOwKYJbzxb2VMwl/G1pzxtY4=; b=WCrAds94R0ndU7b18O8TB1K+L8Lri91YSLAIGNmNxDkmhElZvy12HX/50JSlzRjVo4 EkPMrOHpHRDIQgit7CdBrPwepTq2dPSVZukZBtnBuLkM5vJhw6PHdOK9ZubPbPuPisNK k1MUn2SLaK60LHtWIA9wFQFiaEW5rTZBfCfmiOG/F5FQbL0KXHelKZvubYj8AKnnuPcb DMpMfEnzgTSjeu5xYSF3X1kG8yimz0ZXcRj6mqNoLACeqQS5wnO1aORRM6UbWLqvtaT4 Z61N9kSVN2K6hg2FyxrU4jOJB1FOIMPogInYHnFGnG7+mGIOtRm8HVegCOMRdpuHkJsz 3cUA== X-Forwarded-Encrypted: i=1; AL+hErHHzgTyLjra4XcpN7pVmeSvfrZwbI2WwgIaVMpjzXVSQNvMeb7iItDQzpbsYKGiPCFBBO4kG66hzh+chyw=@vger.kernel.org X-Gm-Message-State: APuU4Z9IR5IEm0NVceCB49+0w0wJ7a0AkX5QOuY3njhve8l1OTQpXucw /AHq2p4dO88NjhannS7P/rit0bf9e+Se8D2CGr1UTcpBpPLXkhfhqZu7ESrOdHPOPL1+o39Sf2H UUjraaOHj2Q== X-Received: from dyjz27.prod.google.com ([2002:a05:7300:b1b:b0:381:fb4c:34e1]) (user=irogers job=prod-delivery.src-stubby-dispatcher) by 2002:a05:7022:b909:b0:1b4:f3af:355e with SMTP id a92af1059eb24-1b5568a660emr4864446c88.13.1795245451525; Fri, 20 Nov 2026 23:17:31 -0800 (PST) Date: Fri, 20 Nov 2026 23:16:47 -0800 In-Reply-To: <20261121071651.67118-1-irogers@google.com> X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list Mime-Version: 1.0 References: <20261121071651.67118-1-irogers@google.com> X-Mailer: git-send-email 2.56.1.750.gf70dc682cf-goog Message-ID: <20261121071651.67118-7-irogers@google.com> Subject: [PATCH v7 06/10] perf symbol: Replace qsort() with natural-run merge sort From: Ian Rogers To: Namhyung Kim , Arnaldo Carvalho de Melo , Alireza Haghdoost , Ian Rogers Cc: Peter Zijlstra , Ingo Molnar , Jiri Olsa , Adrian Hunter , James Clark , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org Content-Type: text/plain; charset="UTF-8" ELF .symtab and .dynsym sections are typically already mostly ordered by address in ascending runs. Invoking full-array qsort() across pre-ordered ELF runs spends avoidable CPU time in symbol comparisons and does not guarantee relative order preservation for equal-start symbol aliases across C library implementations. Replace qsort() in symbols__sort_locked() with a stable natural-run merge sort (symbols__sort_range_with_tmp() and symbols__merge_runs()), falling back to in-place binary insertion sort (symbols__insertion_sort_range()) for small arrays (cnt <= 64) or on scratch-buffer allocation failure. Using 'perf bench internals symbols': Before: Average DSO load + sort: 6.242 msec (+- 0.057 msec) Average bulk insert + lookup: 1404.150 usec (+- 18.752 usec) After (-7.0% load, -13.9% bulk): Average DSO load + sort: 5.808 msec (+- 0.047 msec) Average bulk insert + lookup: 1209.250 usec (+- 18.446 usec) Signed-off-by: Ian Rogers --- tools/perf/util/symbol.c | 183 +++++++++++++++++++++++++++++++++++++-- 1 file changed, 174 insertions(+), 9 deletions(-) diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c index 4119e061e939..114fe5ea3891 100644 --- a/tools/perf/util/symbol.c +++ b/tools/perf/util/symbol.c @@ -263,14 +263,171 @@ static inline bool symbol__less_or_equal(const struct symbol *a, const struct sy return a->start <= b->start; } -static int symbols__sort_cmp(const void *vlhs, const void *vrhs) +static unsigned int symbols__upper_bound(struct symbol **arr, unsigned int len, + const struct symbol *sym) { - const struct symbol *lhs = *((const struct symbol **)vlhs); - const struct symbol *rhs = *((const struct symbol **)vrhs); + unsigned int low = 0, high = len; - if (lhs->start != rhs->start) - return lhs->start < rhs->start ? -1 : 1; - return 0; + while (low < high) { + unsigned int mid = low + (high - low) / 2; + + if (symbol__less_or_equal(arr[mid], sym)) + low = mid + 1; + else + high = mid; + } + return low; +} + +static void symbols__insertion_sort_range(struct symbol **arr, + unsigned int start, + unsigned int end) +{ + for (unsigned int i = start + 1; i < end; i++) { + struct symbol *sym = arr[i]; + + if (!symbol__less_or_equal(arr[i - 1], sym)) { + unsigned int pos = start + + symbols__upper_bound(&arr[start], i - start, sym); + + memmove(&arr[pos + 1], &arr[pos], + (i - pos) * sizeof(struct symbol *)); + arr[pos] = sym; + } + } +} + +static void symbols__merge_runs(struct symbol **arr, + unsigned int left, + unsigned int mid, + unsigned int right, + struct symbol **tmp) +{ + unsigned int first_left, left_len, right_len; + unsigned int i, j, dst; + + if (left >= mid || mid >= right) + return; + if (symbol__less_or_equal(arr[mid - 1], arr[mid])) + return; + + first_left = left + symbols__upper_bound(&arr[left], mid - left, arr[mid]); + left_len = mid - first_left; + right_len = right - mid; + + if (left_len <= right_len) { + memcpy(tmp, &arr[first_left], left_len * sizeof(struct symbol *)); + i = 0; + j = mid; + dst = first_left; + while (i < left_len && j < right) { + if (symbol__less_or_equal(tmp[i], arr[j])) + arr[dst++] = tmp[i++]; + else + arr[dst++] = arr[j++]; + } + if (i < left_len) + memcpy(&arr[dst], &tmp[i], (left_len - i) * sizeof(struct symbol *)); + } else { + memcpy(tmp, &arr[mid], right_len * sizeof(struct symbol *)); + i = mid; + j = right_len; + dst = right; + while (i > first_left && j > 0) { + if (symbol__less_or_equal(arr[i - 1], tmp[j - 1])) + arr[--dst] = tmp[--j]; + else + arr[--dst] = arr[--i]; + } + if (j > 0) + memcpy(&arr[first_left], tmp, j * sizeof(struct symbol *)); + } +} + +struct symbol_run { + unsigned int start; + unsigned int len; +}; + +static void symbols__sort_range_with_tmp(struct symbol **arr, unsigned int n, + struct symbol **tmp) +{ + struct symbol_run runs[64]; + unsigned int nr_runs = 0; + unsigned int i = 0; + + if (n <= 32) { + symbols__insertion_sort_range(arr, 0, n); + return; + } + + while (i < n) { + unsigned int start = i++; + + if (i < n) { + if (symbol__less_or_equal(arr[i - 1], arr[i])) { + while (i < n && symbol__less_or_equal(arr[i - 1], arr[i])) + i++; + } else { + while (i < n && !symbol__less_or_equal(arr[i - 1], arr[i])) + i++; + for (unsigned int lo = start, hi = i - 1; lo < hi; lo++, hi--) { + struct symbol *swap = arr[lo]; + + arr[lo] = arr[hi]; + arr[hi] = swap; + } + } + } + + if (i - start < 32 && i < n) { + i = min(start + 32U, n); + symbols__insertion_sort_range(arr, start, i); + } + + runs[nr_runs++] = (struct symbol_run){ + .start = start, + .len = i - start, + }; + + while (nr_runs > 1) { + unsigned int r = nr_runs - 2; + + if (nr_runs >= 3 && + runs[nr_runs - 3].len <= + runs[nr_runs - 2].len + runs[nr_runs - 1].len) { + if (runs[nr_runs - 3].len < runs[nr_runs - 1].len) + r = nr_runs - 3; + } else if (runs[nr_runs - 2].len > runs[nr_runs - 1].len && + nr_runs < ARRAY_SIZE(runs)) { + break; + } + + symbols__merge_runs(arr, runs[r].start, + runs[r + 1].start, + runs[r + 1].start + runs[r + 1].len, + tmp); + runs[r].len += runs[r + 1].len; + if (r + 2 < nr_runs) + runs[r + 1] = runs[r + 2]; + nr_runs--; + } + } + + while (nr_runs > 1) { + unsigned int r = nr_runs - 2; + + if (nr_runs >= 3 && runs[nr_runs - 3].len < runs[nr_runs - 1].len) + r = nr_runs - 3; + symbols__merge_runs(arr, runs[r].start, + runs[r + 1].start, + runs[r + 1].start + runs[r + 1].len, + tmp); + runs[r].len += runs[r + 1].len; + if (r + 2 < nr_runs) + runs[r + 1] = runs[r + 2]; + nr_runs--; + } } static void symbols__sort_locked(struct symbols *symbols) @@ -278,9 +435,17 @@ static void symbols__sort_locked(struct symbols *symbols) if (symbols->sorted) return; - if (symbols->cnt > 1) { - qsort(symbols->symbols, symbols->cnt, sizeof(struct symbol *), - symbols__sort_cmp); + if (symbols->cnt <= 64) { + symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt); + } else { + struct symbol **tmp = malloc(((symbols->cnt + 1) / 2) * sizeof(struct symbol *)); + + if (tmp) { + symbols__sort_range_with_tmp(symbols->symbols, symbols->cnt, tmp); + free(tmp); + } else { + symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt); + } } symbols->sorted = true; } -- 2.56.1.750.gf70dc682cf-goog