Author: Jim Ingham Date: 2022-08-18T09:34:28-07:00 New Revision: 33722848fcb5b569ab3a388cae15f31acf9a9c5e
URL: https://github.com/llvm/llvm-project/commit/33722848fcb5b569ab3a388cae15f31acf9a9c5e DIFF: https://github.com/llvm/llvm-project/commit/33722848fcb5b569ab3a388cae15f31acf9a9c5e.diff LOG: Use a SmallPtrSet rather than a SmallVector in ClusterManager. The m_objects store in this class is only used to check whether this ClusterManager already owns this pointer. With a SmallVector the is_contained call was non-linear in number of children, and for instance printing all the elements of a 16M element std::vector didn't complete in the time I was willing to wait for it (hours). Since we are only doing insert & contains, some kind of set is a better data structure. In this patch I used SmallPtrSet. With that, the same array prints out in 30 seconds. I also tried a std::unordered_set but that was slightly slower and used a fair bit more memory. Other than performance, this is NFC. Differential Revision: https://reviews.llvm.org/D131996 Added: Modified: lldb/include/lldb/Utility/SharedCluster.h Removed: ################################################################################ diff --git a/lldb/include/lldb/Utility/SharedCluster.h b/lldb/include/lldb/Utility/SharedCluster.h index b3f41dbaa64b0..9f7aa92420ed0 100644 --- a/lldb/include/lldb/Utility/SharedCluster.h +++ b/lldb/include/lldb/Utility/SharedCluster.h @@ -11,7 +11,7 @@ #include "lldb/Utility/LLDBAssert.h" #include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/SmallPtrSet.h" #include <memory> #include <mutex> @@ -32,15 +32,15 @@ class ClusterManager : public std::enable_shared_from_this<ClusterManager<T>> { void ManageObject(T *new_object) { std::lock_guard<std::mutex> guard(m_mutex); - assert(!llvm::is_contained(m_objects, new_object) && - "ManageObject called twice for the same object?"); - m_objects.push_back(new_object); + auto ret = m_objects.insert(new_object); + assert(ret.second && "ManageObject called twice for the same object?"); } std::shared_ptr<T> GetSharedPointer(T *desired_object) { std::lock_guard<std::mutex> guard(m_mutex); auto this_sp = this->shared_from_this(); - if (!llvm::is_contained(m_objects, desired_object)) { + size_t count = m_objects.count(desired_object); + if (count == 0) { lldbassert(false && "object not found in shared cluster when expected"); desired_object = nullptr; } @@ -49,8 +49,14 @@ class ClusterManager : public std::enable_shared_from_this<ClusterManager<T>> { private: ClusterManager() : m_objects() {} - - llvm::SmallVector<T *, 16> m_objects; + // The cluster manager is used primarily to manage the + // children of root ValueObjects. So it will always have + // one element - the root. Pointers will often have dynamic + // values, so having 2 entries is pretty common. It's also + // pretty common to have small (2,3) structs, so setting the + // static size to 4 will cover those cases with no allocations + // w/o wasting too much space. + llvm::SmallPtrSet<T *, 4> m_objects; std::mutex m_mutex; }; _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits