Bug 1148642 - Save some memory in HeapSnapshot instances by using a HashSet with a NodeId lookup, instead of a HashMap; r=jimb
authorNick Fitzgerald <fitzgen@gmail.com>
Wed, 10 Jun 2015 13:37:12 -0700
changeset 248158 6c24d7e60eec52ed6ca0d81407294e3fecaab106
parent 248157 858d09af88bc4b9c3d6538c4fa525b11a8934e36
child 248159 c3840ca0384ff1acbc3d4a1c255c634b3d7b953a
push id28893
push userkwierso@gmail.com
push dateFri, 12 Jun 2015 00:02:58 +0000
treeherderautoland@8cf9d3e497f9 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjimb
bugs1148642
milestone41.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1148642 - Save some memory in HeapSnapshot instances by using a HashSet with a NodeId lookup, instead of a HashMap; r=jimb
toolkit/devtools/server/DeserializedNode.cpp
toolkit/devtools/server/DeserializedNode.h
toolkit/devtools/server/HeapSnapshot.cpp
toolkit/devtools/server/HeapSnapshot.h
toolkit/devtools/server/tests/gtest/DeserializedNodeUbiNodes.cpp
--- a/toolkit/devtools/server/DeserializedNode.cpp
+++ b/toolkit/devtools/server/DeserializedNode.cpp
@@ -117,23 +117,30 @@ DeserializedNode::init(const protobuf::N
 DeserializedNode::DeserializedNode(NodeId id, const char16_t* typeName, uint64_t size)
   : id(id)
   , typeName(typeName)
   , size(size)
   , edges()
   , owner(nullptr)
 { }
 
-DeserializedNode&
+JS::ubi::Node
 DeserializedNode::getEdgeReferent(const DeserializedEdge& edge)
 {
   assertInitialized();
   auto ptr = owner->nodes.lookup(edge.referent);
   MOZ_ASSERT(ptr);
-  return ptr->value();
+
+  // `HashSets` only provide const access to their values, because mutating a
+  // value might change its hash, rendering it unfindable in the set.
+  // Unfortunately, the `ubi::Node` constructor requires a non-const pointer to
+  // its referent.  However, the only aspect of a `DeserializedNode` we hash on
+  // is its id, which can't be changed via `ubi::Node`, so this cast can't cause
+  // the trouble `HashSet` is concerned a non-const reference would cause.
+  return JS::ubi::Node(const_cast<DeserializedNode*>(&*ptr));
 }
 
 } // namespace devtools
 } // namespace mozilla
 
 namespace JS {
 namespace ubi {
 
@@ -182,18 +189,18 @@ public:
     {
       char16_t* name = nullptr;
       if (edgep->name) {
         name = NS_strdup(edgep->name);
         if (!name)
           return false;
       }
 
-      DeserializedNode& referent = node.getEdgeReferent(*edgep);
-      edges.infallibleAppend(mozilla::Move(SimpleEdge(name, Node(&referent))));
+      auto referent = node.getEdgeReferent(*edgep);
+      edges.infallibleAppend(mozilla::Move(SimpleEdge(name, referent)));
     }
 
     settle();
     return true;
   }
 
   void popFront() override
   {
--- a/toolkit/devtools/server/DeserializedNode.h
+++ b/toolkit/devtools/server/DeserializedNode.h
@@ -79,32 +79,53 @@ struct DeserializedNode {
   DeserializedNode& operator=(DeserializedNode&& rhs);
 
   // Initialize a new `DeserializedNode` from the given `protobuf::Node`
   // message.
   bool init(const protobuf::Node& node, HeapSnapshot& owner);
 
   // Get a borrowed reference to the given edge's referent. This method is
   // virtual to provide a hook for gmock and gtest.
-  virtual DeserializedNode& getEdgeReferent(const DeserializedEdge& edge);
+  virtual JS::ubi::Node getEdgeReferent(const DeserializedEdge& edge);
+
+  struct HashPolicy;
 
 protected:
   // This is only for use with `MockDeserializedNode` in testing.
   DeserializedNode(NodeId id, const char16_t* typeName, uint64_t size);
 
 private:
   void assertInitialized() const {
     MOZ_ASSERT(owner);
     MOZ_ASSERT(typeName);
   }
 
   DeserializedNode(const DeserializedNode&) = delete;
   DeserializedNode& operator=(const DeserializedNode&) = delete;
 };
 
+struct DeserializedNode::HashPolicy
+{
+  using Lookup = NodeId;
+
+  static js::HashNumber hash(const Lookup& lookup) {
+    // NodeIds are always 64 bits, but they are derived from the original
+    // referents' addresses, which could have been either 32 or 64 bits long.
+    // As such, a NodeId has little entropy in its bottom three bits, and may or
+    // may not have entropy in its upper 32 bits. This hash should manage both
+    // cases well.
+    uint64_t id = lookup >> 3;
+    return js::HashNumber((id >> 32) ^ id);
+  }
+
+  static bool match(const DeserializedNode& existing, const Lookup& lookup) {
+    return existing.id == lookup;
+  }
+};
+
 } // namespace devtools
 } // namespace mozilla
 
 namespace JS {
 namespace ubi {
 
 using mozilla::devtools::DeserializedNode;
 using mozilla::UniquePtr;
--- a/toolkit/devtools/server/HeapSnapshot.cpp
+++ b/toolkit/devtools/server/HeapSnapshot.cpp
@@ -94,17 +94,17 @@ parseMessage(ZeroCopyInputStream& stream
   codedStream.PopLimit(limit);
   return true;
 }
 
 bool
 HeapSnapshot::saveNode(const protobuf::Node& node)
 {
   DeserializedNode dn;
-  return dn.init(node, *this) && nodes.put(dn.id, Move(dn));
+  return dn.init(node, *this) && nodes.putNew(dn.id, Move(dn));
 }
 
 static inline bool
 StreamHasData(GzipInputStream& stream)
 {
   // Test for the end of the stream. The protobuf library gives no way to tell
   // the difference between an underlying read error and the stream being
   // done. All we can do is attempt to read data and extrapolate guestimations
--- a/toolkit/devtools/server/HeapSnapshot.h
+++ b/toolkit/devtools/server/HeapSnapshot.h
@@ -84,18 +84,18 @@ class HeapSnapshot final : public nsISup
 
   // If present, a timestamp in the same units that `PR_Now` gives.
   Maybe<uint64_t> timestamp;
 
   // The id of the root node for this deserialized heap graph.
   NodeId rootId;
 
   // The set of nodes in this deserialized heap graph, keyed by id.
-  using NodeMap = js::HashMap<NodeId, DeserializedNode>;
-  NodeMap nodes;
+  using NodeSet = js::HashSet<DeserializedNode, DeserializedNode::HashPolicy>;
+  NodeSet nodes;
 
   // Core dump files have many duplicate strings: type names are repeated for
   // each node, and although in theory edge names are highly customizable for
   // specific edges, in practice they are also highly duplicated. Rather than
   // make each Deserialized{Node,Edge} malloc their own copy of their edge and
   // type names, we de-duplicate the strings here and Deserialized{Node,Edge}
   // get borrowed pointers into this set.
   using UniqueStringSet = js::HashSet<UniqueString, UniqueStringHashPolicy>;
--- a/toolkit/devtools/server/tests/gtest/DeserializedNodeUbiNodes.cpp
+++ b/toolkit/devtools/server/tests/gtest/DeserializedNodeUbiNodes.cpp
@@ -21,17 +21,17 @@ struct MockDeserializedNode : public Des
     : DeserializedNode(id, typeName, size)
   { }
 
   bool addEdge(DeserializedEdge&& edge)
   {
     return edges.append(Move(edge));
   }
 
-  MOCK_METHOD1(getEdgeReferent, DeserializedNode&(const DeserializedEdge&));
+  MOCK_METHOD1(getEdgeReferent, JS::ubi::Node(const DeserializedEdge&));
 };
 
 size_t fakeMallocSizeOf(const void*) {
   EXPECT_TRUE(false);
   MOZ_ASSERT_UNREACHABLE("fakeMallocSizeOf should never be called because "
                          "DeserializedNodes report the deserialized size.");
   return 0;
 }
@@ -60,36 +60,36 @@ DEF_TEST(DeserializedNodeUbiNodes, {
                                                                    10));
     DeserializedEdge edge1;
     edge1.referent = referent1->id;
     mocked.addEdge(Move(edge1));
     EXPECT_CALL(mocked,
                 getEdgeReferent(Field(&DeserializedEdge::referent,
                                       referent1->id)))
       .Times(1)
-      .WillOnce(ReturnRef(*referent1.get()));
+      .WillOnce(Return(JS::ubi::Node(referent1.get())));
 
     UniquePtr<DeserializedNode> referent2(new MockDeserializedNode(2,
                                                                    nullptr,
                                                                    20));
     DeserializedEdge edge2;
     edge2.referent = referent2->id;
     mocked.addEdge(Move(edge2));
     EXPECT_CALL(mocked,
                 getEdgeReferent(Field(&DeserializedEdge::referent,
                                       referent2->id)))
       .Times(1)
-      .WillOnce(ReturnRef(*referent2.get()));
+      .WillOnce(Return(JS::ubi::Node(referent2.get())));
 
     UniquePtr<DeserializedNode> referent3(new MockDeserializedNode(3,
                                                                    nullptr,
                                                                    30));
     DeserializedEdge edge3;
     edge3.referent = referent3->id;
     mocked.addEdge(Move(edge3));
     EXPECT_CALL(mocked,
                 getEdgeReferent(Field(&DeserializedEdge::referent,
                                       referent3->id)))
       .Times(1)
-      .WillOnce(ReturnRef(*referent3.get()));
+      .WillOnce(Return(JS::ubi::Node(referent3.get())));
 
     ubi.edges(cx);
   });