[lldb/DWARF] Refactor to prefer emplace_back() vs. push_back()

[dmantipov]

Summary

Prefer emplace_back() over push_back() where appropriate to avoid extra calls to copy and/or move constructors.

[dmantipov]

Minor style adjustments.

[labath]

Using emplacement instead of construction is a good idea, where it makes sense. However, I am not convinced that adding constructors to otherwise-trivial structures is worth it. These structures are usually trivially copyable and/or movable and so an emplacement does not really save much.

And I am definitely sure that the constructors we do add should be taking (lvalue) references -- that precludes construction with anything other than an lvalue, which is just weird. They also force at least one copy, whereas a equivalent (properly written) push_back call could use no copies.

So, I'd just limit this patch to the cases where one does not need to add additional constructors to make emplace_back work.

[dmantipov]

Use std::pair rather than an ad-hoc two-member trivial structures. Since std::pair provides the default constructor to initialize both members, no extra C++ glue is required for emplace_back()'ing the pairs into containers.

[labath]

In D87675#2273831, @dmantipov wrote:

Use std::pair rather than an ad-hoc two-member trivial structures. Since std::pair provides the default constructor to initialize both members, no extra C++ glue is required for emplace_back()'ing the pairs into containers.

I am sorry, but I don't consider that an improvement. The reason these were not pairs in the first place is because the first/second accessors are very nondescript. If you can demonstrate that these actually improve performance, then we can talk about the best way to do this. However, I'd be very surprised if any of these show up in a profile.

[dmantipov]

OK let's reduce it to minimum minimorum.

As for the profiling, l can see possible improvement around DWARFAttributes::Append() - inlining even at -O2 and eliminating extra constructor call makes

10.61%  intern-state     liblldb.so.12.0.0git   [.] DWARFDebugInfoEntry::GetAttributes
7.28%  intern-state     liblldb.so.12.0.0git   [.] DWARFDebugInfoEntry::Extract
6.88%  intern-state     liblldb.so.12.0.0git   [.] lldb_private::ManualDWARFIndex::IndexUnitImpl
5.76%  intern-state     libpthread-2.31.so     [.] __pthread_rwlock_rdlock
5.43%  intern-state     liblldb.so.12.0.0git   [.] lldb_private::DataExtractor::GetU32
4.70%  intern-state     liblldb.so.12.0.0git   [.] DWARFUnit::GetDIE
4.49%  intern-state     liblldb.so.12.0.0git   [.] lldb_private::DWARFContext::LoadOrGetSection
4.37%  intern-state     libLLVM-12git.so       [.] llvm::StringMapImpl::FindKey
3.50%  intern-state     liblldb.so.12.0.0git   [.] DWARFFormValue::GetFixedSize
2.73%  intern-state     liblldb.so.12.0.0git   [.] DWARFUnit::ExtractDIEsRWLocked
2.61%  intern-state     liblldb.so.12.0.0git   [.] Pool::GetConstCStringWithStringRef
2.08%  intern-state     liblldb.so.12.0.0git   [.] lldb_private::DataExtractor::GetULEB128
1.82%  intern-state     ld-2.31.so             [.] __tls_get_addr
1.77%  intern-state     liblldb.so.12.0.0git   [.] std::__introsort_loop<__gnu_cxx::__normal_iterator<lldb_private::UniqueCStringMap<DIERef>::Entry*, std::vector<lldb_private::UniqueCStringMap<DIERef>::Entry, std::allocator<lldb_private::UniqueCStringMap<DIERef>::Entry> > >, long, __gnu_cxx::__ops::_Iter_comp_iter<lldb_private::Uniqu
eCStringMap<DIERef>::Compare> >
1.60%  intern-state     liblldb.so.12.0.0git   [.] DWARFFormValue::ExtractValue
1.55%  intern-state     libpthread-2.31.so     [.] __pthread_rwlock_unlock
1.23%  intern-state     libc-2.31.so           [.] __strlen_avx2
1.15%  intern-state     libc-2.31.so           [.] _int_free
1.15%  intern-state     libc-2.31.so           [.] malloc
1.14%  intern-state     liblldb.so.12.0.0git   [.] DWARFAttributes::ExtractFormValueAtIndex

from:

7.68%  intern-state     liblldb.so.12.0.0git   [.] DWARFAttributes::Append
7.25%  intern-state     liblldb.so.12.0.0git   [.] DWARFDebugInfoEntry::Extract
6.34%  intern-state     liblldb.so.12.0.0git   [.] lldb_private::ManualDWARFIndex::IndexUnitImpl
6.30%  intern-state     liblldb.so.12.0.0git   [.] DWARFDebugInfoEntry::GetAttributes
5.55%  intern-state     libpthread-2.31.so     [.] __pthread_rwlock_rdlock
5.51%  intern-state     liblldb.so.12.0.0git   [.] lldb_private::DataExtractor::GetU32
4.50%  intern-state     liblldb.so.12.0.0git   [.] DWARFUnit::GetDIE
4.34%  intern-state     liblldb.so.12.0.0git   [.] lldb_private::DWARFContext::LoadOrGetSection
4.27%  intern-state     libLLVM-12git.so       [.] llvm::StringMapImpl::FindKey
2.92%  intern-state     liblldb.so.12.0.0git   [.] DWARFFormValue::GetFixedSize
2.65%  intern-state     liblldb.so.12.0.0git   [.] DWARFUnit::ExtractDIEsRWLocked
2.51%  intern-state     liblldb.so.12.0.0git   [.] Pool::GetConstCStringWithStringRef
1.93%  intern-state     liblldb.so.12.0.0git   [.] lldb_private::DataExtractor::GetULEB128
1.79%  intern-state     liblldb.so.12.0.0git   [.] std::__introsort_loop<__gnu_cxx::__normal_iterator<lldb_private::UniqueCStringMap<DIERef>::Entry*, std::vector<lldb_private::UniqueCStringMap<DIERef>::Entry, std::allocator<lldb_private::UniqueCStringMap<DIERef>::Entry> > >, long, __gnu_cxx::__ops::_Iter_comp_iter<lldb_private::UniqueCStringMap<DIERef>::Compare> >
1.78%  intern-state     ld-2.31.so             [.] __tls_get_addr
1.46%  intern-state     libpthread-2.31.so     [.] __pthread_rwlock_unlock
1.45%  intern-state     liblldb.so.12.0.0git   [.] DWARFFormValue::ExtractValue
1.22%  intern-state     libc-2.31.so           [.] __strlen_avx2
1.16%  intern-state     libc-2.31.so           [.] malloc
1.11%  intern-state     libc-2.31.so           [.] _int_free
1.08%  intern-state     liblldb.so.12.0.0git   [.] DWARFAttributes::ExtractFormValueAtIndex

when loading symbols from clang + libLLVM.so (release build with '-O2 -g').

[labath]

Ok, this is something we can talk about. dwarf parsing is a big bottle neck, so spending some time to optimize that (and even sacrifice some readability/mantainability/etc. if needed) is worthwhile.

That said, I am pretty sure that any performance gains you're seeing (you didn't explain what/how you're measuring so it's hard to say for sure), are due to the additional inlining opportunities afforded by moving this function to the header, and _not_ because of the use of emplace_back. In my comparison, the two implementations ended up looking fairly different, but I don't think the differences cannot be explained by the use of emplace_back. In both cases, the compiler was able to fully optimize away all the push_backs, constructor calls, etc., and the fast path for both functions consists of a bunch of move instructions. If one of the two versions ends up being slower, then this indicates a missed optimization opportunity on the side of the compiler (which could be removed or even reversed by using a different compiler), and not a fundamental problem with using push_back with trivially copyable structs.

_That_ said, I don't think adding the constructor is necessarily bad in this case, so I think it's fine to stick with the current implementation.

lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp

           if (!size)
             return false;
           llvm::APInt apint(*size, uval64, is_signed);
-          template_param_infos.args.push_back(
-              clang::TemplateArgument(ast, llvm::APSInt(apint, !is_signed),
-                                      ClangUtil::GetQualType(clang_type)));
-        } else {
-          template_param_infos.args.push_back(
-              clang::TemplateArgument(ClangUtil::GetQualType(clang_type)));
-        }
+          template_param_infos.args.emplace_back(
+              ast, llvm::APSInt(apint, !is_signed),
+              ClangUtil::GetQualType(clang_type));
+        } else
+          template_param_infos.args.emplace_back(
+              ClangUtil::GetQualType(clang_type));
       } else {
         auto *tplt_type = m_ast.CreateTemplateTemplateParmDecl(template_name);
         template_param_infos.names.push_back(name);
-        template_param_infos.args.push_back(
-            clang::TemplateArgument(clang::TemplateName(tplt_type)));
+        template_param_infos.args.emplace_back(clang::TemplateName(tplt_type));
       }
     }
   }

 
       ClangASTMetadata metadata;
       metadata.SetUserID(die.GetID());
-      delayed_properties.push_back(DelayedAddObjCClassProperty(
+      delayed_properties.emplace_back(
           class_clang_type, prop_name, member_type->GetLayoutCompilerType(),
           ivar_decl, prop_setter_name, prop_getter_name, prop_attributes,
-          &metadata));
+          &metadata);
 
       if (ivar_decl)
         m_ast.SetMetadataAsUserID(ivar_decl, die.GetID());

lldb/source/Plugins/SymbolFile/DWARF/DWARFAbbreviationDeclaration.cpp

     if (form == DW_FORM_implicit_const)
       val.value.sval = data.GetULEB128(offset_ptr);
 
-    m_attributes.push_back(DWARFAttribute(attr, form, val));
+    m_attributes.emplace_back(attr, form, val);
   }
 
   return llvm::make_error<llvm::object::GenericBinaryError>(

lldb/source/Plugins/SymbolFile/DWARF/DWARFAttribute.h

   DWARFAttributes();
   ~DWARFAttributes();
 
-  void Append(const DWARFUnit *cu, dw_offset_t attr_die_offset,
-              dw_attr_t attr, dw_form_t form);
+  void Append(const DWARFUnit *cu, dw_offset_t attr_die_offset, dw_attr_t attr,
+              dw_form_t form) {
+    m_infos.emplace_back(cu, attr_die_offset, attr, form);
+  }
   const DWARFUnit *CompileUnitAtIndex(uint32_t i) const {
     return m_infos[i].cu;
   }

                                 // case we have DW_FORM_ref_addr values
     dw_offset_t die_offset;
     DWARFAttribute attr;
+
+    AttributeValue(const DWARFUnit *cu, dw_offset_t die_offset, dw_attr_t attr,
+                   dw_form_t form)
+      : cu(cu), die_offset(die_offset),
+        attr(attr, form, DWARFFormValue::ValueType()) {}
   };
   typedef llvm::SmallVector<AttributeValue, 8> collection;
   collection m_infos;

lldb/source/Plugins/SymbolFile/DWARF/DWARFAttribute.cpp

   return UINT32_MAX;
 }
 
-void DWARFAttributes::Append(const DWARFUnit *cu, dw_offset_t attr_die_offset,
-                             dw_attr_t attr, dw_form_t form) {
-  AttributeValue attr_value = {
-      cu, attr_die_offset, {attr, form, DWARFFormValue::ValueType()}};
-  m_infos.push_back(attr_value);
-}
-
 bool DWARFAttributes::ExtractFormValueAtIndex(
     uint32_t i, DWARFFormValue &form_value) const {
   const DWARFUnit *cu = CompileUnitAtIndex(i);

lldb/source/Plugins/SymbolFile/DWARF/DWARFDIE.cpp

     parent.GetDeclContext(context);
   switch (tag) {
   case DW_TAG_module:
-    context.push_back({CompilerContextKind::Module, ConstString(GetName())});
+    context.emplace_back(CompilerContextKind::Module, ConstString(GetName()));
     break;
   case DW_TAG_namespace:
-    context.push_back({CompilerContextKind::Namespace, ConstString(GetName())});
+    context.emplace_back(CompilerContextKind::Namespace, ConstString(GetName()));
     break;
   case DW_TAG_structure_type:
-    context.push_back({CompilerContextKind::Struct, ConstString(GetName())});
+    context.emplace_back(CompilerContextKind::Struct, ConstString(GetName()));
     break;
   case DW_TAG_union_type:
-    context.push_back({CompilerContextKind::Union, ConstString(GetName())});
+    context.emplace_back(CompilerContextKind::Union, ConstString(GetName()));
     break;
   case DW_TAG_class_type:
-    context.push_back({CompilerContextKind::Class, ConstString(GetName())});
+    context.emplace_back(CompilerContextKind::Class, ConstString(GetName()));
     break;
   case DW_TAG_enumeration_type:
-    context.push_back({CompilerContextKind::Enum, ConstString(GetName())});
+    context.emplace_back(CompilerContextKind::Enum, ConstString(GetName()));
     break;
   case DW_TAG_subprogram:
-    context.push_back(
-        {CompilerContextKind::Function, ConstString(GetPubname())});
+    context.emplace_back(CompilerContextKind::Function,
+                         ConstString(GetPubname()));
     break;
   case DW_TAG_variable:
-    context.push_back(
-        {CompilerContextKind::Variable, ConstString(GetPubname())});
+    context.emplace_back(CompilerContextKind::Variable,
+                         ConstString(GetPubname()));
     break;
   case DW_TAG_typedef:
-    context.push_back({CompilerContextKind::Typedef, ConstString(GetName())});
+    context.emplace_back(CompilerContextKind::Typedef, ConstString(GetName()));
     break;
   default:
     break;