Dirty coding (or: how performance issues turn into bugs who turn into nightmares)

I think it is only fair that I keep the community up to date on what these funny performance issues are that I keep mentioning in my release notes, and why there are comments around about some people experiencing crashes and odd issues.  It makes for a good read if you have a slight interest into coding as well, as it shows you how little things can have big impacts.

The background, bear with me this is going to be important:

In the very early stages of my game, I captured information about what monster spawners have used up how much of their monster count.  Each spawner emits a monster group, and if the party engages with that and wins, the spawner needs to check if it is allowed to spawn another one.  So this is saved in the savegame as each new game will start with zeroes.  Because the world was simple and small, I just captured the MAP, the spawnerID and the COUNT.  in a dirty way: I kept each in a separate array.  so the 3 arrays always have the same length, and the 1st entry in each will give you the number of monster groups that spawned and got killed from a certain spawner in a certain map.

A boss monster for example comes out of a spawner with the MAX_EVER setting of 1.  Skeletons near the undead tomb come out of a spawner with the setting MAX_EVER 100000 (never runs out) and MAX_AT_ONCE of 2.  Which means there can be 2 skeleton groups walking around at any time, if the ones walking around plus the ones killed in the past are not >100000.

Here is where the trouble starts:

Every time the party walks one tile in a map, all spawners check if they could be spawning something.  In order for spawner #3 in map #1 to check how many of its previous spawns got killed, it needs to go through the ENTIRE array to check if there is an entry with this map and spawnerID.  No problem early in the game, the maps were hand-crafted and had a maximum of maybe a dozen spawners.  But as of now, the game has 60 maps and some random ones can have >250 spawners.  So EACH step walking through such a large random dungeon, 250 checks are performed and each check goes through the entirety of all 3 arrays.  8^(

Performance wise, that is B*sh%t coding.  When people complained about performance issues recently, I noticed that.  2.0.5 kept the original data in its awkward form but on entry into a map creates an easy to search array with just the pieces of data relevant for this particular map.  That is what the “Loading” screen is about that got introduced with 2.0.5.  However even this could take >10 seconds for some people and that got me thinking something may not be right.  So I finally said this morning, let’s replace the awful array structure I had with a clear 2-dimensional array of MAP x ID where you can quickly query the right piece of data, and overwrite it as well. Because this means saving a new piece into savegames, I handled this very carefully.  On savegame load, my new 2.0.6 version creates a new array out of the old data.  I thought, for an advanced savegame there are maybe 2,000 spawner data pieces there, should not take long even if I let the game print out the number at each step.  I should see it ticking down from 2,000 to 1 pretty quickly.  I took a savegame that behaved slightly slow-ish, but not as slow as what some players reported, and loaded the game.  The ticker started at 180,000 and going down… I stopped it.

It became clear now that the performance issues people experience are the outcome of two things extrapolating each other:  a data structure that was sub-optimal, and a super large data set to start with.  And I had no clue why it was so large.  If you kill a monstergroup from a spawner that you killed one before, it would overwrite the COUNT, not add a new data set.  So 180,000 is far more than all the spawners in all my maps together (which is about ~3,000).  so there was something seriously wrong.  The arrays collected garbage data and it clogged up everything.

To cut a long story short, there is one other instance where data is added, other than when you kill a monster group.  When I created the undead wizard quest VERY early in the development of this game, I wanted to make it feel like something more than just killing a particular monster.  I wanted to make the skeleton spawners outside the tomb stop spawning, as if you had stopped a source of evil power.  By adding three data sets with count of 999999.  When I analysed my 180,000 entries I found that 99% of them were copies of these entries.  I have re-written that bit now.

I have now also replaced all bits of my code that used the old data arrays, so now there is only one [MAP x ID] array and the performance issues should disappear, as well as the odd long loading times, and even the odd long save times.  I saw that with this 2.0.5 issue some also experienced crashes when it says “saving”.  that is odd, I will need to see if I can reproduce it.  I can only imagine that maybe the file size became too much.

As with all such bugs, apologies for the inconvenience.  Hang in there, I will fix them as they come up.

Kind Regards,

Volker

Advertisements