From dbb1bb205f35f076cf2d82ec443415d858b22e2f Mon Sep 17 00:00:00 2001 From: Brian Demsky Date: Wed, 14 Nov 2012 23:26:45 -0800 Subject: [PATCH] optimize hashtable so we don't always build new ones for cyclegraph check --- cyclegraph.cc | 17 ++++--- cyclegraph.h | 1 + hashtable.h | 132 +++++++++++++++++++++----------------------------- 3 files changed, 65 insertions(+), 85 deletions(-) diff --git a/cyclegraph.cc b/cyclegraph.cc index 33f8cda..ead70ae 100644 --- a/cyclegraph.cc +++ b/cyclegraph.cc @@ -6,6 +6,7 @@ /** Initializes a CycleGraph object. */ CycleGraph::CycleGraph() : + discovered(new HashTable(16)), hasCycles(false), oldCycles(false), hasRMWViolation(false), @@ -182,10 +183,10 @@ bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) */ bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) { std::vector > queue; - HashTable discovered(64); + discovered->reset(); queue.push_back(from); - discovered.put(from, from); + discovered->put(from, from); while(!queue.empty()) { CycleNode * node=queue.back(); queue.pop_back(); @@ -194,8 +195,8 @@ bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) { for(unsigned int i=0;igetEdges()->size();i++) { CycleNode *next=(*node->getEdges())[i]; - if (!discovered.contains(next)) { - discovered.put(next,next); + if (!discovered->contains(next)) { + discovered->put(next,next); queue.push_back(next); } } @@ -205,12 +206,12 @@ bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) { bool CycleGraph::checkPromise(const ModelAction *fromact, Promise *promise) { std::vector > queue; - HashTable discovered(64); + discovered->reset(); CycleNode *from = actionToNode.get(fromact); queue.push_back(from); - discovered.put(from, from); + discovered->put(from, from); while(!queue.empty()) { CycleNode * node=queue.back(); queue.pop_back(); @@ -221,8 +222,8 @@ bool CycleGraph::checkPromise(const ModelAction *fromact, Promise *promise) { for(unsigned int i=0;igetEdges()->size();i++) { CycleNode *next=(*node->getEdges())[i]; - if (!discovered.contains(next)) { - discovered.put(next,next); + if (!discovered->contains(next)) { + discovered->put(next,next); queue.push_back(next); } } diff --git a/cyclegraph.h b/cyclegraph.h index 1cc0d06..f0f04ff 100644 --- a/cyclegraph.h +++ b/cyclegraph.h @@ -37,6 +37,7 @@ class CycleGraph { SNAPSHOTALLOC private: CycleNode * getNode(const ModelAction *); + HashTable * discovered; /** @brief A table for mapping ModelActions to CycleNodes */ HashTable actionToNode; diff --git a/hashtable.h b/hashtable.h index 19fc75b..bf75928 100644 --- a/hashtable.h +++ b/hashtable.h @@ -23,27 +23,11 @@ * @tparam _free Provide your own 'free' for the table, or default to * snapshotting. */ -template +template + struct hashlistnode { _Key key; _Val val; - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *next; - - void * operator new(size_t size) { - return _malloc(size); - } - - void operator delete(void *p, size_t size) { - _free(p); - } - - void * operator new[](size_t size) { - return _malloc(size); - } - - void operator delete[](void *p, size_t size) { - _free(p); - } }; /** @@ -74,24 +58,17 @@ template **) _calloc(initialcapacity, sizeof(struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *)); + table = (struct hashlistnode<_Key,_Val> *) _calloc(initialcapacity, sizeof(struct hashlistnode<_Key,_Val>)); loadfactor = factor; capacity = initialcapacity; + capacitymask = initialcapacity - 1; + threshold = (unsigned int) (initialcapacity*loadfactor); - mask = (capacity << _Shift)-1; size = 0; // Initial number of elements in the hash } /** Destructor */ ~HashTable() { - for(unsigned int i=0;i * bin = table[i]; - while(bin!=NULL) { - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> * next=bin->next; - delete bin; - bin=next; - } - } _free(table); } @@ -117,15 +94,7 @@ template * bin = table[i]; - while(bin!=NULL) { - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> * next=bin->next; - delete bin; - bin=next; - } - } - memset(table, 0, capacity*sizeof(struct hashlistnode<_Key, _Val, _malloc, _calloc, _free> *)); + memset(table, 0, capacity*sizeof(struct hashlistnode<_Key, _Val>)); size=0; } @@ -134,90 +103,99 @@ template threshold) resize(capacity << 1); - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *ptr = table[(((_KeyInt)key) & mask)>>_Shift]; - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *search = ptr; + struct hashlistnode<_Key,_Val> *search; - while(search!=NULL) { + unsigned int index=((_KeyInt)key)>>_Shift; + do { + index=index&capacitymask; + search = &table[index]; if (search->key==key) { search->val=val; return; } - search=search->next; - } - - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *newptr=(struct hashlistnode<_Key,_Val,_malloc,_calloc,_free> *)new struct hashlistnode<_Key,_Val, _malloc, _calloc, _free>; - newptr->key=key; - newptr->val=val; - newptr->next=ptr; - table[(((_KeyInt)key)&mask)>>_Shift]=newptr; + index++; + } while(search->key); + + search->key=key; + search->val=val; size++; } /** Lookup the corresponding value for the given key. */ _Val get(_Key key) { - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *search = table[(((_KeyInt)key) & mask)>>_Shift]; + struct hashlistnode<_Key,_Val> *search; - while(search!=NULL) { + unsigned int index=((_KeyInt)key)>>_Shift; + do { + index=index&capacitymask; + search = &table[index]; if (search->key==key) { return search->val; } - search=search->next; - } - return (_Val)0; + index++; + } while(search->key); + return (_Val) 0; } /** Check whether the table contains a value for the given key. */ bool contains(_Key key) { - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *search = table[(((_KeyInt)key) & mask)>>_Shift]; + struct hashlistnode<_Key,_Val> *search; - while(search!=NULL) { + unsigned int index=((_KeyInt)key)>>_Shift; + do { + index=index&capacitymask; + search = &table[index]; if (search->key==key) { return true; } - search=search->next; - } + index++; + } while(search->key); return false; } /** Resize the table. */ void resize(unsigned int newsize) { - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> ** oldtable = table; - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> ** newtable; + struct hashlistnode<_Key,_Val> * oldtable = table; + struct hashlistnode<_Key,_Val> * newtable; unsigned int oldcapacity = capacity; - if((newtable = (struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> **) _calloc(newsize, sizeof(struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *))) == NULL) { + if((newtable = (struct hashlistnode<_Key,_Val> *) _calloc(newsize, sizeof(struct hashlistnode<_Key,_Val>))) == NULL) { printf("Calloc error %s %d\n", __FILE__, __LINE__); exit(-1); } - + table = newtable; //Update the global hashtable upon resize() capacity = newsize; - threshold = (unsigned int) (newsize * loadfactor); - mask = (newsize << _Shift)-1; + capacitymask = newsize - 1; - for(unsigned int i = 0; i < oldcapacity; i++) { - struct hashlistnode<_Key, _Val, _malloc, _calloc, _free> * bin = oldtable[i]; - - while(bin!=NULL) { - _Key key=bin->key; - struct hashlistnode<_Key, _Val, _malloc, _calloc, _free> * next=bin->next; + threshold = (unsigned int) (newsize * loadfactor); - unsigned int index = (((_KeyInt)key) & mask) >>_Shift; - struct hashlistnode<_Key, _Val, _malloc, _calloc, _free> * tmp=newtable[index]; - bin->next=tmp; - newtable[index]=bin; - bin = next; - } + struct hashlistnode<_Key, _Val> * bin = &oldtable[0]; + struct hashlistnode<_Key, _Val> * lastbin = &oldtable[oldcapacity]; + for(; bin < lastbin; bin++) { + _Key key=bin->key; + + struct hashlistnode<_Key,_Val> *search; + + unsigned int index=((_KeyInt)key)>>_Shift; + do { + index=index&capacitymask; + search = &table[index]; + index++; + } while(search->key); + + search->key=key; + search->val=bin->val; } _free(oldtable); //Free the memory of the old hash table } private: - struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> **table; + struct hashlistnode<_Key,_Val> *table; unsigned int capacity; - _KeyInt mask; unsigned int size; + unsigned int capacitymask; unsigned int threshold; double loadfactor; }; -- 2.34.1