String Hashing and load_helps

While skimming through db.c I noticed that the helpfile keywords and the text itself was being loaded into the hash tables. My understanding of hashtables is that they are only truly benefitical if the string is allocated frequently. Like a mob's name. Is there a particular reason why the help file keywords and the text is loaded into the hash tables? Afterall, what is likelyhood that those particular strings would be allocated again?

As a test I used the 'memory hash' command to get these stats:

(w/ help hashing)
Hash strings allocated: 11246 Total links : 56616
String bytes allocated: 1475140 Bytes saved : 802275
Unique (wasted) links : 7388 Hi-Link count: 27932

(wo/ hashing)
Hash strings allocated: 9823 Total links : 55276
String bytes allocated: 1084862 Bytes saved : 813839
Unique (wasted) links : 5965 Hi-Link count: 28006

I not only decreased my unique links but I increased my saved bytes. Anyone have a good reason why this shouldn't be done?

All I changed was this bit of code in load_helps:

pHelp->level = fread_number( fp );
pHelp->keyword = fread_string_nohash( fp );
if ( pHelp->keyword[0] == '$' )
break;
pHelp->text = fread_string_nohash( fp );

Changing both 'fread_string_nohash' from their original 'fread_string'

The benefit with helpfiles would be in processor load and response times. Usually helpfiles are meant to be a near instant response, which they will be if theyre already loaded into the hash tables. Otherwise there is a potentially sizeable delay in the lookup responses.

Explain "loaded". Regardless of if they are being loaded into the hashtables or not, they are not being re-read from disk. The only thing the string hashtables do is prevent duplicates, and potentially speed the memory allocation process. This should have little to NO affect on the cpu at all. In fact it could possibly improve it, considering there are less unique links to weed through on each hashtable allocation. If a particular string only needs to be allocated once (for example a players 'normally' unique password) then hashing is a waste due to the small but no less significant overhead of the hashing struct. However something like the name of a clan, which is likely allocated many times over in all sorts of places benefit from string hashing due to the fact that the memory space is already allocated. Correct me if I'm wrong someone, but it seems pretty clear to me that's how things work.

Well, I grew curious upon seeing this and decided to see what kind of difference it made in overal allocation. So here's my results on my CVS port:

Helpfiles hashed:

Hash statistics:
Hash strings allocated: 9665 Total links : 36910
String bytes allocated: 1511238 Bytes saved : 300044
Unique (wasted) links : 7586 Hi-Link count: 10294

samson 19563 0.6 1.1 11516 8712 pts/3 RN 04:50 0:01 ../src/afkmud 9500


Helpfiles NOT hashed:

Hash statistics:
Hash strings allocated: 7308 Total links : 34484
String bytes allocated: 841334 Bytes saved : 316439
Unique (wasted) links : 5270 Hi-Link count: 10290

samson 19535 0.6 1.1 11500 8740 pts/3 RN 04:53 0:01 ../src/afkmud 9500

The last line in each is the system usage each boot up generated. As you can see, no real difference in that, but the hash table usage is significantly improved by not hashing your helps.

As for lookup times, I wasn't able to see a difference in that either. Ram is ram, you'll hardly be able to perceive a nanosecond level difference :)

After this, I looked around at other things that may be similar. The only other thing that I've thought of changing are player bios/descs. They are usually quite unique yet are being loaded into the hashtables as well. Though I think you could probably live with that overhead, which works out to about 16 additional bytes per connected player, for hashing.

Something to remember with the hashing tables.... the original code was written to support 1000s of users on a *nix platform for weeks at a time with ease. With that much userload, having the helps referenced in the hashing tables actually makes sense, but for the 20-30 most muds seem to cap at for userload anymore it doesnt make a whole lot of difference.

You have the wrong end of the stick here. Hash tables are not intended to save memory or speed up the allocation process, and preventing duplicates is merely a side-effect.

The point of hashing, where you have many of something (eg. helps) is to speed up subsequent finding of the hashed data. For example the helps consist of over 1,000 topics, without hashing you would require a linear seach, requiring an average of 500 string compares to find a particular one.

However with hashed helps you would hash the word you are looking for (an arithmetic calculation that should take few CPU cycles), then index straight into the hash table to find the target help.

In other words, you are trading off memory usage for extra speed. Remember these programs were written in the days when CPUs were fairly slow.

I would not expect them to be re-read from disk - the purpose of hashing is not to speed the allocation process, but the search process.

I understand that. I understand the use of modulus to index the array of links. I understand that 100 links is far quicker to whip through, then 100,000 links. What I don't understand is how exactly is smaug utilizing this for individual strings and ultimately help files? I can clearly see how the hash tables are utilized for mobs, rooms, commands and objects and the like, and I clearly understand that not hashing those items would not be smart. But take this loop for example(act_info.c):

for ( pHelp = first_help; pHelp; pHelp = pHelp->next )

This loop.. regardless of string hashing or not, it still loops through all help files and still compares the arguments with each keyword, using str_cmp (via is_name). So where's the indexing coming in? It's not.

I realize I may have made my explanation of 'hash tables' a bit vauge. I'm specifically talking about the hashing of individual strings. Specifically the use of the functions in 'hashstr.c'. How is this being utilized to create a 'faster' search? If that was so, every comparison of 'if string = anotherstring' would have to utilize a modulus value of sorts. My understanding of the hashtable utilized for strings gives no benefits beyond that of memory saving and prevention of duplicates. Take a look for yourself.

I should also point out my original post was in regards to string hashing only, and the fact that the keywords and such have no need to be in a hashtable unless it was utilized differently.

(laughs) - Yes, I see it now. :)

I made the assumption - and we all know how you shouldn't make assumptions - that if they hashed the helps they would have done a hashed lookup.

I withdraw my comments in regards to the SMAUG help, although my general explanation was good for why you would, in general, hash the keys for a large list.

Seems like the SMAUG implementors read about how useful hash tables were, but didn't quite understand how to use them.

I also agree there isn't much point to hashing the help text itself, can't see how useful that is.

Heh. I kinda thought that's what had happened. I knew I wasn't *THAT* crazy ;-) Anywho, I've actually decided that I may go ahead and hash them properly and see what kind of difference it may make. Although it may not really be perceivable. It may actually do what was originally intended.

Also, if you notice, they ARE using the hashed strings, but they are using them to see if another link to that pointer should be made, or if a new one should be created. In regards to the functions within hashstr.c I don't think they ever intended that particular set of functions to speed 'searching' beyond it's own uses.

OK, it is a form of reference counting, I suppose there is some sense to that.