Use a SmallPtrSet rather than a SmallVector in ClusterManager.

[jingham]

Summary

The m_objects store in ClusterManager holds pointers to all the objects
managed by the ClusterManager. It is used to check whether
this ClusterManager already owns this pointer before adding it to
the ClusterManager's shared pointer or getting the shared pointer for the object.
When the ClusterManager is deleted, we iterate over it to destroy all the managed objects.
The most common operation by far is "GetSharedPointer" on the cluster.

With a SmallVector and llvm::is_contained the performance was non-linear
in the number of elements. 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 mostly doing insert & contains, some kind of set is likely to be a
better data structure. In this patch I used SmallPtrSet. With
that, the same array prints out in 30 seconds. I couldn't see any noticeable difference
for ValueObjects with a small number of children. I also tried a the same patch using a
std::unordered_set but that was slightly slower and used a fair bit
more memory than the SmallPtrSet.

Other than performance, this is NFC.

[kastiglione]

+1

[JDevlieghere]

LGTM modulo inline comment.

lldb/include/lldb/Utility/SharedCluster.h

52–59

I assume pointers cannot be modified once they're in the set. Can this be const T *?

[labath]

In case you have an idea of what's the "typical" number of objects in shared cluster, then we can tune the integer template parameter (in case we usually have more than 16 objects, then the inline storage is just wasting space, and we could reduce it).

lldb/include/lldb/Utility/SharedCluster.h

52–59

Did you mean pointers temselves, or the objects they point to? The pointers are automatically const (you can't modify the map copy in-place), and if someone wanted to store const objects, he could always instantiate this class with const T instead.

[JDevlieghere]

lldb/include/lldb/Utility/SharedCluster.h

52–59

I meant the latter. You could indeed have an instance of this class with a const T, but that has a different meaning. My point was that the m_objects could always store const objects (even though it's somewhat counter intuitive that you can delete a const pointer). Anyway, it's no big deal, and I guess not making this const T* allows you to have an actual const T template argument while otherwise we'd need const std::remove_const<T> to make that case work, which obviously isn't worth it.

[jingham]

In D131996#3728253, @labath wrote:

In case you have an idea of what's the "typical" number of objects in shared cluster, then we can tune the integer template parameter (in case we usually have more than 16 objects, then the inline storage is just wasting space, and we could reduce it).

I don't remember who made the guess at 16, or what went into that choice.

What we know is that there will ALWAYS be one, and there are a lot of scalar variables floating around in code so that would cover them. The SmallPtrSet rounds the pre-allocation up to the nearest power of 2 however. But that's actually okay since, if the root ValueObject is a pointer, we generally also figure out the dynamic pointer value, which exists a good % of the time in C++, Swift & ObjC code. So that means right off the bat you get two managed ValueObjects for a lot of pointers.

More that that, you'd need to know what is the center of the lowest hump in the graph of "sizes of structs in all C/C++/ObjC code"... My feeling is that you generally end up with a bunch of small utility structs with a couple of elements (points and pairs are common), then after that the sizes expand rapidly - especially since the ClusterManager manages all the children/children of children, etc. So 16 seems high to me. Let's go with 4 which will give us scalars & pointers and 2/3 element structs with no allocation. After that I don't know enough to guess a better answer.

[labath]

lldb/include/lldb/Utility/SharedCluster.h

52–59

Ok, I see what you mean. That sounds reasonable, and I don't think the remove_const thingy would be necessary, as it should be possible add multiple const qualifiers in an idempotent manner.

Also agree, its not a big deal.

lldb/include/lldb/Utility/SharedCluster.h

 //===------------------SharedCluster.h --------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_UTILITY_SHAREDCLUSTER_H
 #define LLDB_UTILITY_SHAREDCLUSTER_H
 
 #include "lldb/Utility/LLDBAssert.h"
 #include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
 
 #include <memory>
 #include <mutex>
 
 namespace lldb_private {
 
 template <class T>
 class ClusterManager : public std::enable_shared_from_this<ClusterManager<T>> {
 public:
   static std::shared_ptr<ClusterManager> Create() {
     return std::shared_ptr<ClusterManager>(new ClusterManager());
   }
 
   ~ClusterManager() {
     for (T *obj : m_objects)
       delete obj;
   }
 
   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;
     }
     return {std::move(this_sp), desired_object};
   }
 
 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;
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_UTILITY_SHAREDCLUSTER_H