From: CSBVAX::MRGATE!schmidt@bonnie.ics.uci.edu@SMTP 9-AUG-1988 23:14 To: ARISIA::EVERHART Subj: Minimum perfect hash function for gcc 1.25 reserved words. Received: from rome.ics.uci.edu by prep.ai.mit.edu; Mon, 8 Aug 88 14:40:17 EST Received: from ics.uci.edu by ROME.ICS.UCI.EDU id aa19109; 8 Aug 88 11:38 PDT Received: by ICS.UCI.EDU id ao24043; 8 Aug 88 11:37 PDT Received: from bonnie.ics.uci.edu by ICS.UCI.EDU id aa06567; 6 Aug 88 0:09 PDT To: info-gcc <@beanie.ICS.UCI.EDU:info-gcc@prep.ai.mit.edu> Subject: Minimum perfect hash function for gcc 1.25 reserved words. Date: Sat, 06 Aug 88 00:04:18 -0700 From: "Douglas C. Schmidt" Message-Id: <8808060009.aa06567@ICS.UCI.EDU> Howdy, While preparing for a data structures course I'm currently teaching at University of California, Irvine, I happened upon a program that generates minimum perfect hash functions for sets of reserved words. The code below contains diffs for the parse.y file. This code implements a minimum perfect hash function for the 36 gcc reserved words. For those of a less theoretical bent, a minimum perfect hash function is simply: 1. a hash function and and a data structure that allows recognition of a key word in a set using 1 probe into the data structure. This is the "perfect" part. 2. the data structure holding the reserved words must be precisely large enough for the set of words, and no larger. This is the "minimum" part (which I've relaxed just a tad; purists will note that this relaxation is unnecessary if an offset is subtracted from the hash value). Some informal empirical tests have shown that this implementation is somewhat faster overall than the "original" gcc method (which uses a hash scheme based on the length of the identifer), especially when the files are large and the number of identifiers with 5 and 6 character lengths are high (this is the worst case scenario for the current gcc scheme, since up to 10 comparison may be performed for 6 character identifiers). Of course, for many input files the difference is insignificant, since the running time of the current method is highly dependent on the input characteristics. Regarding the latter point, the biggest practical and theoretical win with the minimum perfect hash function method is the fact that there is simply no "worst case" *identifier* input that causes the lexical analyzer to perform any worse than "usual." I've produced two versions of the minimum perfect hash functions: the current one, which is easier to understand and maintain, and another version, which is less coherent, but smaller and faster. I'll post the latter version in a subsequent message. I'd be interested in hearing from anyone who installs and tests this out (any improvements would be welcome as well!). Don't expect miracles, since reserved word recognition is certainly not the primary determinant of compiler execution speed. As I said before, the main advantage is the consistent lexical analysis performance and the elimination of worst case inputs. Finally, for anyone who is interested, I'll be happy to send out copies of the minimum hash function *generator* program as well. Those of you working on compilers or any program that requires a key word lookup routine may find this *extremely* useful for speeding up important functions. My program derived the minimum perfect hash function for gcc reserved words in about 3 seconds! Hope you enjoy this! Doug Schmidt ------------------------------( Cut Here )------------------------------ *** parse.y.old Fri Aug 5 23:26:21 1988 --- parse.y Fri Aug 5 23:17:09 1988 *************** *** 1219,1281 **** static char *token_buffer; /* Pointer to token buffer. Actual allocated length is maxtoken + 2. */ ! #define MAXRESERVED 9 - /* frw[I] is index in `reswords' of the first word whose length is I; - frw[I+1] is one plus the index of the last word whose length is I. - The length of frw must be MAXRESERVED + 2 so there is an element - at MAXRESERVED+1 for the case I == MAXRESERVED. */ - - static char frw[MAXRESERVED+2] = - { 0, 0, 0, 2, 5, 13, 19, 29, 31, 35, 36 }; - - /* Table of reserved words. */ - - struct resword { char *name; short token; enum rid rid;}; - #define NORID RID_UNUSED ! static struct resword reswords[] ! = {{"if", IF, NORID}, ! {"do", DO, NORID}, ! {"int", TYPESPEC, RID_INT}, ! {"for", FOR, NORID}, ! {"asm", ASM, NORID}, ! {"case", CASE, NORID}, ! {"char", TYPESPEC, RID_CHAR}, ! {"auto", SCSPEC, RID_AUTO}, ! {"goto", GOTO, NORID}, {"else", ELSE, NORID}, - {"long", TYPESPEC, RID_LONG}, - {"void", TYPESPEC, RID_VOID}, {"enum", ENUM, NORID}, - {"float", TYPESPEC, RID_FLOAT}, - {"short", TYPESPEC, RID_SHORT}, - {"union", UNION, NORID}, - {"break", BREAK, NORID}, {"while", WHILE, NORID}, - {"const", TYPE_QUAL, RID_CONST}, - {"double", TYPESPEC, RID_DOUBLE}, - {"static", SCSPEC, RID_STATIC}, {"extern", SCSPEC, RID_EXTERN}, {"struct", STRUCT, NORID}, {"return", RETURN, NORID}, ! {"sizeof", SIZEOF, NORID}, {"typeof", TYPEOF, NORID}, {"switch", SWITCH, NORID}, ! {"signed", TYPESPEC, RID_SIGNED}, ! {"inline", SCSPEC, RID_INLINE}, ! {"typedef", SCSPEC, RID_TYPEDEF}, ! {"default", DEFAULT, NORID}, ! {"unsigned", TYPESPEC, RID_UNSIGNED}, {"continue", CONTINUE, NORID}, ! {"register", SCSPEC, RID_REGISTER}, ! {"volatile", TYPE_QUAL, RID_VOLATILE}, ! {"__alignof", ALIGNOF, NORID}}; /* The elements of `ridpointers' are identifier nodes ! for the reserved type names and storage classes. ! It is indexed by a RID_... value. */ tree ridpointers[(int) RID_MAX]; --- 1219,1343 ---- static char *token_buffer; /* Pointer to token buffer. Actual allocated length is maxtoken + 2. */ ! #define MIN_WORD_SIZE 2 /* minimum size for C reserved words */ ! #define MAX_WORD_SIZE 9 /* maximum size for C reserved words */ ! #define MIN_KEY_SIZE 4 /* range of the hash keys for the */ ! #define MAX_KEY_SIZE 39 /* minimum perfect hash generator */ #define NORID RID_UNUSED ! struct resword {char *name; short token; enum rid rid;}; ! ! static struct resword reswords[] ! = {{NULL, 0, NORID}, ! {NULL, 0, NORID}, /* these locations are not used. */ ! {NULL, 0, NORID}, /* they simplify the hashing. */ ! {NULL, 0, NORID}, {"else", ELSE, NORID}, {"enum", ENUM, NORID}, {"while", WHILE, NORID}, {"extern", SCSPEC, RID_EXTERN}, + {"double", TYPESPEC, RID_DOUBLE}, + {"default", DEFAULT, NORID}, + {"do", DO, NORID}, + {"goto", GOTO, NORID}, + {"short", TYPESPEC, RID_SHORT}, {"struct", STRUCT, NORID}, {"return", RETURN, NORID}, ! {"signed", TYPESPEC, RID_SIGNED}, ! {"float", TYPESPEC, RID_FLOAT}, {"typeof", TYPEOF, NORID}, + {"typedef", SCSPEC, RID_TYPEDEF}, {"switch", SWITCH, NORID}, ! {"int", TYPESPEC, RID_INT}, ! {"for", FOR, NORID}, ! {"register", SCSPEC, RID_REGISTER}, ! {"inline", SCSPEC, RID_INLINE}, ! {"sizeof", SIZEOF, NORID}, ! {"void", TYPESPEC, RID_VOID}, ! {"__alignof", ALIGNOF, NORID}, ! {"volatile", TYPE_QUAL, RID_VOLATILE}, ! {"case", CASE, NORID}, ! {"const", TYPE_QUAL, RID_CONST}, ! {"if", IF, NORID}, ! {"long", TYPESPEC, RID_LONG}, {"continue", CONTINUE, NORID}, ! {"asm", ASM, NORID}, ! {"union", UNION, NORID}, ! {"char", TYPESPEC, RID_CHAR}, ! {"break", BREAK, NORID}, ! {"static", SCSPEC, RID_STATIC}, ! {"unsigned", TYPESPEC, RID_UNSIGNED}, ! {"auto", SCSPEC, RID_AUTO}}; + /* This function performs the minimum-perfect hash mapping from input + string to reswords table index. It only looks at the first and + last characters in the string, thus assuring the O(1) lookup time + (this keeps our constant down to an insignificant amount!). Compiling + the following 2 functions as inline removes all overhead of the + function calls. */ + + #ifdef __GNUC__ + inline static int hash (char *str,int len) + #else + static int hash (str,len) + register char *str; + register int len; + #endif + { + /* This table is used to build the hash table index that recognizes + reserved words in 0(1) steps. It is larger than strictly necessary, + but I'm trading off the space for the time-saving luxury of avoiding + subtraction of an offset. */ + + static char hash_table[] + = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 6, 0, 29, 31, 24, + 2, 0, 11, 1, 6, 17, 0, 0, 26, 1, + 1, 6, 0, 0, 7, 7, 0, 28, 19, 1, + 0, 0, 0, 0, 0, 0, 0, 0}; + + /* The hash function couldn't be simpler: add the length of the string + to the Hash_Table value of its first and last character. */ + + return len + hash_table[ (int) str[0]] + hash_table[ (int) str[len - 1]]; + } + + /* This routine attempts to match the string found in the Word_Table with + the one from the input stream. If all the relevant details match an + actual strcmp comparison is performed. */ + + #ifdef __GNUC__ + inline struct resword *is_reserved_word (char *str,int len) + #else + struct resword *is_reserved_word (str,len) + register char *str; + register int len; + #endif + { + if (len <= MAX_WORD_SIZE && len >= MIN_WORD_SIZE) + { + register int key = hash (str,len); + + if (key >= MIN_KEY_SIZE && key <= MAX_KEY_SIZE) + if (reswords[key].name[0] == str[0] + && !strcmp (reswords[key].name + 1,str + 1)) + return &reswords[key]; + } + return NULL; + } + /* The elements of `ridpointers' are identifier nodes ! for the reserved type names and storage classes. ! It is indexed by a RID_... value. */ tree ridpointers[(int) RID_MAX]; *************** *** 1810,1844 **** value = IDENTIFIER; yylval.itype = 0; ! /* Try to recognize a keyword. */ ! if (p - token_buffer <= MAXRESERVED) ! { ! register int lim = frw [p - token_buffer + 1]; ! register int i = frw[p - token_buffer]; ! register struct resword *p = &reswords[i]; ! ! for (; i < lim; i++, p++) ! if (p->name[0] == token_buffer[0] ! && !strcmp (p->name, token_buffer)) ! { ! if (p->rid) ! yylval.ttype = ridpointers[(int) p->rid]; ! if ((! flag_no_asm ! || ((int) p->token != ASM ! && (int) p->token != TYPEOF ! && strcmp (p->name, "inline"))) ! /* -ftraditional means don't recognize ! typeof, const, volatile, signed or inline. */ ! && (! flag_traditional ! || ((int) p->token != TYPE_QUAL ! && (int) p->token != TYPEOF ! && strcmp (p->name, "signed") ! && strcmp (p->name, "inline")))) ! value = (int) p->token; ! break; ! } ! } /* If we did not find a keyword, look for an identifier (or a typename). */ --- 1872,1900 ---- value = IDENTIFIER; yylval.itype = 0; ! /* Try to recognize a keyword. Uses minimum-perfect hash function */ ! ! { ! register struct resword *ptr; ! if (ptr = is_reserved_word (token_buffer,p - token_buffer)) ! { ! if (ptr->rid) ! yylval.ttype = ridpointers[(int) ptr->rid]; ! if ((! flag_no_asm ! || ((int) ptr->token != ASM ! && (int) ptr->token != TYPEOF ! && ptr->rid != RID_INLINE)) /* why waste a strcmp? */ ! /* -ftraditional means don't recognize ! typeof, const, volatile, signed or inline. */ ! && (! flag_traditional ! || ((int) ptr->token != TYPE_QUAL ! && (int) ptr->token != TYPEOF ! && ptr->rid != RID_SIGNED /* again, no need for */ ! && ptr->rid != RID_INLINE))) /* a function call. */ ! value = (int) ptr->token; ! } ! } /* If we did not find a keyword, look for an identifier (or a typename). */