[1132] in Coldmud discussion meeting
[COLD] Symbol speedup patch
daemon@ATHENA.MIT.EDU (Thu Nov 14 11:49:46 1996
)
Date: Thu, 14 Nov 1996 17:07:43 +0100 (MET)
From: Miroslav.Silovic@public.srce.hr (Miroslav Silovic)
To: coldstuff@cold.org
This patch should speed up the driver noticably, as it avoids
unnecessary calls to hash() function on each method/variable
lookup. The hash() used to take 10% of the execution time
with ColdDark core, and is likely to take even more in
cores that do large ammount of object shuffling, so the speedup
should be quite noticable.
------------------------------------------------------------------
diff -C 8 -r ../Genesis-1.0p18/src/data/data.c src/data/data.c
*** ../Genesis-1.0p18/src/data/data.c Thu Sep 19 22:27:15 1996
--- src/data/data.c Thu Nov 14 16:46:11 1996
***************
*** 133,149 ****
case LIST:
if (list_length(d->u.list) > 0)
return data_hash(list_first(d->u.list));
else
return 100;
case SYMBOL:
! return hash(ident_name(d->u.symbol));
case T_ERROR:
return hash(ident_name(d->u.error));
case FROB:
return d->u.frob->cclass + data_hash(&d->u.frob->rep);
case DICT:
--- 133,149 ----
case LIST:
if (list_length(d->u.list) > 0)
return data_hash(list_first(d->u.list));
else
return 100;
case SYMBOL:
! return ident_hash(d->u.symbol);
case T_ERROR:
return hash(ident_name(d->u.error));
case FROB:
return d->u.frob->cclass + data_hash(&d->u.frob->rep);
case DICT:
diff -C 8 -r ../Genesis-1.0p18/src/data/ident.c src/data/ident.c
*** ../Genesis-1.0p18/src/data/ident.c Tue Oct 22 19:43:07 1996
--- src/data/ident.c Thu Nov 14 16:33:03 1996
***************
*** 11,26 ****
--- 11,27 ----
* of two, assuming an Int is four bytes. */
/* HACKNOTE: BAD */
#define MALLOC_DELTA 8
#define INIT_TAB_SIZE (512 - MALLOC_DELTA)
typedef struct xident_entry {
char *s;
Int refs;
+ uLong hash;
Long next;
} xIdent_entry;
static xIdent_entry *tab;
static Long *hashtab;
static Long tab_size, blanks;
Ident perm_id, type_id, div_id, integer_id, float_id, string_id, objnum_id,
***************
*** 134,150 ****
Ident ident_get(char *s)
{
uLong hval = hash(s);
Long ind, new_size, i;
/* Look for an existing identifier. */
ind = hashtab[hval % tab_size];
while (ind != -1) {
! if (strcmp(tab[ind].s, s) == 0) {
tab[ind].refs++;
#ifdef IDENT_DEBUG
write_err("get(old) %s: %d refs %d", s, ind, tab[ind].refs);
#endif
return ind;
}
ind = tab[ind].next;
--- 135,151 ----
Ident ident_get(char *s)
{
uLong hval = hash(s);
Long ind, new_size, i;
/* Look for an existing identifier. */
ind = hashtab[hval % tab_size];
while (ind != -1) {
! if (tab[ind].hash == hval && strcmp(tab[ind].s, s) == 0) {
tab[ind].refs++;
#ifdef IDENT_DEBUG
write_err("get(old) %s: %d refs %d", s, ind, tab[ind].refs);
#endif
return ind;
}
ind = tab[ind].next;
***************
*** 165,192 ****
blanks = tab_size;
/* Reset hash table. */
for (i = 0; i < new_size; i++)
hashtab[i] = -1;
/* Install old symbols in hash table. */
for (i = 0; i < tab_size; i++) {
! ind = hash(tab[i].s) % new_size;
tab[i].next = hashtab[ind];
hashtab[ind] = i;
}
tab_size = new_size;
}
/* Install symbol at first blank. */
ind = blanks;
blanks = tab[ind].next;
tab[ind].s = tstrdup(s);
tab[ind].refs = 1;
tab[ind].next = hashtab[hval % tab_size];
hashtab[hval % tab_size] = ind;
#ifdef IDENT_DEBUG
write_err("get(new) %s: %d refs %d", s, ind, tab[ind].refs);
#endif
--- 166,194 ----
blanks = tab_size;
/* Reset hash table. */
for (i = 0; i < new_size; i++)
hashtab[i] = -1;
/* Install old symbols in hash table. */
for (i = 0; i < tab_size; i++) {
! ind = tab[i].hash % new_size;
tab[i].next = hashtab[ind];
hashtab[ind] = i;
}
tab_size = new_size;
}
/* Install symbol at first blank. */
ind = blanks;
blanks = tab[ind].next;
tab[ind].s = tstrdup(s);
+ tab[ind].hash = hval;
tab[ind].refs = 1;
tab[ind].next = hashtab[hval % tab_size];
hashtab[hval % tab_size] = ind;
#ifdef IDENT_DEBUG
write_err("get(new) %s: %d refs %d", s, ind, tab[ind].refs);
#endif
***************
*** 233,240 ****
--- 235,246 ----
return id;
}
char *ident_name(Ident id)
{
return tab[id].s;
}
+ uLong ident_hash(Ident id)
+ {
+ return tab[id].hash;
+ }
diff -C 8 -r ../Genesis-1.0p18/src/data/object.c src/data/object.c
*** ../Genesis-1.0p18/src/data/object.c Sat Oct 19 23:08:05 1996
--- src/data/object.c Thu Nov 14 16:45:23 1996
***************
*** 459,475 ****
Long object_del_var(Obj *object, Long name)
{
Int *indp;
Var *var;
/* This is the index-thread equivalent of double pointers in a standard
* linked list. We traverse the list using pointers to the ->next element
* of the variables. */
! indp = &object->vars.hashtab[hash(ident_name(name)) % object->vars.size];
for (; *indp != -1; indp = &object->vars.tab[*indp].next) {
var = &object->vars.tab[*indp];
if (var->name == name && var->cclass == object->objnum) {
/* write_err("##object_del_var %d %s", var->name, ident_name(var->name));*/
ident_discard(var->name);
data_discard(&var->val);
var->name = -1;
--- 459,475 ----
Long object_del_var(Obj *object, Long name)
{
Int *indp;
Var *var;
/* This is the index-thread equivalent of double pointers in a standard
* linked list. We traverse the list using pointers to the ->next element
* of the variables. */
! indp = &object->vars.hashtab[ident_hash(name) % object->vars.size];
for (; *indp != -1; indp = &object->vars.tab[*indp].next) {
var = &object->vars.tab[*indp];
if (var->name == name && var->cclass == object->objnum) {
/* write_err("##object_del_var %d %s", var->name, ident_name(var->name));*/
ident_discard(var->name);
data_discard(&var->val);
var->name = -1;
***************
*** 513,529 ****
/* find the parameter definition in cclass (method object). */
if (!object_find_var(cclass, cclass->objnum, name))
return varnf_id;
/* Get variable slot on object */
var = object_find_var(object, cclass->objnum, name);
if (var) {
! indp=&object->vars.hashtab[hash(ident_name(name))%object->vars.size];
for (; *indp != -1; indp = &object->vars.tab[*indp].next) {
var = &object->vars.tab[*indp];
if (var->name == name && var->cclass == cclass->objnum) {
ident_discard(var->name);
data_discard(&var->val);
var->name = -1;
/* Remove ind from hash table thread, and add it to blanks
--- 513,529 ----
/* find the parameter definition in cclass (method object). */
if (!object_find_var(cclass, cclass->objnum, name))
return varnf_id;
/* Get variable slot on object */
var = object_find_var(object, cclass->objnum, name);
if (var) {
! indp=&object->vars.hashtab[ident_hash(name)%object->vars.size];
for (; *indp != -1; indp = &object->vars.tab[*indp].next) {
var = &object->vars.tab[*indp];
if (var->name == name && var->cclass == cclass->objnum) {
ident_discard(var->name);
data_discard(&var->val);
var->name = -1;
/* Remove ind from hash table thread, and add it to blanks
***************
*** 588,604 ****
new_size = object->vars.size * 2 + MALLOC_DELTA + 1;
object->vars.tab = EREALLOC(object->vars.tab, Var, new_size);
object->vars.hashtab = EREALLOC(object->vars.hashtab, Int, new_size);
/* Refill hash table. */
for (i = 0; i < new_size; i++)
object->vars.hashtab[i] = -1;
for (i = 0; i < object->vars.size; i++) {
! ind = hash(ident_name(object->vars.tab[i].name)) % new_size;
object->vars.tab[i].next = object->vars.hashtab[ind];
object->vars.hashtab[ind] = i;
}
/* Create new thread of blanks, setting names to -1. */
for (i = object->vars.size; i < new_size; i++) {
object->vars.tab[i].name = -1;
object->vars.tab[i].next = i + 1;
--- 588,604 ----
new_size = object->vars.size * 2 + MALLOC_DELTA + 1;
object->vars.tab = EREALLOC(object->vars.tab, Var, new_size);
object->vars.hashtab = EREALLOC(object->vars.hashtab, Int, new_size);
/* Refill hash table. */
for (i = 0; i < new_size; i++)
object->vars.hashtab[i] = -1;
for (i = 0; i < object->vars.size; i++) {
! ind = ident_hash(object->vars.tab[i].name) % new_size;
object->vars.tab[i].next = object->vars.hashtab[ind];
object->vars.hashtab[ind] = i;
}
/* Create new thread of blanks, setting names to -1. */
for (i = object->vars.size; i < new_size; i++) {
object->vars.tab[i].name = -1;
object->vars.tab[i].next = i + 1;
***************
*** 615,647 ****
/* Fill in new variable. */
cnew->name = ident_dup(name);
cnew->cclass = cclass;
cnew->val.type = INTEGER;
cnew->val.u.val = 0;
/* Add variable to hash table thread. */
! ind = hash(ident_name(name)) % object->vars.size;
cnew->next = object->vars.hashtab[ind];
object->vars.hashtab[ind] = cnew - object->vars.tab;
object->dirty = 1;
return cnew;
}
/* Look for a variable on an object. */
static Var *object_find_var(Obj *object, Long cclass, Long name)
{
Int ind;
Var *var;
/* Traverse hash table thread, stopping if we get a match on the name. */
! ind = object->vars.hashtab[hash(ident_name(name)) % object->vars.size];
for (; ind != -1; ind = object->vars.tab[ind].next) {
var = &object->vars.tab[ind];
if (var->name == name && var->cclass == cclass)
return var;
}
return NULL;
}
--- 615,647 ----
/* Fill in new variable. */
cnew->name = ident_dup(name);
cnew->cclass = cclass;
cnew->val.type = INTEGER;
cnew->val.u.val = 0;
/* Add variable to hash table thread. */
! ind = ident_hash(name) % object->vars.size;
cnew->next = object->vars.hashtab[ind];
object->vars.hashtab[ind] = cnew - object->vars.tab;
object->dirty = 1;
return cnew;
}
/* Look for a variable on an object. */
static Var *object_find_var(Obj *object, Long cclass, Long name)
{
Int ind;
Var *var;
/* Traverse hash table thread, stopping if we get a match on the name. */
! ind = object->vars.hashtab[ident_hash(name) % object->vars.size];
for (; ind != -1; ind = object->vars.tab[ind].next) {
var = &object->vars.tab[ind];
if (var->name == name && var->cclass == cclass)
return var;
}
return NULL;
}
***************
*** 823,839 ****
/* Look for a method on an object. */
Method *object_find_method_local(Obj *object, Long name, Bool is_frob)
{
Int ind, method;
Method *meth;
/* Traverse hash table thread, stopping if we get a match on the name. */
! ind = hash(ident_name(name)) % object->methods.size;
method = object->methods.hashtab[ind];
if (is_frob == FROB_ANY) {
for (; method != -1; method = object->methods.tab[method].next) {
meth=object->methods.tab[method].m;
if (meth->name == name)
return object->methods.tab[method].m;
}
}
--- 823,839 ----
/* Look for a method on an object. */
Method *object_find_method_local(Obj *object, Long name, Bool is_frob)
{
Int ind, method;
Method *meth;
/* Traverse hash table thread, stopping if we get a match on the name. */
! ind = ident_hash(name) % object->methods.size;
method = object->methods.hashtab[ind];
if (is_frob == FROB_ANY) {
for (; method != -1; method = object->methods.tab[method].next) {
meth=object->methods.tab[method].m;
if (meth->name == name)
return object->methods.tab[method].m;
}
}
***************
*** 928,944 ****
new_size);
object->methods.hashtab = EREALLOC(object->methods.hashtab, Int,
new_size);
/* Refill hash table. */
for (i = 0; i < new_size; i++)
object->methods.hashtab[i] = -1;
for (i = 0; i < object->methods.size; i++) {
! ind = hash(ident_name(object->methods.tab[i].m->name)) % new_size;
object->methods.tab[i].next = object->methods.hashtab[ind];
object->methods.hashtab[ind] = i;
}
/* Create new thread of blanks and set method pointers to null. */
for (i = object->methods.size; i < new_size; i++) {
object->methods.tab[i].m = NULL;
object->methods.tab[i].next = i + 1;
--- 928,944 ----
new_size);
object->methods.hashtab = EREALLOC(object->methods.hashtab, Int,
new_size);
/* Refill hash table. */
for (i = 0; i < new_size; i++)
object->methods.hashtab[i] = -1;
for (i = 0; i < object->methods.size; i++) {
! ind = ident_hash(object->methods.tab[i].m->name) % new_size;
object->methods.tab[i].next = object->methods.hashtab[ind];
object->methods.hashtab[ind] = i;
}
/* Create new thread of blanks and set method pointers to null. */
for (i = object->methods.size; i < new_size; i++) {
object->methods.tab[i].m = NULL;
object->methods.tab[i].next = i + 1;
***************
*** 953,985 ****
method->name = ident_dup(name);
/* Add method at first blank. */
ind = object->methods.blanks;
object->methods.blanks = object->methods.tab[ind].next;
object->methods.tab[ind].m = method_dup(method);
/* Add method to hash table thread. */
! hval = hash(ident_name(name)) % object->methods.size;
object->methods.tab[ind].next = object->methods.hashtab[hval];
object->methods.hashtab[hval] = ind;
object->dirty = 1;
}
Int object_del_method(Obj *object, Long name) {
Int *indp, ind;
/* Invalidate the method cache. */
cur_stamp++;
/* This is the index-thread equivalent of double pointers in a standard
* linked list. We traverse the list using pointers to the ->next element
* of the method pointers. */
! ind = hash(ident_name(name)) % object->methods.size;
indp = &object->methods.hashtab[ind];
for (; *indp != -1; indp = &object->methods.tab[*indp].next) {
ind = *indp;
if (object->methods.tab[ind].m->name == name) {
/* check the lock at a higher level, this is a better
location to put it, but it causes logistic problems */
/* ack, we found it, but its locked! */
if (object->methods.tab[ind].m->m_flags & MF_LOCK)
--- 953,985 ----
method->name = ident_dup(name);
/* Add method at first blank. */
ind = object->methods.blanks;
object->methods.blanks = object->methods.tab[ind].next;
object->methods.tab[ind].m = method_dup(method);
/* Add method to hash table thread. */
! hval = ident_hash(name) % object->methods.size;
object->methods.tab[ind].next = object->methods.hashtab[hval];
object->methods.hashtab[hval] = ind;
object->dirty = 1;
}
Int object_del_method(Obj *object, Long name) {
Int *indp, ind;
/* Invalidate the method cache. */
cur_stamp++;
/* This is the index-thread equivalent of double pointers in a standard
* linked list. We traverse the list using pointers to the ->next element
* of the method pointers. */
! ind = ident_hash(name) % object->methods.size;
indp = &object->methods.hashtab[ind];
for (; *indp != -1; indp = &object->methods.tab[*indp].next) {
ind = *indp;
if (object->methods.tab[ind].m->name == name) {
/* check the lock at a higher level, this is a better
location to put it, but it causes logistic problems */
/* ack, we found it, but its locked! */
if (object->methods.tab[ind].m->m_flags & MF_LOCK)
diff -C 8 -r ../Genesis-1.0p18/src/include/ident.h src/include/ident.h
*** ../Genesis-1.0p18/src/include/ident.h Tue Oct 22 19:43:37 1996
--- src/include/ident.h Thu Nov 14 16:46:04 1996
***************
*** 28,38 ****
--- 28,39 ----
/* method id's */
extern Ident signal_id;
void init_ident(void);
Ident ident_get(char *s);
void ident_discard(Ident id);
Ident ident_dup(Ident id);
char * ident_name(Ident id);
+ uLong ident_hash(Ident id);
#endif