From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 0EA6AC25B06 for ; Thu, 4 Aug 2022 22:20:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S240115AbiHDWUt (ORCPT ); Thu, 4 Aug 2022 18:20:49 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47972 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240103AbiHDWTv (ORCPT ); Thu, 4 Aug 2022 18:19:51 -0400 Received: from mail-yb1-xb4a.google.com (mail-yb1-xb4a.google.com [IPv6:2607:f8b0:4864:20::b4a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CE12372EE1 for ; Thu, 4 Aug 2022 15:19:08 -0700 (PDT) Received: by mail-yb1-xb4a.google.com with SMTP id w3-20020a258503000000b00676bd41edabso612938ybk.5 for ; Thu, 04 Aug 2022 15:19:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=content-transfer-encoding:cc:to:from:subject:references :mime-version:message-id:in-reply-to:date:from:to:cc; bh=4sKjIkmYkxcPgdqfn3mzo5ECG/fhrbPKoovcaQBneno=; b=RPm1sCjET5JP8rNcetK1qF6U3qw+w4oLLcGhOWWOu6L1nGDRTQOuOliumqxWh/gKIX /9yKGK/DBjlSzOJoAEnI8awONqJrPt8jJdDpabeEJsIpGx6Azhbs+NJ3l/6DHoaLnJAK iNfK+TCPk3sbqCiJXNNHG/RA1dtiLHE0H/Fd49d8eU7Sri+xugWbE1EhCKXlJdnmCTqB rbYIxHKfLk4UTPxs3M8dea/EN0OfJggsJJ/zVHHmz3o+JOprkTttk13fyYZ928dUigUh kDM7BJaruWI9v6ppGVYpxP7wIR9PEzOHNqqUA2nfkq0TcCOlbYuvMWFoY6ORd6dZg3zR P3cA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:cc:to:from:subject:references :mime-version:message-id:in-reply-to:date:x-gm-message-state:from:to :cc; bh=4sKjIkmYkxcPgdqfn3mzo5ECG/fhrbPKoovcaQBneno=; b=aRFp7q0KWNm4MQ9UmtZGzODbG4xeowGw7a/BYi+yHmpXtoq9tqhAG6V7ldQsDUeh6G 5Q2Ux5LIzrjb+FrMrOnIk44O+eN/oALsEZgkEkvpYNqWcJA+S+obi2s53yIxrZXkKD6M d/JkNz3sIYSmrrpWZNXfgKArB4VFN1stQd8ueJwsFA+HPIW0xM8OxszfhcvreSC+Xz4O Nyc7Yq7mh89q2GVN3vy5hLuUQVJMHcWuHxxvbRZPMRtOIgw18OzK9MMqkuD5rQjqr6y8 F9Uc5uL8Z/GQqx3raPY25VergZzEE3LSNnlst/zpxzmo2TMPCzmNwwE/RZY/czeUraxc wqEg== X-Gm-Message-State: ACgBeo3MlT7fFUaM5JPigtCTxgSufmx049JfDBPsK0sZUlFpXboyVODV XX0HA6nXck9TmaJ9n5JXKWjMEhdTaLYm X-Google-Smtp-Source: AA6agR4FmNYXeclC++bbyZH3TZg+ZhvtAunrgtkYw8Z7YOjZT3L+beFF6zd42weYs5tFP9F2zwFabCWCQG6g X-Received: from irogers.svl.corp.google.com ([2620:15c:2d4:203:f5e1:5bc5:7dab:2b7c]) (user=irogers job=sendgmr) by 2002:a0d:c007:0:b0:324:8274:24cf with SMTP id b7-20020a0dc007000000b00324827424cfmr3627946ywd.213.1659651548135; Thu, 04 Aug 2022 15:19:08 -0700 (PDT) Date: Thu, 4 Aug 2022 15:18:16 -0700 In-Reply-To: <20220804221816.1802790-1-irogers@google.com> Message-Id: <20220804221816.1802790-18-irogers@google.com> Mime-Version: 1.0 References: <20220804221816.1802790-1-irogers@google.com> X-Mailer: git-send-email 2.37.1.559.g78731f0fdb-goog Subject: [PATCH v4 17/17] perf jevents: Fold strings optimization From: Ian Rogers To: John Garry , Will Deacon , James Clark , Mike Leach , Leo Yan , Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Mark Rutland , Alexander Shishkin , Jiri Olsa , Namhyung Kim , Andi Kleen , Zhengjun Xing , Ravi Bangoria , Kan Liang , Adrian Hunter , linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, linux-perf-users@vger.kernel.org Cc: Stephane Eranian , Ian Rogers Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org If a shorter string ends a longer string then the shorter string may reuse the longer string at an offset. For example, on x86 the event arith.cycles_div_busy and cycles_div_busy can be folded, even though they have difference names the strings are identical after 6 characters. cycles_div_busy can reuse the arith.cycles_div_busy string at an offset of 6. In pmu-events.c this looks like the following where the 'also:' lists folded strings: /* offset=3D177541 */ "arith.cycles_div_busy\000\000pipeline\000Cycles the = divider is busy\000\000\000event=3D0x14,period=3D2000000,umask=3D0x1\000\00= 0\000\000\000\000\000\000\000" /* also: cycles_div_busy\000\000pipeline\000= Cycles the divider is busy\000\000\000event=3D0x14,period=3D2000000,umask= =3D0x1\000\000\000\000\000\000\000\000\000 */ As jevents.py combines multiple strings for an event into a larger string, the amount of folding is minimal as all parts of the event must align. Other organizations can benefit more from folding, but lose space by say recording more offsets. Signed-off-by: Ian Rogers --- tools/perf/pmu-events/jevents.py | 55 ++++++++++++++++++++++++++++---- 1 file changed, 48 insertions(+), 7 deletions(-) diff --git a/tools/perf/pmu-events/jevents.py b/tools/perf/pmu-events/jeven= ts.py index a5e162558994..e5545758c92d 100755 --- a/tools/perf/pmu-events/jevents.py +++ b/tools/perf/pmu-events/jevents.py @@ -80,7 +80,9 @@ class BigCString: are all the other C strings (to avoid memory issues the string itself is held as a list of strings). The offsets within the big string are recorded and when stored to disk these don't need - relocation. + relocation. To reduce the size of the string further, identical + strings are merged. If a longer string ends-with the same value as a + shorter string, these entries are also merged. """ strings: Set[str] big_string: Sequence[str] @@ -96,6 +98,33 @@ class BigCString: def compute(self) -> None: """Called once all strings are added to compute the string and offsets= .""" =20 + folded_strings =3D {} + # Determine if two strings can be folded, ie. let 1 string use the + # end of another. First reverse all strings and sort them. + sorted_reversed_strings =3D sorted([x[::-1] for x in self.strings]) + + # Strings 'xyz' and 'yz' will now be [ 'zy', 'zyx' ]. Scan forward + # for each string to see if there is a better candidate to fold it + # into, in the example rather than using 'yz' we can use'xyz' at + # an offset of 1. We record which string can be folded into which + # in folded_strings, we don't need to record the offset as it is + # trivially computed from the string lengths. + for pos,s in enumerate(sorted_reversed_strings): + best_pos =3D pos + for check_pos in range(pos + 1, len(sorted_reversed_strings)): + if sorted_reversed_strings[check_pos].startswith(s): + best_pos =3D check_pos + else: + break + if pos !=3D best_pos: + folded_strings[s[::-1]] =3D sorted_reversed_strings[best_pos][::-1= ] + + # Compute reverse mappings for debugging. + fold_into_strings =3D collections.defaultdict(set) + for key, val in folded_strings.items(): + if key !=3D val: + fold_into_strings[val].add(key) + # big_string_offset is the current location within the C string # being appended to - comments, etc. don't count. big_string is # the string contents represented as a list. Strings are immutable @@ -104,13 +133,25 @@ class BigCString: big_string_offset =3D 0 self.big_string =3D [] self.offsets =3D {} - # Emit all strings in a sorted manner. + + # Emit all strings that aren't folded in a sorted manner. for s in sorted(self.strings): - self.offsets[s] =3D big_string_offset - self.big_string.append(f'/* offset=3D{big_string_offset} */ "') - self.big_string.append(s) - self.big_string.append('"\n') - big_string_offset +=3D c_len(s) + if s not in folded_strings: + self.offsets[s] =3D big_string_offset + self.big_string.append(f'/* offset=3D{big_string_offset} */ "') + self.big_string.append(s) + self.big_string.append('"') + if s in fold_into_strings: + self.big_string.append(' /* also: ' + ', '.join(fold_into_string= s[s]) + ' */') + self.big_string.append('\n') + big_string_offset +=3D c_len(s) + continue + + # Compute the offsets of the folded strings. + for s in folded_strings.keys(): + assert s not in self.offsets + folded_s =3D folded_strings[s] + self.offsets[s] =3D self.offsets[folded_s] + c_len(folded_s) - c_len= (s) =20 _bcs =3D BigCString() =20 --=20 2.37.1.559.g78731f0fdb-goog From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 23D22C25B06 for ; Thu, 4 Aug 2022 22:37:11 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:Cc:To:From:Subject:References: Mime-Version:Message-Id:In-Reply-To:Date:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Owner; bh=2yDsL1sZHWmDRL3Ez6Of1uNYLe3rtelMWsjrleRPabY=; b=UI7vDIPUs8+CJT/fWLti6SIkLR QeWXCNecLx7DOskwZlqskQUmV7ew6WvLyWmWTQ+3+6YQeoCt7JVZJbGMT2FBlhz5HjkgWyMrWCdPP dje9Rdd+8JQ67meuJSl3W3VuP9XGkT8phAn3JVSznGq6RmSO2NUYNnzoOso3nQOXL8RwHSTPhQNqN /6/7CX4AydMYVZ6A8v12w+AeBJPyjLgMQMxSh5vuFKw4pUErjMgrzdm0FliQumAjqvOFkrq2V/jbo z2yGlKLzHpa1uJOBo2nM0Y1ibwf71L5R2x7DDUrhEtR4madOLLtS1DwiVq1Aa4GICyXLPVZD5p4qt /18riRpA==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1oJjRW-009cyI-0O; Thu, 04 Aug 2022 22:35:50 +0000 Received: from desiato.infradead.org ([2001:8b0:10b:1:d65d:64ff:fe57:4e05]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1oJjCC-009WfZ-4I for linux-arm-kernel@bombadil.infradead.org; Thu, 04 Aug 2022 22:20:00 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=desiato.20200630; h=Content-Transfer-Encoding:Content-Type :Cc:To:From:Subject:References:Mime-Version:Message-Id:In-Reply-To:Date: Sender:Reply-To:Content-ID:Content-Description; bh=4sKjIkmYkxcPgdqfn3mzo5ECG/fhrbPKoovcaQBneno=; b=YlDiIj6nrXB3dYUQrPNHzjbp1M jT9EbAjyKsmArLHH2GdYNpCGX9+fiBswFL3w0/hgJCivmXXB0Q7Pu9BUOFjsa5b17PC1ENaa50JPK niIul6XMgIUWWBNpcf/PLd6IakZoSDf+5odruhJaeUquAEQvK5kCCJfSc8uYdLrq1IOHF+SCzGcd/ VM+Z84vRYSLimy7ydF59EmFpskwPNWI9G80idybJcZqOFZK9o+0V2vS941VqP+ZXPD+6Zovyos8nW 4zTXC0frONmGbKDRWvgqeu4g4DyF6/U6eG6sRXw2/MVYV/mSU9FuinHfP9KsTMnfZlDZntje6didz AyYyAQ4g==; Received: from mail-yb1-xb4a.google.com ([2607:f8b0:4864:20::b4a]) by desiato.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1oJjBp-0034Il-Ak for linux-arm-kernel@lists.infradead.org; Thu, 04 Aug 2022 22:19:53 +0000 Received: by mail-yb1-xb4a.google.com with SMTP id m11-20020a5b040b000000b0066fcc60d1a0so577801ybp.19 for ; Thu, 04 Aug 2022 15:19:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=content-transfer-encoding:cc:to:from:subject:references :mime-version:message-id:in-reply-to:date:from:to:cc; bh=4sKjIkmYkxcPgdqfn3mzo5ECG/fhrbPKoovcaQBneno=; b=RPm1sCjET5JP8rNcetK1qF6U3qw+w4oLLcGhOWWOu6L1nGDRTQOuOliumqxWh/gKIX /9yKGK/DBjlSzOJoAEnI8awONqJrPt8jJdDpabeEJsIpGx6Azhbs+NJ3l/6DHoaLnJAK iNfK+TCPk3sbqCiJXNNHG/RA1dtiLHE0H/Fd49d8eU7Sri+xugWbE1EhCKXlJdnmCTqB rbYIxHKfLk4UTPxs3M8dea/EN0OfJggsJJ/zVHHmz3o+JOprkTttk13fyYZ928dUigUh kDM7BJaruWI9v6ppGVYpxP7wIR9PEzOHNqqUA2nfkq0TcCOlbYuvMWFoY6ORd6dZg3zR P3cA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:cc:to:from:subject:references :mime-version:message-id:in-reply-to:date:x-gm-message-state:from:to :cc; bh=4sKjIkmYkxcPgdqfn3mzo5ECG/fhrbPKoovcaQBneno=; b=RUaMP+AzzCyYrAH0i/Y2fr1QNrdkprZ4r7+o508K0eiDicbHeEZje/JrPEyXLjb3E1 aUru4/TvqKZj0buZWTfPo3/yaA0CLnKlFzKE0MRFf0QxFbioF/VH89dIp1aVy/BW9sll o1ycqksL6Cok4UUty/lJ+QG/3uJlyizYDJ3I1KDjgWLpNviXlFWMgpXjnlzMzyeRigFN MxzoLJGexM+dv9BU2B8gk+T3BsUazlugxZ4T6fkq+hvupAZHFHCaDBsIkru1Vil6kX0D kTW5dcUF43q8Avngo3BysvbhH6B2hZPkFp7cd/c550djAkrbZ3+aZFxXhEUg/GygKuma vjUw== X-Gm-Message-State: ACgBeo3Ip6gRUWvC+FwUQmvD0kuISu0BafJDFUUkcUc2zkaksL/bcXwP PKj0Z7TWi8BkIdS5pglFo3Sxvpz37ppl X-Google-Smtp-Source: AA6agR4FmNYXeclC++bbyZH3TZg+ZhvtAunrgtkYw8Z7YOjZT3L+beFF6zd42weYs5tFP9F2zwFabCWCQG6g X-Received: from irogers.svl.corp.google.com ([2620:15c:2d4:203:f5e1:5bc5:7dab:2b7c]) (user=irogers job=sendgmr) by 2002:a0d:c007:0:b0:324:8274:24cf with SMTP id b7-20020a0dc007000000b00324827424cfmr3627946ywd.213.1659651548135; Thu, 04 Aug 2022 15:19:08 -0700 (PDT) Date: Thu, 4 Aug 2022 15:18:16 -0700 In-Reply-To: <20220804221816.1802790-1-irogers@google.com> Message-Id: <20220804221816.1802790-18-irogers@google.com> Mime-Version: 1.0 References: <20220804221816.1802790-1-irogers@google.com> X-Mailer: git-send-email 2.37.1.559.g78731f0fdb-goog Subject: [PATCH v4 17/17] perf jevents: Fold strings optimization From: Ian Rogers To: John Garry , Will Deacon , James Clark , Mike Leach , Leo Yan , Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Mark Rutland , Alexander Shishkin , Jiri Olsa , Namhyung Kim , Andi Kleen , Zhengjun Xing , Ravi Bangoria , Kan Liang , Adrian Hunter , linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, linux-perf-users@vger.kernel.org Cc: Stephane Eranian , Ian Rogers X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20220804_231951_429621_C5B922E3 X-CRM114-Status: GOOD ( 20.58 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org If a shorter string ends a longer string then the shorter string may reuse the longer string at an offset. For example, on x86 the event arith.cycles_div_busy and cycles_div_busy can be folded, even though they have difference names the strings are identical after 6 characters. cycles_div_busy can reuse the arith.cycles_div_busy string at an offset of 6. In pmu-events.c this looks like the following where the 'also:' lists folded strings: /* offset=177541 */ "arith.cycles_div_busy\000\000pipeline\000Cycles the divider is busy\000\000\000event=0x14,period=2000000,umask=0x1\000\000\000\000\000\000\000\000\000" /* also: cycles_div_busy\000\000pipeline\000Cycles the divider is busy\000\000\000event=0x14,period=2000000,umask=0x1\000\000\000\000\000\000\000\000\000 */ As jevents.py combines multiple strings for an event into a larger string, the amount of folding is minimal as all parts of the event must align. Other organizations can benefit more from folding, but lose space by say recording more offsets. Signed-off-by: Ian Rogers --- tools/perf/pmu-events/jevents.py | 55 ++++++++++++++++++++++++++++---- 1 file changed, 48 insertions(+), 7 deletions(-) diff --git a/tools/perf/pmu-events/jevents.py b/tools/perf/pmu-events/jevents.py index a5e162558994..e5545758c92d 100755 --- a/tools/perf/pmu-events/jevents.py +++ b/tools/perf/pmu-events/jevents.py @@ -80,7 +80,9 @@ class BigCString: are all the other C strings (to avoid memory issues the string itself is held as a list of strings). The offsets within the big string are recorded and when stored to disk these don't need - relocation. + relocation. To reduce the size of the string further, identical + strings are merged. If a longer string ends-with the same value as a + shorter string, these entries are also merged. """ strings: Set[str] big_string: Sequence[str] @@ -96,6 +98,33 @@ class BigCString: def compute(self) -> None: """Called once all strings are added to compute the string and offsets.""" + folded_strings = {} + # Determine if two strings can be folded, ie. let 1 string use the + # end of another. First reverse all strings and sort them. + sorted_reversed_strings = sorted([x[::-1] for x in self.strings]) + + # Strings 'xyz' and 'yz' will now be [ 'zy', 'zyx' ]. Scan forward + # for each string to see if there is a better candidate to fold it + # into, in the example rather than using 'yz' we can use'xyz' at + # an offset of 1. We record which string can be folded into which + # in folded_strings, we don't need to record the offset as it is + # trivially computed from the string lengths. + for pos,s in enumerate(sorted_reversed_strings): + best_pos = pos + for check_pos in range(pos + 1, len(sorted_reversed_strings)): + if sorted_reversed_strings[check_pos].startswith(s): + best_pos = check_pos + else: + break + if pos != best_pos: + folded_strings[s[::-1]] = sorted_reversed_strings[best_pos][::-1] + + # Compute reverse mappings for debugging. + fold_into_strings = collections.defaultdict(set) + for key, val in folded_strings.items(): + if key != val: + fold_into_strings[val].add(key) + # big_string_offset is the current location within the C string # being appended to - comments, etc. don't count. big_string is # the string contents represented as a list. Strings are immutable @@ -104,13 +133,25 @@ class BigCString: big_string_offset = 0 self.big_string = [] self.offsets = {} - # Emit all strings in a sorted manner. + + # Emit all strings that aren't folded in a sorted manner. for s in sorted(self.strings): - self.offsets[s] = big_string_offset - self.big_string.append(f'/* offset={big_string_offset} */ "') - self.big_string.append(s) - self.big_string.append('"\n') - big_string_offset += c_len(s) + if s not in folded_strings: + self.offsets[s] = big_string_offset + self.big_string.append(f'/* offset={big_string_offset} */ "') + self.big_string.append(s) + self.big_string.append('"') + if s in fold_into_strings: + self.big_string.append(' /* also: ' + ', '.join(fold_into_strings[s]) + ' */') + self.big_string.append('\n') + big_string_offset += c_len(s) + continue + + # Compute the offsets of the folded strings. + for s in folded_strings.keys(): + assert s not in self.offsets + folded_s = folded_strings[s] + self.offsets[s] = self.offsets[folded_s] + c_len(folded_s) - c_len(s) _bcs = BigCString() -- 2.37.1.559.g78731f0fdb-goog _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel