Store pointers to seen formatting states.

[djasper]

Summary

As the memory ownership is handled by the SpecificBumpPtrAllocator anyway, there is no need to duplicate states when inserting them into the Seen-set. This leads to an improvement of ~10% on the benchmark formatting file. Not sure whether this is worth it, or whether we should straight away look into implementing this as a hash map.

[klimek]

test2

[djasper]

As there was no objection by now, I assume this is acceptable.

[djasper]

Submitted as r209422.

lib/Format/Format.cpp

   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
                               std::greater<QueueItem> > QueueType;
 
+  struct Compare {
+    bool operator()(LineState *obj1, LineState *obj2) const {
+      return *obj1 < *obj2;
+    }
+  };
+
   /// \brief Analyze the entire solution space starting from \p InitialState.
   ///
   /// This implements a variant of Dijkstra's algorithm on the graph that spans

   /// find the shortest path (the one with lowest penalty) from \p InitialState
   /// to a state where all tokens are placed.
   unsigned analyzeSolutionSpace(LineState &InitialState) {
-    std::set<LineState> Seen;
+    std::set<LineState *, Compare> Seen;
 
     // Insert start element into queue.
     StateNode *Node =

       }
       Queue.pop();
 
-      if (!Seen.insert(Node->State).second)
+      if (!Seen.insert(&Node->State).second)
         // State already examined with lower penalty.
         continue;