header image
 

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.ToggleActiveCollection();
    _DbState.Saving = true;
    SaveDbState();

    // switch collection
    _EntityCollection = _Db.GetCollection<Entity>(_DbState.ActiveCollectionName);
    _EntityCollection.RemoveAll(); // clear

    Stopwatch sw = new Stopwatch();

    sw.Start();
    // _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);
    }
    sw.Stop();
    Console.WriteLine("Active snapshot: {0}ms, {1} entities", sw.ElapsedMilliseconds, copy.Length);

    Console.Write("Save to {0}: ", _DbState.ActiveCollectionName);
    sw.Restart();
    // 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)
                    SaveEntity(dirty);
                else
                    DeleteEntity(entity);
            }
            else // not modified, save original object
                SaveEntity(entity);
        }
    }
    sw.Stop();
    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;
    SaveDbState();
    Console.WriteLine("SaveAll() finished");
    _Dirty.Clear();
}

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))
   DoSomething();

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!

Interesting times

May you live in interesting times, says a curse (wrongly) attributed to the ancient Chinese. Are times of change worse than idle stability? I don’t think so.

And we indeed live in interesting times. Last year brought us many breakthroughs and intriguing discoveries. We learned about the first small rocky exoplanet, Kepler-10b. Large Hadron Collider, the largest machine man ever built, finally observed some hints that may be attributed to Higgs boson, an elusive particle missing from the Standard Model of particle physics. Another experiment, OPERA, shocked the world with possibility that neutrinos may travel faster than light, notion at odds with Einstein’s theory of special relativity. Human clinical tests of a HIV vaccine were approved to start in early 2012. And hundreds more.

Technological progress accelerates. And accelerates with increasing speed. That means exponential growth of knowledge and abilities to change our world. At a conference in 2010, Google CEO said that mankind creates as much data in two days as it did from the beginning of civilization up until 2003. That’s of course a rough estimate, but it’s still striking. Amount of data produced globally more than doubles every two years. Somewhere in 2007 that amount exceeded storage capabilities of the world (which is also doubling, but at a slower rate). In 2010 quantity of newly created and replicated information exceeded one zettabyte for the first time. That’s 1000000000000000000000 bytes.

Human brain contains about 1011 neurons and 1014 synapses. Maximum frequency at which neurons can discharge is about 1 kilohertz. If every synapse in the brain processed one bit of information with maximum speed, that would give us theoretical upper limit of about 1017 bits per second as brain’s information processing capability. Of course in reality that number is much, much lower (limited mainly by sensory input), but let’s take 1016 bytes (ten million gigabytes) per second as the upper value. Such super-powered brain would need over two days to process 2011′s two zettabytes of new data. “That’s nothing!”, you might say. Let’s conduct a small thought experiment then. If the amount of data produced by human civilization rises by 50% each year (a very conservative stance) it will exceed 6*1033B (6 billion yottabytes) by 2083. World’s human population will almost reach 17 billion then, with 1.2% annual growth rate. If we calculate total computing power of 17 billion human super-brains at that time, it will be less than 6*1033 bytes per year. That means even if our brains reach impossible efficiency, humanity will not be able to comprehend all the data generated worldwide.

Of course that’s only very approximate estimation, assuming upper limits and steady exponential progression, not accounting for physical limitations etc. Accuracy is not the point however. Everything we have seen so far points to an explosive growth of processing power available to humans in the near future, and that our mental capacity will eventually be outclassed. Outclassed by artificially built computers, and most likely soon. Maybe even within our lifetimes.

What does that mean? Why is it so significant to think about the day when we build the first super-intelligent system? And is it even possible?

Human brain is a machine. Incredibly complex and precise one, but still only machine. It can be analyzed down to molecular level (that’s what Blue Brain project is aiming to do) and possibly replicated artificially or simulated. The same laws of physics govern neurons as well as transistors. Given time we will gain complete understanding of how our brains work. But it’s most likely not necessary for general artificial intelligence to be created. If quantum effects do not significantly impact brain’s operation, we should be fine with just map of neurons, synaptic connections and their states. And it would be foolish to expect that our brain is the only structure capable of intelligent thought. Intelligence may just be a property of sufficiently complex systems, quite possibly systems with different physical characteristics. We already know that many deceivingly simple systems exhibit self-emergent behavior. Cellular automata, nonlinear dynamic systems, even a recursive quadratic function. But I digress.

So we will finally create something that is more intelligent than us. Super-intelligence, SI for short. What then?

SI will not be a computer like we know today. It most likely won’t be programmed: it will “program” itself, like our brain. We will need to communicate with it in a meaningful way, which may not be easy. It may not even want to communicate with us. Yes – if such an intelligent being can set its own goals, those goals may not be in line with our goals. It can even perceive humans as a threat, if it learns of our existence. Rogue AI, such a lovely subject for science-fiction. Of course the reason for lack of communication may be more prosaic: if the SI is intelligent enough, it may just come to conclusion that exchanging data with such primitive creatures as humans is a waste of time. Who knows.

Let’s say we overcome all these difficulties and humanity is able to benefit from SI’s power. What now?

Let an ultraintelligent machine be defined as a machine that can far surpass all the intellectual activities of any man however clever. Since the design of machines is one of these intellectual activities, an ultraintelligent machine could design even better machines; there would then unquestionably be an ‘intelligence explosion,’ and the intelligence of man would be left far behind. Thus the first ultraintelligent machine is the last invention that man need ever make. – Good, I. J. (1965), Franz L. Alt and Morris Rubinoff, ed., “Speculations Concerning the First Ultraintelligent Machine”.

Indeed. Recursive self-improvement. Once the first SI is created, the exponential growth of our technological prowess will accelerate even further, to the point that present human would not be able to comprehend such future in any meaningful way. It’s like a veil covering things to come, asymptote in a plot, event horizon of a black hole. Thus we call such an event a technological singularity.

It’s not possible to predict impact of even “normal” inventions if they are radical enough. What would 18th century man say when presented with a present-day personal computer or a phone? How would he comprehend working of GPS system, which relies on Einstein’s theories for precise measurements? And technological singularity is far more radical than that.

We can try to come up with possible achievements of a post-singularity era. Most are incarnations of old and new dreams. Immortality achieved by repairing our bodies or creating new ones from scratch, biological or not. Better bodies, better brains integrated with the new superintelligent network. Breakthroughs in physics allowing manipulation of space and time. Working molecular nanotechnology shaping the world around and inside us as we desire, probably eliminating the need for material economy forever. Possibility to extend our consciousness, make snapshots of it, split and merge multiple copies of our mind. But that’s only speculation. In essence, such posthumans will probably rapidly advance to and beyond Kardashev’s Type I civilization, completely controlling their home planet. Come to think of it, what if some cosmic civilization achieved such state thousands or millions of years ago, still a very short time in the grand scheme of things? They would be like gods to us, almost omnipotent, incomprehensible, alien.

What’s striking is that we are most likely very close to the Singularity ourselves. We are transhumans, witnessing qualitative change of our civilization happening before our eyes. If we are lucky, we may live long enough to peek through the veil and become something else. Something greater. Something more.

~ ~ ~

Sources and/or recommended reading:
The Coming Technological Singularity: How to Survive in the Post-Human Era
The Law of Accelerating Returns
Wikipedia: Technological singularity, Exabyte, Zettabyte, Artificial Intelligence, Neuron, Mind uploading, Nanotechnology, Kardashev scale, Post-scarcity
New Measure of Human Brain Processing Speed
How Much Information? 2003
How much total information is there in the world?
The Expanding Digital Universe (2007), The Diverse and Exploding Digital Universe (2008), Extracting Value from Chaos (2011)

Fiction:
Charles StrossAccelerando and other works.
Stanisław Lem
Jacek Dukaj
Peter WattsBlindsight
Neal Stephenson
Bruce Sterling
William Gibson
Dan Simmons
Iain Banks
Walter Jon WilliamsAristoi
Ian McDonald

Vacations

December is a quiet month (as November was, mostly). I took a break from coding to “reset my mind”. Our rat family has grown temporarily, we had 17 beasts for one day, but that’s all temporary. Still only 4 of them are ours. I’ve been playing Skyrim, The Binding of Isaac and recently, Terraria with the new 1.1 update. After some fooling around with friends in multi-player, I started a single player playthrough with hardcore character. That means, if he dies – it’s over. It reminds me of roguelikes in that every move can be your last if you’re not careful. I already buried two characters – one died from falling damage in a corrupted chasm, the other was burned to a crisp by lava thanks to my lack of attention. We’ll see if the next one succeeds in at least activating the hard mode. It’s a very fun game, highly recommended. I also bought the new Dungeons of Dredmor DLC/expansion Realm of the Diggle Gods and will give it a shot soon. Dungeons of Dredmor is an indie graphical roguelike with insane sense of humor, containing skills like Fleshsmithing, Mathemagic, Necronomiconomics or Emomancy. It’s a great entry to the roguelike world if you haven’t play any yet.

That’s it for now, happy holidays everyone!

Kids Christmas Tree

Recently my friend published an iPhone/iPod/iPad game for kids, which is in essence decorating a virtual Christmas tree. It’s dirt cheap, fun and features wonderful hand-drawn art. Get it, you still have some time!

So, Heimdall

What I’ve been doing lately? Playing Skyrim, playing The Binding of Isaac, procrastinating and thinking about internal structure of a MMORPG game server, roughly in that order.

Wait, what? A MMORPG game server?

Yeah. Let this be an introduction to Heimdall – my personal pet project since around spring this year. Heimdall is (going to be) the engine for a (pseudo) isometric 2.5D MMORPG inspired by Ultima Online. I was a player and an administrator/programmer for many custom UO shards back in the days. I actually learned C# to be able to script RunUO, the best UO server emulator out there. Some time ago I and a couple of my friends came to a conclusion that it would be really nice to have a game like UO, but without its limitations, with our own world, lore and freedom to create things we would like to see out there. Game that is not another WoW clone, but a sandbox without meaningless “kill ten bears” quests all over the place, game where you could actually roleplay, fight and have good old-fashioned fun.

Of course at the beginning I was very skeptic to an idea of making a MMO from scratch. I’m a software engineer and a gamer, I know damn well how complicated it would be. To think of it, MMORPGs are probably one of the most complex pieces of software in existence. Let’s think about what topics you and your team need to know about:

  • Have damn good design skills to come up with a half-decent, maintanable and extendable architecture for the whole thing
  • Network programming on a pretty sophisticated level
  • Databases and storage backends
  • Security, on multiple levels (server, client, network)
  • Actual game design, which is enormous topic in itself (basic mechanics, world lore, map design, quests, encounters, etc etc)
  • Artificial Intelligence (or artificial stupidity) for your hostile entities
  • Graphics programming
  • Asset creation – drawing, modelling, creating sounds and music
  • GUI creation, usability, extendability of client UI
  • Patching, content distribution
  • Probably lots of other things I forgot

And that’s without a whole slew of issues that appear if you want to be “big”: server/database sharding, reliability, system/network engineering, knowledge of financial processing systems… Yeah, that’s A LOT of things to take care of. I knew that. But I still took the challenge. It may take years to come up with something usable, but it’s worth it for the learning experience alone for me.

So where do I stand now? I have the basic system architecture planned. I have an account/authentication server working (creating acounts, logging in, selecting game servers etc). I have a first prototype of graphical client in progress. Now I’m at the point of the biggest initial challenge (IMHO): to proceed with the initial prototype, I need to have base design for actual game server mechanics. First iteration requirement includes player avatars moving on the map, able to see each other. That means game server needs to process/store game world entities. Game entities need to be able to interact with each other, at least on a basic “perception” level. Coming up with a good, extendable and maintanable architecture for game entities is harrowing. Especially if you don’t know what will be added in the future.

At the moment I’m planning to use entity system approach instead of the traditional OO class tree. I’ll talk about it in more detail in a future post most likely, but that’s it for now.

OPERA neutrinos still rocking

So, the faster-than-light neutrinos may actually be real. Improved version of the original experiment confirms the initial result. Of course real “proof” would be repeating that in another place by an entirely different team. We’ll see. I’m cautiously optimistic.

On WinAPI timers and their resolution

While working on PuttyRec (that is practically rewriting it from scratch) I wondered about resolution of various Windows timer APIs. Of course that’s pretty irrelevant in the context of a terminal recorder, not that you need to cope with more that a few events per second there. But being the curious man I am (and sometimes a perfectionist when it comes to code) I set to investigate the matter myself.

What selection do we have then? There is the SetTimer, of course. PuttyRec used it before and that worked without much problems. SetTimer has its problems though, the biggest being that it’s only available to use on UI threads (that is, threads owning a message queue). Although creating a message queue is easy (just call any message-related API), that’s hardly convenient. It also has reputation of being more than slightly inaccurate.

Then we have timeSetEvent, a multimedia timer. It doesn’t require message queue (but also runs on a separate thread) and is supposed to be more accurate. The MSDN page contains a curious notice though: Note This function is obsolete. New applications should use CreateTimerQueueTimer to create a timer-queue timer. A “better” function, eh? I used it before and it also seemed to work well.

Interestingly MSDN doesn’t specify what resolution these functions have. That’s pretty useless if you need a high-precision timer. I wrote a quick and dirty test program that runs all three of the above timers for a period of one second with varying timer period. As a reference I included a “busy wait” loop that just spins for desired amount of time. Time measurement was done by QueryPerformanceCounter. Without further ado, here are the results (32bit release, but 64bit/debug is roughly the same):

Period: 100ms
CreateTimerQueueTimer    : count=   9, avg error= 0.085%, std dev= 0.193
timeSetEvent             : count=   9, avg error= 0.013%, std dev= 0.017
Busy wait                : count=   9, avg error= 0.000%, std dev= 0.000
SetTimer                 : count=   8, avg error= 9.629%, std dev= 2.060

Period: 50ms
CreateTimerQueueTimer    : count=  19, avg error= 0.109%, std dev= 0.140
timeSetEvent             : count=  19, avg error= 0.027%, std dev= 0.022
Busy wait                : count=  19, avg error= 0.000%, std dev= 0.000
SetTimer                 : count=  15, avg error=24.800%, std dev= 3.117

Period: 20ms
CreateTimerQueueTimer    : count=  49, avg error= 0.177%, std dev= 0.242
timeSetEvent             : count=  49, avg error= 0.106%, std dev= 0.095
Busy wait                : count=  49, avg error= 0.135%, std dev= 0.656
SetTimer                 : count=  31, avg error=55.518%, std dev=12.167

Period: 10ms
CreateTimerQueueTimer    : count=  99, avg error= 0.216%, std dev= 0.197
timeSetEvent             : count=  99, avg error= 0.192%, std dev= 0.257
Busy wait                : count=  99, avg error= 0.122%, std dev= 0.537
SetTimer                 : count=  63, avg error=60.329%, std dev=35.078

Period: 5ms
CreateTimerQueueTimer    : count= 199, avg error= 0.796%, std dev= 3.244
timeSetEvent             : count= 199, avg error= 0.257%, std dev= 0.380
Busy wait                : count= 199, avg error= 0.014%, std dev= 0.106
SetTimer                 : count=  63, avg error=212.087%, std dev=74.290

Period: 2ms
CreateTimerQueueTimer    : count= 499, avg error= 2.291%, std dev=12.107
timeSetEvent             : count= 499, avg error= 0.790%, std dev= 0.831
Busy wait                : count= 499, avg error= 0.006%, std dev= 0.005
SetTimer                 : count=  63, avg error=680.188%, std dev=209.531

Period: 1ms
CreateTimerQueueTimer    : count= 999, avg error= 4.185%, std dev=11.480
timeSetEvent             : count= 999, avg error= 1.268%, std dev= 1.695
Busy wait                : count= 999, avg error= 0.225%, std dev= 3.743
SetTimer                 : count=  62, avg error=1450.387%, std dev=415.344

What can we say about that?

  • Obviously, inaccuracy raises as the period gets smaller.
  • SetTimer is really inaccurate. Even with a 100ms period it was off by 10%, and below that it’s just useless.
  • Busy wait was of course the most accurate.
  • CreateTimerQueueTimer was remarkably worse than the “obsolete” timeSetEvent! What’s going on here?
  • timeSetEvent was performing really well even with the smallest periods. Errors below 1%, low standard deviation. Deprecated my ass.

So there you have it. I’d recommend using timeSetEvent for good precision, and if that’s not enough for you – timeSetEvent with short busy wait at the end to refine the result.

And the source code:

#include <math.h>
#include <Windows.h>
#include <MMSystem.h>

#pragma comment(lib, "winmm")

LARGE_INTEGER freq;
double elapsed1[10000], elapsed2[10000], elapsed3[10000], elapsed4[10000];
int idx1, idx2, idx3, idx4;

// timer queue
void CALLBACK timer1_callback(void* param, BOOLEAN unused)
{
    static LARGE_INTEGER old = {0};
    LARGE_INTEGER current;

    if (old.QuadPart == 0)
        QueryPerformanceCounter(&old);

    QueryPerformanceCounter(&current);
    double elapsed = (current.QuadPart-old.QuadPart)/(double)freq.QuadPart;
    elapsed1[idx1] = elapsed;
    old.QuadPart = current.QuadPart;
    idx1++;
}

// MM timer
void CALLBACK timer2_callback(UINT uTimerID, UINT uMsg, DWORD_PTR param, DWORD_PTR dw1, DWORD_PTR dw2)
{
    static LARGE_INTEGER old = {0};
    LARGE_INTEGER current;

    if (old.QuadPart == 0)
        QueryPerformanceCounter(&old);

    QueryPerformanceCounter(&current);
    double elapsed = (current.QuadPart-old.QuadPart)/(double)freq.QuadPart;
    elapsed2[idx2] = elapsed;
    old.QuadPart = current.QuadPart;
    idx2++;
}

// busy wait
void timer3_callback()
{
    static LARGE_INTEGER old = {0};
    LARGE_INTEGER current;

    if (old.QuadPart == 0)
        QueryPerformanceCounter(&old);

    QueryPerformanceCounter(&current);
    double elapsed = (current.QuadPart-old.QuadPart)/(double)freq.QuadPart;
    elapsed3[idx3] = elapsed;
    old.QuadPart = current.QuadPart;
    idx3++;
}

// SetTimer
DWORD WINAPI UiThread(void* param)
{
    static LARGE_INTEGER old = {0};
    LARGE_INTEGER current;
    MSG msg;
    DWORD period = (DWORD)param;

    SetTimer(0, 1, period, 0); // this creates message queue

    while (1) // message loop
    {
        if (GetMessage(&msg, 0, 0, 0))
        {
            switch (msg.message)
            {
            case WM_TIMER:
                if (old.QuadPart == 0)
                    QueryPerformanceCounter(&old);

                QueryPerformanceCounter(&current);
                double elapsed = (current.QuadPart-old.QuadPart)/(double)freq.QuadPart;
                elapsed4[idx4] = elapsed;
                old.QuadPart = current.QuadPart;
                idx4++;
                break;
            }
        }
    }

    return 0;
}

void display_stats(double* array, int count, DWORD period, WCHAR* name)
{
    double off, min, total=0, avg=0, max=0, stddev=0;
    min = period*10; 

    count--;
    for (int i=1; i<count+1; i++)
    {
        off = fabs(array[i]-period/1000.0)/(period/1000.0)*100.0;
        total += off;
        if (off < min)
            min = off;
        if (off > max)
            max = off;
    }
    avg = total / count;

    for (int i=1; i<count+1; i++)
    {
        off = fabs(array[i]-period/1000.0)/(period/1000.0)*100.0;
        stddev += (off-avg)*(off-avg);
    }
    stddev /= (count-1);
    stddev = sqrt(stddev);

    wprintf(L"%-25s: count=%4d, avg error=%6.3f%%, std dev=%6.3f\n", name, count, avg, stddev);
}

int _tmain(int argc, _TCHAR* argv[])
{
    LARGE_INTEGER pc1, pc2;
    QueryPerformanceFrequency(&freq);
    DWORD periods[] = {100, 50, 20, 10, 5, 2, 1}; // timer periods in ms

    timeBeginPeriod(1); // set best multimedia timer resolution, in case it affectso ther timers

    for (int p=0; p<7; p++)
    {
        DWORD period = periods[p];
        wprintf(L"\nPeriod: %dms\n", period);

        // timer queue
        idx1 = 0;
        HANDLE timer1;
        CreateTimerQueueTimer(&timer1, NULL, timer1_callback, 0, 0, period, 0);
        QueryPerformanceCounter(&pc1);
        Sleep(1000);
        QueryPerformanceCounter(&pc2);
        DeleteTimerQueueTimer(NULL, timer1, 0);
        display_stats(elapsed1, idx1, period, L"CreateTimerQueueTimer");

        // MM timer
        idx2 = 0;
        MMRESULT timer2 = timeSetEvent(period, 0, timer2_callback, 0, TIME_PERIODIC);
        QueryPerformanceCounter(&pc1);
        Sleep(1000);
        QueryPerformanceCounter(&pc2);
        timeKillEvent(timer2);
        display_stats(elapsed2, idx2, period, L"timeSetEvent");

        // busy waiting
        idx3 = 0;
        double slice = period/1000.0;
        QueryPerformanceCounter(&pc1);
        while ((pc2.QuadPart-pc1.QuadPart)/(double)freq.QuadPart < 1)
        {
            // "timer" function
            timer3_callback();

            // delay till next loop
            do
            {
                QueryPerformanceCounter(&pc2);
            }
            while ((pc2.QuadPart-pc1.QuadPart)/(double)freq.QuadPart < slice*idx3);
        }
        QueryPerformanceCounter(&pc2);
        display_stats(elapsed3, idx3, period, L"Busy wait");

        // user32 SetTimer
        idx4 = 0;
        HANDLE thread = CreateThread(0, 0, UiThread, (void*)period, 0, 0);
        QueryPerformanceCounter(&pc1);
        Sleep(1000);
        QueryPerformanceCounter(&pc2);
        TerminateThread(thread, 0);
        display_stats(elapsed4, idx4, period, L"SetTimer");
    }
    timeEndPeriod(1);

    return 0;
}

Roguelike-like on strike

I’ve been slacking a bit lately. My excuse is that I’ve been playing some really interesting games.

Let’s start with Breath of Death VII: The Beginning. I got it along with Cthulhu Saves the World, but wanted to play the weaker thing first. Both are retro-style hack&slash RPGs with a healthy dose of humour. In Breath of Death VII you take control of a skeletal knight DEM in a post-apocalyptic world populated by undead. You assemble a party, kill monsters and save the world (sort of). It was fun, althought the fighting became a bit tiresome at the end. Still, Cthulhu is supposed to be even better. Both games cost almost nothing, so get them!



~ ~ ~

Next up: Spelunky. I stumbled upon it while reading old Rock, Paper, Shotgun archives. It can be described as a roguelike-inspired platformer. Like randomly-generated dungeons, death lurking everywhere and fiendish difficulty? Enjoying being eaten alive by man-eating plants, shot to death by angry shopkeepers, mauled by cavemen, exploded, crushed, torn by spikes and traps? Get it! It’s free! Spelunky features nice pixel art, great music and is a work of just one man: Derek Yu. Bonus: if you’d rather watch other people being mutilated by this game, see this. It’s hilarious.



~ ~ ~

Finally, there is The Binding of Isaac. I’ve heard about it before, but thought that its arcade-shootery action isn’t for me. Boy, was I wrong. I got myself Voxatron at the Humble Bundle, and a day later they added Isaac to the package. Now I had no excuse to try it. It’s a grotesque-themed twin-stick shooter mixed with a roguelike. You play as Isaac (or other unlockable characters) journeying through a randomly-generated basement filled with his personified childhood fears. Gather (random) powerups, collect unique items, kill (lots of) stuff. It’s weird, it’s fun, it’s addictive. I needed all my willpower to stop myself clicking that “try again” button. Get it!




Let there be HFONT

After some preliminary refactoring of PuTTY Recorder’s code I started it and was greeted with an unresponsive window. It wasn’t completely locked, just very, very slow at updating. First thought – some kind of rampant recursion in OnPaint handler, but that would lock the window up for good. So I launched the profiler… and found nothing unusual. Dialog procedure was on top of inclusive samples of course, and then just updating and painting – well duh, I knew that already. Tried to profile with instrumentation instead of sampling in hope of getting better accuracy, but that also got me nowhere. Huh. I stepped through the program initialization and everything seemed to be in order. Oh well, time for the best debugging method – DebugPrint()! I added print statements on top of the most suspicious functions and restarted the application.

PuttyRecDlg::OnPaint
TerminalFrame::Draw
PuttyRecDlg::OnUpdate
PuttyRecDlg::OnPaint
TerminalFrame::Draw
PuttyRecDlg::OnUpdate
PuttyRecDlg::OnPaint
TerminalFrame::Draw

Uh-oh. As I watched the output, I realized that each Draw call took seconds to complete. What the hell? It’s just some text rendering and one bitmap blit. It worked perfectly before. The only major change was that I added the ability for user to select font used for terminal rendering.

void TerminalFrame::Draw(HDC hdc, UINT startx, UINT starty, UINT char_width, UINT char_height) const
{
    if (m_font == 0)
        THROW("No font selected");

    SelectObject(hdc, m_font);

Font wasn’t null since I wasn’t getting exceptions. Checked manually – yeah, SelectObject() call was successful. Then I realized that despite font being seemingly OK, no text was appearing in the window. What gives? I ran the program again, waited agonizingly until it stopped updating and selected some font manually. Lo and behold, that seemed to fix everything – window became responsive and text was visible. Let’s see where the font is being created for the first time then.

void TerminalFrame::SetFont(const LOGFONT* logfont)
{
    if (m_font)
    {
        DeleteObject(m_font);
        m_font = 0;
    }
    m_font = CreateFontIndirect(logfont);
    if (!m_font)
        THROW("CreateFont failed");
}

I put a breakpoint there and restart. What do you know, logfont is uninitialized. Apparently I forgot to set it to something sensible. But wait a second. If logfont is garbage, how does CreateFontIndirect() work? It returns something and is NOT apparently failing. Just when you use the resulting font, text operations are excruciatingly slow (and don’t do much).

So, TLDR: You can create a font from nothing, but don’t expect it to work.