mbox series

[v2,0/3] RISC-V: Disassembler Core Optimization 1-2 (Mapping symbols)

Message ID cover.1669610841.git.research_trasio@irq.a4lg.com
Headers
Series RISC-V: Disassembler Core Optimization 1-2 (Mapping symbols) |

Message

Tsukasa OI Nov. 28, 2022, 4:47 a.m. UTC 
  Hello,

This is the Part 4 of 4-part project to improve disassembler performance
drastically:
<https://github.com/a4lg/binutils-gdb/wiki/proj_dis_perf_improvements_1>

** this patchset does not apply to master directly. **

This patchset requires following patchset(s) to be applied first:
<https://sourceware.org/pipermail/binutils/2022-November/124378.html>
<https://sourceware.org/pipermail/binutils/2022-November/124519.html>

[Changes: v1 -> v2]
-   Rebased against commit 97f006bc56af:
    "RISC-V: Better support for long instructions (disassembler)"


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(m + n*log(n)) time on initialization where n < m),
-   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
in development:

-   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: 5b561967091a59d0052bd717d1b9f3e31ef841cc