[DynInst_API:] [dyninst/dyninst] 74d16f: Replace Loop std::set of exclusive blocks with map...

["Mark W. Krentel" <noreply@xxxxxxxxxx>]

  Branch: refs/heads/master
  Home:   https://github.com/dyninst/dyninst
  Commit: 74d16f89c366b68d438360372bb202bbbc720317
      https://github.com/dyninst/dyninst/commit/74d16f89c366b68d438360372bb202bbbc720317
  Author: Mark W. Krentel <krentel@xxxxxxxx>
  Date:   2026-03-31 (Tue, 31 Mar 2026)

  Changed paths:
    M parseAPI/h/CFG.h
    M parseAPI/src/Loop.C
    M parseAPI/src/LoopAnalyzer.C

  Log Message:
  -----------
  Replace Loop std::set of exclusive blocks with map. (#2178)

This allows replacing O(n) lookup in Loop::containsAddress() with
O(logn) lookup.

For the troublesome libmpi.so.12.5.0 binary, this speeds up the time
for getLoopTree() from 275 sec to 13 sec, a factor of 20x and the
overall time for hpcstruct from 390 sec to 135, a factor of about 2.8x.

Note: it is possible but very infrequent for basic blocks to overlap.
If there are no overlapping blocks, then lower_bound or upper_bound
will find an address in O(logn) time.  If blocks do overlap, then we
fall back to linear search.

This allows a search algorithm that is always correct and almost
always fast.

Closes #2167



To unsubscribe from these emails, change your notification settings at https://github.com/dyninst/dyninst/settings/notifications