Sunday, August 21, 2011

Tremendous bug!

It didn't take you long to find out what was wrong in the solution I presented in http://fonline2238.blogspot.com/2011/08/what-would-be-point-of-having.html. In fact, you were faster than me fixing it, after the bug introduced by it occured on 2238 server.

Let's start from beginning. In first iteration of gathering (called production) back then, we needed a notion of facility that player could use to obtain some resource. A facility could be one item (item pretending to be scenery object actually, it had to be item because of the scripting possibilities), or collection of items. So, a barrel in Modoc was one facility and all the plants somewhere on the crop could be one facility as well. And when the player obtained some resources from it, we needed to apply timeout for it (store it on the item somewhere). Also, we needed even more scripting possibilities - rotgut still for example. Perfect situation to use the wrapping pattern:

interface IFacility

{
bool CheckTimeout();
void Use(Critter& cr);
}
class BarrelFacility : IFacility
{
Item@ barrel;
BarrelFacility(Item& item)
{
this.item = item;
}
bool CheckTimeout()
{
return item.Val1 > __FullSecond;
}
void Use(Critter& cr)
{
if(CheckTimeout())
{
// give junk
item.Val1 = __FullSecond + 60; // 60 seconds of barrel cooldown
}
}
}


Of course above code is simplification, and we needed to wrap the item for other reasons as well - for example having one facility object per many items, but it's not the point of that post to explain all of it.
So, we were adding the BarrelFacility objects in barrel script:
void item_init(Item& item, bool)

{
AddFacility(BarrelFacility(item));
}

And we had that global array of IFacility objects. I didn't implement removal procedure, simply because, all those facilities were in towns and other fixed locations. So, they were destroyed only when server was being shut down, and were created only on server start. Additionaly, because of the fact there was only few of them, and I think I haven't got any unused Item::ValX field, I haven't been storing the index to the array for fast fetch (like I wrote in previous blogpost on that), but I was iterating over whole array to find proper object. It hadn't got big performance impact, but one day we decided we need to change the system: we introduced facilities into encounters. Boom!

Yes, that was it - the IFacility objects were created very often, and never being destroyed. The array was growing and growing, and the fetching procedure was O(n) in complexity instead of O(1). Terrible stuff. When players started to jumping into encounters, after some time the array was so big that every time someone wanted to use facility, the algorithm had to go through thousands of iterations to find proper index in the array. And the appending was quite painful as well - the underlying array object needs to copy all elements on resize, as it does not reserve space up-front.

And that caused a lag. The Lag in fact, it was so big that it had destroyed the fun from early beta days. And we haven't fixed it that fast. To put it simply - I forgot that the objects are never removed, and found that out later... A little embarassing, I know, but now, when looking at it after such amount of time - it's quite funny to recall.

And quite funny story about 2238 development I think.