Dwarf 5 .debug_names is one of the most important index tables for reducing lldb startup performance. While dogfooding and using it, we have identified some performance issues. For instance, there is a code path in lldb that takes 50-60 seconds to display local variables for a stack frame.
Investigation reveals that the bottleneck occurs when lldb is resolving the type for a type declaration within a compile unit. The key issue is that the current LLVM .debug_names implementation only emits the base name for a type. For example, when lldb attempts to resolve/complete a type declaration like company::folly::Optional<Foo>::StorageTriviallyDestructible , there can be numerous StorageTriviallyDestructible entries in .debug_names pointing to various split dwarf DWO files. Additionally, each DWO file may contain several template instantiations for company::folly::Optional<int> or company::folly::Optional<float> , and so on.
As a result, LLDB has to load thousands of DWO files and parse each Debugging Information Entry (DIE) and its parent chain to determine if the full type declaration context matches, leading to a significant slowdown.
To address this issue, ideally, we would like .debug_names to be capable of type lookup without the need to touch or hydrate DIEs in DWO files. There are three options to consider (with my brief comment for their pros/cons):
Emitting fully qualified type names instead of base type names.
Pros:
This is the simplest approach to implement for both producers and consumers.
I heard that PDB uses a similar approach.
Cons:
It may increase the size of the string table.
Generating a type hash (DW_IDX_type_hash) for fully qualified type names.
Pros:
Very quick and straightforward.
Cons:
Does it align with the semantics of DW_IDX_type_hash?
There might be a potential increase in compile time due to hash calculation.
Emitting the parent type declaration chain via DW_IDX_parent.
Pros:
No risk of violating the Dwarf specification.
Cons:
Could this be too slow (for consumer) for a large .debug_names table?
So the name-without-template-parameters happened as a part of support for -gsimple-template-names which was motivated due to DWARF size (in Googleâs particular case, putting the full names in the string debug info in the DWP was exceeeding 4GB/32 bit offsets were overflowing in .debug_str.dwo)
Since it seemed suitable/important to have the index contain the same names as the DWARF - the simplified names were also added to the index. (this also, yes, would reduce .debug_names size - putting the full names in there could be quite expensive)
But, also/relatedly - the names of template instantiations arenât precise. The simplest example is that t1<int, int> and t1<int,int> are the same - and the index could only contain one of these, but the user might write the other. This gets worse with extra parentheses, casts, and other ways to write the same template instantiation name.
We do already have type hashes/the mangled name of the type - but it has the problems of canonicalization above.
If the DW_IDX_parent is enough to get adequate performance it might be the best option. Though is it likely to be enough? Iâd have thought most of the perf problems come from multiple instantiations of the same template - so theyâll all have the same parent chain, so this might not help improve performance by much?
For the Apple accelerator tables we include the 32 bit has of the fully qualified type name. It was unclear from reading the DWARF spec if DW_IDX_type_hash is supposed to be the 32 bit DJB hash of the fully qualified type name. If it is, then I would vote for this solution as it stops LLDB from having to even parse the main compile unit or type unit DIE in the first place.
If we want to lookup the type for âstd::vector::iteratorâ, the only thing in the accelerator tables is by type base name âiteratorâ, so we have to check for any DIE that matches âiteratorâ. So the flow for Apple accelerator tables is:
lookup âiteratorâ and get many many results from every STL type in the universe
filter out any accelerator table entries whose type hash doesnât match
only parse a few types that actually match
This saves us from parsing all of the DIEs for any compile units or type units that have matching entry, and it also stops us from having to convert the DWARF into clang AST types. The result is a huge memory savings from not having to parse all of the DIEs in all CUs/TUs that contain âiteratorâ.
The flow without this feature goes:
lookup âiteratorâ and get many many results from every STL type in the universe
convert all of the above matches into clang AST types
filter out the types whose fully qualified names donât match after they have all been created
The spec says, in non-normative text (& without actually using the DW_IDX_type_hash name to refer to it, which makes it a bit hard to find):
The type hash attribute, not to be confused with the type signature for a TU, may be provided for type entries whose declarations are not in a type unit, for the convenience of link-time or post-link utilities that wish to de-duplicate type declarations across compilation units. The type hash, however, is computed by the same method as specified for type signatures.
Which means, no, it isnât the hash of the fully qualified name. Though LLVM uses the hash of the mangled name for type units anyway, not the DWARF-specâd type unit hash. We could put that in the hash table too, but it wouldnât be all that much use - since itâs the mangled name, not the user-visible/âprettyâ name.
That said - using a hash of the pretty name seems rather problematic due to the canonicalization concerns I mentioned above - if a user writes std::vector<int >::iterator the extra space would throw off the hash (& even efforts to canonicalize this wouldnât be perfect or would be very involved - knowing where extra parens can be removed, whether to represent something as an enum constant or a cast of an integer constant (& having to map between those two things to implement such canonicalization). Not to mention, std::vector has some other template parameters, so its name is really std::vector<int, std::allocator<int>>::iterator (& then you get the >> canonicalization problem too)
Given that class members canât be used unqualified anyway (except in the context of the class - in which case youâve already got the right context and wouldnât need an accelerator table to tell you anything) - would it not be more general & make for a more compact index, while admittedly being somewhat less efficient (but probably not âbuild the AST of every unit with an entity named âiteratorâ inefficientâ) to look up âvectorâ in the accelerator table, find every instance (again, this is the cost of non-canonicalization) and look for the ones that match the template parameters the user wrote - then look for an âiteratorâ inside that/those instances?
I am not so concerned with what the user types with pretty names, but more of what is in the DWARF when doing lookups for the expression parser.
If we have some string that has the qualified name then we can avoid pulling in all of the DIEs from each CU/TU just to find out we donât need to actually parse the type. Any other solution means we will parse all of the DIEs in the CU/TU so we can get more context on the type so we can know if we want it or not.
Given that class members canât be used unqualified anyway (except in the context of the class - in which case youâve already got the right context and wouldnât need an accelerator table to tell you anything) - would it not be more general & make for a more compact index, while admittedly being somewhat less efficient (but probably not âbuild the AST of every unit with an entity named âiteratorâ inefficientâ) to look up âvectorâ in the accelerator table, find every instance (again, this is the cost of non-canonicalization) and look for the ones that match the template parameters the user wrote - then look for an âiteratorâ inside that/those instances?
There is no âvectorâ anywhere in the accelerator tables (or in the DIE names). They are always specialized instances with template parameters (âvector<int>â), unless the simple template names option is enabled.
When enabling simple template names, there is code in LLDB to ignore any matches to something like âvectorâ if we actually do get a match because if we end up making a type from the âvectorâ match, then we return a specialized instance of vector<int> and it messes up the expression parser. If the expression parser is parsing text like std::vector<int>() the expression parser will lookup âstdâ, get the namespace, then say âwithin the decl context of âstdâ please find âvectorââ and then this will fail in LLDB due to lack of accelerator table entries as there is no simple âvectorâ class that represents just a âvectorâ. And if we wanted to find âvectorâ from a standard accelerator table, we would need to manually parse all accelerator table names and manually chop them up in case we would need to find âvectorâ in type matches. There is a Google Stadia patch I would like to try and get into LLDB at some point that fixes this issue, though I havenât fully looked at the patch:
I do have a type lookup patch that unifies how all type searches are done. Right now we have 2 APIs users can use to lookup types, and this patch simplifies this down so users can specify the decl context in a simple way that that I need to revive and get into LLDB soon:
This patch makes type lookups a bit more efficient where any matching entry from the accelerator tables will need to have the DIE tree for the containing CU/TU parsed, but it can filter out non matching entries before we actually make clang AST types from them.
But it would still be nice to be able to filter out any non matching entries at accelerator table access time if possible so we can avoid parsing any of the unneeded DWARF DIEs up front. Not sure what the right approach is to make that happen as you have pointed out that the pretty names can be problematic. Does this issue go away if we assume the pretty name is created by traversing the DWARF decl context parent DIEs or if we ask the compiler for the qualified name at compile time when making the accelerator table entry?
Not to change the subject too much, but what is the status of DWARF6? Did your proposal for enabling 64bit in DWP get accepted? To put it another way, is it at the stage where we can implement it in llvm?
Hmm, not sure I follow - where would these strings appear in the DWARF/how would they be used for lookups into the accelerator tables? Like if I were debugging something inside a member function of a std::vector instantiation and I wanted to print out a variable that was of the local iterator type - that wouldnât involve using the accelerator table, would it? Thatâd be able to be found directly using the DWARF from the current context, Iâd have thought.
Ah, right, sorry - I was assuming simplified template names - both because itâs what we use at Google (& figured you folks at Meta might be exploring it, given youâve hit similar scaling issues with DWARF, by the sounds of it) and I have some hope/desire that we could move towards that model for DWARF by default/more generally, because it is quite expensive to store these full names (& their lack of canonicalization makes harms their applicability as well)
Hmm, Iâve missed a step here - are you describing the state of things now, or the state of things if we made some change to the accelerator tables?
Because as it is today, my understanding is that the simplified names are still used for index lookups - but theyâre ambiguous. Are you saying they arenât used and then what? The index is ignored and manual parsing is done again?
When you say âstandard accelerator tableâ - what are you comparing/contrasting that to? Do you mean a .debug_names accelerator table, but without simplified names?
I donât think it does go away in either case - in simple template names, traversing just the parent tree wouldnât produce all the template parameters anyway (âiteratorâ would have a parent named âvectorâ with a parent named âstdâ).
But even if itâs an unsimplified name (either because youâre building without simplified template names, or because itâs simplified but we put the unsimplified name in the accelerator table) - thereâs still the issue of canonicalization. The name coming from DWARF isnât necessarily going to match the way a user spells it⌠- so Iâm not sure how having template argument lists in the accelerator table can lead to a good user experience. Itâd require the user to spell the names exactly the same as the compiler, punctuation and all.
But you mentioned up top youâre concerned about something else/not human spellings and Iâm still a bit confused by that - perhaps we can dig into that further.
Maybe? I believe in the past there had been some drama about implementations jumping the gun on implementing the standard. There are real concerns about compatibility - weâd have to be totally clear that thereâs no expectation of compatibility day-over-day of any features implemented based on an incomplete DWARF spec.
Perhaps we could have -gdwarf-next thatâs unstable/not guaranteed/etc (like use it only with a particularly matching debugger/tools, do not archive any object files/expect them to work with newer tools or expect tomorrowâs compiler to work with yesterdayâs tools, etc) - not sure if thatâs a useful feature for anything but experimentation, though. Like if you ship that to users, how do they use it reliably? (Oh, I have a crash in a production binary from last month - which debugger do I use to debug it?)
& the issue around .debug_names and DWP files looks like itâll involve further index work (unless I can convince you folks that only the primary type needs to be in the index - which seems questionable/unlikely) - and that change might be a bit more invasive than the 64 bit one, in some ways - more structurally complicated.
Yes indeed. Local variables donât ever use the accelerator tables. Only expression parsing. Expression parsing in LLDB uses clang and an external AST source to do all of the lookups as they are needed.
Yes this does reduce string table sizes when enabled. Simple template names are not great for type manual type lookups by exact name though, not expression parsing here, just a simple type lookup by a user.
The state of things now. Simple template name accelerator table entries get ignored because they mess things up compared to normal DWARF.
No just ignored because they donât match normal DWARF. The simple template names interfere with expression evaluation as vector would match any vector<T>
yes that is what I mean. These compiler features often get enabled without knowing if they affect debugging and they often do, so we have to learn to work around any
features that might get enabled.
I am just talking about how types are requested during expression evaluation for clang. First âstdâ, then âfind âvectorâ inside of âstdââ, etc.
During type lookups for the expression parser, we often know the decl context that must contain a type like âiteratorâ, so we know we are looking for std::vector<int>::iterator, but when we do lookups for this type using accelerator tables, we must use the basename iterator and filter out results that donât match (filter out std::*<T>::iterator where * are all STL classes but keep any whose decl context matches std::vector<int>. If we canât quickly remove matching accelerator table entries somehow (we can with Apple accelerator tables), we must parse all of the DWARF (parse all DIEs in any matching CUs/TUS) and we currently make clang AST types out of each âiteratorâ match from all STL classes, and then throw away things by checking the decl context of the matching types that were produced.
So we made the Apple accelerator tables allow us to remove any unneeded entry matches without having to parse ANY dies from any CUs/TUs whose decl context doesnât match std::vector<int>.
Hmm - how does that square with the work done in D134378? Was that work incomplete? Iâd like to know more about how to ensure this is working well.
I donât believe that was the case with -gsimple-template-names - we did make an effort to ensure it works with lldb.
Once you reach a class type, though, like std::vector<int> would it be feasible to search inside the DWARF description or Clang AST of that type, rather than consulting the context-free index? (I understand this wouldnât be the right choice for a namespace, like std, but for class members, itâs a bit more bounded - and âmembers of std::vector<int>â is probably a smaller list than âall entities named iteratorâ, for instance)
Nah, itâs not enabled by default as yet. But itâd be good to get there at some point. (Itâd be nice to also get it to the point where there arenât a bunch of opt-outs - cases where DWARF doesnât carry enough info to reconstitute full type names)
Yeah, probably.
Itâs a pretty tight situation, though - if we want to be able to break backcompat (eg: if we end up needing to change the index again for .debug_names+type units) then you canât have any archival debug info. For instance, that wouldnât work at Google for production builds - weâd still need to be able to debug 6 month old programs, for instance.
Though Googleâs also still slightly supporting debugging with gdb, so we probably wouldnât move to an experimental index just yet - be a harder sell to have gdb adopt it too, etc. (& weâre on older gdbs/arenât updating much/at all)
We could carve out a part of the index version for our own uses, or put it in a different section for now, with /some/ backcompat guarantees.
But, yeah, if itâs purely experimental/no backcompat guarantees at all, it might be workable.
But, yeah, another thread to discuss all these issues would be good.
I have spent some time prototyping and investigating the DW_IDX_parent approach to the decl context parent chain (option 3 as discussed in the post). The most significant performance concern arises from the consumer/lldb side, and Iâll explain it in more detail below.
According to the specification, DW_IDX_parent can represent either the parent pool entry index (the âIndex of the name table entry for the parentâ) or the parent pool entry offset (âThis is represented as the offset of the entry relative to the start of the entry poolâ). It might be a bit confusing which one to use, but it doesnât matter for explaining the performance issue.
When a consumer locates a name entry, it needs to traverse the parent chain via DW_IDX_parent to construct the full decl context. For each DW_IDX_parent, it must quickly find two pieces of information: 1. the parent pool entry, and 2. the parent pool entryâs name. Since the second piece lacks a lookup table (the name index is not designed for this kind of reverse lookup), the consumer has to create a mapping table from pool entry to name entry to obtain the name. As some parent pool entries can be nameless (e.g., types inside an anonymous namespace), the consumer has to scan through all pool entries and cross-check with the name entriesâ range to build this mapping. The net result is that any potential type match in a name index will require all pool entries in that index to be indexed.
Based on this analysis, it appears that option 2 (using DW_IDX_type_hash) would be a simpler and faster design. Please let me know if this explanation makes sense.
I was just independently investigating the exact same issue pointed by the OP here, and was also looking into the DW_IDX_parent solution. Glad to have found this discussion.
it must quickly find two pieces of information: 1. the parent pool entry, and 2. the parent pool entryâs name.
the name index is not designed for this kind of reverse lookup
@jeffreytan81 I donât think we need to perform the reverse lookup here. We know the parentâs name (since we have the entire parent chain), so we know its hash in the table, and therefore we know which offsets have that name. If the DW_IDX_parent is one such offset, we have a match.
DW_IDX_parent can represent either the parent pool entry index [âŚ] or the parent pool entry offset
I agree it doesnât matter much, but on page 141, lines 22-24, it says that:
Parent debugging information entry, a reference to the index entry for the parent. This is represented as the offset of the entry relative to the start of the entry pool.
More generally though, I think the bigger problem of template / simple / canonical names remain: when we are looking for A::B::C, the spelling of âBâ may be different in the table and in what LLDB is querying (see the template examples provided in this thread). Right now I donât see a way to reconcile DW_IDX_parent with the template canonical name problem, unless we can guarantee that LLDBâs context query will use the same spelling used in the table.
To answer @dblaikie question from an earlier post:
If the DW_IDX_parent is enough to get adequate performance it might be the best option. Though is it likely to be enough? Iâd have thought most of the perf problems come from multiple instantiations of the same template - so theyâll all have the same parent chain, so this might not help improve performance by much?
This should be enough because the slow part is parsing the DIEs in the debug_info section for the false hits. If we can resolve everything exclusively through the accelerator table â without parsing DIEs â then things would be fast even with multiple instantiations of the same template.
since we have the entire parent chain, so we know its hash in the table, and therefore we know which offsets have that name
That may not be accurate. The index table consists of two types of entries: name table entries and pool entries. One name table entry can have multiple pool entries (multiple types can share the same base name). Therefore, DW_IDX_parent should point to a pool entry (the second type), not a name table entry. Otherwise, it would be impossible to determine the specific pool entry that DW_IDX_parent is pointing to.
The issue with the current implementation in LLDB is that âpool entriesâ are lazily parsed and do not have a backward pointer to their corresponding âname table entry.â As a result, the pool entry only contains the tag and lacks the ânameâ information. To address this, LLDB will need to eagerly parse all pool entries to create a reverse mapping from pool entry to name table entry (i.e., <pool entry => name table entry>).
To add more complexity, the parent pool entry can be nameless (see the specification section below) which canât be indexed from named table entry. So we will have to flatten all pool entries scanning to fully build the parent chain:
It is possible that an indexed debugging information entry has a parent that is
not indexed (for example, if its parent does not have a name attribute). In such a
case, a parent attribute may point to a nameless index entry (that is, one that
cannot be reached from any entry in the name table), or it may point to the
nearest ancestor that does have an index entry.
Therefore, DW_IDX_parent should point to a pool entry (the second type), not a name table entry.
Yup, this makes sense. But consider this example, where we are looking for A::B and do the following queries:
Query the table for B, letâs say it gives us a single result, and its DW_IDX= pool_entry_B_parent (a pool entry).
Query the table for A, letâs say it gives us two results: pool_entry_A1 and pool_entry_A2. If either pool_entry_A1 == pool_entry_B_parent or pool_entry_A2 == pool_entry_B_parent, we know that pool_entry_B_parent has the name A.
This precludes the need for parent name information. Does that make sense?
To add more complexity, the parent pool entry can be nameless
Would that be a concern for us though? Whenever we are doing type lookup, we have names for everything (A::B::C). If we found something on the accelerator table without a parent â or a nameless parent â we know this is not the entry we are looking for, no?
, I think the bigger problem of template / simple / canonical names remain
Even if we resolve the parent name issue, I still donât see how we get around the template names problem, either with IDX_parent or IDX_type_hash. Did you have a plan for those?
