Interesting performance numbers

Grinning Fool · Joined: 12 Feb 2005 Posts: 264

So I was doing some informal testing last night on how long it took to perform a simple key-value lookup in mysql, vs string comparisons. Testing was done on a T7400. Performance results as recorded from the TIME plugin.

Loop 320 times through 11 if/then/else string == value comparisons (total 3520 comparisons), where value is a 5-byte string and string is a constant with nothing in common. On average 7 ms or .002ms for one string comparison.

Loop 320 times through the same comparison as above, but using StringCompare: average 15.5 ms or .004ms for one string comparison. I didn't test it, but I suspect if I made that case sensitive, it would be the same as the "==" comparison.

Perform a single key/value lookup on an indexed mysql table containing 320 records (none of which match the key), perform SQLFetch(). On average 4ms.

So basically - if you need to do a key-value lookup, it will be faster to hard-code string compares for up to about 2000 values. This of course will vary slightly depending on database speed; too, my database was hosted elsewhere on my LAN.

Separately, I found that executing if/then/else to compare an int variable against 11 integer constants in a loop for 320 times ran about .1 ms slower on average than using a switch/case statement to do the same. (0.6 ms if/then/else, 0.5 switch/case)

Anyway... just some numbers I found interesting and figured to share. I will also probably be testing storing string data in a hashmap through a plugin, and running the same perf test. I just need time to write the plugin...
_________________
Khalidine, a NWN2 persistent world

Looking for volunteers.

caloup · Joined: 29 Sep 2006 Posts: 59 Location: albi (france)

Thanks for your work ! If someone could do the same with a MySQL server on the same computer...

Grinning Fool · Joined: 12 Feb 2005 Posts: 264

Papillon · x-man Joined: 28 Dec 2004 Posts: 1060 Location: Germany

Hold on, there is something I do not get here: You said you were doing 11 if-then-else comparisons, 320 times, and that took 7ms. Now you do 320 lookups in the hashset, but that contains 400 entries, not only 11, right ? Is that even comparable ?

Anyway, very interesting stuff! I'd like to add that the plugin hashmap solution scales with constant O, while the if-then-else construct only scales with O(n) - until it runs into a TMI error Smile

.

Btw, the overhead of calling nwnx functions is likely to go down in the future.

I know you are busy with the demo modules, but would you be interested in porting the hashset plugin over to nwnx4 ?
_________________
Papillon

Grinning Fool · Joined: 12 Feb 2005 Posts: 264

Grinning Fool · Joined: 12 Feb 2005 Posts: 264

Hm -- went to download the hashtable plugin, but didn't see the source anywhere?
_________________
Khalidine, a NWN2 persistent world

Looking for volunteers.

Papillon · x-man Joined: 28 Dec 2004 Posts: 1060 Location: Germany

I've added the source to the hash plugin. It seems like I forgot to add it when I uploaded the archive last year.

But beware, the source code is likely a mess and it might be better to implement something like this with STL containers. You could use the include file and the plugin as a working set of functions and methods, and extend from there.
_________________
Papillon

Grinning Fool · Joined: 12 Feb 2005 Posts: 264

Papillon · x-man Joined: 28 Dec 2004 Posts: 1060 Location: Germany

Since DestroyObject is not hooked, you can not know when an object is destroyed. Therefore, it has to be the user's responsibility to clean up properly. IMHO, hooking DestroyObject just for that reason is not really worth it... but of course, it could be done.

Another way would be to add a function that inspects all known objects in memory. Maybe DestroyObject marks the objects in memory somehow ? Not sure. Anyway, the gameObject pointer in the Payload function is not valid right now, so this would be an option for the future.
_________________
Papillon

FunkySwerve · Joined: 02 Jun 2005 Posts: 377

Can someone explain the advantages of hashes vs other data storage setups, to a nonprogrammer? I'm planning to do a nwnx4 version of my legendary level system, and I need to store large masses of 2da data in faster-access format. With nwn1, I simply scripted the data into scripts, which was acceptable because it was fast and there were no more expansions coming at that point to worry about. With nwn2, there are (hopefully) expansions coming, and I'd like a data setup that's fast and easy to update. Options I've thought of to date:

1) A custom 2da. I have to access too many 2das for the data I need, but the last 2 2das accessed are cached, assuming nwn2 carried over that little bit of optimization. Having all the data in one table would make a standard scripted 2da lookup fast, or at least fast enough, I think.
2) A nwnx database. Not sure how many values I'd have to select in a go, but I'm confident it would outpace 2da reads substantially.
3) Script functions. While this is what I went with in 1, it'd be a pain to update.

Would a hash be better than the above options?

Thanks,
Funky

Lokey · Joined: 02 Jan 2005 Posts: 158

You still need to populate the hash from one of your options at say module load, but reading it will probably be fastest/lowest overhead among them depending on how fast the NWNx connection is. That's probably what counts most.
_________________
Neversummer PW NWNx powered mayhem Wink

FunkySwerve · Joined: 02 Jun 2005 Posts: 377

Again, I'm a non-programmer - I have no idea what 'populating' the hash entails - loading data into it? Wouldn't it be possible to store the data permanetnly in it as wioth a database, or is that the difference between them, other than speed?
Funky

Grinning Fool · Joined: 12 Feb 2005 Posts: 264

That would be the other difference between them. Hash tables aren't persistent -- they exist only in memory. So at the module startup, you'd need to populate them. THe NWNX4 hashtable plugin will provide a way to do so using a file; or you can load it from a database through nwscript.
_________________
Khalidine, a NWN2 persistent world

Looking for volunteers.

FunkySwerve · Joined: 02 Jun 2005 Posts: 377

Ok, thanks, both of you. Smile

Funky

abraxas77 · Joined: 17 Nov 2006 Posts: 15

That timer is a nifty little tool, eh.

I ran a few test comparing two methods of storing/retrieving a list of 256 (pregenerated) random names. First method was storing them as local strings on a single waypoint. In the second method, I stored one local string on 256 waypoints.

I can't compare the population times b/c I was testing a cache system ... my bit field tracking methods about doubled my population times. Anyways, the access times suprised me a little. (but again ... my cache has to translate the index into bucket+bucketindex).

I used a stardard for loop to iterate over 256 strings: get the string and write it to a log.

Local Strings on one waypoint did it in ~9ms.
My cache of waypoints did it in ~10ms. (using GetWaypointByTag)
Using GetObjectByTag, the cache did it in ~11ms.

The local string populated 256 strings ~5ms.

It took ~100ms to create 256 waypoints.
It took ~450ms to create 1024 waypoints.

I did run a few test on an earlier version of my cache ... before I implemented the bucket structute and a bit fields. My test data wasn't as uniform as my latest test which caused inconsistant results ... but on average it seemed the cache method was slightly faster ... at best 1ms faster access time over 128 elements.
_________________
aka. twp_andrew

:: Lead Script Design :: The World of Paladium II ::

The NWNX Community Forum