[clangd] Introduce MemoryTrees

[kadircet]

Summary

A structure that can be used to represent memory usage of a nested
set of systems.

[sammccall]

clang-tools-extra/clangd/support/MemoryTree.h

23

(I'm wondering if there are other resources we'd like to count, like disk size or so, but probably YAGNI and a concrete name is nice)

25

The concept of "detail" should be introduced somewhere, or just be something more concrete
(like IsFilename)

There's a few things about filenames that make erasing them sensible:

• they have uniform semantics - we don't really know the difference between them
• can be very many of them so the result is inherently hard to interpret
• can be many/large so we don't want to copy them

Thinking about how to generalize these - I think the name detail is OK (if you want a general name) but we should mention some of it.

26

do we support nodes with both usage and children?
This API makes such a construction awkward.

vs something like addUsage(size_t)

32

In earlier discussions we talked about avoiding the cost of *assembling* the detailed tree, not just summarizing it at output time.

This requires CollapseDetails to be passed into the profiling function, which in turn suggests making it part of a tree and passing a reference to the tree in. e.g. an API like

class MemoryTree {
  MemoryTree(bool Detailed);
  MemoryTree* addChild(StringLiteral); // no copy
  MemoryTree* addDetail(StringRef); // returns `this` unless detailed
  void addUsage(size_t);
}

32

It's hard to evaluate a tree-traversal API without its usages... how will this be used?

[sammccall]

clang-tools-extra/clangd/support/MemoryTree.cpp

29

Here the detailed nodes are entirely collapsed. This isn't quite as powerful as collapsing the detail *edges* only, which is worth considering.

e.g. consider TUScheduler. The natural accounting of resources is (IMO)

clangd.TUScheduler.<filename>.AST
clangd.TUScheduler.<filename>.Preamble.InMemory
clangd.TUScheduler.<filename>.Preamble.Inputs

or something like that.

Instead of aggregating to clangd.TUScheduler only, collapsing the <filename> edges mean you get clangd.TUScheduler.AST etc.

[kadircet]

clang-tools-extra/clangd/support/MemoryTree.cpp

29

yes this was an option i hadn't considered. my only hesitation is this likely implies different paths with the same name. current api also doesn't protect against it, but they are a lot less likely as we collapse whole subtrees.

I believe deleting the edge should also imply aggregating all the paths with the same name, e.g.
a.b.<deleted-1>.c, 5 and a.b.<deleted-2>.c, 8 should end up being a.b.c,13. WDYT?

clang-tools-extra/clangd/support/MemoryTree.h

23

i went with this one as i didn't want to call it Tree and couldn't find a nice generic name, maybe something around NamedBytesTree.

26

yes we do, I haven't added any because it wasn't needed and internal collapsing mechanism could update the size. i'll add an explicit addUsage too.

32

you can find some in https://reviews.llvm.org/D88414

[sammccall]

clang-tools-extra/clangd/support/MemoryTree.cpp

29

Agree with your desired behavior.

If you're willing to make collapsing a property of the tree rather than the query, you avoid this problem, because you collapse up-front and make addChild idempotent:

class Tree {
  BumpPtrAllocator *DetailAllocator; // Null if no detail
  StringMap<Tree> Children;
  size_t Self = 0;

  Tree* childImpl(StringRef Name) {
    return &*Children.try_emplace(Name, DetailAllocator).first;
  }

public:  
  Tree(BumpPtrAllocator *);
  Tree* child(StringLiteral Name) { return childImpl(Name); }
  Tree* detail(StringRef Name) {
    return DetailAllocator ? child(DetailAllocator->copy(Name)) : this;
  }
  void add(unsigned Size) { Self += Size; }
};

[kadircet]

• Address comments

[sammccall]

Looks good - some concerns that the traversal isn't flexible enough but we can address that later once it's used.

clang-tools-extra/clangd/support/MemoryTree.cpp

11

If you're only going to pass one size, I'd think total (rather than self) is the most meaningful.
This is easier if you do postorder of course...

12

if you pass ComponentName as a StringRef you can avoid lots of allocations by using the same underlying string (which will grow and shrink, but not reallocate much).
You'll need a recursion helper with a different signature though.

clang-tools-extra/clangd/support/MemoryTree.h

32

I guess you mean D88417?

This works well when exporting all nodes somewhere keyed by dotted path, but it's pretty awkward+inefficient if you want to - totally hypothetical example here - dump the memory tree as a JSON structure over RPC.

So I think we need a more flexible API, at which point... maybe we should punt, expose const DenseMap<StringRef, MemoryTree> &children() const, and move the traverse implementation to the metrics exporter?

34

nit: I'd call this parameter DetailAlloc to hint at what's stored there

42

nit: Name.copy(*Alloc) is a little more direct

50

nit: need to be explicit whether this is self or subtree (or could pass both)

[sammccall]

clang-tools-extra/clangd/support/MemoryTree.h

36

Maybe mention that child pointers are invalidated by future addChild/addDetail

37

actually, why do these return pointers rather than references?

[sammccall]

clang-tools-extra/clangd/support/MemoryTree.h

37

reading call sites, child() might be both more fluent and more accurate than addChild - we're not calling it for the side effect and there may or may not be one.

50

I think it'd be worth having size_t total() with a comment that it traverses the tree.

We have places where we only want this info (e.g. log messages) and it's probably nice in unit tests too.

[kadircet]

• Rename add{Detail,Child} -> {detail,child}
• Get rid of traverseTree API and only expose total
• Add a children() getter

clang-tools-extra/clangd/support/MemoryTree.h

32

SGTM.

37

actually, why do these return pointers rather than references?

It is to make usage with auto safer, as it won't capture ref by default and make a copy. e.g. auto child = MT.child(); child.addusage(1) won't work as expected.

I suppose we can make the object non-copyable and prevent such misuse.

42

ah thanks, didn't know that!

[sammccall]

LGTM, thanks!

clang-tools-extra/clangd/support/MemoryTree.h

37

Oh, right - yes ref but noncopyable seems even better to me

58

oops, we should probably also expose self?

[kadircet]

• Add self

[kadircet]

• Make MemoryTree move-only and return refs instead of pointers on child and detail.

[sammccall]

Still LGTM, commit it already :-D

clang-tools-extra/clangd/support/MemoryTree.cpp

27

nit: could inline this consistent with addUsage

[kadircet]

Still LGTM, commit it already :-D

Haha, waiting for dependents to be stamped as well :D

[kadircet]

• Inline MemoryTree::self

clang-tools-extra/clangd/support/CMakeLists.txt

 endif()
 
 include_directories(..)
 add_clang_library(clangdSupport
   Cancellation.cpp
   Context.cpp
   Logger.cpp
   Markup.cpp
+  MemoryTree.cpp
   Shutdown.cpp
   Threading.cpp
   ThreadsafeFS.cpp
   Trace.cpp
 
   LINK_LIBS
   ${LLVM_PTHREAD_LIB}
   ${CLANGD_ATOMIC_LIB}
   )

clang-tools-extra/clangd/support/MemoryTree.h

+//===--- MemoryTree.h - A special tree for components and sizes -*- 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 LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_MEMORYTREE_H_
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_MEMORYTREE_H_
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/StringSaver.h"
+#include <cstddef>
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace clangd {
+
+/// A tree that can be used to represent memory usage of nested components while
+/// preserving the hierarchy.
+/// Edges have associated names. An edge that might not be interesting to all
+/// traversers or costly to copy (e.g. file names) can be marked as "detail".
+/// Tree construction allows chosing between a detailed and brief mode, in brief
+/// mode all "detail" edges are ignored and tree is constructed without any
+/// string copies.
+struct MemoryTree {
+public:
+  /// If Alloc is nullptr, tree is in brief mode and will ignore detail edges.
+  MemoryTree(llvm::BumpPtrAllocator *DetailAlloc = nullptr)
+      : DetailAlloc(DetailAlloc) {}
+
+  /// No copy of the \p Name.
+  /// Note that returned pointers are invalidated with subsequent calls to
+  /// child/detail.
+  MemoryTree &child(llvm::StringLiteral Name) { return createChild(Name); }
+
+  MemoryTree(const MemoryTree &) = delete;
+  MemoryTree &operator=(const MemoryTree &) = delete;
+
+  MemoryTree(MemoryTree &&) = default;
+  MemoryTree &operator=(MemoryTree &&) = default;
+
+  /// Makes a copy of the \p Name in detailed mode, returns current node
+  /// otherwise.
+  /// Note that returned pointers are invalidated with subsequent calls to
+  /// child/detail.
+  MemoryTree &detail(llvm::StringRef Name) {
+    return DetailAlloc ? createChild(Name.copy(*DetailAlloc)) : *this;
+  }
+
+  /// Increases size of current node by \p Increment.
+  void addUsage(size_t Increment) { Size += Increment; }
+
+  /// Returns edges to direct children of this node.
+  const llvm::DenseMap<llvm::StringRef, MemoryTree> &children() const;
+
+  /// Returns total number of bytes used by this sub-tree. Performs a traversal.
+  size_t total() const;
+
+  /// Returns total number of bytes used by this node only.
+  size_t self() const { return Size; }
+
+private:
+  /// Adds a child with an edge labeled as \p Name. Multiple calls to this
+  /// function returns the same node.
+  MemoryTree &createChild(llvm::StringRef Name);
+
+  /// Allocator to use for detailed edge names.
+  llvm::BumpPtrAllocator *DetailAlloc = nullptr;
+
+  /// Bytes owned by this component specifically.
+  size_t Size = 0;
+
+  /// Edges from current node to its children. Keys are the labels for edges.
+  llvm::DenseMap<llvm::StringRef, MemoryTree> Children;
+};
+
+} // namespace clangd
+} // namespace clang
+
+#endif

clang-tools-extra/clangd/support/MemoryTree.cpp

+#include "support/MemoryTree.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include <cstddef>
+
+namespace clang {
+namespace clangd {
+
+MemoryTree &MemoryTree::createChild(llvm::StringRef Name) {
+  auto &Child = Children.try_emplace(Name, DetailAlloc).first->getSecond();
+  return Child;
+}
+
+const llvm::DenseMap<llvm::StringRef, MemoryTree> &
+MemoryTree::children() const {
+  return Children;
+}
+
+size_t MemoryTree::total() const {
+  size_t Total = Size;
+  for (const auto &Entry : Children)
+    Total += Entry.getSecond().total();
+  return Total;
+}
+} // namespace clangd
+} // namespace clang

clang-tools-extra/clangd/unittests/CMakeLists.txt

add_unittest(ClangdUnitTests ClangdTests
   URITests.cpp
   XRefsTests.cpp
   ${CMAKE_CURRENT_BINARY_DIR}/DecisionForestRuntimeTest.cpp
 
   support/CancellationTests.cpp
   support/ContextTests.cpp
   support/FunctionTests.cpp
   support/MarkupTests.cpp
+  support/MemoryTreeTests.cpp
   support/ThreadingTests.cpp
   support/TestTracer.cpp
   support/TraceTests.cpp
 
   ${REMOTE_TEST_SOURCES}
 
   $<TARGET_OBJECTS:obj.clangDaemonTweaks>
   )

clang-tools-extra/clangd/unittests/support/MemoryTreeTests.cpp

+//===-- MemoryTreeTests.cpp -------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "support/MemoryTree.h"
+#include "llvm/Support/Allocator.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <ostream>
+
+namespace clang {
+namespace clangd {
+namespace {
+using testing::Contains;
+using testing::IsEmpty;
+using testing::UnorderedElementsAre;
+
+MATCHER_P2(WithNameAndSize, Name, Size, "") {
+  return arg.first == Name &&
+         arg.getSecond().total() == static_cast<size_t>(Size);
+}
+
+TEST(MemoryTree, Basics) {
+  MemoryTree MT;
+  EXPECT_EQ(MT.total(), 0U);
+  EXPECT_THAT(MT.children(), IsEmpty());
+
+  MT.addUsage(42);
+  EXPECT_EQ(MT.total(), 42U);
+  EXPECT_THAT(MT.children(), IsEmpty());
+
+  MT.child("leaf").addUsage(1);
+  EXPECT_EQ(MT.total(), 43U);
+  EXPECT_THAT(MT.children(), UnorderedElementsAre(WithNameAndSize("leaf", 1)));
+
+  // child should be idempotent.
+  MT.child("leaf").addUsage(1);
+  EXPECT_EQ(MT.total(), 44U);
+  EXPECT_THAT(MT.children(), UnorderedElementsAre(WithNameAndSize("leaf", 2)));
+}
+
+TEST(MemoryTree, DetailedNodesWithoutDetails) {
+  MemoryTree MT;
+  MT.detail("should_be_ignored").addUsage(2);
+  EXPECT_THAT(MT.children(), IsEmpty());
+  EXPECT_EQ(MT.total(), 2U);
+
+  // Make sure children from details are merged.
+  MT.detail("first_detail").child("leaf").addUsage(1);
+  MT.detail("second_detail").child("leaf").addUsage(1);
+  EXPECT_THAT(MT.children(), Contains(WithNameAndSize("leaf", 2)));
+}
+
+TEST(MemoryTree, DetailedNodesWithDetails) {
+  llvm::BumpPtrAllocator Alloc;
+  MemoryTree MT(&Alloc);
+
+  {
+    auto &Detail = MT.detail("first_detail");
+    Detail.child("leaf").addUsage(1);
+    EXPECT_THAT(MT.children(), Contains(WithNameAndSize("first_detail", 1)));
+    EXPECT_THAT(Detail.children(), Contains(WithNameAndSize("leaf", 1)));
+  }
+
+  {
+    auto &Detail = MT.detail("second_detail");
+    Detail.child("leaf").addUsage(1);
+    EXPECT_THAT(MT.children(), Contains(WithNameAndSize("second_detail", 1)));
+    EXPECT_THAT(Detail.children(), Contains(WithNameAndSize("leaf", 1)));
+  }
+}
+} // namespace
+} // namespace clangd
+} // namespace clang