Bug 16994

Summary: performance issue looking up static symbols (e.g. int, int64 typedef).
Product: gdb Reporter: dje
Component: symtabAssignee: Tom Tromey <tromey>
Status: RESOLVED FIXED    
Severity: normal CC: sam, tromey, xdje42
Priority: P2 Keywords: performance
Version: HEAD   
Target Milestone: 18.1   
See Also: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
https://sourceware.org/bugzilla/show_bug.cgi?id=17684
https://sourceware.org/bugzilla/show_bug.cgi?id=16253
https://sourceware.org/bugzilla/show_bug.cgi?id=33447
https://sourceware.org/bugzilla/show_bug.cgi?id=33557
Host: Target:
Build: Last reconfirmed:
Project(s) to access: ssh public key:
Bug Depends on: 32939    
Bug Blocks:    

Description dje 2014-05-28 17:18:50 UTC 
This pr is to address the performance issue gdb has when looking up symbols in STATIC_BLOCK.

gdb will iterate over all CUs looking for static symbols as a last resort, but this introduces performance issues that one might not easily predict.
See pr 16253 for an example of accidentally introducing such a perf regression.

E.g., to perform "info fun ^foo::(anonymous namespace)", inspect_type will first look in STRUCT_DOMAIN for a symbol, and if that fails look in VAR_DOMAIN.  However, the attributes in .gdb_index don't distinguish STRUCT_DOMAIN types from VAR_DOMAIN types.  During symbol lookup, dw2_symtab_iter_next will return every entry that exists for int64 (and there can be thousands), gdb will expand the CU, look for the symbol, not get a match because it's in the wrong domain, and then try the next.
This will cause gdb to expand every CU.  Then when this lookup fails inspect_type will try VAR_DOMAIN, assuming the user was willing to wait that long ...

In this case the "last resort" lookup is killing us, we want the lookup in STRUCT_DOMAIN to fail fast.

ref: symtab.c:lookup_symbol_aux
    /* Now search all static file-level symbols.  Not strictly correct,                                                                                          
       but more useful than an error.  */

  =>return lookup_static_symbol_aux (name, domain);

"more useful than an error" is ignoring the *massive* performance hit (and by massive I mean effectively doing a -readnow in a program with a 2G fission .dwp file).

There is also the issue of looking up base types like "int". It can be slower than necessary too, for similar reasons.  Plus if some type isn't defined in the CU (say double) then we want gdb to look in the default set (provided by the architecture) after it has looked in the current CU and before it does this last
resort attempt of looking through all CUs.  One reason for doing this is that if the next CU to be looked in happened to be compiled with -fshort-double gdb will give the wrong answer.
Comment 1 dje 2014-05-29 23:32:19 UTC 
In the .gdb_index of the monster benchmark I'm using, there are 10K entries for int64, and none for void.
Thus any time gdb iterates over symbol tables to look up void, it's a total waste of time.

gdb should probably (still TBD) use .gdb_index for STATIC_BLOCK lookups in addition to GLOBAL_BLOCK lookups (see pr 16998), before iterating over all currently expanded symtabs.  But I think the case of looking up "void" is a good example of needing to look in the default set (provided by the arch) after looking in the current CU for STATIC_BLOCK lookups.
Comment 2 Doug Evans 2014-12-07 19:19:56 UTC 
Filed PR 17684 to address the particular case of looking up builtin(/primitive) types.
Comment 3 Sourceware Commits 2025-09-10 22:18:06 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=29fa4279c2f1bc2e0ac7cf77a95cbc0d83dd3c4a

commit 29fa4279c2f1bc2e0ac7cf77a95cbc0d83dd3c4a
Author: Tom Tromey <tom@tromey.com>
Date:   Sat Dec 7 15:51:24 2024 -0700

    Remove dwarf2_per_cu_data::mark
    
    This removes dwarf2_per_cu_data::mark, replacing it with a
    locally-allocated boolean vector.  It also inverts the sense of the
    flag -- now, the flag is true when a CU should be skipped, and false
    when the CU should be further examined.  Also, the validity of the
    flag is no longer dependent on 'file_matcher != NULL'.
    
    This patch makes the subsequent patch to searching a bit simpler, so
    I've separated it out.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 4 Sourceware Commits 2025-09-10 22:18:12 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=f88f9f42db8ff782758435214678ad87d3fc3a18

commit f88f9f42db8ff782758435214678ad87d3fc3a18
Author: Tom Tromey <tom@tromey.com>
Date:   Sat Dec 7 16:26:06 2024 -0700

    Have expand_symtabs_matching work for already-expanded CUs
    
    Currently, gdb will search the already-expanded symtabs in one loop,
    and then also expand matching symtabs in another loop.  However, this
    is somewhat inefficient -- when searching the already-expanded
    symtabs, all such symtabs are examined.  However, the various "quick"
    implementations already know which subset of symtabs might have a
    match.
    
    This changes the contract of expand_symtabs_matching to also call the
    callback for an already-expanded symtab.  With this change, and some
    subsequent enabling changes, the number of searched symtabs should
    sometimes be reduced.  This also cuts down on the amount of redundant
    code.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=30736
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 5 Sourceware Commits 2025-09-10 22:18:23 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=5b66439bc8b0ce287852f62378cbfca28927ffd0

commit 5b66439bc8b0ce287852f62378cbfca28927ffd0
Author: Tom Tromey <tom@tromey.com>
Date:   Wed Dec 18 19:18:22 2024 -0700

    Convert default_collect_symbol_completion_matches_break_on
    
    This converts default_collect_symbol_completion_matches_break_on to
    the callback approach, merging the search loop and the call to
    expand_symtabs_matching.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 6 Sourceware Commits 2025-09-10 22:18:30 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=1696b45a6304d01f6253d43c691a682b77cb61b3

commit 1696b45a6304d01f6253d43c691a682b77cb61b3
Author: Tom Tromey <tom@tromey.com>
Date:   Wed Dec 18 17:26:16 2024 -0700

    Convert gdbpy_lookup_static_symbols
    
    This changes gdbpy_lookup_static_symbols to the callback approach,
    merging the search loop and the call to expand_symtabs_matching.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 7 Sourceware Commits 2025-09-10 22:18:35 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=59cc52253ea73f983b1d8d2f76cee6e03dddcb92

commit 59cc52253ea73f983b1d8d2f76cee6e03dddcb92
Author: Tom Tromey <tom@tromey.com>
Date:   Sat Dec 7 17:28:06 2024 -0700

    Convert ada_add_global_exceptions
    
    This converts ada_add_global_exceptions to the callback approach,
    merging the search loop and the call to expand_symtabs_matching.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 8 Sourceware Commits 2025-09-10 22:18:40 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=e271cb3281858fd475b7888043d6ed4539f0c8e3

commit e271cb3281858fd475b7888043d6ed4539f0c8e3
Author: Tom Tromey <tom@tromey.com>
Date:   Sat Dec 7 17:30:42 2024 -0700

    Convert ada_language_defn::collect_symbol_completion_matches
    
    This converts ada_language_defn::collect_symbol_completion_matches to
    the callback approach, merging the search loop and the call to
    expand_symtabs_matching.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 9 Sourceware Commits 2025-09-10 22:18:46 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=b7561b2a31ca40b59cc29311836755cc7dfe7bb4

commit b7561b2a31ca40b59cc29311836755cc7dfe7bb4
Author: Tom Tromey <tom@tromey.com>
Date:   Sat Dec 7 16:48:45 2024 -0700

    Convert ada-lang.c:map_matching_symbols
    
    This converts ada-lang.c:map_matching_symbols to the callback
    approach, merging the search loop and the call to
    expand_symtabs_matching.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 10 Sourceware Commits 2025-09-10 22:18:56 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=ce889924a72ac43e6792972f07082a4fa1f32d49

commit ce889924a72ac43e6792972f07082a4fa1f32d49
Author: Tom Tromey <tom@tromey.com>
Date:   Tue Dec 31 10:30:15 2024 -0700

    Simplify basic_lookup_transparent_type
    
    This patch changes basic_lookup_transparent_type to always work via
    the "quick" API -- that is, no separate search of the already-expanded
    symtabs is needed.
    
    This is more efficient when many CUs have already been expanded.  It
    also makes the lookup more consistent, as the result is no longer
    dependent on the order in which CUs were previously expanded.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 11 Sourceware Commits 2025-09-10 22:19:01 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=4a0b3e62a43567fadadf167390feaf147118fd76

commit 4a0b3e62a43567fadadf167390feaf147118fd76
Author: Tom Tromey <tom@tromey.com>
Date:   Tue Dec 31 13:11:50 2024 -0700

    Remove objfile::expand_symtabs_for_function
    
    objfile::expand_symtabs_for_function only has a single caller now, so
    it can be removed.  This also allows us to merge the expansion and
    searching phases, as done in other patches in this series.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 12 Sourceware Commits 2025-09-10 22:19:07 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=5f99f39a396476c122a04f8eb7c0c40c76c101db

commit 5f99f39a396476c122a04f8eb7c0c40c76c101db
Author: Tom Tromey <tom@tromey.com>
Date:   Tue Dec 31 13:15:17 2024 -0700

    Convert linespec.c:iterate_over_all_matching_symtabs
    
    This converts linespec.c:iterate_over_all_matching_symtabs to the
    callback approach, merging the search loop and the call to
    expand_symtabs_matching.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 13 Sourceware Commits 2025-09-10 22:19:33 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=c879f4dc3e317cf6353a45a803ecf00d577a13d8

commit c879f4dc3e317cf6353a45a803ecf00d577a13d8
Author: Tom Tromey <tom@tromey.com>
Date:   Tue Dec 31 13:30:18 2024 -0700

    Convert lookup_symbol_via_quick_fns
    
    This converts lookup_symbol_via_quick_fns to the callback approach,
    merging the search loop and the call to expand_symtabs_matching.
    
    Note that this changes lookup_symbol_via_quick_fns to use a
    best_symbol_tracker.  Before this patch there was a discrepancy here
    between the two search functions.
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 14 Sourceware Commits 2025-09-10 22:19:38 UTC 
The master branch has been updated by Tom Tromey <tromey@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=86ac8c546235a67d6a6bb29476a3a9ac8f7a620a

commit 86ac8c546235a67d6a6bb29476a3a9ac8f7a620a
Author: Tom Tromey <tom@tromey.com>
Date:   Thu Jan 2 15:28:18 2025 -0700

    Convert lookup_symbol_in_objfile
    
    This converts lookup_symbol_in_objfile to the callback approach by
    removing the call to lookup_symbol_in_objfile_symtabs.  (The latter is
    not removed as there are still other callers.)
    
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16994
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=16998
    Acked-By: Simon Marchi <simon.marchi@efficios.com>
Comment 15 Tom Tromey 2025-09-11 00:06:31 UTC 
Fixed.