Optimize GetCompileUnitContainingDIE with a lookup table

[clayborg]

Summary

Optimize GetCompileUnitContainingDIE with a lookup table

For large executable with debug symbols GetCompileUnitContainingDIE
took most of the time spent on DWARF parsing. Optimize it from linear
search to a logarithmic search with a lookup table.

[jingham]

I'll let Greg weigh in on the actual details, but if as I understand the patch, the m_die_to_index_map only stored CU dies, can you make the name of the ivar indicate that fact?

[tberghammer]

Yes it only contains compile unit indexes. The reason I haven't included in the name because the class focuses on compile units, but I can add it if you prefer it that way.

[clayborg]

No need for an extra map. A local C++ guru a while back told me about being able to use a comparison function with two different types if you use std::lower_bound() or std::upper_bound(). Since m_compiler_units is sorted, we can just do:

static bool CompileUnitOffsetLessThan (dw_offset_t die_offset, const DWARFCompileUnitSP& cu_sp)
{
    return die_offset < cu_sp->GetOffset();
}

DWARFCompileUnitSP
DWARFDebugInfo::GetCompileUnitContainingDIE(dw_offset_t die_offset)
{
    DWARFCompileUnitSP cu_sp;
    if (die_offset != DW_INVALID_OFFSET)
    {
        ParseCompileUnitHeadersIfNeeded();

        // Watch out for single compile unit executable as they are pretty common
        const size_t num_cus = m_compile_units.size();
        if (num_cus == 1)
        {
            if (m_compile_units[0]->ContainsDIEOffset(die_offset))
                cu_sp = m_compile_units[0];
        }
        else if (num_cus)
        {
            CompileUnitColl::const_iterator end_pos = m_compile_units.end();
            CompileUnitColl::const_iterator begin_pos = m_compile_units.begin();
            CompileUnitColl::const_iterator pos = std::upper_bound(begin_pos, end_pos, die_offset, CompileUnitOffsetLessThan);
            if (pos != begin_pos)
            {
                --pos;
                if ((*pos)->ContainsDIEOffset(die_offset))
                    cu_sp = *pos;
            }
        }
    }
    return cu_sp;
}

Try out the changes and make sure they work and then switch to using the code above.

[clayborg]

I actually checked my changes in with:

% svn commit
Sending source/Plugins/SymbolFile/DWARF/DWARFDebugInfo.cpp
Transmitting file data .
Committed revision 242852.

source/Plugins/SymbolFile/DWARF/DWARFDebugInfo.h

public:
 
     bool LookupAddress(
             const dw_addr_t address,
             const dw_offset_t cu_offset,    // Can be valid (find in .debug_aranges), or DW_INVALID_OFFSET if we need to search manually
             DWARFCompileUnitSP& cu_shared_ptr,
             DWARFDebugInfoEntry** function_die,
             DWARFDebugInfoEntry** block_die);
 
-    void AddCompileUnit(DWARFCompileUnitSP& cu);
     size_t GetNumCompileUnits();
     bool ContainsCompileUnit (const DWARFCompileUnit *cu) const;
     DWARFCompileUnit* GetCompileUnitAtIndex(uint32_t idx);
     DWARFCompileUnitSP GetCompileUnit(dw_offset_t cu_offset, uint32_t* idx_ptr = NULL);
     DWARFCompileUnitSP GetCompileUnitContainingDIE(dw_offset_t die_offset);
 
     DWARFDebugInfoEntry* GetDIEPtr(dw_offset_t die_offset, DWARFCompileUnitSP* cu_sp_ptr);
     DWARFDebugInfoEntry* GetDIEPtrWithCompileUnitHint (dw_offset_t die_offset, DWARFCompileUnit**cu_handle);
public:
 
     DWARFDebugAranges &
     GetCompileUnitAranges ();
 
 protected:
     SymbolFileDWARF* m_dwarf2Data;
     typedef std::vector<DWARFCompileUnitSP>     CompileUnitColl;
     CompileUnitColl m_compile_units;
+    std::map<dw_offset_t, size_t> m_die_to_index_map;
     std::unique_ptr<DWARFDebugAranges> m_cu_aranges_ap; // A quick address to compile unit table
 
 private:
     // All parsing needs to be done partially any managed by this class as accessors are called.
     void ParseCompileUnitHeadersIfNeeded();
 
     DISALLOW_COPY_AND_ASSIGN (DWARFDebugInfo);
 };
 
 #endif  // SymbolFileDWARF_DWARFDebugInfo_h_

source/Plugins/SymbolFile/DWARF/DWARFDebugInfo.cpp

 using namespace std;
 
 //----------------------------------------------------------------------
 // Constructor
 //----------------------------------------------------------------------
 DWARFDebugInfo::DWARFDebugInfo() :
     m_dwarf2Data(NULL),
     m_compile_units(),
-    m_cu_aranges_ap ()
+    m_die_to_index_map(),
+    m_cu_aranges_ap()
 {
 }
 
 //----------------------------------------------------------------------
 // SetDwarfData
 //----------------------------------------------------------------------
 void
 DWARFDebugInfo::SetDwarfData(SymbolFileDWARF* dwarf2Data)
 {
     m_dwarf2Data = dwarf2Data;
     m_compile_units.clear();
+    m_die_to_index_map.clear();
 }
 
 
 DWARFDebugAranges &
 DWARFDebugInfo::GetCompileUnitAranges ()
 {
     if (m_cu_aranges_ap.get() == NULL && m_dwarf2Data)
     {
if (m_compile_units.empty())
                 // Out of memory?
                 if (cu_sp.get() == NULL)
                     break;
 
                 if (cu_sp->Extract(debug_info_data, &offset) == false)
                     break;
 
                 m_compile_units.push_back(cu_sp);
+                m_die_to_index_map[cu_sp->GetOffset()] = m_compile_units.size() - 1;
 
                 offset = cu_sp->GetNextCompileUnitOffset();
             }
         }
     }
 }
 
 size_t
DWARFDebugInfo::GetCompileUnit(dw_offset_t cu_offset, uint32_t* idx_ptr)
     if (idx_ptr)
         *idx_ptr = cu_idx;
     return cu_sp;
 }
 
 DWARFCompileUnitSP
 DWARFDebugInfo::GetCompileUnitContainingDIE(dw_offset_t die_offset)
 {
-    DWARFCompileUnitSP cu_sp;
     if (die_offset != DW_INVALID_OFFSET)
     {
         ParseCompileUnitHeadersIfNeeded();
 
-        CompileUnitColl::const_iterator end_pos = m_compile_units.end();
-        CompileUnitColl::const_iterator pos;
-
-        for (pos = m_compile_units.begin(); pos != end_pos; ++pos)
-        {
-            dw_offset_t cu_start_offset = (*pos)->GetOffset();
-            dw_offset_t cu_end_offset = (*pos)->GetNextCompileUnitOffset();
-            if (cu_start_offset <= die_offset && die_offset < cu_end_offset)
-            {
-                cu_sp = *pos;
-                break;
-            }
-        }
-    }
+        auto pos = m_die_to_index_map.upper_bound(die_offset);
+        if (pos == m_die_to_index_map.begin())
+            return DWARFCompileUnitSP();
+        --pos;
+
+        DWARFCompileUnitSP& cu_sp = m_compile_units[pos->second];
+        assert(cu_sp->GetOffset() <= die_offset && "m_die_to_index_map contains invalid data");
+        if (die_offset < cu_sp->GetNextCompileUnitOffset())
             return cu_sp;
     }
+    return DWARFCompileUnitSP();
+}
 
 //----------------------------------------------------------------------
 // GetDIE()
 //
 // Get the DIE (Debug Information Entry) with the specified offset.
 //----------------------------------------------------------------------
 DWARFDebugInfoEntry*
 DWARFDebugInfo::GetDIEPtr(dw_offset_t die_offset, DWARFCompileUnitSP* cu_sp_ptr)

 {
     DWARFCompileUnitSP cu_sp(GetCompileUnitContainingDIE(die_offset));
     if (cu_sp_ptr)
         *cu_sp_ptr = cu_sp;
     if (cu_sp.get())
         return cu_sp->GetDIEPtrContainingOffset(die_offset);
 
     return NULL;    // Not found in any compile units
-
 }
 
 //----------------------------------------------------------------------
-// AddCompileUnit
-//----------------------------------------------------------------------
-void
-DWARFDebugInfo::AddCompileUnit(DWARFCompileUnitSP& cu)
-{
-    m_compile_units.push_back(cu);
-}
-
-/*
-void
-DWARFDebugInfo::AddDIE(DWARFDebugInfoEntry& die)
-{
-    m_die_array.push_back(die);
-}
-*/
-
-
-
-
-//----------------------------------------------------------------------
 // Parse
 //
 // Parses the .debug_info section and uses the .debug_abbrev section
 // and various other sections in the SymbolFileDWARF class and calls the
 // supplied callback function each time a compile unit header, or debug
 // information entry is successfully parsed. This function can be used
 // for different tasks such as parsing the file contents into a
 // structured data, dumping, verifying and much more.