From 0dc4895e7c40b9588d5ece94cba09e2fe2af420d Mon Sep 17 00:00:00 2001
From: Brian Demsky <bdemsky@uci.edu>
Date: Mon, 4 Mar 2013 17:23:48 -0800
Subject: [PATCH] little optimizations motivated by profiling...
1. reduce allocations of vectors for queues
2. reduce calls to checkReachable
---
cyclegraph.cc | 41 ++++++++++++++++++++---------------------
cyclegraph.h | 2 ++
2 files changed, 22 insertions(+), 21 deletions(-)
diff --git a/cyclegraph.cc b/cyclegraph.cc
index d2cac49..240d24f 100644
--- a/cyclegraph.cc
+++ b/cyclegraph.cc
@@ -8,6 +8,7 @@
/** Initializes a CycleGraph object. */
CycleGraph::CycleGraph() :
discovered(new HashTable<const CycleNode *, const CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free>(16)),
+ queue(new std::vector< const CycleNode *, ModelAlloc<const CycleNode *> >()),
hasCycles(false),
oldCycles(false)
{
@@ -198,11 +199,11 @@ bool CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode)
{
bool added;
- if (!hasCycles)
- hasCycles = checkReachable(tonode, fromnode);
-
- if ((added = fromnode->addEdge(tonode)))
+ if ((added = fromnode->addEdge(tonode))) {
rollbackvector.push_back(fromnode);
+ if (!hasCycles)
+ hasCycles = checkReachable(tonode, fromnode);
+ }
/*
* If the fromnode has a rmwnode that is not the tonode, we should add
@@ -210,10 +211,10 @@ bool CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode)
*/
CycleNode *rmwnode = fromnode->getRMW();
if (rmwnode && rmwnode != tonode) {
- if (!hasCycles)
- hasCycles = checkReachable(tonode, rmwnode);
-
if (rmwnode->addEdge(tonode)) {
+ if (!hasCycles)
+ hasCycles = checkReachable(tonode, rmwnode);
+
rollbackvector.push_back(rmwnode);
added = true;
}
@@ -386,22 +387,20 @@ void CycleGraph::dumpGraphToFile(const char *filename) const
*/
bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
{
- std::vector< const CycleNode *, ModelAlloc<const CycleNode *> > queue;
discovered->reset();
-
- queue.push_back(from);
+ queue->clear();
+ queue->push_back(from);
discovered->put(from, from);
- while (!queue.empty()) {
- const CycleNode *node = queue.back();
- queue.pop_back();
+ while (!queue->empty()) {
+ const CycleNode *node = queue->back();
+ queue->pop_back();
if (node == to)
return true;
-
for (unsigned int i = 0; i < node->getNumEdges(); i++) {
CycleNode *next = node->getEdge(i);
if (!discovered->contains(next)) {
discovered->put(next, next);
- queue.push_back(next);
+ queue->push_back(next);
}
}
}
@@ -438,15 +437,15 @@ template bool CycleGraph::checkReachable(const Promise *from,
/** @return True, if the promise has failed; false otherwise */
bool CycleGraph::checkPromise(const ModelAction *fromact, Promise *promise) const
{
- std::vector< CycleNode *, ModelAlloc<CycleNode *> > queue;
discovered->reset();
+ queue->clear();
CycleNode *from = actionToNode.get(fromact);
- queue.push_back(from);
+ queue->push_back(from);
discovered->put(from, from);
- while (!queue.empty()) {
- CycleNode *node = queue.back();
- queue.pop_back();
+ while (!queue->empty()) {
+ const CycleNode *node = queue->back();
+ queue->pop_back();
if (node->getPromise() == promise)
return true;
@@ -458,7 +457,7 @@ bool CycleGraph::checkPromise(const ModelAction *fromact, Promise *promise) cons
CycleNode *next = node->getEdge(i);
if (!discovered->contains(next)) {
discovered->put(next, next);
- queue.push_back(next);
+ queue->push_back(next);
}
}
}
diff --git a/cyclegraph.h b/cyclegraph.h
index 3f1c933..25401d9 100644
--- a/cyclegraph.h
+++ b/cyclegraph.h
@@ -68,6 +68,8 @@ class CycleGraph {
bool mergeNodes(CycleNode *node1, CycleNode *node2);
HashTable<const CycleNode *, const CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free> *discovered;
+ std::vector< const CycleNode *, ModelAlloc<const CycleNode *> > * queue;
+
/** @brief A table for mapping ModelActions to CycleNodes */
HashTable<const ModelAction *, CycleNode *, uintptr_t, 4> actionToNode;
--
2.34.1