Synopsis: Optimizing Envy2's race_lookup() with a hash table. July 96 Date: Mon, 1 Jul 1996 22:32:52 +0200 (MET DST) From: erwin@pip.dknet.dk To: MERC/Envy Mailing List Subject: Envy2: race_lookup() optimizations I have played with profiling my Envy2 MUD, and found out that race_lookup() is called quite a number of times. After running for a few minutes, race_lookup() called str_prefix() about 2.2 million times. race_lookup() is called mainly by hit_gain() which compares the player's race to about 12 different races to compute extra hit point gain. This was in a very small world, with no more than 500 mobs. However, my world's hitpoints/mana/move are updated 5 seconds, so the number in your case might be a bit different. According to my gprof output, it took about 30% of the MUD's time. Anyway, it's still a lot. Assuming a world with 3000 active mobiles/players, 17 race_lookups in hit_gain(), move_gain() and mana_gain() it means about 50,000 calls to race_lookup() each tick. Let us assume that on the average, the race we are looking up is found in 1/4 of the race table (which has 41 entries). This means 1/2 million calls to str_prefix() each 30 seconds. The simple optimization is to add three additional fields to the race_data structure, namely extra hp, mana and move gain. Envy2 gives a set number of hp, no matter what level the mob is, but a percentage gain for mana and move - I am not sure how you would want to handle it, but I have changed them all to be relative (i.e. Gods regenerate 3 times as fast, Dwarves regenerate 20% faster). One could even imagine a "Gargoyle" race, made completely out of inorganic material, that would require use of some special spells to regenerate "tissue", and would have a hp regeneration rate of 0. Then get rid of all the race_lookup() calls in hit/mana/move_gain(), and replace them with something like: gain = (gain * race_table[ch->race].hp_gain) / 100; (i.e. a 100 gain would mean normal speed). Something like this could be made for thirst and hunger as well - let the number be a percent chance to lose one unit instead of always calling gain_condition, with values over 100 meaning that the character always loses one unit of food, and has (remaining percent - 100) % chance of losing another. Anyway, there was still a lot of calls to race_lookup(), so I have created these functions to hash the table. The algorithms could probably be optimized further - perhaps using the sum of the first two letters as the hash index, instead of just the first one, thus gaining nearly a perfect hash key (at present, there are 7 races starting with 'h). Or even first letter + length of string. Though, that would require that all strings are typed in fully, as the current race_lookup() allows prefixes. Ensure that you call init_race_hash_table() before any calls to the new race_lookup() - it must be in boot_db(), before any loading of areas happens. The pointer arithmethics (node - race_table) might look funny, but is perfectly all right. I suppose that the size of the hash table could be lowered, so that the base is 'a', having only 25 entries. I thought of that after a pasted this, so if you want to save 400 bytes of memory, go ahead and change it :) PS: While profiling, it is necessary to change at least the two select() calls to not to exit if there is an EINTR error. It should I suppose also be necessary for the reads/writes, but I did not receive any error there. The general construction would be: while (select (....) < 0) if (errno != EINTR) { perror ("..."); exit(1); } struct race_hash_node { struct race_hash_node * next; const struct race_type * race; }; #define MAX_RACE_HASH 128 static struct race_hash_node * race_hash_table [MAX_RACE_HASH]; void init_race_hash_table () { int c, i; for (i = 0; i < MAX_RACE; i++) { struct race_hash_node * node; node = alloc_perm (sizeof (struct race_hash_node)); node->race = &race_table[i]; c = LOWER(race_table[i].name[0]); if (c <= 0 || c >= MAX_RACE_HASH) { bugf ("Race %d has illegal name: %s", i, race_table[i].name); exit (1); } node->next = race_hash_table[c]; race_hash_table[c] = node; } } #define RACE_NOTFOUND -1 int race_lookup (const char * race) { int c; struct race_hash_node * node; c = LOWER(race[0]); /* Our hash key is the first letter */ if (c <= 0 || c >= MAX_RACE_HASH) { bugf ("race_lookup() called with illegal name: %s", race); return RACE_NOTFOUND; } for (node = race_hash_table[c]; node; node = node->next) if (!str_prefix (race, node->race->name)) return (node->race - race_table); return RACE_NOTFOUND; } /* bugf - a handy little thing - remember to #include stdarg.h */ void bugf (char * fmt, ...) { char buf [MAX_STRING_LENGTH]; va_list args; va_start (args, fmt); vsprintf (buf, fmt, args); va_end (args); bug (buf, 0); } ============================================================================== Erwin Andreasen Viby J, Denmark Computer Science Student at Aarhus Business 4u2@aabc.dk Click here! College ==============================================================================