[frontierkernel-commits] Frontier/Common/source langhash.c,1.4.2.24,1.4.2.25 langops.c,1.3.2.1,1.3.2.2

[Andre R. <and...@us...>]

Update of /cvsroot/frontierkernel/Frontier/Common/source
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv32621/Common/source

Modified Files:
      Tag: New_Tables_Experiment-branch
	langhash.c langops.c 
Log Message:
First cut at hash-once optimizations: The new hash function is more costly in terms of CPU cycles than the old one. Luckily, we can compensate for this by reducing the number of times the hash value of the node key will be computed. For example, for a UserTalk identifier, the hash value only really needs to be computed once at compile time. Initially, we start this optimization in the low-level hash table functions in langhash.c and then let it percolate upwards. There is a compatibility layer for existing code implemented as pre-processor macros in lang.h.

Index: langops.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/langops.c,v
retrieving revision 1.3.2.1
retrieving revision 1.3.2.2
diff -C2 -d -r1.3.2.1 -r1.3.2.2
*** langops.c	21 Nov 2004 15:04:35 -0000	1.3.2.1
--- langops.c	17 Dec 2004 13:15:00 -0000	1.3.2.2
***************
*** 382,385 ****
--- 382,386 ----
  	register boolean flspecialsymbol = false;
  	register short n;
+ 	tyhashval hashval = hashfunction (bs);
  	
  	*htable = nil;
***************
*** 406,410 ****
  		if ((!(**h).fllocaltable) || flspecialsymbol || (refcon == 0) || (lexrefcon == refcon) || (lexrefcon == 0)) {
  			
! 			if (hashtablelookupnode (h, bs, hnode)) { /*symbol is defined in htable*/
  				
  				*htable = h;
--- 407,411 ----
  		if ((!(**h).fllocaltable) || flspecialsymbol || (refcon == 0) || (lexrefcon == refcon) || (lexrefcon == 0)) {
  			
! 			if (hashtablekeylookupnode (h, bs, hashval, hnode)) { /*symbol is defined in htable*/
  				
  				*htable = h;
***************
*** 437,441 ****
  					}
  
! 				if (hashtablelookupnode (hwith, bs, hnode)) { /*found symbol*/
  					
  					*htable = hwith;
--- 438,442 ----
  					}
  
! 				if (hashtablekeylookupnode (hwith, bs, hashval, hnode)) { /*found symbol*/
  					
  					*htable = hwith;

Index: langhash.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/langhash.c,v
retrieving revision 1.4.2.24
retrieving revision 1.4.2.25
diff -C2 -d -r1.4.2.24 -r1.4.2.25
*** langhash.c	15 Dec 2004 21:36:21 -0000	1.4.2.24
--- langhash.c	17 Dec 2004 13:14:59 -0000	1.4.2.25
***************
*** 1282,1286 ****
  #if 0
  
! 	unsigned long hashfunction (const bigstring bskey) {
  		
  		/*
--- 1282,1286 ----
  #if 0
  
! 	tyhashval hashfunction (const bigstring bskey) {
  		
  		/*
***************
*** 1333,1337 ****
  	#define getuchar(d) ((unsigned long)(getlower (d)))
  	
! 	unsigned long hashfunction (const bigstring bskey) {
  	
  		/*
--- 1333,1337 ----
  	#define getuchar(d) ((unsigned long)(getlower (d)))
  	
! 	tyhashval hashfunction (const bigstring bskey) {
  	
  		/*
***************
*** 1405,1409 ****
  #if 0
  
! 	long hashfunction (const bigstring bs) {
  		
  		/*
--- 1405,1409 ----
  #if 0
  
! 	tyhashval hashfunction (const bigstring bs) {
  		
  		/*
***************
*** 1470,1474 ****
  	tyvaluerecord val1, val2;
  	register tyvaluetype t1, t2;
! 	
  	val1 = (***(hdlhashnode *)hnode1).val;
  	
--- 1470,1474 ----
  	tyvaluerecord val1, val2;
  	register tyvaluetype t1, t2;
! 
  	val1 = (***(hdlhashnode *)hnode1).val;
  	
***************
*** 1523,1527 ****
  	register boolean flequal = false;
  	boolean flcomparable;
! 	
  	flcomparable = (**h1).val.valuetype == (**h2).val.valuetype;
  	
--- 1523,1527 ----
  	register boolean flequal = false;
  	boolean flcomparable;
! 
  	flcomparable = (**h1).val.valuetype == (**h2).val.valuetype;
  	
***************
*** 1811,1818 ****
  	/*
  	a sure-fire hash-algorithm-independent way to unlink a node.
  	*/
  	
! 	register long i;
! 	register hdlhashnode nomad, prev;
  	
  	for (i = 0; i < gethashbucketcount (htable); i++) {
--- 1811,1831 ----
  	/*
  	a sure-fire hash-algorithm-independent way to unlink a node.
+ 
+ 	2004-12-17 aradke: can't hurt to check the bucket first that *should* contain hnode
  	*/
  	
! 	register long i = hashtobucketindex (htable, (**hnode).hashval);
! 	register hdlhashnode nomad = nthhashbucket (htable, i);
! 	register hdlhashnode prev = nil;
! 	
! 	while (nomad != nil) {	/*2004-12-17 aradke*/
! 		
! 		if (nomad == hnode) /*found it*/
! 			goto afterloop;
! 			
! 		prev = nomad;
! 		
! 		nomad = (**nomad).hashlink;
! 		} /*while*/
  	
  	for (i = 0; i < gethashbucketcount (htable); i++) {
***************
*** 1835,1839 ****
  	return (false); /*not found*/
  	
! 	afterloop:
  	
  	if (prev == nil) 
--- 1848,1852 ----
  	return (false); /*not found*/
  	
! afterloop:
  	
  	if (prev == nil) 
***************
*** 2052,2056 ****
  */
  
! boolean hashlocate (const bigstring bs, hdlhashnode *hnode, hdlhashnode *hprev) {
  
  	/*
--- 2065,2069 ----
  */
  
! boolean hashkeylocate (const bigstring bs, tyhashval hashval, hdlhashnode *hnode, hdlhashnode *hprev) {
  
  	/*
***************
*** 2058,2064 ****
  	begins with a $, we return the node and prev for the nth guy in the sorted
  	list of the table.
  	*/
  	
- 	register long ixbucket;
  	register hdlhashnode nomad, nomadprev;
  	
--- 2071,2083 ----
  	begins with a $, we return the node and prev for the nth guy in the sorted
  	list of the table.
+ 	
+ 	2004-11-24 aradke: depend on caller to provide hashval instead of calling
+ 	hashfunction ourselves. this will allow us to calculate the hash just
+ 	once if we need to look up the same key in several tables (i.e. search
+ 	path lookups during language execution) or if we need to check whether
+ 	a key already exists before inserting. later, we may want to put bs
+ 	and hashval into a new struct type, possibly to be called tyhashkey.
  	*/
  	
  	register hdlhashnode nomad, nomadprev;
  	
***************
*** 2072,2082 ****
  	*/
  	
! 	ixbucket = hashtobucketindex (currenthashtable, hashfunction (bs));
! 
! 	//assert (currenthashtable != nil);
! 
! 	//assert (validhandle ((Handle) currenthashtable));
  	
! 	nomad = nthhashbucket (currenthashtable, ixbucket);
  	
  	nomadprev = nil;
--- 2091,2097 ----
  	*/
  	
! 	assert (hashfunction (bs) == hashval);
  	
! 	nomad = gethashbucket (currenthashtable, hashval);
  	
  	nomadprev = nil;
***************
*** 2084,2088 ****
  	while (nomad != nil) {
  		
! 		if (equalidentifiers (bs, (**nomad).hashkey)) {
  		
  			*hnode = nomad;
--- 2099,2103 ----
  	while (nomad != nil) {
  		
! 		if (/*(hashval == (**nomad).hashval) && */ equalidentifiers (bs, (**nomad).hashkey)) {
  		
  			*hnode = nomad;
***************
*** 2099,2106 ****
  		
  	return (false); /*loop terminated, not found*/
! 	} /*hashlocate*/
  
  
! static boolean hashdeletenode (const bigstring bs, hdlhashnode *hnode) {
  	
  	/*
--- 2114,2121 ----
  		
  	return (false); /*loop terminated, not found*/
! 	} /*hashkeylocate*/
  
  
! static boolean hashkeydeletenode (const bigstring bs, tyhashval hashval, hdlhashnode *hnode) {
  	
  	/*
***************
*** 2115,2119 ****
  	register hdlhashnode hn;
  	
! 	if (!hashlocate (bs, hnode, &hprev)) {
  	
  		langparamerror (cantdeleteerror, bs);
--- 2130,2134 ----
  	register hdlhashnode hn;
  	
! 	if (!hashkeylocate (bs, hashval, hnode, &hprev)) {
  	
  		langparamerror (cantdeleteerror, bs);
***************
*** 2126,2135 ****
  	langsymbolunlinking (currenthashtable, hn);
  	
! 	if (hprev == nil) {
! 	
! 		assert ((**hn).hashval == hashfunction (bs));
! 
! 		nthhashbucket (currenthashtable, hashtobucketindex (currenthashtable, (**hn).hashval)) = (**hn).hashlink;
! 		}
  	else 
  		(**hprev).hashlink = (**hn).hashlink;
--- 2141,2146 ----
  	langsymbolunlinking (currenthashtable, hn);
  	
! 	if (hprev == nil)
! 		sethashbucket (currenthashtable, hashval, (**hn).hashlink);
  	else 
  		(**hprev).hashlink = (**hn).hashlink;
***************
*** 2140,2147 ****
  
  	return (true);
! 	} /*hashdeletenode*/
  	
  
! boolean hashunlink (const bigstring bs, hdlhashnode *hnode) {
  		
  	/*
--- 2151,2158 ----
  
  	return (true);
! 	} /*hashkeydeletenode*/
  	
  
! boolean hashkeyunlink (const bigstring bs, tyhashval hashval, hdlhashnode *hnode) {
  		
  	/*
***************
*** 2150,2154 ****
  	*/
  
! 	if (!hashdeletenode (bs, hnode))
  		return (false);
  
--- 2161,2165 ----
  	*/
  
! 	if (!hashkeydeletenode (bs, hashval, hnode))
  		return (false);
  
***************
*** 2158,2165 ****
  	
  	return (true);
! 	} /*hashunlink*/
  
  
! boolean hashdelete (const bigstring bs, boolean fldisposevalue, boolean fldisk) {
  	
  	/*
--- 2169,2176 ----
  	
  	return (true);
! 	} /*hashkeyunlink*/
  
  
! boolean hashkeydelete (const bigstring bs, tyhashval hashval, boolean fldisposevalue, boolean fldisk) {
  	
  	/*
***************
*** 2170,2174 ****
  	hdlhashnode hn;
  	
! 	if (!hashdeletenode (bs, &hn))
  		return (false);
  	
--- 2181,2185 ----
  	hdlhashnode hn;
  	
! 	if (!hashkeydeletenode (bs, hashval, &hn))
  		return (false);
  	
***************
*** 2180,2187 ****
  	
  	return (true);
! 	} /*hashdelete*/
  
  
! boolean hashtabledelete (hdlhashtable htable, bigstring bs) {
  	
  	boolean fl;
--- 2191,2198 ----
  	
  	return (true);
! 	} /*hashkeydelete*/
  
  
! boolean hashtablekeydelete (hdlhashtable htable, bigstring bs, tyhashval hashval) {
  	
  	boolean fl;
***************
*** 2190,2221 ****
  		return (false);
  	
! 	fl = hashdelete (bs, true, true);
  	
  	pophashtable ();
  
  	return (fl);
! 	} /*hashtabledelete*/
  
  
! boolean hashsymbolexists (const bigstring bs) {
  	
! 	hdlhashnode hnode, hprev;
  	
! 	return (hashlocate (bs, &hnode, &hprev));
! 	} /*hashsymbolexists*/
  
  
! boolean hashtablesymbolexists (hdlhashtable htable, const bigstring bs) {
  	
  	boolean fl;
  	
  	pushhashtable (htable);
  	
! 	fl = hashsymbolexists (bs);
  	
  	pophashtable ();
  	
  	return (fl);
! 	} /*hashtablesymbolexists*/
  
  
--- 2201,2246 ----
  		return (false);
  	
! 	fl = hashkeydelete (bs, hashval, true, true);
  	
  	pophashtable ();
  
  	return (fl);
! 	} /*hashtablekeydelete*/
  
  
! boolean hashkeyexists (const bigstring bs, tyhashval hashval) {
  	
! 	/*
! 	2004-12-17 aradke: for performance, duplicate loop from hashkeylocate
! 	without keeping track of prev node.
! 	*/
! 
! 	register hdlhashnode nomad;
  	
! 	assert (hashfunction (bs) == hashval);
! 	
! 	for (nomad = gethashbucket (currenthashtable, hashval); nomad != nil; nomad = (**nomad).hashlink) {
! 		
! 		if (equalidentifiers (bs, (**nomad).hashkey))
! 			return (true);
! 		} /*for*/
! 		
! 	return (false); /*loop terminated, not found*/
! 	} /*hashkeyexists*/
  
  
! boolean hashtablekeyexists (hdlhashtable htable, const bigstring bs, tyhashval hashval) {
  	
+ 	hdlhashnode hnode, hprev;
  	boolean fl;
  	
  	pushhashtable (htable);
  	
! 	fl = hashkeylocate (bs, hashval, &hnode, &hprev);
  	
  	pophashtable ();
  	
  	return (fl);
! 	} /*hashtablekeyexists*/
  
  
***************
*** 2591,2595 ****
  
  
! boolean hashlookup (const bigstring bs, tyvaluerecord *vreturned, hdlhashnode *hnode) {
  	
  	/*
--- 2616,2620 ----
  
  
! boolean hashkeylookup (const bigstring bs, tyhashval hashval, tyvaluerecord *vreturned, hdlhashnode *hnode) {
  	
  	/*
***************
*** 2599,2603 ****
  	hdlhashnode hprev;
  	
! 	if (!hashlocate (bs, hnode, &hprev)) 
  		return (false);
  	
--- 2624,2628 ----
  	hdlhashnode hprev;
  	
! 	if (!hashkeylocate (bs, hashval, hnode, &hprev)) 
  		return (false);
  	
***************
*** 2608,2615 ****
  	
  	return (true);
! 	} /*hashlookup*/
  	
  
! boolean hashtablelookup (hdlhashtable htable, const bigstring bs, tyvaluerecord *vreturned, hdlhashnode *hnode) {
  	
  	boolean fl;
--- 2633,2640 ----
  	
  	return (true);
! 	} /*hashkeylookup*/
  	
  
! boolean hashtablekeylookup (hdlhashtable htable, const bigstring bs, tyhashval hashval, tyvaluerecord *vreturned, hdlhashnode *hnode) {
  	
  	boolean fl;
***************
*** 2618,2633 ****
  		return (false);	/*so the check is done here.*/
  	
- 	
  	pushhashtable (htable);
  	
! 	fl = hashlookup (bs, vreturned, hnode);
  	
  	pophashtable ();
  	
  	return (fl);
! 	} /*hashtablelookup*/
  
  
! boolean hashlookupnode (const bigstring bs, hdlhashnode *hnode) {
  	
  	/*
--- 2643,2657 ----
  		return (false);	/*so the check is done here.*/
  	
  	pushhashtable (htable);
  	
! 	fl = hashkeylookup (bs, hashval, vreturned, hnode);
  	
  	pophashtable ();
  	
  	return (fl);
! 	} /*hashtablekeylookup*/
  
  
! boolean hashkeylookupnode (const bigstring bs, tyhashval hashval, hdlhashnode *hnode) {
  	
  	/*
***************
*** 2637,2648 ****
  	hdlhashnode hprev;
  	
! 	if (!hashlocate (bs, hnode, &hprev))
  		return (false);
  	
  	return (hashresolvevalue (currenthashtable, *hnode));
! 	} /*hashlookupnode*/
  
  
! boolean hashtablelookupnode (hdlhashtable htable, const bigstring bs, hdlhashnode *hnode) {
  	
  	boolean fl;
--- 2661,2672 ----
  	hdlhashnode hprev;
  	
! 	if (!hashkeylocate (bs, hashval, hnode, &hprev))
  		return (false);
  	
  	return (hashresolvevalue (currenthashtable, *hnode));
! 	} /*hashkeylookupnode*/
  
  
! boolean hashtablekeylookupnode (hdlhashtable htable, const bigstring bs, tyhashval hashval, hdlhashnode *hnode) {
  	
  	boolean fl;
***************
*** 2650,2659 ****
  	pushhashtable (htable);
  	
! 	fl = hashlookupnode (bs, hnode);
  	
  	pophashtable ();
  	
  	return (fl);
! 	} /*hashtablelookupnode*/
  
  
--- 2674,2683 ----
  	pushhashtable (htable);
  	
! 	fl = hashkeylookupnode (bs, hashval, hnode);
  	
  	pophashtable ();
  	
  	return (fl);
! 	} /*hashtablekeylookupnode*/