From: bdemsky Date: Fri, 27 Feb 2004 07:41:19 +0000 (+0000) Subject: Checking in super-optimized SimpleHash code... Good for a little performance increase... X-Git-Url: http://plrg.eecs.uci.edu/git/?p=repair.git;a=commitdiff_plain;h=69c007fa54253b3631aba3bc32d6650730bb7d0e Checking in super-optimized SimpleHash code... Good for a little performance increase... --- diff --git a/Repair/RepairCompiler/MCC/Compiler.java b/Repair/RepairCompiler/MCC/Compiler.java index 1c0d7e1..05c6033 100755 --- a/Repair/RepairCompiler/MCC/Compiler.java +++ b/Repair/RepairCompiler/MCC/Compiler.java @@ -100,6 +100,8 @@ public class Compiler { gcode3.close(); } else { WorklistGenerator ng = new WorklistGenerator(state); + SetInclusion.worklist=true; + RelationInclusion.worklist=true; ng.generate(gcode); } gcode.close(); diff --git a/Repair/RepairCompiler/MCC/IR/RelationInclusion.java b/Repair/RepairCompiler/MCC/IR/RelationInclusion.java index 4e415bf..58e2664 100755 --- a/Repair/RepairCompiler/MCC/IR/RelationInclusion.java +++ b/Repair/RepairCompiler/MCC/IR/RelationInclusion.java @@ -9,7 +9,7 @@ public class RelationInclusion extends Inclusion { // #TBD#: this flag needs to be set by some static analysis boolean typesafe = true; - static boolean worklist = false; + public static boolean worklist = false; public RelationInclusion(Expr leftelementexpr, Expr rightelementexpr, RelationDescriptor relation) { this.leftelementexpr = leftelementexpr; diff --git a/Repair/RepairCompiler/MCC/IR/SetInclusion.java b/Repair/RepairCompiler/MCC/IR/SetInclusion.java index fb0f9ec..b18b08e 100755 --- a/Repair/RepairCompiler/MCC/IR/SetInclusion.java +++ b/Repair/RepairCompiler/MCC/IR/SetInclusion.java @@ -10,7 +10,7 @@ public class SetInclusion extends Inclusion { public String generatedresult = null; public String generatedaddeditem = null; - static boolean worklist = false; + public static boolean worklist = false; public boolean dostore = true; public String toString() { diff --git a/Repair/RepairCompiler/MCC/SimpleHash.cc b/Repair/RepairCompiler/MCC/SimpleHash.cc index ed8401d..c3e2165 100755 --- a/Repair/RepairCompiler/MCC/SimpleHash.cc +++ b/Repair/RepairCompiler/MCC/SimpleHash.cc @@ -134,39 +134,32 @@ void WorkList::add(int id,int type, int lvalue, int rvalue) { } /* SIMPLE HASH ********************************************************/ +SimpleIterator* SimpleHash::iterator() { + return new SimpleIterator(listhead,this); +} SimpleHash::SimpleHash(int size) { if (size <= 0) { throw SimpleHashException(); } this->size = size; - this->bucket = new LinkedHashNode* [size]; - for (int i=0;inodelist=0; + this->bucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*size,1); + /* Set allocation blocks*/ + this->listhead=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1); + this->listtail=this->listhead; + this->tailindex=0; + /*Set data counts*/ this->numparents = 0; this->numchildren = 0; this->numelements = 0; } -SimpleHash::SimpleHash() { - this->size = 100; - this->bucket = new LinkedHashNode* [size]; - for (int i=0;inodelist = 0; - this->numparents = 0; - this->numelements = 0; - this->numchildren = 0; -} - - SimpleHash::~SimpleHash() { - delete [] this->bucket; - LinkedHashNode *ptr=nodelist; + free(bucket); + struct ArraySimple *ptr=listhead; while(ptr) { - LinkedHashNode *next=ptr->lnext; - delete ptr; + struct ArraySimple *next=ptr->nextarray; + free(ptr); ptr=next; } } @@ -183,7 +176,7 @@ void SimpleHash::addChild(SimpleHash *child) { int SimpleHash::remove(int key, int data) { unsigned int hashkey = (unsigned int)key % size; - LinkedHashNode **ptr = &bucket[hashkey]; + struct SimpleNode **ptr = &bucket[hashkey]; for (int i = 0; i < numchildren; i++) { children[i]->remove(key, data); @@ -191,13 +184,11 @@ int SimpleHash::remove(int key, int data) { while (*ptr) { if ((*ptr)->key == key && (*ptr)->data == data) { - LinkedHashNode *toremove=*ptr; + struct SimpleNode *toremove=*ptr; *ptr=(*ptr)->next; - if (toremove->lprev) - toremove->lprev->lnext=toremove->lnext; - if (toremove->lnext) - toremove->lnext->lprev=toremove->lprev; - delete toremove; + + toremove->inuse=0; /* Marked as unused */ + numelements--; return 1; } @@ -212,7 +203,7 @@ int SimpleHash::remove(int key, int data) { int SimpleHash::add(int key, int data) { unsigned int hashkey = (unsigned int)key % size; - LinkedHashNode **ptr = &bucket[hashkey]; + struct SimpleNode **ptr = &bucket[hashkey]; /* check that this key/object pair isn't already here */ // TBD can be optimized for set v. relation */ @@ -222,12 +213,17 @@ int SimpleHash::add(int key, int data) { } ptr = &((*ptr)->next); } + if (tailindex==ARRAYSIZE) { + listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1); + tailindex=0; + listtail=listtail->nextarray; + } - *ptr = new LinkedHashNode(key, data, 0); - (*ptr)->lnext=nodelist; - if (nodelist!=0) - nodelist->lprev=*ptr; - nodelist=*ptr; + *ptr = &listtail->nodes[tailindex++]; + (*ptr)->key=key; + (*ptr)->data=data; + (*ptr)->inuse=1; + numelements++; for (int i = 0; i < numparents; i++) { @@ -240,7 +236,7 @@ int SimpleHash::add(int key, int data) { bool SimpleHash::contains(int key) { unsigned int hashkey = (unsigned int)key % size; - LinkedHashNode *ptr = bucket[hashkey]; + struct SimpleNode *ptr = bucket[hashkey]; while (ptr) { if (ptr->key == key) { // we already have this object @@ -255,7 +251,7 @@ bool SimpleHash::contains(int key) { bool SimpleHash::contains(int key, int data) { unsigned int hashkey = (unsigned int)key % size; - LinkedHashNode *ptr = bucket[hashkey]; + struct SimpleNode *ptr = bucket[hashkey]; while (ptr) { if (ptr->key == key && ptr->data == data) { // we already have this object @@ -271,7 +267,7 @@ int SimpleHash::count(int key) { unsigned int hashkey = (unsigned int)key % size; int count = 0; - LinkedHashNode *ptr = bucket[hashkey]; + struct SimpleNode *ptr = bucket[hashkey]; while (ptr) { if (ptr->key == key) { count++; @@ -284,7 +280,7 @@ int SimpleHash::count(int key) { int SimpleHash::get(int key, int&data) { unsigned int hashkey = (unsigned int)key % size; - LinkedHashNode *ptr = bucket[hashkey]; + struct SimpleNode *ptr = bucket[hashkey]; while (ptr) { if (ptr->key == key) { data = ptr->data; @@ -298,12 +294,22 @@ int SimpleHash::get(int key, int&data) { int SimpleHash::countdata(int data) { int count = 0; - LinkedHashNode *ptr = nodelist; + struct ArraySimple *ptr = listhead; while(ptr) { - if (ptr->data == data) { - count++; + if (ptr->nextarray) { + for(int i=0;inodes[i].data == data + &&ptr->nodes[i].inuse) { + count++; + } + } else { + for(int i=0;inodes[i].data == data + &&ptr->nodes[i].inuse) { + count++; + } } - ptr = ptr->next; + ptr = ptr->nextarray; } return count; } diff --git a/Repair/RepairCompiler/MCC/SimpleHash.h b/Repair/RepairCompiler/MCC/SimpleHash.h index 182351c..82b2821 100755 --- a/Repair/RepairCompiler/MCC/SimpleHash.h +++ b/Repair/RepairCompiler/MCC/SimpleHash.h @@ -59,62 +59,26 @@ struct ListNode { int data[WLISTSIZE]; ListNode *next; }; - - -/* SimpleIterator *****************************************************/ - -class SimpleIterator { - -private: - - LinkedHashNode *cur; - -public: - - inline SimpleIterator(LinkedHashNode *start) { - cur = start; - } - - inline int hasNext() { - return (int)cur->next == 0 ? 0 : 1; - } - - inline int next() { - cur = cur->next; - return cur->data; - } - - inline int key() { - return cur->key; - } - - inline int size() { - int temp = 0; - while (cur->next) { - temp++; - cur = cur->next; - } - return temp; - } - -}; - /* SimpleHash *********************************************************/ +class SimpleIterator; class SimpleHash { private: int numelements; int size; - LinkedHashNode **bucket; - LinkedHashNode *nodelist; + struct SimpleNode **bucket; + struct ArraySimple *listhead; + struct ArraySimple *listtail; + + int numparents; int numchildren; SimpleHash* parents[10]; SimpleHash* children[10]; void addChild(SimpleHash* child); public: - SimpleHash(); - SimpleHash(int size); + int tailindex; + SimpleHash(int size=100); ~SimpleHash(); int add(int key, int data); int remove(int key, int data); @@ -123,12 +87,8 @@ public: int get(int key, int& data); int countdata(int data); void addParent(SimpleHash* parent); - inline int firstkey() { - return nodelist->key; - } - inline SimpleIterator* iterator() { - return new SimpleIterator(nodelist); - } + int firstkey(); + SimpleIterator* iterator(); inline int count() { return numelements; } @@ -138,6 +98,66 @@ public: /* SimpleHashExcepion *************************************************/ + +/* SimpleIterator *****************************************************/ +#define ARRAYSIZE 100 + +struct SimpleNode { + struct SimpleNode *next; + int data; + int key; + int inuse; +}; + +struct ArraySimple { + struct SimpleNode nodes[ARRAYSIZE]; + struct ArraySimple * nextarray; +}; + + +class SimpleIterator { + +private: + + struct ArraySimple *cur; + int index; + SimpleHash * table; +public: + + inline SimpleIterator(struct ArraySimple *start, SimpleHash *t) { + cur = start; + table=t; + index=0; + } + + inline int hasNext() { + while((index==ARRAYSIZE)||!cur->nodes[index].inuse) { + if (cur->nextarray==0 && + index==table->tailindex) + return 0; + index++; + if (index==ARRAYSIZE) { + index=0; + cur=cur->nextarray; + } + } + if (cur->nodes[index].inuse) + return 1; + else + return 0; + } + + inline int next() { + return cur->nodes[index++].data; + } + + inline int key() { + return cur->nodes[index].key; + } +}; + +/* SimpleHashExcepion *************************************************/ + class SimpleHashException { public: SimpleHashException(); diff --git a/Repair/RepairCompiler/MCC/ex_test.cc b/Repair/RepairCompiler/MCC/ex_test.cc index 9b0ab1e..fd08277 100755 --- a/Repair/RepairCompiler/MCC/ex_test.cc +++ b/Repair/RepairCompiler/MCC/ex_test.cc @@ -1,5 +1,4 @@ #include "ex_aux.h" - struct Node { int data; struct Node *next; @@ -18,5 +17,5 @@ int main(int argc, char **argv) { for(int j=0;j<6000;j++) { #include "ex.cc" } - + }