WolfenQt

Today I spotted this post about Qt widget rendering in OpenGL on the Trolltech blog. You can read it, or you can just watch the video:



It links to another post, which already describes features that would be sufficient for an experiment. What Samuel Rødal shows in his posts would mean basically all Qt widgets would be able to render to an arbitrary OpenGL surface. This suggests it would be interesting to experiment with Qt integration in Spring. Basically any GUI toolkit would be a huge improvement over the current GUI of Spring, and the fact that we'd get it for free with even a company (Nokia) backing it, would be a huge bonus.

Besides a replacement for Spring's native GUI, LUA bindings could be supplied to allow LUA widgets and gadgets to create a consistent look and feel throughout the engine, no matter whether a piece of functionality is hardcoded in the engine or supplied by a LUA script.

Could this mean the end of the "Bermuda GUI"?

String concatenation, now in near infinite time!

One particular thing has always surprised me in languages like Java and C#. Consider the following piece of code, taken from this file in ChanServ (a bot in the Spring lobby server for moderation/administration purposes.)

// precondition: there exists a logfile with filename ,
// which may contain a very large amount of lines, which are
// to be inserted in a MySQL database.

ArrayList<Long> stamps = new ArrayList<Long>();
ArrayList<String> lines = new ArrayList<String>();

String update = "";
BufferedReader in = new BufferedReader(new FileReader(file));
String line;

int lineCount = 0;
while ((line = in.readLine()) != null) {
    if (line.trim().equals("")) continue; // empty line

    long stamp;
    try {
        stamp = Long.parseLong(line.substring(0, line.indexOf(' ')));
    } catch (NumberFormatException e) {
        Log.error("Line from log file " + file.getName() + " does not contain time stamp. Line is: \"" + line + "\"");
        return ;
    }

    if (lineCount == 0) {
        update += "INSERT INTO `" + name + "` (stamp, line) values (?, ?)";
    } else {
        update += ","+ Misc.EOL + "(?, ?)";              
    }
     
    stamps.add(stamp);
    lines.add(line.substring(line.indexOf(' ')+1, line.length()));
     
    lineCount++;
}
in.close();

update += ";";

// it continues by creating a prepared SQL statement and setting
// the parameters using the stamps and lines ArrayLists...

Now, do you already see the issue? Don't worry if you don't - I've seen the same issue in various projects (including commercial projects) already, so you're not the only one who doesn't see it.

Let me give you a hint related to this specific code: One day the box hosting the Spring lobby server went down. So when it came back up I began to restart the lobby server software. First the lobby server itself. All was fine. Then ChanServ, the bot which contained the above code back then. I ran it's startup script, and waited..., and kept waiting...! The script didn't finish. At all.

Any clue yet?

No? Let me explain.

What - after some debugging - happened to be the case, was that this code in ChanServ was being invoked to import some rather large log files into the database. Now take a look at the code again: for every line in the log file, it appends a small string to update. This wouldn't be bad, if appending to a string in Java and .NET wasn't O(n), with n the length of the total string. In other words, the algorithm above as a whole was O(n²) instead of O(n) with respect to the number of lines in the file! (For example, this means that if importing 1000 lines takes 1 second, then importing 1 million lines takes, no, not half an hour, but a whopping 278 hour!)

It was trivial to rewrite the above code using StringBuilder. Afterwards, ChanServ started up and imported the log files into the database in a few minutes only.

StringBuilder update = new StringBuilder();

while ((line = in.readLine()) != null) {

    // ...

    if (lineCount == 0) {
        update.append( "INSERT INTO `" + name + "` (stamp, line) values (?, ?)" );
    } else {
        update.append( ","+ Misc.EOL + "(?, ?)" );
    }

  // ...
}

All in all, I want to urge you as C# or Java developer (or any other language with immutable strings) to keep in mind the algorithmic complexity of string concatenation. In simpler terms, I want you to use StringBuilder / StringBuffer whenever you are concatenating more then a few hundred characters into a string, to prevent nasty suprises like the one above.

SpringLobby release

A new version of SpringLobby has been released including a feature I made - as guest developer, you could say :-)

Besides the minimap (a picture of the map's texture), which has been present in Spring Lobbies practically forever, and the metalmap, which I added earlier to test a unitsync feature, you can now also view the heightmap.


As usual for SpringLobby, prebuilt packages are available on the site.

Have fun!

Gdb tricks

Yesterday I was debugging some curious bug in the Spring engine. I was playing a game of XTA and near the 51th minute the engine suddenly appeared to hang. So I fired up gdb, attached it to the process, and started to examine it. Now I wouldn't post here if I didn't learn some new things in gdb. That's what this post is about.


Static typing vs dynamic typing

By default, gdb uses some sort of static typing when examining data. If I point it at a memory location and tell it it contains a CObject pointer, then it will interpret it as a CObject pointer. Sometimes however, you have a list of polymorphous objects, and you want to know the actual type of the object being pointed to. This can be toggled on and off for all print commands using set print object on/off.

(gdb) p $99
$129 = (CObject *) 0xfe545f0
(gdb) set print object on
(gdb) p $99
$130 = (CUnit *) 0xfe545f0

Pretty printing

By default, gdb uses a very concise format for printing out objects. This may be good enough if you're looking at a tiny data structure, but for large structures it becomes illegible. You can, however, toggle pretty printing, which changes exactly this. Suddenly all members of a class are nicely indented, etc. Use set print pretty on/off for this.

Often when debugging, I find I'm absolutely not interested in the value of static members of classes. Even so, gdb still prints them out every time you print an instance of such class. This can be turned off using set print static on/off.


The poor man's loop applied to a linked list

I needed to go through a linked list yesterday, and was wondering how to do this without having to type a new print command every time. A little bit of googling brought me to this blog entry however, detailing how to loop through an array using the feature that pressing "return" on an empty line repeats the previous command. A similar thing can be done be used to loop through a linked list, in this example a std::list<CObject>. (Example is under the assumption of a 32 bit system.)

(gdb) set $node = 0x804a018
(gdb) p {CObject*} ($node + 8)
content of first node
(gdb) p {CObject*} (($node = *$node) + 8)
content of second node
(gdb)
content of third node
(gdb)
content of fourth node
...

I hope this helps you and I welcome all improvements and other tips!

Measure, measure, measure

(Skipping the introductory post for later - maybe.)

Today BrainDamage - developer of the SpringLobby client for the Spring Lobby - showed me some profiles of the Spring engine. Some interesting things can be observed in the profile. That is, if you are in some way involved with, or interested in, Spring engine development :-)


This is the big picture. The red blobs are the program entry point and related functions. From this the call graph branches into CGame::Update (left) and CGame::Draw (right). Let's zoom in to have a clearer picture of this.


Boring eh? Not much happening yet. The left branch (green) goes to CGame::Update, which then branches out to all - synchronized and unsynchronized - non-rendering logic. The right branch (also green) goes to CGame::Draw, which branches out to all rendering code. Update takes 38%, rendering 61%. Rendering is this high because the engine always tries to maintain an as high number of FPS as possible. In other words, all CPU time not spent on logic, is - by definition - spent on rendering. This also explains why it sums to 100% (approximately).


It gets interesting when we dive deeper inside the left part of the graph (click to enlarge). CGame::ClientReadNet is the sole method called by CGame::Update. Due to the networking model, this is the method calling the CGame::SimFrame method - the "main()" of the simulation - whenever a network message arrives instructing it to do so. This part of the tree as a whole took 38% of CPU time, so I'll normalize CPU percentages against this value.

We see a few methods taking single digit CPU percentages, but we see one taking 57% of the entire simulation: CUnitHandler::Update. This isn't too suprising. Lots of units involved in a real time strategy game. Let's see where this time is spent. About a third goes to CUnit::Update - called every frame for every unit. The rest goes to CUnit::SlowUpdate - called every sixteenth frame for every unit. The fact that the least called method of these two eats the most CPU may come as a surprise, but Spring unit simulation code was built taking into account that CPU intensive tasks are better not done every game frame for every unit. This is why SlowUpdate was invented: to perform the heavy tasks only once every few frames. (It's also spread out over all game frames, ie. one sixteenth of all units is SlowUpdated every frame.)


Here we see how CUnit::SlowUpdate spends it's time: it likes to call CAirMoveType::SlowUpdate. A movetype is an abstraction of the movement class of a unit. Each mobile unit has a movetype. Obviously, the CAirMoveType is used for airplanes. So airplanes take about 28% of total simulation time. Compare this to CGroundMoveType, which uses only 3%, even though BrainDamage ensured me he made more ground units then aircraft!

So what is burning the CPU inside CAirMoveType? It's the highlighted node: CLosHandler::MoveUnit. CLosHandler is the class that handles Line Of Sight calculations. Appararently over one third of all the simulation time is spent calculating whether units can see each other, while the other two thirds are fragmented over a lot of different methods.

This sounds like a bottleneck, and who knows, it might be optimizable. (To be continued?)

PS.: for those interested, here is the full graph.