llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-lldb Author: Felipe de Azevedo Piovezan (felipepiovezan) <details> <summary>Changes</summary> This is a multimap of Hash -> ObjCISA (lldb::addr_t), and it shows up cpu traces of swift applications. This commit replaces `std::multimap<hash, addr_t>` with `DenseMap<hash, SmallVector<addr_t, 3>>`. This data structure was chosen because of the following experiment. When evaluating a frame variable command for a SwiftUI variable, this object gets populated with ~186,000 entries: * over a thousand of them had 2 hash collisions. * 300 of them had 3 hash collisions. * 21 of them had 4 hash collisions. * 1 of them had 5 hash collisions. On a release build (no asserts), this patch brought down the CPU cycles measured for that command from 487M cycles to 389M cycles. --- Full diff: https://github.com/llvm/llvm-project/pull/197444.diff 2 Files Affected: - (modified) lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.cpp (+8-10) - (modified) lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.h (+2-3) ``````````diff diff --git a/lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.cpp b/lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.cpp index 512426d0bd254..d0dc252199800 100644 --- a/lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.cpp +++ b/lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.cpp @@ -194,16 +194,14 @@ ObjCLanguageRuntime::GetDescriptorIterator(ConstString name) { // Name hashes were provided, so use them to efficiently lookup name to // isa/descriptor const uint32_t name_hash = llvm::djbHash(name.GetStringRef()); - std::pair<HashToISAIterator, HashToISAIterator> range = - m_hash_to_isa_map.equal_range(name_hash); - for (HashToISAIterator range_pos = range.first; range_pos != range.second; - ++range_pos) { - ISAToDescriptorIterator pos = m_isa_to_descriptor.find(range_pos->second); - if (pos != m_isa_to_descriptor.end()) { - if (pos->second->GetClassName() == name) - return pos; - } - } + auto matches_it = m_hash_to_isa_map.find(name_hash); + if (matches_it == m_hash_to_isa_map.end()) + return m_isa_to_descriptor.end(); + + for (auto isa : matches_it->second) + if (auto pos = m_isa_to_descriptor.find(isa); + pos != m_isa_to_descriptor.end() && pos->second->GetClassName() == name) + return pos; return m_isa_to_descriptor.end(); } diff --git a/lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.h b/lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.h index 74ac557906d41..104c6033643aa 100644 --- a/lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.h +++ b/lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.h @@ -353,7 +353,7 @@ class ObjCLanguageRuntime : public LanguageRuntime { uint32_t class_name_hash) { if (isa != 0) { m_isa_to_descriptor.insert_or_assign(isa, descriptor_sp); - m_hash_to_isa_map.insert(std::make_pair(class_name_hash, isa)); + m_hash_to_isa_map[class_name_hash].push_back(isa); return true; } return false; @@ -420,9 +420,8 @@ class ObjCLanguageRuntime : public LanguageRuntime { typedef std::map<ClassAndSel, lldb::addr_t> MsgImplMap; typedef std::map<ClassAndSelStr, lldb::addr_t> MsgImplStrMap; typedef llvm::DenseMap<ObjCISA, ClassDescriptorSP> ISAToDescriptorMap; - typedef std::multimap<uint32_t, ObjCISA> HashToISAMap; + typedef llvm::DenseMap<uint32_t, llvm::SmallVector<ObjCISA, 3>> HashToISAMap; typedef ISAToDescriptorMap::iterator ISAToDescriptorIterator; - typedef HashToISAMap::iterator HashToISAIterator; typedef ThreadSafeDenseMap<void *, uint64_t> TypeSizeCache; MsgImplMap m_impl_cache; `````````` </details> https://github.com/llvm/llvm-project/pull/197444 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
