Branch: refs/heads/bbiiggppiigg/faster-getgaprange
Home: https://github.com/dyninst/dyninst
Commit: 30db7ef95c1541443f856d21ab37dbe92ce7160e
https://github.com/dyninst/dyninst/commit/30db7ef95c1541443f856d21ab37dbe92ce7160e
Author: wuxx1279 <bbiiggppiigg@xxxxxxxxx>
Date: 2026-06-20 (Sat, 20 Jun 2026)
Changed paths:
M parseAPI/src/Parser-speculative.C
M parseAPI/src/Parser.h
Log Message:
-----------
parseAPI: speed up speculative getGapRange without changing its result
Parser::getGapRange located the gap around curAddr by rebuilding a start-ordered
set of *every* parsed function's extents on every call. It runs once per gap
found during speculative parsing, so the pass was ~O(gaps x functions); on a
large, symbol-rich library (e.g. a ~400 MB shared object with ~250k functions)
that per-call rebuild dominated rewrite time -- the speculative pass ran for
hours while the recursive-descent parse before it finished in seconds.
Build the start-ordered extent index ONCE in probabilistic_gap_parsing and pass
it to getGapRange, which keeps the original upper_bound logic verbatim (so the
gaps scanned are byte-for-byte identical). After each gap-discovered function is
finalized, fold its extents into the index incrementally; funcs_to_ranges is
drained into funcsByRange up front and after each discovery to keep that tree
current for other consumers. The pass drops from O(gaps x F) to
O(F + gaps x log F) -- hours to ~seconds on the large-library case -- with no
change to results.
Co-Authored-By: Claude Opus 4.8 <noreply@xxxxxxxxxxxxx>
To unsubscribe from these emails, change your notification settings at https://github.com/dyninst/dyninst/settings/notifications
|