25 October 2008

Profiling and optimizations

In the last two or three weeks, I spent a lot of time optimizing the server.
I rewrote all kind of functions, and fixed a few bugs while at it. The profiling results were kind of surprising, for example the most expensive function in my code is was a big loop, mostly empty, that looks something like this:
for 0 to 6K
if()
if()
if()
if()
//only maybe 30% of the times the execution gets here.
do some stuff, not very time expensive

Now, this function is called 8 times a second, but even so, it was a little bit unexpected that such a little innocent function would take about 0.7 ms at each run.
So, I focused all my m4d hax0r skillz on optimizing this function, which meant making a few lists to get rid of some of the ifs. But this required reordering some networking code, which took a while.

After doing this, I was expecting the CPU usage to drop a lot. But, to my surprise, it did not drop at all (nothing noticeable, anyway).
And then it finally realized it:
The problem was not in the server code, the problem was on the networking side!

For example, a server with no players, but 1300+ AI (which do most of the things players would do) takes about 1% of the CPU.
But a server with 100 players takes about 2%, and a server with 800 players (and player run bots) takes 18% of the CPU.

From the very beginning, I relied on SDL_net for the networking, but until a few days ago, I didn't even look at the SDL_net source code to see how it is doing things. So I took a look, and didn't find any problems, except that it has to go through the list of all the connections once, and through the list of active connections twice. Then the server must go through the list of all the connections once again, to check for data.
Obviously, this is not optimal.
After doing some research, I found out that the select() method, which SDL_net is using, scales very poorly when there are a lot of connections, because the kernel must do a lot of expensive operations as well.

Well, Learner told me today that on FreeBSD there is another way to check to see if the sockets have any data, with kqueue.
After doing some more research on the matter, I found this. It explains in details how kqueue works, and why it is so much faster than the good ol' select().
So I am going to implement kqueue on the server, to be used on the 'production' server, but also leave the SDL_net way in there as well, because my development is done on Windows.
Right now, I am downloading Desktop BSD and will run it on a virtual machine, to help me with my local testing. Once I actually start implementing the new system, will let you know how it went.

08 October 2008

Optimizations

Today I finally finished optimizing something that I always wanted to optimize, namely the system which checks who sees who. The old system was checking if someone moved, then if it did, it will check against everyone one the map. For under 20 or so actors on a map, that was pretty fast, but when there were hundreds, even thousands actors (such as during events or invasions), then things were very slow.
For example, the server would use about 33% of one CPU with 1607 invaded monster in one map.
The new system uses sectors, so the players are only check near the nearby sectors, considerably improving the speed. Right now, with 1607 monsters in one map, the server is using only 7-8% of the CPU, so the speed improvement is ~450%. Of course, that is obvious in extreme cases like this, but it should also work better than the old system in any maps with over 10-15 players.

On a related note, tomorrow we hope to unveil one of the secret features me and Schmurk worked at. I am pretty sure that people will be very, very happy when they will see it :)

03 October 2008

Mules going live, server optimizations, new things

Well, the mules went live a few days ago, and now people can make them and their food.
I didn't see too many mules in the game, which is good, the last thing I wanted was everyone to become a mule. But there are many mule glyphs and pets food being produced by players, so there must be some demand for them. And because the creature food requires a refined vegetal mixture, a lot of people are using a lot of harvestible items that were previously not so useful.

The optimizations I made a while ago proved to be almost useless, there was no visible reduction in the server CPU use. I mean, the CPU works less because of them, but there are other tasks which tax the CPU much more, so they are sort of like a drop in the ocean.
I was a little dissapointed and mentioned it to Schmurk (the guy who implemented the arrows, finished the sky and the 1st person view, improved the camera movement and animations, etc.) and he gave me a really good idea bout how to optimize some stuff. And not only that, but he wrote a program to test it, so I am going to use part of his code (with modifications) to improve the server speed.

As I said before, there are two new (and secret) features coming in the game soon (this year). One of them is almost 90% done (still needs more testing), and the other is ~60% done. I hope that we will be able to test the first feature in a week or two, and the players will see what it is. I am confident that everyone will enjoy it a lot, it's been requested quite a few times. Unfortunately, they both require a client update, so probably we'll have them on the main server sometime in December (we need to wait for other stuff to be done as well).