Checking in super-optimized SimpleHash code... Good for a little performance increase...
authorbdemsky <bdemsky>
Fri, 27 Feb 2004 07:41:19 +0000 (07:41 +0000)
committerbdemsky <bdemsky>
Fri, 27 Feb 2004 07:41:19 +0000 (07:41 +0000)
Repair/RepairCompiler/MCC/Compiler.java
Repair/RepairCompiler/MCC/IR/RelationInclusion.java
Repair/RepairCompiler/MCC/IR/SetInclusion.java
Repair/RepairCompiler/MCC/SimpleHash.cc
Repair/RepairCompiler/MCC/SimpleHash.h
Repair/RepairCompiler/MCC/ex_test.cc

index 1c0d7e1..05c6033 100755 (executable)
@@ -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();
index 4e415bf..58e2664 100755 (executable)
@@ -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;
index fb0f9ec..b18b08e 100755 (executable)
@@ -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() {
index ed8401d..c3e2165 100755 (executable)
@@ -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;i<size;i++)
-      bucket[i]=0;
-    this->nodelist=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;i<size;i++)
-      bucket[i]=0;
-    this->nodelist = 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;i<ARRAYSIZE;i++)
+         if (ptr->nodes[i].data == data
+             &&ptr->nodes[i].inuse) {
+           count++;
+         }
+      } else {
+       for(int i=0;i<tailindex;i++)
+         if (ptr->nodes[i].data == data
+             &&ptr->nodes[i].inuse) {
+           count++;
+         }
       }
-      ptr = ptr->next;
+      ptr = ptr->nextarray;
     }
     return count;
 }
index 182351c..82b2821 100755 (executable)
@@ -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();
index 9b0ab1e..fd08277 100755 (executable)
@@ -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"
   }
-  
 }