From 61ce611eaaba867615b9424e26adfb6a185c29fa Mon Sep 17 00:00:00 2001 From: bdemsky Date: Wed, 3 Sep 2008 06:18:09 +0000 Subject: [PATCH] optimizations to checkpointing --- Robust/src/Runtime/Queue.c | 12 ++- Robust/src/Runtime/Queue.h | 4 +- Robust/src/Runtime/chash.c | 127 ++++++++++++++------------------ Robust/src/Runtime/chash.h | 5 +- Robust/src/Runtime/checkpoint.c | 112 ++++++++++++++-------------- Robust/src/Runtime/checkpoint.h | 6 +- Robust/src/Runtime/garbage.c | 15 ++-- Robust/src/Runtime/runtime.h | 1 + Robust/src/Runtime/task.c | 16 ++-- 9 files changed, 147 insertions(+), 151 deletions(-) diff --git a/Robust/src/Runtime/Queue.c b/Robust/src/Runtime/Queue.c index 90743065..b00a7d78 100644 --- a/Robust/src/Runtime/Queue.c +++ b/Robust/src/Runtime/Queue.c @@ -15,10 +15,6 @@ void freeQueue(struct Queue * q) { RUNFREE(q); } -int isEmpty(struct Queue *queue) { - return queue->head==NULL; -} - struct QueueItem * addNewItem(struct Queue * queue, void * ptr) { struct QueueItem * item=RUNMALLOC(sizeof(struct QueueItem)); item->objectptr=ptr; @@ -82,3 +78,11 @@ struct QueueItem * getTail(struct Queue * queue) { struct QueueItem * getNext(struct QueueItem * qi) { return qi->next; } + +void * getItem(struct Queue * queue) { + struct QueueItem * q=queue->head; + void * ptr=q->objectptr; + queue->head=q->next; + RUNFREE(q); + return ptr; +} diff --git a/Robust/src/Runtime/Queue.h b/Robust/src/Runtime/Queue.h index 033478bf..07260fb4 100644 --- a/Robust/src/Runtime/Queue.h +++ b/Robust/src/Runtime/Queue.h @@ -13,6 +13,9 @@ struct QueueItem { struct QueueItem * prev; }; +#define isEmpty(x) (x->head==NULL) + +void * getItem(struct Queue * queue); void freeQueue(struct Queue * q); struct Queue * createQueue(); struct QueueItem * addNewItem(struct Queue * queue, void * ptr); @@ -21,7 +24,6 @@ struct QueueItem * addNewItem_I(struct Queue * queue, void * ptr); #endif struct QueueItem * findItem(struct Queue * queue, void * ptr); void removeItem(struct Queue * queue, struct QueueItem * item); -int isEmpty(struct Queue *queue); struct QueueItem * getTail(struct Queue * queue); diff --git a/Robust/src/Runtime/chash.c b/Robust/src/Runtime/chash.c index 3759fef0..6c98d94f 100644 --- a/Robust/src/Runtime/chash.c +++ b/Robust/src/Runtime/chash.c @@ -1,5 +1,4 @@ #include "chash.h" -#define INLINE inline __attribute__((always_inline)) void crehash(ctable_t *table) { cResize(table, table->size); @@ -27,42 +26,40 @@ ctable_t *cCreate(unsigned int size, float loadfactor) { ctable->mask = (size << 2)-1; ctable->numelements = 0; // Initial number of elements in the hash ctable->loadfactor = loadfactor; + ctable->resize=loadfactor*size; ctable->listhead=NULL; return ctable; } //Store objects and their pointers into hash -unsigned int cInsert(ctable_t *table, unsigned int key, void *val) { +INLINE void cInsert(ctable_t *table, unsigned int key, void *val) { unsigned int newsize; int index; cnode_t *ptr, *node; - if(table->numelements > (table->loadfactor * table->size)) { - //Resize - newsize = table->size << 1; - cResize(table,newsize); + ptr = &table->table[(key & table->mask)>>2]; + if (ptr->key==0) { + ptr->key=key; + ptr->val=val; + ptr->lnext=table->listhead; + table->listhead=ptr; + return; } - ptr = table->table; + cnode_t *tmp=malloc(sizeof(cnode_t)); + tmp->next=ptr->next; + ptr->next=tmp; + tmp->key=key; + tmp->val=val; + tmp->lnext=table->listhead; + table->listhead=tmp; + table->numelements++; - index =(key & table->mask)>>2; - if(ptr[index].next == NULL && ptr[index].key == 0) { // Insert at the first position in the hashtable - ptr[index].key = key; - ptr[index].val = val; - } else { // Insert in the beginning of linked list - if ((node = calloc(1, sizeof(cnode_t))) == NULL) { - printf("Calloc error %s, %d\n", __FILE__, __LINE__); - return 1; - } - node->key = key; - node->val = val; - node->next = ptr[index].next; - node->lnext=table->listhead; - table->listhead=node; - ptr[index].next = node; + if(table->numelements > table->resize) { + newsize = table->size << 1; + cResize(table,newsize); } - return 0; } // Search for an address for a given oid @@ -112,63 +109,47 @@ unsigned int cRemove(ctable_t *table, unsigned int key) { } unsigned int cResize(ctable_t *table, unsigned int newsize) { - cnode_t *node, *ptr, *curr, *next; // curr and next keep track of the current and the next chashlistnodes in a linked list - unsigned int oldsize; - int isfirst; // Keeps track of the first element in the chashlistnode_t for each bin in hashtable - int i,index; - cnode_t *newnode; + int i; cnode_t *last=NULL; + int mask=(newsize<<2)-1; + int oldsize = table->size; + cnode_t *ptr = table->table; + cnode_t * ntable=calloc(newsize, sizeof(cnode_t)); - ptr = table->table; - oldsize = table->size; - - if((node = calloc(newsize, sizeof(cnode_t))) == NULL) { - printf("Calloc error %s %d\n", __FILE__, __LINE__); - return 1; - } - - table->table = node; //Update the global hashtable upon resize() + table->table = ntable; table->size = newsize; - table->mask = (newsize << 2)-1; - table->numelements = 0; - - for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table - curr = &ptr[i]; - isfirst = 1; - while (curr != NULL) { //Inner loop to go through linked lists - if (curr->key == 0) { //Exit inner loop if there the first element for a given bin/index is NULL - break; //key = val =0 for element if not present within the hash table - } - next = curr->next; - - index =(curr->key & table->mask)>>2; - // Insert into the new table - if(table->table[index].next == NULL && table->table[index].key == 0) { - table->table[index].key = curr->key; - table->table[index].val = curr->val; - table->numelements++; - table->table[index].lnext=last; - last=&table->table[index]; - } else { - if((newnode = calloc(1, sizeof(cnode_t))) == NULL) { - printf("Calloc error %s, %d\n", __FILE__, __LINE__); - return 1; - } - newnode->key = curr->key; - newnode->val = curr->val; - newnode->next = table->table[index].next; - table->table[index].next = newnode; - table->numelements++; + table->mask = mask; + table->resize=newsize*table->loadfactor; + + for(i = 0; i < oldsize; i++) { + int isfirst=1; + cnode_t * curr=&ptr[i]; + if (curr->key==0) + continue; + while(curr!=NULL) { + cnode_t * next = curr->next; + int index =(curr->key & mask)>>2; + cnode_t * newnode=&ntable[index]; + + if(newnode->key==0) { + newnode->key=curr->key; + newnode->val=curr->val; newnode->lnext=last; last=newnode; - } - - //free the linked list of chashlistnode_t if not the first element in the hash table - if (isfirst != 1) { + } else { + cnode_t *tmp=malloc(sizeof(cnode_t)); + tmp->next=newnode->next; + newnode->next=tmp; + tmp->key=curr->key; + tmp->val=curr->val; + tmp->lnext=last; + last=tmp; + } + if (isfirst) { + isfirst=0; + } else { free(curr); } - - isfirst = 0; curr = next; } } diff --git a/Robust/src/Runtime/chash.h b/Robust/src/Runtime/chash.h index d85fbd03..f21f3c94 100644 --- a/Robust/src/Runtime/chash.h +++ b/Robust/src/Runtime/chash.h @@ -3,6 +3,8 @@ #include #include +#define INLINE inline __attribute__((always_inline)) +//#define INLINE typedef struct cnode { unsigned int key; @@ -16,13 +18,14 @@ typedef struct ctable { unsigned int size; unsigned int mask; unsigned int numelements; + unsigned int resize; float loadfactor; struct cnode *listhead; } ctable_t; /* Prototypes for hash*/ ctable_t *cCreate(unsigned int size, float loadfactor); -unsigned int cInsert(ctable_t *table, unsigned int key, void * val); +void cInsert(ctable_t *table, unsigned int key, void * val); void * cSearch(ctable_t *table, unsigned int key); //returns val, NULL if not found unsigned int cRemove(ctable_t *table, unsigned int key); //returns -1 if not found unsigned int cResize(ctable_t *table, unsigned int newsize); diff --git a/Robust/src/Runtime/checkpoint.c b/Robust/src/Runtime/checkpoint.c index 51b577a3..5585699a 100644 --- a/Robust/src/Runtime/checkpoint.c +++ b/Robust/src/Runtime/checkpoint.c @@ -2,6 +2,7 @@ #include "runtime.h" #include "structdefs.h" #include +#include "Queue.h" #ifdef DMALLOC #include "dmalloc.h" #endif @@ -65,7 +66,8 @@ void checkvalid(void * ptr) { } } -void validitycheck(struct RuntimeHash *forward, struct RuntimeHash *reverse) { +/* +void validitycheck(struct ctable *forward, struct ctable *reverse) { struct RuntimeIterator rit; RuntimeHashiterator(forward, &rit); while(RunhasNext(&rit)) { @@ -114,55 +116,56 @@ void validitycheck(struct RuntimeHash *forward, struct RuntimeHash *reverse) { } } } +*/ - -void ** makecheckpoint(int numparams, void ** srcpointer, struct RuntimeHash * forward, struct RuntimeHash * reverse) { +void ** makecheckpoint(int numparams, void ** srcpointer, struct ctable * forward, struct ctable * reverse) { #ifdef PRECISE_GC void **newarray=cpmalloc(sizeof(void *)*numparams); #else void **newarray=RUNMALLOC(sizeof(void *)*numparams); #endif - struct RuntimeHash *todo=allocateRuntimeHash(100); + struct Queue *todo=createQueue(); int i; for(i=0; iflagptr; if (objptr!=NULL) { - if (!RuntimeHashcontainskey(forward, (int) objptr)) { + void *dst; + if ((dst=cSearch(forward, (unsigned int)objptr))==NULL) { void *copy=createcopy(objptr); - RuntimeHashadd(forward, (int) objptr, (int) copy); - RuntimeHashadd(reverse, (int) copy, (int) objptr); - RuntimeHashadd(todo, (int) objptr, (int) objptr); + cInsert(forward, (int) objptr, copy); + cInsert(reverse, (int) copy, objptr); + addNewItem(todo, objptr); ((struct ___TagDescriptor___*)cpy)->flagptr=copy; } else { - RuntimeHashget(forward, (int) objptr, (int *) &(((struct ___TagDescriptor___*) cpy)->flagptr)); - } + ((struct ___TagDescriptor___*) cpy)->flagptr=dst; } - } else + } + } else #endif if (pointer==0) { /* Array of primitives */ @@ -174,16 +177,17 @@ void ** makecheckpoint(int numparams, void ** srcpointer, struct RuntimeHash * f int length=ao->___length___; int i; for(i=0; i___length___)+sizeof(int)))[i]; if (objptr==NULL) { ((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]=NULL; - } else if (RuntimeHashcontainskey(forward, (int) objptr)) - RuntimeHashget(forward,(int) objptr,(int *) &((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]); + } else if ((dst=cSearch(forward, (int)objptr))!=NULL) + ((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]=dst; else { void * copy=createcopy(objptr); - RuntimeHashadd(forward, (int) objptr, (int)copy); - RuntimeHashadd(reverse, (int) copy, (int) objptr); - RuntimeHashadd(todo, (int) objptr, (int) objptr); + cInsert(forward, (int) objptr, copy); + cInsert(reverse, (int) copy, objptr); + addNewItem(todo, objptr); ((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]=copy; } } @@ -193,22 +197,23 @@ void ** makecheckpoint(int numparams, void ** srcpointer, struct RuntimeHash * f for(i=1; i<=size; i++) { int offset=pointer[i]; void * objptr=*((void **)(((int)ptr)+offset)); + void *dst; if (objptr==NULL) { *((void **)(((int)cpy)+offset))=NULL; - } else if (RuntimeHashcontainskey(forward, (int) objptr)) - RuntimeHashget(forward, (int) objptr, (int *) &(((char *)cpy)[offset])); + } else if ((dst=cSearch(forward, (unsigned int)objptr))!=NULL) + *((void **) &(((char *)cpy)[offset]))=dst; else { void * copy=createcopy(objptr); - RuntimeHashadd(forward, (int) objptr, (int) copy); - RuntimeHashadd(reverse, (int) copy, (int) objptr); - RuntimeHashadd(todo, (int) objptr, (int) objptr); + cInsert(forward, (int) objptr, copy); + cInsert(reverse, (int) copy, objptr); + addNewItem(todo, objptr); *((void **)(((int)cpy)+offset))=copy; } } } } } - freeRuntimeHash(todo); + freeQueue(todo); return newarray; } @@ -244,28 +249,27 @@ void * createcopy(void * orig) { } } -void restorecheckpoint(int numparams, void ** original, void ** checkpoint, struct RuntimeHash *forward, struct RuntimeHash * reverse) { - struct RuntimeHash *todo=allocateRuntimeHash(100); - struct RuntimeHash *visited=allocateRuntimeHash(100); +void restorecheckpoint(int numparams, void ** original, void ** checkpoint, struct ctable *forward, struct ctable * reverse) { + struct Queue *todo=createQueue(); + struct ctable *visited=cCreate(256, 0.5); int i; for(i=0; iflagptr; memcpy(cpy, ptr, size); if (objptr!=NULL) { - if (!RuntimeHashcontainskey(visited, (int) objptr)) { - RuntimeHashadd(visited, (int) objptr, (int) objptr); - RuntimeHashadd(todo, (int) objptr, (int) objptr); + if (cSearch(visited, (unsigned int)objptr)==NULL) { + cInsert(visited, (int) objptr, objptr); + addNewItem(todo, objptr); } - RuntimeHashget(reverse, (int) objptr, (int *) &(((struct ___TagDescriptor___ *)cpy)->flagptr)); + *((void **) &(((struct ___TagDescriptor___ *)cpy)->flagptr))=cSearch(reverse, (int) objptr); } } else #endif @@ -301,11 +305,11 @@ void restorecheckpoint(int numparams, void ** original, void ** checkpoint, stru if (objptr==NULL) ((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]=NULL; else { - if (!RuntimeHashcontainskey(visited, (int) objptr)) { - RuntimeHashadd(visited, (int) objptr, (int) objptr); - RuntimeHashadd(todo, (int) objptr, (int) objptr); + if (cSearch(visited, (int) objptr)==NULL) { + cInsert(visited, (int) objptr, objptr); + addNewItem(todo, objptr); } - RuntimeHashget(reverse, (int) objptr, (int *) &((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]); + *((void **) &((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i])=cSearch(reverse, (int) objptr); } } } else { @@ -326,11 +330,11 @@ void restorecheckpoint(int numparams, void ** original, void ** checkpoint, stru if (objptr==NULL) *((void **)(((int)cpy)+offset))=NULL; else { - if (!RuntimeHashcontainskey(visited, (int) objptr)) { - RuntimeHashadd(visited, (int) objptr, (int) objptr); - RuntimeHashadd(todo, (int) objptr, (int) objptr); + if (cSearch(visited, (int)objptr)==NULL) { + cInsert(visited, (int) objptr, objptr); + addNewItem(todo, objptr); } - RuntimeHashget(reverse, (int) objptr, (int *) &(((char *)cpy)[offset])); + *((void **) &(((char *)cpy)[offset]))=cSearch(reverse, (int) objptr); } } if (hasflags[type]) { @@ -347,6 +351,6 @@ void restorecheckpoint(int numparams, void ** original, void ** checkpoint, stru } } } - freeRuntimeHash(todo); - freeRuntimeHash(visited); + freeQueue(todo); + cDelete(visited); } diff --git a/Robust/src/Runtime/checkpoint.h b/Robust/src/Runtime/checkpoint.h index 9f600953..62daeb95 100644 --- a/Robust/src/Runtime/checkpoint.h +++ b/Robust/src/Runtime/checkpoint.h @@ -1,10 +1,10 @@ #ifndef CHECKPOINT_H #define CHECKPOINT_H -#include "SimpleHash.h" +#include "chash.h" -void ** makecheckpoint(int numparams, void ** pointerarray, struct RuntimeHash * forward, struct RuntimeHash * reverse); +void ** makecheckpoint(int numparams, void ** pointerarray, struct ctable * forward, struct ctable * reverse); -void restorecheckpoint(int numparams, void ** original, void ** checkpoint, struct RuntimeHash *forward, struct RuntimeHash * reverse); +void restorecheckpoint(int numparams, void ** original, void ** checkpoint, struct ctable *forward, struct ctable * reverse); void * createcopy(void * orig); void freemalloc(); diff --git a/Robust/src/Runtime/garbage.c b/Robust/src/Runtime/garbage.c index fb03fe5a..f608e4d6 100644 --- a/Robust/src/Runtime/garbage.c +++ b/Robust/src/Runtime/garbage.c @@ -3,6 +3,7 @@ #include "structdefs.h" #include "Queue.h" #include "SimpleHash.h" +#include "chash.h" #include "GenericHashtable.h" #include #if defined(THREADS) || defined(DSTM) @@ -30,8 +31,8 @@ extern struct parameterwrapper * objectqueues[NUMCLASSES]; #endif extern struct genhashtable * failedtasks; extern struct taskparamdescriptor *currtpd; -extern struct RuntimeHash *forward; -extern struct RuntimeHash *reverse; +extern struct ctable *forward; +extern struct ctable *reverse; extern struct RuntimeHash *fdtoobject; #endif @@ -209,20 +210,20 @@ void collect(struct garbagelist * stackptr) { } if (forward!=NULL) { - struct RuntimeNode * ptr=forward->listhead; + struct cnode * ptr=forward->listhead; while(ptr!=NULL) { void * orig=(void *)ptr->key; ENQUEUE(orig, *((void **)(&ptr->key))); ptr=ptr->lnext; } - RuntimeHashrehash(forward); /* Rehash the table */ + crehash(forward); /* Rehash the table */ } if (reverse!=NULL) { - struct RuntimeNode * ptr=reverse->listhead; + struct cnode * ptr=reverse->listhead; while(ptr!=NULL) { - void *orig=(void *)ptr->data; - ENQUEUE(orig, *((void**)(&ptr->data))); + void *orig=(void *)ptr->val; + ENQUEUE(orig, *((void**)(&ptr->val))); ptr=ptr->lnext; } } diff --git a/Robust/src/Runtime/runtime.h b/Robust/src/Runtime/runtime.h index fcc62a61..f80a4ab7 100644 --- a/Robust/src/Runtime/runtime.h +++ b/Robust/src/Runtime/runtime.h @@ -79,6 +79,7 @@ void createstartupobject(); #ifdef TASK #include "SimpleHash.h" +#include "chash.h" #ifndef MULTICORE #include "ObjectHash.h" #include "structdefs.h" diff --git a/Robust/src/Runtime/task.c b/Robust/src/Runtime/task.c index a7bb77a4..53861273 100644 --- a/Robust/src/Runtime/task.c +++ b/Robust/src/Runtime/task.c @@ -25,8 +25,8 @@ struct genhashtable * activetasks; struct parameterwrapper * objectqueues[NUMCLASSES]; struct genhashtable * failedtasks; struct taskparamdescriptor * currtpd; -struct RuntimeHash * forward; -struct RuntimeHash * reverse; +struct ctable * forward; +struct ctable * reverse; int main(int argc, char **argv) { #ifdef BOEHM_GC @@ -1163,8 +1163,8 @@ parameterpresent: { /* Checkpoint the state */ - forward=allocateRuntimeHash(100); - reverse=allocateRuntimeHash(100); + forward=cCreate(256, 0.4); + reverse=cCreate(256, 0.4); void ** checkpoint=makecheckpoint(currtpd->task->numParameters, currtpd->parameterArray, forward, reverse); int x; if (x=setjmp(error_handler)) { @@ -1186,8 +1186,8 @@ parameterpresent: RUNFREE(fsesarray[counter]); } #endif - freeRuntimeHash(forward); - freeRuntimeHash(reverse); + cDelete(forward); + cDelete(reverse); freemalloc(); forward=NULL; reverse=NULL; @@ -1226,8 +1226,8 @@ parameterpresent: } #endif - freeRuntimeHash(forward); - freeRuntimeHash(reverse); + cDelete(forward); + cDelete(reverse); freemalloc(); // Free up task parameter descriptor RUNFREE(currtpd->parameterArray); -- 2.34.1