From: mmcg@cs.monash.edu.au (Mike  Mc Gaughey)
Subject: Re: Darker Realms - The Mudlib
Organization: Computer Science, Monash University, Australia
Date: Thu, 20 Aug 1992 06:44:11 GMT

amylaar@mcshh.Hanse.DE (Joern Rennecke) writes:
>mmcg@cs.monash.edu.au (Mike  Mc Gaughey) writes:
>>amylaar@opal.cs.tu-berlin.de (J"orn Rennecke) and
>>>d8andjo@dtek.chalmers.se (Johan Andersson) snipe:

>>>>In article <1992Aug13.035858.26673@cs.tu-berlin.de> amylaar@opal.cs.tu-berlin.de (J"orn Rennecke) writes:
>>>>
>>>>Or by rewriting the switch-case code. Few switches are longer than 5-10

>>size?  (hell, there has to be an optimal size under which you compile

>Huh? what kind of optimal size do you mean? switch can handle case label lists
>from a single one to as much code as a struct program can handle.

A size under which compiling it to if/then type constructs, rather than
a perfect hash table and/or binary search (choose whichever you prefer)
will be faster.  Remember, with under about 9 switch cases, a looping
linear search is faster than a binary search anyway (but it's a small
part of total execution time anyway, so I'll not be bothering :)

>Both is hashed on pointers. But the CD driver uses different pointers for the
>same string more often.

Pointers to WHAT, you moron?  Strings?  String pointer XOR object pointer?
Different pointers for the same string implies a better hit ratio if you're
not taking the object pointer into account (but this should be obvious anyway).

>>    Hash table size/implementation?
>size: read th postings		implementation: read the source.

Oh, lah dee fucking dah.  You want to poke fun at other people's implementations,
you need to be able to describe your own.

>>Profile it - how much time is spent in inserting shared strings?

>This can't be done well, since the overall locality of the program is affected
>when you have extra shared strings. Strings that are added together are likely
>to be unique strings, and quite long ones at that. Having them in the hash
>chains means to reference this otherwise seldomly referenced part of memory
>every time a string is newly created in this hash chain.

>Do you have any profilers for THAT ?

Paging behaviour.  Yeah, I have, but only gross tools like 'top' and 'ps' :)

This is actually quite interesting - since they are seldom referenced,
do we care that we have to take extra time hashing on them anyway?
Traversing a complete hash chain is a matter of about 8 or ten probes
maximum (if it isn't, you need to increase your hash table size);
average probe length is of the order of 1.5 or so for us.

If you are _serious_ about decreasing this sort of swap wait, you could
allocate special string spaces for various sized strings; about 95% of
references are to short strings, so this should improve your paging
behaviour.  But again, I don't think the statistics justify it - long
strings tend to migrate to the end of hash chains anyway, and are
referenced far less (and most of the time, strings being added are
found already in the table - since they're being added another time,
they are in the "more frequently used" set, and so are usually near the
head of a chain anyway).

>>How much time does string hashing take (% of total CPU)?  Which of the (various)
>This will depend a lot on the way your CPU handles the modulo operator.
>could be replaced with a multiplication,

Yes, but HOW MUCH TIME DOES HASHING TAKE?  For YOUR system?
If it's <1% of CPU, why bother fixing it?

>>shared string packages do you use?  Is it worth your time and effort to save

>Hmm, lars included only one. Of course, the code gets modified when you work a
> bit on the driver, like speeding things up & correcting handling of high ref
> counts.
>What other packages are there?

Oh, a couple of different styles of hashing (my original one - basic 3-prime
stuff, ones that only hash N chars of the string, ones that cut off the initial
part of the strings in the object hash, hash.c, etc.  Personally, I get the
best results by far with the simple, original one - I save nothing with the
others, as decstation integer arithmetic ops are fast anyway).

There's also the basic stralloc code (which _did_ handle high reference counts
properly, thank YOU very much :), as well as a number of variants.

>>driver) is saved by your function caches?  Is it >5%, or is it the (much
>>more likely) embarrassingly low figure of 0.1%?  After all, all the
>>function string pointers will be stored in the same memory page...

>But you sometimes want very simple functions to be called very often, like
>with sort_array(). This efun, like all the map efuns, wasn't usable on arrays
>of interersting size till the cache was introduced.

Mmm - I'm taking a different approach to these problems, and so hadn't
really considered it (Shattered is becoming an asynchronous
event-driven language).

>>Mmm.  What about call-other?  Or don't you usually compile those to bytecodes?

>The object that the call_other is applied on can never be determined in a
>static way. Even if called by a string constant, the source for this object
>might be changed, and the object updated.

Uhh, run that past me again...  You mean you _don't_ have a
"compiled_time" timestamp on your objects?  How will you compile away
all those tag checks?  For shame...

What?  You mean checking tags is an insignificant part of total CPU
usage?  But... but... I thought that *most* of the things we were
bragging about optimising here were _also_ things that weren't worth
optimising... :)

(N.B. time taken for tag checking _does_ matter to my system - it's not really
LPC anymore...)

>>_ALL_ strings should be either shared or in compile space.  And they

>Hmmm. Why? do you want to eleminate the string_type field? You should then
>go ahead and delete the type field as well...

Strings should all be shared so there's a simple, clean string
interface internally, along with the possibility of compiling the code
to be tagless and still getting fast string comparison, etc (by pointer
comparison, of course :), and with less possibility of bugs, etc.

But you do it however you want to :)

Mike.
--
Mike McGaughey			AARNET:	mmcg@bruce.cs.monash.edu.au

"Head stompin', ass kickin', finger licking nastiness"