[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

22

(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)

24

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.

25

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

vs something like addUsage(size_t)

31

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);
}

31

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

28

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

28

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

22

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.

25

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.

31

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

[sammccall]

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

28

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

31

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

31

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/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include <cstddef>
+#include <vector>
+
+namespace clang {
+namespace clangd {
+
+/// A tree that can be used to represent memory usage of nested components while
+/// preserving the hierarchy.
+struct MemoryTree {
+public:
+  void addChild(llvm::StringRef Name, MemoryTree MT, bool IsDetail = false);
+  void addChild(llvm::StringRef Name, size_t Size);
+
+  /// Performs a pre-order traversal of the tree, while concatenating compenent
+  /// names with dots(".").
+  /// If CollapseDetails is set, accumulates the size of subtrees marked as
+  /// detail to root, and doesn't report any descendants.
+  void traverseTree(bool CollapseDetails,
+                    llvm::function_ref<void(size_t /*Size*/,
+                                            llvm::StringRef /*ComponentName*/)>
+                        CB,
+                    llvm::StringRef ComponentPrefix = "") const;
+
+private:
+  // Enables optional traversal of the tree by collapsing any descendants into
+  // this node.
+  bool IsDetail = false;
+  // A human-readable identifier for the component.
+  std::string Name;
+  // Bytes owned by this component specifically.
+  size_t Size = 0;
+  // Significant components nested under current one.
+  std::vector<MemoryTree> Children;
+};
+
+} // namespace clangd
+} // namespace clang
+
+#endif

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

+#include "support/MemoryTree.h"
+
+namespace clang {
+namespace clangd {
+
+void MemoryTree::addChild(llvm::StringRef Name, MemoryTree MT, bool IsDetail) {
+  MT.IsDetail = IsDetail;
+  MT.Name = Name.str();
+  Children.emplace_back(std::move(MT));
+}
+
+void MemoryTree::addChild(llvm::StringRef Name, size_t Size) {
+  Children.emplace_back();
+  Children.back().Name = Name.str();
+  Children.back().Size = Size;
+}
+
+void MemoryTree::traverseTree(
+    bool CollapseDetails, llvm::function_ref<void(size_t, llvm::StringRef)> CB,
+    llvm::StringRef ComponentPrefix) const {
+  std::string ComponentName = ComponentPrefix.str();
+  if (!ComponentName.empty())
+    ComponentName += '.';
+  ComponentName += Name;
+
+  if (CollapseDetails && IsDetail) {
+    size_t ChildrenSize = 0;
+    for (const auto &C : Children) {
+      C.traverseTree(CollapseDetails,
+                     [&ChildrenSize](size_t Size, llvm::StringRef) {
+                       ChildrenSize += Size;
+                     });
+    }
+    CB(Size + ChildrenSize, ComponentName);
+    return;
+  }
+
+  CB(Size, ComponentName);
+  for (const auto &C : Children)
+    C.traverseTree(CollapseDetails, CB, ComponentName);
+}
+
+} // 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 "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+using testing::ElementsAreArray;
+
+TEST(MemoryTree, Traversal) {
+  // *
+  // | - leaf
+  // | - child1
+  //   | - leaf
+  // | - child2 (detailed)
+  //   | - leaf
+  //   | - child
+  //     | - leaf
+  MemoryTree MT;
+  MT.addChild("leaf", 1);
+  {
+    MemoryTree Child1;
+    Child1.addChild("leaf", 1);
+    MT.addChild("child1", Child1);
+    {
+      MemoryTree Child2;
+      Child2.addChild("leaf", 1);
+      Child1.addChild("child", std::move(Child2));
+      MT.addChild("child2", std::move(Child1), true);
+    }
+  }
+
+  struct Component {
+    std::string Name;
+    size_t Size;
+    bool operator==(const Component &RHS) const {
+      return std::tie(Name, Size) == std::tie(RHS.Name, RHS.Size);
+    }
+  };
+  std::vector<Component> SeenComponents;
+  auto CB = [&SeenComponents](size_t Size, llvm::StringRef CompName) {
+    Component C;
+    C.Name = CompName.str();
+    C.Size = Size;
+    SeenComponents.emplace_back(std::move(C));
+  };
+
+  // Ensure sizes and component names are reported correctly.
+  Component ExpectedComponents[] = {
+      {"", 0},
+      {"leaf", 1},
+      {"child1", 0},
+      {"child1.leaf", 1},
+      {"child2", 0},
+      {"child2.leaf", 1},
+      {"child2.child", 0},
+      {"child2.child.leaf", 1},
+  };
+  MT.traverseTree(false, CB);
+  EXPECT_THAT(SeenComponents, ElementsAreArray(ExpectedComponents));
+  SeenComponents.clear();
+
+  // Ensure detailed sub-trees are collapsed when requested.
+  Component ExpectedComponentsHidden[] = {
+      {"", 0}, {"leaf", 1}, {"child1", 0}, {"child1.leaf", 1}, {"child2", 2},
+  };
+  MT.traverseTree(true, CB);
+  EXPECT_THAT(SeenComponents, ElementsAreArray(ExpectedComponentsHidden));
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang