From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-sender-0.a4lg.com (mail-sender-0.a4lg.com [IPv6:2401:2500:203:30b:4000:6bfe:4757:0]) by sourceware.org (Postfix) with ESMTPS id 6AC083889E3F for ; Sun, 20 Nov 2022 01:10:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6AC083889E3F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=irq.a4lg.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=irq.a4lg.com Received: from [127.0.0.1] (localhost [127.0.0.1]) by mail-sender-0.a4lg.com (Postfix) with ESMTPSA id B7007300089; Sun, 20 Nov 2022 01:10:10 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=irq.a4lg.com; s=2017s01; t=1668906610; bh=EEXLNCg+ut1LrlEjppQiysyUDV7/cbJDGsRuXMg74wA=; h=From:To:Cc:Subject:Date:Message-Id:Mime-Version: Content-Transfer-Encoding; b=In8sZFYlFPQRVePs0PhPQisDHnp/joQUVRGSGVw+ElwU/dLAyqxqQkUNWufV/5YK0 bNfirVJyJTwsMMJzJ/x7eMRnzRjNWaaILznOQPaYHrUWshL24O8jsv+R96ySmbFgDa 8a9Bxs2U3/wv+/k2th4y95+FuEzASQuT/s1dH3bA= From: Tsukasa OI To: Tsukasa OI , Nelson Chu , Kito Cheng , Palmer Dabbelt Cc: binutils@sourceware.org Subject: [PATCH 0/3] RISC-V: Disassembler Core Optimization 1-2 (Mapping symbols) Date: Sun, 20 Nov 2022 01:10:06 +0000 Message-Id: Mime-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-6.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Hello, This is the Part 4 of 4-part project to improve disassembler performance drastically: ** this patchset does not apply to master directly. ** This patchset requires following patchset(s) to be applied first: Following is basically a copy from the PATCH 3/3 commit message. For ELF files with many symbols and/or sections (static libraries, partially linked files [e.g. vmlinux.o] or large object files), the disassembler is drastically slowed down by looking up the suitable mapping symbol. This is caused by the fact that: - It used an inefficient linear search to find the suitable mapping symbol - symtab_pos is not always a good hint for forward linear search and - The symbol table accessible by the disassembler is sorted by address and then section (not section, then address). They sometimes force O(n^2) mapping symbol search time while searching for the suitable mapping symbol for given address. This commit implements: - A binary search to look up suitable mapping symbol (O(log(n)) time per a lookup call, O(n) time on initialization), - Separate mapping symbol table, sorted by section and then address (unless the section to disassemble is NULL), - A very short linear search, even faster than binary search, when disassembling consecutive addresses (usually traverses only 1 or 2 symbols, O(n) on the worst case but this is only expected on adversarial samples) and - Efficient tracking of mapping symbols with ISA string (by propagating arch field of "$x+(arch)" to succeeding "$x" symbols). It also changes when the disassembler reuses the last mapping symbol. This commit only uses the last disassembled address to determine whether the last mapping symbol should be reused. This commit doesn't improve the disassembler performance much on regular programs in general. However, it expects >50% disassembler performance improvements on some files that "RISC-V: Use faster hash table on disassembling" was not effective enough. On bigger libraries, following numbers are observed during the benchmark: - x 2.13 - 2.22 : Static library : Newlib (libc.a) - x 5.67 - 6.09 : Static library : GNU libc (libc.a) - x 11.72 - 12.04 : Shared library : OpenSSL (libcrypto.so) - x 96.29 : Shared library : LLVM 14 (libLLVM-14.so) Thanks, Tsukasa Tsukasa OI (3): RISC-V: Easy optimization on riscv_search_mapping_symbol RISC-V: Per-section private data initialization RISC-V: Optimized search on mapping symbols opcodes/disassemble.c | 1 + opcodes/disassemble.h | 2 + opcodes/riscv-dis.c | 443 +++++++++++++++++++++++++++++------------- 3 files changed, 311 insertions(+), 135 deletions(-) base-commit: 844db363911065a3b5f0c5e4601f89ee1d7360c5 -- 2.38.1