From patchwork Thu Jul 28 22:28:35 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 12931814 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 188A3C04A68 for ; Thu, 28 Jul 2022 23:45:23 +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=StsW/nEr/hUN9uxZA5b73GGcGf8QJMctEndmHZzKD7o=; b=yZcXNvhdk2of4gcnTti8ujEenW xupC2t9wVEWH2lBFjtVvm8hOVlH04mEyI2McgpnweadEt1skW4yWAZ5loSsm866NVmoUtjXieRFa1 tzKkVC/sNb/EvxF1h1R3149gJEak/QnpVQNAanl/cCvcHvWubv5juVlrMMftcm4+4/AXRuwr2e9HZ KyZcGd59P3xUo4l8fcdDV2pNCN0PqK6Xo8WboR8Xo4rGzQTyOjeN3OOzkMxeedfsRXlzCYMkHB/rW 0vu0ywFHuCx4mt41ERpdUGMfWRSKvyZnuVePSyxAcnHG2igJqVYlQqOeiloiT/oolLuX/Jaz1DQK2 KXhdUVKA==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1oHDAa-00FoP8-GL; Thu, 28 Jul 2022 23:43:56 +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 1oHDAQ-00FoMq-D5 for linux-arm-kernel@bombadil.infradead.org; Thu, 28 Jul 2022 23:43:46 +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=HomNzY0vohqpUh0WW0YjSOj5dnamYzXcJXTx/P5QSJY=; b=AhJaW4uFUGVOm2K6NQasZsLUVT QJkq/a5VoGn3p0FopcuOT988BDR3Tao27CWBLQY5eoULfCIiPKx17b4bDl3g4VZyS6s7eY2pT33HB kc2EjMSc2rvaH275+Xvmhq+WKF3nrtQH+FIvjiT4plTXhur+ojqgfhQVJvfJFb7kXSAW64GXAwuBK uHAjrjCbxROEPLpljY5Uv1csOFwsrLo2HJlk8b6z7MJhWBQYp9EgcvBk218qI2eqr7OOZh9Sx5Qsb GvwBRXEorX1uUAKwwoYdICisKv2k14BG3dXWc/TCL44xY8uRcbMm8o5tFvrB3toSMZM7UeEE1qdlH 3y0CPYRA==; Received: from mail-pl1-x649.google.com ([2607:f8b0:4864:20::649]) by desiato.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1oHC0R-001BrW-Pw for linux-arm-kernel@lists.infradead.org; Thu, 28 Jul 2022 22:29:25 +0000 Received: by mail-pl1-x649.google.com with SMTP id z15-20020a170903018f00b0016d6e7a043dso1889513plg.12 for ; Thu, 28 Jul 2022 15:29:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc:content-transfer-encoding; bh=HomNzY0vohqpUh0WW0YjSOj5dnamYzXcJXTx/P5QSJY=; b=fugd2W/0FjFmERrZHRJ9Oge/AIsnKYu3XZGvHxf3pm+xuy8aTUBYfcc57eE3YRtOTL P+xx5Ox6IBSsqS8rgGVLo61QqxBSTq4SbiiVEJNr2KG5WgbyNKLsAtVlHA/5yS0M/kQG KzQrjQM+4EYVQ9XV6Xs2zwjFVax8gm0QrGgAonUw3mFiOoNyByq3iKKyWUTHpRGlSP61 Uu3NGhTd+d14uzyYxb7mYrrOxlhlT3f+z0UB3yYuDaoPc4daKB4VR2eeMOophaas8Wks RDWA0dWyFLyXGltBy0qtbnv1I1KlKP5EzUeGIv5jatpDB+3wGwwiWK75H+0lijxbFZKj kiXA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc:content-transfer-encoding; bh=HomNzY0vohqpUh0WW0YjSOj5dnamYzXcJXTx/P5QSJY=; b=UOnnAM+Vtc/J1sWkN9Vdd5zyMIk63Jz5rxAU/ftYlEOnKVUaePWrzcJ/DTr01e8Ri2 mlY1DlNJfkzSgr+rmFoGzG6IPV7s72GAXLgKMc0WHgivZQvDutUh5J/8yBoPArq5Rwo8 nrDSJCK6m10Gi06FXuaU6wOc477b17lwOiSnOHolh2pF22yjoHYajPkq5CJUG8ZtW4rz amK+YltemUDIAnTjMKhBco1be/ZzQ8xhacOnbck/pFddYyGrKjpAxiyrNNTbntSoA2cf hq21o8UEwUFasvcETCAZUGH83malCHY6BXIFcoy185C6Lo8RGHA8n0C7Qi5QiCwg2Jz2 ZnSg== X-Gm-Message-State: ACgBeo0f+ULWuLA8rbb/QYKEwsSCyeGI7jbj4zMomfrsbu+H0ykqOIFt ewAziXjs8jhG7QNirMD2iK72PdmCRJh6 X-Google-Smtp-Source: AA6agR6+1QKKxTjuVaAPBjV66yElg9YxhvqlisXjAfM/4vKw5/WJYArP6PhxtmBbr8Hwlms499G2kXCu/Zzg X-Received: from irogers.svl.corp.google.com ([2620:15c:2d4:203:fd09:96c3:28af:b08f]) (user=irogers job=sendgmr) by 2002:a17:902:6bc5:b0:16c:ea31:5934 with SMTP id m5-20020a1709026bc500b0016cea315934mr903077plt.172.1659047360858; Thu, 28 Jul 2022 15:29:20 -0700 (PDT) Date: Thu, 28 Jul 2022 15:28:35 -0700 In-Reply-To: <20220728222835.3254224-1-irogers@google.com> Message-Id: <20220728222835.3254224-17-irogers@google.com> Mime-Version: 1.0 References: <20220728222835.3254224-1-irogers@google.com> X-Mailer: git-send-email 2.37.1.455.g008518b4e5-goog Subject: [PATCH v2 16/16] 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-20220728_232923_971313_F4DB86D1 X-CRM114-Status: GOOD ( 20.26 ) 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: , 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 f6f0459a261d..e446b8d9a3b2 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()