[tracing] Implement composable memory usage estimators.

base/trace_event/estimate_memory_usage_unittest.cc

Index: base/trace_event/estimate_memory_usage_unittest.cc
diff --git a/base/trace_event/estimate_memory_usage_unittest.cc b/base/trace_event/estimate_memory_usage_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..9390f41f106f2026df69151278c4996bd5aac48f
--- /dev/null
+++ b/base/trace_event/estimate_memory_usage_unittest.cc
@@ -0,0 +1,310 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/trace_event/estimate_memory_usage.h"
+
+#include <stdlib.h>
+
+#include "base/memory/ptr_util.h"
+#include "base/strings/string16.h"
+#include "base/test/scoped_memory_usage.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+// Estimation accuracy (as percentage of the real usage).
+#define ESTIMATION_ACCURACY 10
+
+#define BEGIN_MEMORY_USAGE_SCOPE \
+  test::ScopedMemoryUsage scoped_memory_usage
+
+#define EXPECT_MEMORY_USAGE(estimated_usage) \
+  { \
+    size_t real_usage = scoped_memory_usage.Usage(); \
+    bool estimation_is_accurate = IsAccurateEstimation( \
+        estimated_usage, \
+        real_usage, \
+        ESTIMATION_ACCURACY); \
+    EXPECT_TRUE(estimation_is_accurate) \
+        << estimated_usage << " is outside of " \
+        << ESTIMATION_ACCURACY << "% margin of " << real_usage; \
+  }
+
+namespace base {
+namespace trace_event {
+
+namespace {
+
+bool IsAccurateEstimation(size_t estimation, size_t reality, size_t margin) {
+  size_t low = reality - (reality * margin / 100);
+  size_t high = reality + (reality * margin / 100);
+  return estimation >= low && estimation <= high;
+}
+
+// Guaranteed (if at all possible) to hit short-string-optimization.
+std::string GetShortString() {
+  // All known SSO implementations can accommodate 6-char strings.
+  return std::string("small");
+}
+
+// Guaranteed to defeat short-string-optimization and allocate on the heap.
+std::string GetLongString(int seed = 0) {
+  // Definitely won't fit into std::string.
+  constexpr size_t kLongLength = sizeof(std::string) + 1;
+  std::string string(kLongLength, '?');
+  int random = seed;
+  for (auto& ch : string) {
+    random = random * 1103515245 + 12345;
+    ch = 'a' + abs(random % 26);
+  }
+  return string;
+}
+
+// Compilers will happily optimize allocation / deallocation
+// completely if you don't use your pointer. This "uses" a
+// pointer and prevents optimizations.
+template <class T>
+void UseAllocatedPointer(T* pointer) {
+  EXPECT_NE(1u, reinterpret_cast<uintptr_t>(pointer));
+}
+
+}  // namespace
+
+class EstimateMemoryUsageTest : public testing::Test {
+ public:
+  void SetUp() override { test::ScopedMemoryUsage::Initialize(); }
+};
+
+TEST_F(EstimateMemoryUsageTest, String) {
+  // Short
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    std::string string = GetShortString();
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(string));
+  }
+
+  // Long
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    std::string string = GetLongString();
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(string));
+  }
+
+  // Capacity
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    std::string string;
+    string.reserve(777);
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(string));
+  }
+}
+
+TEST_F(EstimateMemoryUsageTest, String16) {
+  auto copy16 = [](const std::string& source) -> string16 {
+    string16 copy(source.size(), '?');
+    std::copy(source.begin(), source.end(), copy.begin());
+    return copy;
+  };
+
+  // Short
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    string16 string = copy16(GetShortString());
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(string));
+  }
+
+  // Long
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    string16 string = copy16(GetLongString());
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(string));
+  }
+
+  // Capacity
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    string16 string;
+    string.reserve(777);
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(string));
+  }
+}
+
+TEST_F(EstimateMemoryUsageTest, Arrays) {
+  // std::array
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    std::array<std::string, 10> array{{GetLongString()}};
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(array));
+  }
+
+  // T[N]
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    struct Item {
+      std::unique_ptr<std::string> data;
+
+      Item() : data(new std::string(GetLongString())) {}
+      size_t EstimateMemoryUsage() const {
+        using base::trace_event::EstimateMemoryUsage;
+        return EstimateMemoryUsage(data);
+      }
+    };
+    Item array[10];
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(array));
+  }
+
+  // C array
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    struct Item {
+      char payload[10];
+    };
+    Item* array = new Item[7];
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(array, 7));
+    UseAllocatedPointer(array);
+    delete[] array;
+  }
+}
+
+TEST_F(EstimateMemoryUsageTest, UniquePtr) {
+  // Empty
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    std::unique_ptr<std::string> ptr;
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(ptr));
+  }
+
+  // Not empty
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    std::unique_ptr<std::string> ptr(new std::string(GetLongString()));
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(ptr));
+  }
+
+  // With a pointer
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    std::unique_ptr<std::string*> ptr(new std::string*());
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(ptr));
+    UseAllocatedPointer(ptr.get());
+  }
+
+  // With an array
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    struct Item {
+      int payload[10];
+    };
+    std::unique_ptr<Item[]> ptr(new Item[7]);
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(ptr, 7));
+    UseAllocatedPointer(ptr.get());
+  }
+}
+
+TEST_F(EstimateMemoryUsageTest, Vector) {
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    std::vector<std::string> vector;
+    for (int i = 0; i != 1000; ++i) {
+      vector.push_back(GetLongString(i));
+    }
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(vector));
+  }
+
+  // Capacity
+  {
+    BEGIN_MEMORY_USAGE_SCOPE;
+    struct POD {
+      short data;
+    };
+    std::vector<POD> vector;
+    vector.reserve(1000);
+    EXPECT_MEMORY_USAGE(EstimateMemoryUsage(vector));
+  }
+}
+
+TEST_F(EstimateMemoryUsageTest, List) {
+  BEGIN_MEMORY_USAGE_SCOPE;
+  struct POD {
+    short data;
+  };
+  std::list<POD> list;
+  for (int i = 0; i != 1000; ++i) {
+    list.push_back(POD());
+  }
+  EXPECT_MEMORY_USAGE(EstimateMemoryUsage(list));
+}
+
+TEST_F(EstimateMemoryUsageTest, Set) {
+  BEGIN_MEMORY_USAGE_SCOPE;
+  std::set<std::pair<int, std::string>> set;
+  for (int i = 0; i != 1000; ++i) {
+    set.insert({i, GetLongString(i)});
+  }
+  EXPECT_MEMORY_USAGE(EstimateMemoryUsage(set));
+}
+
+TEST_F(EstimateMemoryUsageTest, MultiSet) {
+  BEGIN_MEMORY_USAGE_SCOPE;
+  std::multiset<bool> set;
+  for (int i = 0; i != 1000; ++i) {
+    set.insert((i & 1) != 0);
+  }
+  EXPECT_MEMORY_USAGE(EstimateMemoryUsage(set));
+}
+
+TEST_F(EstimateMemoryUsageTest, Map) {
+  BEGIN_MEMORY_USAGE_SCOPE;
+  std::map<std::string, int> map;
+  for (int i = 0; i != 1000; ++i) {
+    map.insert({GetLongString(i), i});
+  }
+  EXPECT_MEMORY_USAGE(EstimateMemoryUsage(map));
+}
+
+TEST_F(EstimateMemoryUsageTest, MultiMap) {
+  BEGIN_MEMORY_USAGE_SCOPE;
+  std::multimap<char, std::string> map;
+  for (int i = 0; i != 1000; ++i) {
+    map.insert({static_cast<char>(i), GetLongString(i)});
+  }
+  EXPECT_MEMORY_USAGE(EstimateMemoryUsage(map));
+}
+
+TEST_F(EstimateMemoryUsageTest, UnorderedSet) {
+  BEGIN_MEMORY_USAGE_SCOPE;
+  std::unordered_set<std::string> set;
+  for (int i = 0; i != 1000; ++i) {
+    set.insert(GetLongString(i));
+  }
+  EXPECT_MEMORY_USAGE(EstimateMemoryUsage(set));
+}
+
+TEST_F(EstimateMemoryUsageTest, UnorderedMultiSet) {
+  BEGIN_MEMORY_USAGE_SCOPE;
+  std::unordered_multiset<short> set;
+  for (int i = 0; i != 1000; ++i) {
+    set.insert(static_cast<short>(i));
+  }
+  EXPECT_MEMORY_USAGE(EstimateMemoryUsage(set));
+}
+
+TEST_F(EstimateMemoryUsageTest, UnorderedMap) {
+  BEGIN_MEMORY_USAGE_SCOPE;
+  std::unordered_map<std::string, void*> map;
+  for (int i = 0; i != 1000; ++i) {
+    map.insert({GetLongString(i), reinterpret_cast<void*>(i)});
+  }
+  EXPECT_MEMORY_USAGE(EstimateMemoryUsage(map));
+}
+
+TEST_F(EstimateMemoryUsageTest, UnorderedMultiMap) {
+  BEGIN_MEMORY_USAGE_SCOPE;
+  std::unordered_multimap<char, short> map;
+  for (int i = 0; i != 1000; ++i) {
+    map.insert({static_cast<char>(i), 777});
+  }
+  EXPECT_MEMORY_USAGE(EstimateMemoryUsage(map));
+}
+
+}  // namespace trace_event
+}  // namespace base