[tracing] Implement composable memory usage estimators.

base/trace_event/estimate_memory_usage.h

+// 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.
+
+#ifndef BASE_TRACE_EVENT_ESTIMATE_MEMORY_USAGE_H_
+#define BASE_TRACE_EVENT_ESTIMATE_MEMORY_USAGE_H_
+
+#include <array>
+#include <list>
+#include <map>
+#include <memory>
+#include <set>
+#include <string>
+#include <type_traits>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+#include "base/template_util.h"
+
+// Composable memory usage estimators.
+//
+// This file defines set of EstimateMemoryUsage(object) functions that return
+// approximate memory usage of their argument.
+//
+// The ultimate goal is to make memory usage estimation for a class simply a
+// matter of aggregating EstimateMemoryUsage() results over all fields.
+//
+// That is achieved via composability: if EstimateMemoryUsage() is defined
+// for T then EstimateMemoryUsage() is also defined for any combination of
+// containers holding T (e.g. std::map<int, std::vector<T>>).
+//
+// There are two ways of defining EstimateMemoryUsage() for a type:
+//
+// 1. As a global function 'size_t EstimateMemoryUsage(T)' in type's namespace
+//    (or as a last resort, in base::trace_event namespace).
+//
+// 2. As 'size_t T::EstimateMemoryUsage() const' method. In this case global
+//    EstimateMemoryUsage(T) function in base::trace_event namespace is
+//    provided automatically.
+//
+// Here is an example implementation:
+//
+// size_t foo::bar::MyClass::EstimateMemoryUsage() const {
+//   using base::trace_event::EstimateMemoryUsage;
+//   return EstimateMemoryUsage(name_) +
+//          EstimateMemoryUsage(id_) +
+//          EstimateMemoryUsage(items_);
+// }
+//
+// Two things to note:
+//
+// 1. It starts with 'using' declaration. This makes everything defined in

[Primiano Tucci (use gerrit), 2016/11/08 14:09:16]

?? Why this doesn't work if you just say base::trace_event::EstimateMemoryUsage?
You are not importing a namespace 

[DmitrySkiba, 2016/11/08 17:47:14]

It won't work if EstimateMemoryUsage() for T is defined as a free function in
T's namespace. In that case it should be just EstimateMemoryUsage() so that ADL
finds correct one.

And I really don't want callers to think about where and how EMU is defined. You
do using, and then just call EstimateMemoryUsage() on all eligible members.

[dcheng, 2016/11/08 19:31:48]

FWIW, if we can figure out some way to avoid 'using', I think that'd be better.
std::swap is supposed to be used the same way, but the 'using' statement is
often just omitted completely.

(ParamTraits for IPC get around this by requiring everyone to specialize
ParamTraits in the IPC namespace. Maybe we could just add a namespace
requirement on the traits class here; that doesn't seem unreasonable to me,
since the EMU function itself is in base...)

+//    this file (i.e. all EstimateMemoryUsage variants) available for compiler
+//    to choose from.
+//
+// 2. It just calls EstimateMemoryUsage() on all (suitable) members.
+//    The pattern is simple: first call EstimateMemoryUsage() on all members,
+//    then fix compilation errors that are caused by types not implementing
+//    EstimateMemoryUsage().
+
+namespace base {
+namespace trace_event {
+
+// Declarations
+
+// If T declares 'EstimateMemoryUsage() const' member function, then
+// global function EstimateMemoryUsage(T) is available, and just calls
+// the member function.
+template <class T>
+auto EstimateMemoryUsage(const T& object)

[Primiano Tucci (use gerrit), 2016/11/08 14:09:16]

out of curiosity isn't this always size_t? Why do you need a trailing return
type here?
Or is it forced because of the lambda?

[DmitrySkiba, 2016/11/08 17:47:14]

The trick here is that if T doesn't have EMU member function, this global
function is not considered. I.e. decltype(object.EstimateMemoryUsage()) silently
fails and removes this function from candidate list for T. Function can be
written without trailing return, with std::declval, but it'll be uglier.

+    -> decltype(object.EstimateMemoryUsage());
+
+// String
+
+template <class C, class T, class A>
+size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string);
+
+// Arrays
+
+template <class T, size_t N>
+size_t EstimateMemoryUsage(const std::array<T, N>& array);
+
+template <class T, size_t N>
+size_t EstimateMemoryUsage(T (&array)[N]);
+
+template <class T>
+size_t EstimateMemoryUsage(const T* array, size_t array_length);
+
+// std::unique_ptr
+
+template <class T>
+size_t EstimateMemoryUsage(const std::unique_ptr<T>& ptr);

[dcheng, 2016/11/08 19:31:48]

Note that unique_ptr has a custom delete parameter.

+
+template <class T>
+size_t EstimateMemoryUsage(const std::unique_ptr<T[]>& array,
+                           size_t array_length);
+
+// Containers
+
+template <class F, class S>
+size_t EstimateMemoryUsage(const std::pair<F, S>& pair);
+
+template <class T, class A>
+size_t EstimateMemoryUsage(const std::vector<T, A>& vector);
+
+template <class T, class A>
+size_t EstimateMemoryUsage(const std::list<T, A>& list);
+
+template <class T, class C, class A>
+size_t EstimateMemoryUsage(const std::set<T, C, A>& set);
+
+template <class T, class C, class A>
+size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set);
+
+template <class K, class V, class C, class A>
+size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map);
+
+template <class K, class V, class C, class A>
+size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map);
+
+template <class T, class H, class KE, class A>
+size_t EstimateMemoryUsage(const std::unordered_set<T, H, KE, A>& set);
+
+template <class T, class H, class KE, class A>
+size_t EstimateMemoryUsage(const std::unordered_multiset<T, H, KE, A>& set);
+
+template <class K, class V, class H, class KE, class A>
+size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map);
+
+template <class K, class V, class H, class KE, class A>
+size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map);
+
+// TODO(dskiba):
+//   std::forward_list
+//   std::deque
+//   std::queue
+//   std::stack
+//   std::queue
+//   std::priority_queue
+
+// Definitions
+
+namespace internal {
+
+// HasEMU<T>::value is true iff EstimateMemoryUsage(T) is available.
+// (This is the default version, which is false.)
+template <class T, class X = void>
+struct HasEMU : std::false_type {};
+
+// This HasEMU specialization is only picked up if there exists function
+// EstimateMemoryUsage(const T&) that returns size_t. Simpler ways to
+// achieve this don't work on MSVC.
+template <class T>
+struct HasEMU<
+    T,
+    typename std::enable_if<std::is_same<
+        size_t,
+        decltype(EstimateMemoryUsage(std::declval<const T&>()))>::value>::type>
+    : std::true_type {};
+
+// EMUCaller<T> does three things:
+// 1. Defines Call() method that calls EstimateMemoryUsage(T) if it's
+//    available.
+// 2. If EstimateMemoryUsage(T) is not available, but T has trivial dtor
+//    (i.e. it's POD, integer, pointer, enum, etc.) then it defines Call()
+//    method that returns 0. This is useful for containers, which allocate
+//    memory regardless of T (also for cases like std::map<int, MyClass>).
+// 3. Finally, if EstimateMemoryUsage(T) is not available, then it triggers
+//    a static_assert with a helpful message. That cuts numbers of errors
+//    considerably - if you just call EstimateMemoryUsage(T) but it's not
+//    available for T, then compiler will helpfully list *all* possible
+//    variants of it, with an explanation for each.
+template <class T, class X = void>
+struct EMUCaller {
+  // std::is_same<> below is only to make static_assert depend on T
+  // to force compilers to include type of T in the error message.

[dcheng, 2016/11/08 19:31:48]

clang and msvc will both tell you which template instantiation caused this to
fail, which includes all the template params.

However, we can't just static_assert(false, ...) here: it's important to make
sure the static assert is dependent on a template type:
http://stackoverflow.com/questions/14637356/static-assert-fails-compilation-e...

I'd document this latter reason probably, since it's somewhat subtle.

+  static_assert(std::is_same<T, X>::value,
+                "Neither global function 'size_t EstimateMemoryUsage(T)' "
+                "nor member function 'size_t T::EstimateMemoryUsage() const' "
+                "is defined for the type.");
+
+  static size_t Call(const T&) { return 0; }
+};
+
+template <class T>
+struct EMUCaller<T, typename std::enable_if<HasEMU<T>::value>::type> {
+  static size_t Call(const T& value) { return EstimateMemoryUsage(value); }
+};
+
+template <class T>
+struct EMUCaller<
+    T,
+    typename std::enable_if<!HasEMU<T>::value &&
+                            is_trivially_destructible<T>::value>::type> {
+  static size_t Call(const T& value) { return 0; }
+};
+
+}  // namespace internal
+
+// Proxy that deducts T and calls EMUCaller<T>.
+// To be used by EstimateMemoryUsage() implementations for containers.
+template <class T>
+size_t EstimateItemMemoryUsage(const T& value) {
+  return internal::EMUCaller<T>::Call(value);
+}
+
+template <class I>
+size_t EstimateIterableMemoryUsage(const I& iterable) {
+  size_t memory_usage = 0;
+  for (const auto& item : iterable) {
+    memory_usage += EstimateItemMemoryUsage(item);
+  }
+  return memory_usage;
+}
+
+// Global EstimateMemoryUsage(T) that just calls T::EstimateMemoryUsage().
+template <class T>
+auto EstimateMemoryUsage(const T& object)
+    -> decltype(object.EstimateMemoryUsage()) {
+  static_assert(
+      std::is_same<decltype(object.EstimateMemoryUsage()), size_t>::value,
+      "'T::EstimateMemoryUsage() const' must return size_t.");
+  return object.EstimateMemoryUsage();
+}
+
+// String
+
+template <class C, class T, class A>
+size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string) {
+  using string_type = std::basic_string<C, T, A>;
+  using value_type = typename string_type::value_type;
+  // C++11 doesn't leave much room for implementors - std::string can
+  // use short string optimization, but that's about it. We detect SSO
+  // by checking that c_str() points inside |string|.
+  const char* cstr = reinterpret_cast<const char*>(string.c_str());
+  const char* inline_cstr = reinterpret_cast<const char*>(&string);
+  if (cstr >= inline_cstr && cstr < inline_cstr + sizeof(string)) {
+    // SSO string
+    return 0;
+  }
+  return (string.capacity() + 1) * sizeof(value_type);
+}
+
+// Arrays
+
+template <class T, size_t N>
+size_t EstimateMemoryUsage(const std::array<T, N>& array) {
+  return EstimateIterableMemoryUsage(array);
+}
+
+template <class T, size_t N>
+size_t EstimateMemoryUsage(T (&array)[N]) {
+  return EstimateIterableMemoryUsage(array);
+}
+
+template <class T>
+size_t EstimateMemoryUsage(const T* array, size_t array_length) {
+  size_t memory_usage = sizeof(T) * array_length;
+  for (size_t i = 0; i != array_length; ++i) {
+    memory_usage += EstimateItemMemoryUsage(array[i]);
+  }
+  return memory_usage;
+}
+
+// std::unique_ptr
+
+template <class T>
+size_t EstimateMemoryUsage(const std::unique_ptr<T>& ptr) {
+  return ptr ? (sizeof(T) + EstimateItemMemoryUsage(*ptr)) : 0;
+}
+
+template <class T>
+size_t EstimateMemoryUsage(const std::unique_ptr<T[]>& array,
+                           size_t array_length) {
+  return EstimateMemoryUsage(array.get(), array_length);
+}
+
+// std::pair
+
+template <class F, class S>
+size_t EstimateMemoryUsage(const std::pair<F, S>& pair) {
+  return EstimateItemMemoryUsage(pair.first) +
+         EstimateItemMemoryUsage(pair.second);
+}
+
+// std::vector
+
+template <class T, class A>
+size_t EstimateMemoryUsage(const std::vector<T, A>& vector) {
+  return sizeof(T) * vector.capacity() + EstimateIterableMemoryUsage(vector);
+}
+
+// std::list
+
+template <class T, class A>
+size_t EstimateMemoryUsage(const std::list<T, A>& list) {
+  using value_type = typename std::list<T, A>::value_type;
+  struct Node {
+    Node* prev;
+    Node* next;
+    value_type value;
+  };
+  return sizeof(Node) * list.size() +
+         EstimateIterableMemoryUsage(list);
+}
+
+// Tree containers
+
+template <class V>
+size_t EstimateTreeMemoryUsage(size_t size) {
+  // Tree containers are modeled after libc++
+  // (__tree_node from include/__tree)
+  struct Node {
+    Node* left;
+    Node* right;
+    Node* parent;
+    bool is_black;
+    V value;
+  };
+  return sizeof(Node) * size;
+}
+
+template <class T, class C, class A>
+size_t EstimateMemoryUsage(const std::set<T, C, A>& set) {
+  using value_type = typename std::set<T, C, A>::value_type;
+  return EstimateTreeMemoryUsage<value_type>(set.size()) +
+         EstimateIterableMemoryUsage(set);
+}
+
+template <class T, class C, class A>
+size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set) {
+  using value_type = typename std::multiset<T, C, A>::value_type;
+  return EstimateTreeMemoryUsage<value_type>(set.size()) +
+         EstimateIterableMemoryUsage(set);
+}
+
+template <class K, class V, class C, class A>
+size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map) {
+  using value_type = typename std::map<K, V, C, A>::value_type;
+  return EstimateTreeMemoryUsage<value_type>(map.size()) +
+         EstimateIterableMemoryUsage(map);
+}
+
+template <class K, class V, class C, class A>
+size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map) {
+  using value_type = typename std::multimap<K, V, C, A>::value_type;
+  return EstimateTreeMemoryUsage<value_type>(map.size()) +
+         EstimateIterableMemoryUsage(map);
+}
+
+// HashMap containers
+
+template <class V>
+size_t EstimateHashMapMemoryUsage(size_t bucket_count, size_t size) {
+  // Hashtable containers are modeled after libc++
+  // (__hash_node from include/__hash_table)
+  struct Node {
+    void* next;
+    size_t hash;
+    V value;
+  };
+  using Bucket = void*;
+  return sizeof(Bucket) * bucket_count + sizeof(Node) * size;
+}
+
+template <class K, class H, class KE, class A>
+size_t EstimateMemoryUsage(const std::unordered_set<K, H, KE, A>& set) {
+  using value_type = typename std::unordered_set<K, H, KE, A>::value_type;
+  return EstimateHashMapMemoryUsage<value_type>(set.bucket_count(),
+                                                set.size()) +
+         EstimateIterableMemoryUsage(set);
+}
+
+template <class K, class H, class KE, class A>
+size_t EstimateMemoryUsage(const std::unordered_multiset<K, H, KE, A>& set) {
+  using value_type = typename std::unordered_multiset<K, H, KE, A>::value_type;
+  return EstimateHashMapMemoryUsage<value_type>(set.bucket_count(),
+                                                set.size()) +
+         EstimateIterableMemoryUsage(set);
+}
+
+template <class K, class V, class H, class KE, class A>
+size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map) {
+  using value_type = typename std::unordered_map<K, V, H, KE, A>::value_type;
+  return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(),
+                                                map.size()) +
+         EstimateIterableMemoryUsage(map);
+}
+
+template <class K, class V, class H, class KE, class A>
+size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map) {
+  using value_type =
+      typename std::unordered_multimap<K, V, H, KE, A>::value_type;
+  return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(),
+                                                map.size()) +
+         EstimateIterableMemoryUsage(map);
+}
+
+}  // namespace trace_event
+}  // namespace base
+
+#endif  // BASE_TRACE_EVENT_ESTIMATE_MEMORY_USAGE_H_