From nobody Sun Feb 8 10:49:39 2026 Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 115C0185084 for ; Wed, 3 Jul 2024 17:21:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1720027289; cv=none; b=QmK+wZzlYql3FxeIbll6G9cquDYdAWXSVRR39eIdIXtaCMac74Z8qP6CJbM4k/k90tSHZY6fBtp0P243p94KoeIyvqXSAAzNldUrzi28+VnfWEdLD8B93zm2s90HhM6phKe+oj8GyIQMumEvfNhBnPocCi/YY3vyYINrq/Rp+rs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1720027289; c=relaxed/simple; bh=FLT+4gnVINf7KJ4R59I14FmcEQjfh9jmHIWgHUoNFp8=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=Jd5r6KayKxB+cfPPRjabrR5j88mEvnJ5kfBLgopZuShc3m5a90ul38fDvml1c7FsTGd3GfsOKYgT8iP0bV+XpIUAVXZGI2o8bTmIeFm/YHqnibucO+yObm78UWGisDxX6QLZoo482VQAqKGWMx/ayae23xCy1xlrqJsMaNg/6+0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=Se5z1rIF; arc=none smtp.client-ip=209.85.219.201 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.b="Se5z1rIF" Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-e033e353528so8589503276.0 for ; Wed, 03 Jul 2024 10:21:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1720027287; x=1720632087; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=aKtmGrW1KJvIQ629mFQxU63SX5o3BneZ2oyJxXNdreU=; b=Se5z1rIFwHsSvZ5yMsKBNUYByHpppybNEo8O0tgV9EKzTFAdf4OQ1/UlnmG8fLY4gV qORiAgT3tBOb0pk6cfG3OIJfcYe7hD8QzpBjTnGkAOSHDz5TbKsy6fPlrjnIrX90fR6Z TvJHhr6GjMJeSs5Wf/WCSwZO1F/aLcEWe+mq6VknhzWLgnAHffJDfjnAehjvG3useSlH Rbdv9XrNcxaaUjzOaezlKA9b+Feyq1S/hOv+9dgwyfydqxCm5IuJoNC5swnklu+q0F66 y5e7hIGIQ4Df7ZlOPxjJx9Hc6BpTLo179wWMKqmYDeLl4jdlRkFEAGQBllw5WzbpHAxU 5tQg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1720027287; x=1720632087; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=aKtmGrW1KJvIQ629mFQxU63SX5o3BneZ2oyJxXNdreU=; b=nflGyi5YYLqrmMo25up2l7ay2A0qPl9hX2I33Nv0TTbCQ0Ukoh1gquQYFGlZnnW8vc lj+UvdmLlh5JRcBHBmMDCzeH5ybBRwhzgJ5f6pDGXK3icRZ7eqgWQ7x5KNDFNN6jOOI2 Xf4LjrSXCb0GIXoIVQbDrzzEtoIpjNw3pftdzhZCmJEQz/7EdlVDIiADlKRvYnCWwNl0 n2DPghhwaNBHuYXKojYp33HrrMmZfX/UOKcT7GfPirDmgsVFV1irtxFDlDy+XiCBr/qv RhTR5QVplfMAYmGhi28rDz0pjKu4uYZtDKROGJSk11PKMlGXHt3A0mMXmKiqJrmZgkQm jxKA== X-Forwarded-Encrypted: i=1; AJvYcCUsNKEehNYzX6TM4cVUW05qxW89rLK8LONZ0vkmvh6rj3KYtJZ4z/TVHr4syMPnPHapSuflie6bp9Z5wP9ui6qvHgpTZlmfr1NeI2Xh X-Gm-Message-State: AOJu0YwGJYwYdmfZiPnV2yYL8hkCFmHXbIyQWbbcYOo12mMKWfdD76w1 Lwl2hGB2laSfGaSkjSeSSNk+/3lZAIp63C4vEYdhdXDCFCcVAOSIp+2aS5CvhxItgGKhK4C0wHo UP+Llbw== X-Google-Smtp-Source: AGHT+IHCpYgI1BZEzBCU2eJZ/7hopipDE9WsWDyt5JVynM2pswdESfEjBC6p1Zsq9sgn9+jXRngYeqpBdgyf X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:bdc2:f28d:3877:f0f2]) (user=irogers job=sendgmr) by 2002:a05:6902:1501:b0:dfd:a911:5722 with SMTP id 3f1490d57ef6-e036ec2dc31mr24953276.8.1720027287156; Wed, 03 Jul 2024 10:21:27 -0700 (PDT) Date: Wed, 3 Jul 2024 10:21:16 -0700 In-Reply-To: <20240703172117.810918-1-irogers@google.com> Message-Id: <20240703172117.810918-2-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240703172117.810918-1-irogers@google.com> X-Mailer: git-send-email 2.45.2.803.g4e1b14247a-goog Subject: [PATCH v1 1/2] perf comm str: Avoid sort during insert From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Kan Liang , Athira Rajeev , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, Steinar Gunderson , Matt Fleming Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The array is sorted, so just move the elements and insert in order. Reported-by: Matt Fleming Signed-off-by: Ian Rogers Tested-by: Matt Fleming --- tools/perf/util/comm.c | 29 ++++++++++++++++++----------- 1 file changed, 18 insertions(+), 11 deletions(-) diff --git a/tools/perf/util/comm.c b/tools/perf/util/comm.c index 233f2b6edf52..49b79cf0c5cc 100644 --- a/tools/perf/util/comm.c +++ b/tools/perf/util/comm.c @@ -86,14 +86,6 @@ static struct comm_str *comm_str__new(const char *str) return result; } =20 -static int comm_str__cmp(const void *_lhs, const void *_rhs) -{ - const struct comm_str *lhs =3D *(const struct comm_str * const *)_lhs; - const struct comm_str *rhs =3D *(const struct comm_str * const *)_rhs; - - return strcmp(comm_str__str(lhs), comm_str__str(rhs)); -} - static int comm_str__search(const void *_key, const void *_member) { const char *key =3D _key; @@ -169,9 +161,24 @@ static struct comm_str *comm_strs__findnew(const char = *str) } result =3D comm_str__new(str); if (result) { - comm_strs->strs[comm_strs->num_strs++] =3D result; - qsort(comm_strs->strs, comm_strs->num_strs, sizeof(struct comm_str *), - comm_str__cmp); + int low =3D 0, high =3D comm_strs->num_strs - 1; + int insert =3D comm_strs->num_strs; /* Default to inserting at the end.= */ + + while (low <=3D high) { + int mid =3D low + (high - low) / 2; + int cmp =3D strcmp(comm_str__str(comm_strs->strs[mid]), str); + + if (cmp < 0) { + low =3D mid + 1; + } else { + high =3D mid - 1; + insert =3D mid; + } + } + memmove(&comm_strs->strs[insert + 1], &comm_strs->strs[insert], + (comm_strs->num_strs - insert) * sizeof(struct comm_str *)); + comm_strs->num_strs++; + comm_strs->strs[insert] =3D result; } } up_write(&comm_strs->lock); --=20 2.45.2.803.g4e1b14247a-goog From nobody Sun Feb 8 10:49:39 2026 Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9AA4C187540 for ; Wed, 3 Jul 2024 17:21:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1720027294; cv=none; b=U9V1dtFtRbWsgKGiEN0cPjI1dyh+WmzPmk57IF6+ppXaAKuy0zrIlfpOaSg94FJVPQjd/dyDTk74aVJmh5z1aiHHnmzk0NFvkaVfo4GxNq9O2KGckPu7DyGTdul+5J3W4Hd3P0EqUrG/IKP79g3mPbW5d+MZlXFWNG77Co+2xWM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1720027294; c=relaxed/simple; bh=PyUC4JnOx8t49+z9OfoW03gptn9Bhl8DXa2Hy8+Ghhk=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=O4ixu0rjWeSt5FyLtnJnjkThxyIkd3XtA0LRG9QU3O6ztnYjYKXgKMXsvW9iLKuvtenZLsD2fw0TOVnB45cTyrgLApIcHGS1T514crugsP2iTWwPJfAb+yAPjANCxThB7rFOWGlcp0r58BrqiGUKSXK77mNLHa8aIhUJnsPahjk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=tumwyInO; arc=none smtp.client-ip=209.85.219.201 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.b="tumwyInO" Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-e0342b6f7fbso9364935276.0 for ; Wed, 03 Jul 2024 10:21:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1720027289; x=1720632089; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=K0FWSWvUbekODbWV63YGf3s/rZsG/y2vGmr0tGGkdh4=; b=tumwyInOQMVTUdUQfOcAnw6ccxJ5a1K0GQPopHDL7D3Hyac94/jprk2Z3A9TIZc8eD +60Z5kt+pfvxLd/EFKxnLS2IIpuuwc2po/RWFf8SD7DGe0IuAQKCJCWgszxvblTl9vnI VX3HiOWoDj+LWQE05SFUH//AVogKTANegkaVOuOZrTuhVDWCxNiUTFECDd8kAJwLO/kY DF3pchQR+urmu+DCf+eS7VkQYkmQpga5KZhFSCALAmdj0Suo0+vci9VGBQ13ixvQOidw AvhpU0mpBO+YjQ3WG87GZylDdxsnrmu/Vr0qnqL6wOpSaXk9Fj5c0DYSP0L3PLNElNOY OkHg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1720027289; x=1720632089; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=K0FWSWvUbekODbWV63YGf3s/rZsG/y2vGmr0tGGkdh4=; b=T52uE5h9jcEnp3bHBG8sYAuWVaQqE7i2SvUVIvjUZ2K37vvuyf9QCVjEyqtBckj8QZ d3xfA4drUIm8nS0+Q3PTYTE3fZZscBzz+CdZkvXhgQT9craqpgNc07vPoTvpSvF6KrzJ z0syj7BEzj8r4b59huA9c1qnabAoVIwud4D6ekp2IeUq0G7SCsHA3VgqYcAsnEuyvocZ KvSXuUv5bMaf+P8UXZx6gswNjH22bcxrFS6KvvnwxUE4jPaQBr8Fs0+1/+3CQEyAVmjC kpsvBHDD6dGZVmYUZl/9/YeZ8M1nJMaKCopLiQx2qvOTYRMk623QjY7vAeRKw9Sp5af9 GA3Q== X-Forwarded-Encrypted: i=1; AJvYcCU6Ork6njHe8wE9n0sIzOQgQlJoqXqArEs3RPymLvYFAd1gdtuAgUzIWRp4WhqPeU3JzSEnYErpJTHSSqdHHhCF7L+MBhMYKQXkRZYI X-Gm-Message-State: AOJu0YzO/cFklo3FDcDk6wkw7KTPoY8qKrVFBRJyuPugKW9lgMM/ZuXI oka2PXqxT/t29PTXM6zPaN1l+0U75mwX90knp1ErqrAtcyWpCwHfzqm+r2iVoeCz3HwAFjECBbY mW1aKWQ== X-Google-Smtp-Source: AGHT+IGgzf2ypPsf+gg7WY15qEpj68EM85AeI9lS4mElKvh7OEaQdift7C8lBXTuoGY+dMzeU9TsXsOPncCe X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:bdc2:f28d:3877:f0f2]) (user=irogers job=sendgmr) by 2002:a05:6902:c03:b0:dfe:3a4a:bef2 with SMTP id 3f1490d57ef6-e036ec62e39mr866543276.11.1720027289687; Wed, 03 Jul 2024 10:21:29 -0700 (PDT) Date: Wed, 3 Jul 2024 10:21:17 -0700 In-Reply-To: <20240703172117.810918-1-irogers@google.com> Message-Id: <20240703172117.810918-3-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240703172117.810918-1-irogers@google.com> X-Mailer: git-send-email 2.45.2.803.g4e1b14247a-goog Subject: [PATCH v1 2/2] perf dsos: When adding a dso into sorted dsos maintain the sort order From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Kan Liang , Athira Rajeev , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, Steinar Gunderson , Matt Fleming Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" dsos__add would add at the end of the dso array possibly requiring a later find to re-sort the array. Patterns of find then add were becoming O(n*log n) due to the sorts. Change the add routine to be O(n) rather than O(1) but to maintain the sorted-ness of the dsos array so that later finds don't need the O(n*log n) sort. Reported-by: Namhyung Kim Signed-off-by: Ian Rogers Tested-by: Namhyung Kim --- tools/perf/util/dsos.c | 26 +++++++++++++++++++++----- 1 file changed, 21 insertions(+), 5 deletions(-) diff --git a/tools/perf/util/dsos.c b/tools/perf/util/dsos.c index 5e5e05f86dd3..d4acdb37f046 100644 --- a/tools/perf/util/dsos.c +++ b/tools/perf/util/dsos.c @@ -206,11 +206,27 @@ int __dsos__add(struct dsos *dsos, struct dso *dso) dsos->dsos =3D temp; dsos->allocated =3D to_allocate; } - dsos->dsos[dsos->cnt++] =3D dso__get(dso); - if (dsos->cnt >=3D 2 && dsos->sorted) { - dsos->sorted =3D dsos__cmp_long_name_id_short_name(&dsos->dsos[dsos->cnt= - 2], - &dsos->dsos[dsos->cnt - 1]) - <=3D 0; + if (!dsos->sorted) { + dsos->dsos[dsos->cnt++] =3D dso__get(dso); + } else { + int low =3D 0, high =3D dsos->cnt - 1; + int insert =3D dsos->cnt; /* Default to inserting at the end. */ + + while (low <=3D high) { + int mid =3D low + (high - low) / 2; + int cmp =3D dsos__cmp_long_name_id_short_name(&dsos->dsos[mid], &dso); + + if (cmp < 0) { + low =3D mid + 1; + } else { + high =3D mid - 1; + insert =3D mid; + } + } + memmove(&dsos->dsos[insert + 1], &dsos->dsos[insert], + (dsos->cnt - insert) * sizeof(struct dso *)); + dsos->cnt++; + dsos->dsos[insert] =3D dso__get(dso); } dso__set_dsos(dso, dsos); return 0; --=20 2.45.2.803.g4e1b14247a-goog