Hi klimek,
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.
http://llvm-reviews.chandlerc.com/D418
Files:
lib/Format/Format.cpp
Index: lib/Format/Format.cpp
===================================================================
--- lib/Format/Format.cpp
+++ lib/Format/Format.cpp
@@ -676,6 +676,12 @@
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
@@ -683,7 +689,7 @@
/// 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 =
@@ -701,7 +707,7 @@
}
Queue.pop();
- if (!Seen.insert(Node->State).second)
+ if (!Seen.insert(&Node->State).second)
// State already examined with lower penalty.
continue;
Index: lib/Format/Format.cpp
===================================================================
--- lib/Format/Format.cpp
+++ lib/Format/Format.cpp
@@ -676,6 +676,12 @@
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
@@ -683,7 +689,7 @@
/// 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 =
@@ -701,7 +707,7 @@
}
Queue.pop();
- if (!Seen.insert(Node->State).second)
+ if (!Seen.insert(&Node->State).second)
// State already examined with lower penalty.
continue;
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
