llvm/llvm-project

[BOLT] Evaluate and speedup discoverFileObjects

Open

#90,661 opened on Apr 30, 2024

View on GitHub
 (14 comments) (0 reactions) (0 assignees)C++ (10,782 forks)batch import
BOLTgood first issuehelp wanted

Repository metrics

Stars
 (26,378 stars)
PR merge metrics
 (Avg merge 1d 2h) (1,000 merged PRs in 30d)

Description

Operations with symbols such as name lookup are expensive and some binaries have millions of symbols, so it makes sense to try to reduce the symbol-related overheads.

Measure how much the following cost and refactor/eliminate:

  1. Checks for symbol name being equal to __asan_init and __llvm_coverage_mapping for every single symbol: https://github.com/llvm/llvm-project/blob/a1423ba4278775472523fed074de6dbdfd01898a/bolt/lib/Rewrite/RewriteInstance.cpp#L824-L837
  2. FileName set for every local function symbol (with O(1M) for large binaries) while we can instead use file symbol lookup with O(log N_Syms) cost and FileSyms memory cost https://github.com/llvm/llvm-project/pull/89088
  3. Merge iteration over two loops over symbols into one: https://github.com/llvm/llvm-project/blob/a1423ba4278775472523fed074de6dbdfd01898a/bolt/lib/Rewrite/RewriteInstance.cpp#L824 and https://github.com/llvm/llvm-project/blob/a1423ba4278775472523fed074de6dbdfd01898a/bolt/lib/Rewrite/RewriteInstance.cpp#L876

Contributor guide

Research direction
Measure the cost of symbol name checks and file name set operations, then refactor to eliminate redundant checks and merge loops for performance improvement.
Tech stack
cpp
Domain
compilers
Issue type
Performance
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
2
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
Half day
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
Active
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
Clear
Prerequisites
C++Compiler Infrastructure
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
40