[PATCH 0/5] gdb: Store section map in an interval tree

[Ilya Leoshkevich <iii@linux.ibm.com>]

Hi,

When debugging JITs that report ~10k sections, GDB slows to a crawl,
even with the recent optimization [1].  The problem is that the
algorithmic complexity of adding N new sections is O((N**2)*log(N)),
because the code calls update_section_map() and thus std::sort() N
times.

This series aims to reduce this to O(N*log(N)) by storing sections in
an interval tree and updating it incrementally instead of rebuilding it
every time from scratch.  The interval tree is chosen instead of
simpler alternatives in order to handle overlapping sections.

- Patch 1 introduces obstack_newvec() for allocating obj_section
  objects, which later become non-POD types.
- Patches 2-3 introduce interval tree implementation and tests for it.
- Patch 5 is the actual optimization.

The performance testing [2] results can be found here: [3].

This series survives the regtest on x86_64, power and s390x.

Best regards,
Ilya

[1] https://sourceware.org/git/?p=binutils-gdb.git;a=commit;h=625b6eae091709b95471eae92d42dc6bc71e6553
[2] https://sourceware.org/pipermail/gdb-patches/2022-May/189592.html
[3] https://github.com/iii-i/binutils-gdb/blob/section-map-20220601-2/gdb/testsuite/jit.png


Ilya Leoshkevich (5):
  gdbsupport: Introduce obstack_newvec
  gdbsupport: Introduce interval_tree
  gdbsupport: Add interval_tree unit tests
  gdbsupport: Add interval_tree fuzzing harness
  gdb: Optimize section map

 gdb/Makefile.in                         |   1 +
 gdb/objfiles.c                          | 384 +++++-----
 gdb/objfiles.h                          |  15 +-
 gdb/symfile.c                           |   2 +-
 gdb/unittests/interval_tree-selftests.c | 400 +++++++++++
 gdbsupport/gdb_obstack.h                |  26 +
 gdbsupport/interval_tree.h              | 915 ++++++++++++++++++++++++
 7 files changed, 1526 insertions(+), 217 deletions(-)
 create mode 100644 gdb/unittests/interval_tree-selftests.c
 create mode 100644 gdbsupport/interval_tree.h

-- 
2.35.3