https://github.com/felipepiovezan created https://github.com/llvm/llvm-project/pull/206986
The RangeVector abstraction is slow w.r.t. amount of sorting it requires, and it is particularly bad when sorting a MemoryRegionInfo, as this object is expensive to move. All of this is aggravated in sanitizer bots, where a handful of tests started timing out as a result of the MemoryRegionInfoCache. This commit fixes the situation by simplifying the code: just use a std::map. Based on current usage, behaviour should be identical to before. In particular, neither case addresses cases like this: 1. Insert range [100, 200] 2. Insert range [150, 160] 3. Query address 170. In both cases we fail to find a cached range and proceed to query the inferior again. Which is not incorrect, jut doesn't maximize the cache usage. A proper fix is to use an interval tree, with the assumption that if overlapping ranges are inserted, they have the same memory region info contents and we can just join the intervals. >From b922c443e6a79e47b916fc8b32b46225f254655d Mon Sep 17 00:00:00 2001 From: Felipe de Azevedo Piovezan <[email protected]> Date: Wed, 1 Jul 2026 13:43:39 +0100 Subject: [PATCH] [lldb] Use std::map in MemoryRegionInfoCache The RangeVector abstraction is slow w.r.t. amount of sorting it requires, and it is particularly bad when sorting a MemoryRegionInfo, as this object is expensive to move. All of this is aggravated in sanitizer bots, where a handful of tests started timing out as a result of the MemoryRegionInfoCache. This commit fixes the situation by simplifying the code: just use a std::map. Based on current usage, behaviour should be identical to before. In particular, neither case addresses cases like this: 1. Insert range [100, 200] 2. Insert range [150, 160] 3. Query address 170. In both cases we fail to find a cached range and proceed to query the inferior again. Which is not incorrect, jut doesn't maximize the cache usage. A proper fix is to use an interval tree, with the assumption that if overlapping ranges are inserted, they have the same memory region info contents and we can just join the intervals. --- .../lldb/Target/MemoryRegionInfoCache.h | 9 +++----- lldb/source/Target/MemoryRegionInfoCache.cpp | 23 ++++++++----------- 2 files changed, 12 insertions(+), 20 deletions(-) diff --git a/lldb/include/lldb/Target/MemoryRegionInfoCache.h b/lldb/include/lldb/Target/MemoryRegionInfoCache.h index 538d01f5fb81f..5117f1f598e55 100644 --- a/lldb/include/lldb/Target/MemoryRegionInfoCache.h +++ b/lldb/include/lldb/Target/MemoryRegionInfoCache.h @@ -10,15 +10,15 @@ #define LLDB_TARGET_MEMORYREGIONINFOCACHE_H #include "lldb/Target/MemoryRegionInfo.h" -#include "lldb/Utility/RangeMap.h" +#include <map> #include <mutex> #include <optional> namespace lldb_private { class MemoryRegionInfoCache { public: - MemoryRegionInfoCache() : m_region_infos(), m_is_sorted(true), m_mutex() {} + MemoryRegionInfoCache() = default; /// Remove all cached entries. Should be called whenever /// Process resumes execution of the inferior. @@ -34,10 +34,7 @@ class MemoryRegionInfoCache { size_t GetSize(); private: - typedef RangeDataVector<lldb::addr_t, size_t, lldb_private::MemoryRegionInfo> - InfoMap; - InfoMap m_region_infos; - bool m_is_sorted; + std::map<lldb::addr_t, MemoryRegionInfo> m_region_infos; std::mutex m_mutex; }; } // namespace lldb_private diff --git a/lldb/source/Target/MemoryRegionInfoCache.cpp b/lldb/source/Target/MemoryRegionInfoCache.cpp index 4adaf20227910..47694b3ad58fc 100644 --- a/lldb/source/Target/MemoryRegionInfoCache.cpp +++ b/lldb/source/Target/MemoryRegionInfoCache.cpp @@ -14,33 +14,28 @@ using namespace lldb_private; void MemoryRegionInfoCache::Clear() { std::lock_guard<std::mutex> guard(m_mutex); - m_region_infos.Clear(); - m_is_sorted = true; + m_region_infos.clear(); } size_t MemoryRegionInfoCache::GetSize() { std::lock_guard<std::mutex> guard(m_mutex); - return m_region_infos.GetSize(); + return m_region_infos.size(); } std::optional<MemoryRegionInfo> MemoryRegionInfoCache::GetMemoryRegion(addr_t load_addr) { std::lock_guard<std::mutex> guard(m_mutex); - if (!m_is_sorted) { - m_region_infos.Sort(); - m_is_sorted = true; - } - uint32_t index = m_region_infos.FindEntryIndexThatContains(load_addr); - if (index != UINT32_MAX) - return m_region_infos.GetEntryAtIndex(index)->data; + auto it = m_region_infos.upper_bound(load_addr); + if (it == m_region_infos.begin()) + return std::nullopt; + --it; + if (load_addr < it->second.GetRange().GetRangeEnd()) + return it->second; return std::nullopt; } void MemoryRegionInfoCache::AddRegion(const MemoryRegionInfo &ri) { std::lock_guard<std::mutex> guard(m_mutex); - InfoMap::Entry new_entry(ri.GetRange().GetRangeBase(), - ri.GetRange().GetByteSize(), ri); - m_region_infos.Append(new_entry); - m_is_sorted = false; + m_region_infos.insert_or_assign(ri.GetRange().GetRangeBase(), ri); } _______________________________________________ lldb-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
