header image

Higgs boson most likely found

A proton-proton collision that may have produced Higgs boson. © CERN 2012

A proton-proton collision event that may have produced Higgs boson. © CERN 2012

According to the CERN conference today they finally found the Higgs boson. The results are still preliminary, but results from both Atlas and CMS detectors have confidence of 5 standard deviations needed for the “discovery” claim. It is still not official as there were some irregularities in the data observed and the analysis is ongoing. New boson was found, but it’s not yet sure if it’s the Higgs or not. The particle was found with methods tuned to catch the Standard Model Higgs, so it’s quite likely. Peter Higgs shed a tear or two at the end of the speech – must have been an incredible moment for him.

Press release.


It is so hard to write this, but our most beloved rat, Sznurówka (Shoelace), is no longer with us.

She was barely alive when we got her. Rescued at the age of about eleven months from a pet shop where she was used as a reproductive female, kept in terrible conditions. She was undernourished, had a bad case of pneumonia, heart issues, abscesses – you name it. We knew that she will need to take medicines for the rest of her life, but we wanted her to have a good, safe home.

Right after she came to us, still in very poor shape

Continue reading ‘Elegy’

Gwen.Net – SFML renderer updated

SFML 2.0 RC came out recently and I finally found some time to update the Gwen.Net renderer to support it.

Windows console is SLOW

If you don’t know this already, here’s a hint: don’t use standard windows console to print large amounts of data if you care about performance. It’s dead slow.

Recently while writing custom data exporter for a certain business application I noticed strange slowdowns. The application server runs on JBoss as a servlet and I’m communicating with it via web service interface from a C# app. One day I logged on the server machine via remote desktop while my data crawler was running and noticed that the JBoss console was furiously printing heaps of log messages. As it turned out every single HTTP request was printed on the console in detail as INFO message. JBoss uses log4j so I could filter INFO messages out, but the application server also uses INFO for some other diagnostic stuff I’d like to keep. HTTP requests are certainly debug-level data, but apparently creators of the app didn’t think that way. So what did I do? Minimized the JBoss console. Instant speed up of ~20%.

Performance of various square root computing algorithms

After reading a post on fast integer square roots on Robert Basler’s blog I got curious about performance of those algorithms on modern hardware. The most famous is of course the “Quake 3 invsqrt”. I’ve also tested two algorithms mentioned on Stack Overflow.

My microbenchmark approach was basically to compute sum of square roots from 1 to 1e9 into a UINT64 variable. loops is 1e9.

// math.h double sqrt
UINT64 uu = 0;
for (UINT32 i = 0; i < loops; i++)
    uu += (UINT64)sqrt((double)i);
elapsed = (pc2.QuadPart-pc1.QuadPart)/(double)freq.QuadPart;
wprintf(L"Sqrt double: %.3fms (%u)\n", elapsed*1000.0, uu);

Results from my laptop (DualCore Intel Core i7 620M, 2666 MHz (20 x 133), times in milliseconds):

Long double sum of sqrts: 21081851051977.781000

Sqrt float: 17741.012 (1652390483)
Sqrt double: 16131.129 (1651579237)
Fast uint sqrt: 20723.943 (1651579237)
Fast ulong sqrt: 93737.070 (1651579237)
Fast int sqrt: 27791.603 (2558293500)
Fast Q3 float sqrt: 20919.534 (3883084482)
Fast Q3 double sqrt: 21357.330 (3882261863)

Sqrt float: 7135.535 (1652359905)
Sqrt double: 12613.416 (1651579237)
Fast uint sqrt: 23390.084 (1651579237)
Fast ulong sqrt: 32878.867 (1651579237)
Fast int sqrt: 24430.502 (2558293500)
Fast Q3 float sqrt: 5352.906 (3883079922)
Fast Q3 double sqrt: 15216.076 (3882257735)

Compiled as speed-optimized release using VC2010. Enabling SSE/SSE2 didn’t produce noticeable differences. Using fast floating-point model over precise or strict does improve built-in sqrt function performance (as well as Q3’s invsqrt) but I chose to stick to precise model since it’s the default. static_cast had the same performance as C-style casts. Numbers in parentheses are integer sqrt sums, as you can see they vary wildly due to different accuracy of the algorithms.

64bit executable is pretty much always faster, especially for floats. Casting to UINT64 is slower on 32bits of course, but using UINT32 doesn’t change much (tested that as well, minimal differences). Built-in sqrt is still fastest except for float version of Q3’s invsqrt, which is blazingly fast and still very accurate.

Continue reading ‘Performance of various square root computing algorithms’

Rats gallery

Finally took some time to create proper gallery for our rats. I don’t have a great camera so photos are of varying quality. Anyway, take a look here.

Layout, docking, autosizing

I’m working on some issues with docking and autosizing controls in GWEN.Net. It’s uncommon to have for example autosizing ListBox, typically you define its boundaries in advance in order to fit it into your layout. If there is large amount of rows or rows with long text, you can always add scroll bars and be done with it. However I need such an autosizing ListBox for my game client to display some information. Well, need is a strong word, but if something doesn’t work I better fix it instead of working around the bug. I also added debug outlines (render bounds, margins, padding):

Nested GroupBoxes with debug outlines

The One Man MMO Project

While reading comments over at Elder Game I stumbled upon another one man MMO project. It’s pretty vague on what it’s going to be about, but the goal is to develop a “big” 3D MMO. Robert Basler works on it full-time so it’s a pretty ambitious endeavor. I wish him luck, and got more motivation to work on my hobby project as well.

Saving first characters

Over the last few days I’ve implemented persistence for Artemis entity system. I heavily modified it in the process since it was not really designed for that. So now my game server has a somewhat working world update loop running Artemis. Saving world state can be done in two ways: pausing the update loop and just dumping every entity and component into the DB, or saving in the background. Pausing is the easy way, it takes a few seconds to save over 100000 simple entities on my laptop. The disadvantage is, of course, that every player will be frozen during the process. Ultima Online emulators do it that way, but we can do better. Background saving is much trickier because save process is not instantaneous. If the main loop is not paused some game entities can me modified during the save, rendering saved state inconsistent. How to avoid that?

Right now my save method looks like that:

internal void SaveAll()
    if (_DbState.Saving) // _DbState holds some global database state variables
        throw new InvalidOperationException("Database is in inconsistent state, reset Saving property to continue");

    Console.WriteLine("SaveAll() started");
    // _Dirty holds entities that are modified during the save
    _Dirty = new Dictionary<long, Entity>(_Active.Count); // initial size to prevent resizing
    // we alternate between two DB collections to prevent data corruption if the game server explodes during save
    _DbState.Saving = true;

    // switch collection
    _EntityCollection = _Db.GetCollection<Entity>(_DbState.ActiveCollectionName);
    _EntityCollection.RemoveAll(); // clear
    Stopwatch sw = new Stopwatch();
    // _Active is a dictionary with active entities, we take a snapshot of their IDs at the beginning of a save
    long[] copy;
    lock (_ActiveLock)
        // this only takes a few milliseconds
        copy = new long[_Active.Count];
        _Active.Keys.CopyTo(copy, 0);
    Console.WriteLine("Active snapshot: {0}ms, {1} entities", sw.ElapsedMilliseconds, copy.Length);

    Console.Write("Save to {0}: ", _DbState.ActiveCollectionName);
    // now the save proper, less efficient than a batch insert but what can you do
    foreach (var entity in copy) // loop through all entities in the snapshot
        lock (_DirtyLock)
            if (_Dirty.ContainsKey(entity)) // this entity was modified, use cloned value
                var dirty = _Dirty[entity];
                if (dirty != null)
            else // not modified, save original object
    Console.WriteLine("{0}ms, dirties: {1}, not modified: {2}, total: {3}", sw.ElapsedMilliseconds, _Dirty.Count, copy.Length-_Dirty.Count, copy.Length);
    // save entities the easy way: batch insert, this needs paused update loop
    //_EntityCollection.InsertBatch(_Active.Values, SafeMode.True);

    // to make sure everything was written (if SafeMode==false) loop this check a few times
    if (_EntityCollection.Count() != copy.Length)
        Console.WriteLine("Not all entities were written!");

    // save finished
    _DbState.Saving = false;
    Console.WriteLine("SaveAll() finished");

Of course this is a prototype and needs stress testing for possible locking and data loss issues, but it seems to work fine for now. Background saves require some overhead when updating entities though: if a save is in progress, a clone of the entity needs to be added to Dirty list before the entity is modified. Also memory requirements go up a bit, because we need to store those clones during save. Testing shows me it’s not too bad, but we’ll see how it works for a real server.

In my test I have 10 types of components, each with a simple data field of varying types. I create 100000 entities with 1-10 random components. There are 5 systems, processing 1-5 different types of components. Every system alters every entity it processes (pessimistic scenario). During every loop around 50 new entities are created, amounting to pretty unrealistic few thousand new entities per second. Here is a sample run on my laptop with background saves every 20 seconds:

Init: 536ms
Loading from 0: 0 entities, 14ms, 0 e/s
Creating 100000 entities: 2213ms, 45187 e/s
Looping for 300s...
SaveAll() started
Active snapshot: 1ms, 112920 entities
Save to Entities1: 7259ms, dirties: 59332, not modified: 53588, total: 112920
SaveAll() finished
SaveAll() started
Active snapshot: 1ms, 124530 entities
Save to Entities0: 8085ms, dirties: 55214, not modified: 69316, total: 124530
SaveAll() finished
SaveAll() started
Active snapshot: 2ms, 135260 entities
Save to Entities1: 10312ms, dirties: 54271, not modified: 80989, total: 135260
SaveAll() finished
SaveAll() started
Active snapshot: 1ms, 145250 entities
Save to Entities0: 12097ms, dirties: 76273, not modified: 68977, total: 145250
SaveAll() finished
SaveAll() started
Active snapshot: 1ms, 154500 entities
Save to Entities1: 12325ms, dirties: 81132, not modified: 73368, total: 154500
SaveAll() finished
SaveAll() started
Active snapshot: 1ms, 163250 entities
Save to Entities0: 13825ms, dirties: 85726, not modified: 77524, total: 163250
SaveAll() finished
SaveAll() started
Active snapshot: 1ms, 171650 entities
Save to Entities1: 14030ms, dirties: 90208, not modified: 81442, total: 171650
SaveAll() finished
SaveAll() started
Active snapshot: 1ms, 179690 entities
Save to Entities0: 15005ms, dirties: 94482, not modified: 85208, total: 179690
SaveAll() finished
SaveAll() started
Active snapshot: 1ms, 187360 entities
Save to Entities1: 16442ms, dirties: 98475, not modified: 88885, total: 187360
SaveAll() finished
Loops: 3046, 10.15 loops/s, 191380 entities)
Entities subscribed: s12: 30432, s340: 13091, s5: 74095, s6789: 5419, s2458: 5384, total: 128421
Saving 191380 entities to 0
SaveAll() started
Active snapshot: 2ms, 191380 entities
Save to Entities0: 17398ms, dirties: 0, not modified: 191380, total: 191380
SaveAll() finished
Save: 17421ms, 10986 e/s

I’m happy with the numbers. Of course test systems and entities are very simple, but there are lots of them and the pressure on the GC is pretty high. Still, CPU spent in the GC is below 10% and memory usage peaks at around 300 MB. 10 loops per second seems enough for a MMORPG server, it’s not a shooter. I might be wrong, but we’ll see later. And of course my laptop is not exactly a server-grade hardware 😉

Right now the only thing game server actually stores are player characters, which are entities with just two components: name and location.

/* 0 */
  "_id" : NumberLong(1),
  "Components" : {
    "Name" : {
      "_t" : "Name",
      "Value" : "admin"
    "Location" : {
      "_t" : "Location",
      "X" : 1.0,
      "Y" : 2.0,
      "Z" : 0.0

/* 1 */
  "_id" : NumberLong(2),
  "Components" : {
    "Name" : {
      "_t" : "Name",
      "Value" : "Omeg"
    "Location" : {
      "_t" : "Location",
      "X" : 1.0,
      "Y" : 2.0,
      "Z" : 0.0

It’s a start, but once the framework is there, extending it will be easy. Stay tuned.

Entity systems, input and persistence

As my development of Heimdall continues, I run into various problems and difficulties. It’s expected, a project of such complexity can’t be all smooth sailing. Right now I’m implementing the core logic of a game server, a foundation for the whole game world simulation and processing. As mentioned before I’m using an entity system approach. So what exactly is an Entity System?

In a nutshell, an Entity System is a way to organize game entities. By ‘game entity’ I mean every object that exists in the game world. So it includes players, items, enemies, interactive terrain features, invisible script triggers etc. The traditional way to structure game entities is an object-oriented class hierarchy. There is some base “Game object” class, then more detailed “Movable object” or “Trigger” classes and so on. It’s pretty self-explanatory, widely used and everyone understands it. So why not use it? Well, there are some problems with hardcoded deep inheritance chains. First, you need to plan pretty much everything right at the beginning of the design process. Once you have a class hierarchy, it’s very hard to change it afterwards. Even worse, game entities are hard to partition into perfect tree. Suppose we have a Human class and a Vehicle class. They both derive from a Mobile class. But what if we want some objects to have an AI and not be controlled by player(s)? We need to either introduce another base class(es) – Controllable/Scriptable, or cram input handling and AI into each class, even if that code won’t be used at all half the time. First solution introduces multiple inheritance into our class tree, and that is A Bad Thing most of the time – the code will be even harder to maintain and changes to the class structure will be almost impossible. The second solution bloats classes with unnecessary code that is only needed for some objects. As more such situations appear, base classes will contain more and more functionality, leading to feature overload and unneeded complexity.

What can we do about that? Entity System or component approach tells us to separate related object data into components, and to partition functionality into systems that acts on said components. There will be no traditional class hierarchy, just a basic Entity class that only really has a unique ID and is an aggregation of data components. Components are just bags of data, they contain no logic themselves. Systems are where the logic lies – they process components, may communicate with each other and generally make the game run. It’s worth saying that systems should be indiscriminate: each and every entity should be “equal” for them. In practice that means systems shouldn’t feature code like this:

if (entity.HasComponent(SomeComponentType))

Systems usually “subscribe” to components they are interested in. Let’s say we have a Rendering system. It may be interested in Position and GraphicsModel components. Then usually every game tick entities are dispatched to systems depending on such “subscriptions”. Rendering system draws entities it’s been given using just the data it needs. AI system acts on all entities that have AIState component. This way both data and logic are nicely separated and partitioned into manageable chunks. All entities have only components they need. We can have a player-controlled human (has InputState component), or AI-controlled human (has AIState component). No multiple inheritance needed and we have great flexibility. We can mix and match, create entities from templates containing lists of components, even make templates that include each other to facilitate data reuse. Such flexibility and data-driven design is a great asset for any MMORPG.

So we have an Entity System and all is great. There are still practical obstacles and implementation details to overcome. If we design a MMO game server, we need data persistence. Every game entity needs to be stored in some way, usually in a database. I’m using mongoDB – an open-source, NoSQL, high-performance document-oriented database. I feel it’s better suited for the job than traditional relational databases, game objects don’t map well into SQL tables and rows. mongoDB is also damn fast, just look at their production deployment list. I’ve done some tests myself and the accounting system already uses it without issues.

How do we store game entities then? Because entity is just a bag of components and components are just bags of data, this should be relatively simple. We just need to ensure that all Component implementations have proper DB (de)serializers. We also need some form of creation engine that will construct entities from templates, because manually adding each component every time is tedious and prone to errors. That implies having template storage, designing template format and parser for it. My Entity System implementation is based on Artemis – a C# port of a Java ES under the same name. I’m modifying it as I go since it’s got some rough edges. It doesn’t have any support for templates and modifications to the entity factory are required if I want proper integration with persistent DB (generating unique IDs is an issue there).

Another problem lies in the implementation of the input system and I’m not sure how to solve it yet. We have a game server. Clients connect to it and send network packets with input commands. Now we need to pass that input data to appropriate system(s) that can in turn act on Player Character (and possibly other) entities. How to do that without breaking encapsulation? Networking layer shouldn’t manipulate entities by itself obviously. Each client connection has a player ID assigned, which is basically the player character’s entity ID – that’s determined upon login. Data in each incoming packet needs to be validated. This should be done by appropriate systems: if we get a “move character request”, network handler should pass the data to Movement system… But systems themselves should be stateless! Do we make an exception for input data? Or do we create a “MovementQueue” component that holds the input data and is processed and validated by Movement system? MovementQueue concept is nice because it can also be used by AI systems. Right now I’m in favor of the queue, but I’m not sure how well it will scale. What with other input data? Do we have an attack queue, speech queue etc? I can see a large number of “action” queues in the future if I do it this way. Or maybe we can make just one ActionQueue? But data required for different actions has different structure. Maybe there should be an “ActionDispatcher” system? Questions, questions!