Spinning mirrors

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

Posted by omeg in C#, code, GUI, gwen.net

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%.

Posted by omeg in code, rant

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
QueryPerformanceCounter(&pc1);
UINT64 uu = 0;
for (UINT32 i = 0; i < loops; i++)
{
    uu += (UINT64)sqrt((double)i);
}
QueryPerformanceCounter(&pc2);
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

32bit:
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)

64bit:
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.

Also, a small quiz: why the times increase twofold on FP sqrts if I remove the (UINT64) cast in the inner loop (hint: look at the sum)?

(32bit, but it's similar for 64bit)
uu += sqrt((float)i);

Sqrt float: 41906.894 (1652612419)

To check how much casting the results to integer affects performance I also did test without it: sqrt functions returning double were summed to a double variable (same with floats). Results below:

Long double sum of sqrts: 21081851051977.781000

32bit:
Sqrt float: 12666.459 (549755813888.000000)
Sqrt double: 12647.830 (21081851051977.781000)
Fast uint sqrt: 23757.851 (1651579237)
Fast ulong sqrt: 92842.952 (1651579237)
Fast int sqrt: 28243.427 (2558293500)
Fast Q3 float sqrt: 11077.491 (549755813888.000000)
Fast Q3 double sqrt: 9390.088 (21062606916280.066000)

64bit:
Sqrt float: 7151.176 (549755813888.000000)
Sqrt double: 12596.555 (21081851051977.781000)
Fast uint sqrt: 20426.025 (1651579237)
Fast ulong sqrt: 35248.122 (1651579237)
Fast int sqrt: 24476.170 (2558293500)
Fast Q3 float sqrt: 3429.053 (549755813888.000000)
Fast Q3 double sqrt: 9192.112 (21062606916106.129000)

Integer sqrts are unaffected since they didn’t have casts anyway. Built-in sqrt is much faster now, but it’s outperformed by the invsqrt for doubles (and floats on x64)! Something to consider if you don’t need very accurate numbers (it’s still pretty damn accurate).

C++ sqrt performance comparison

32-native: 32bit executable with sqrts summed to native types (without casts)
32-uint64: 32bit executable with sqrts summed to UINT64

I wouldn’t be myself if I didn’t test the same algorithms in C#. Both “fast uint” and “fast ulong” algorithms translate without changes. Q3′s invsqrt just needs unsafe context to use pointers for bit conversions (using BitConverter is slooow). Results? Might surprise you (using .NET 4.0)

32bit summing to UINT64:
Sqrt double: 42939 (21081351068005)
Fast uint sqrt: 26769 (21081851045129)
Fast ulong sqrt: 120578 (21081851045129)
Fast Q3 float sqrt: 58303 (21062106914641)
Fast Q3 double sqrt: 60314 (21061877534026)

64bit summing to UINT64:
Sqrt double: 12597 (21081351068005)
Fast uint sqrt: 32374 (21081851045129)
Fast ulong sqrt: 24520 (21081851045129)
Fast Q3 float sqrt: 17643 (21062107732210)
Fast Q3 double sqrt: 6810 (21061877534026)

32bit summing to native types:
Sqrt double: 25200 (21081851051977.8)
Fast uint sqrt: 26084 (2151556361)
Fast ulong sqrt: 120248 (21081851045129)
Fast Q3 float sqrt: 38560 (5.497558E+11)
Fast Q3 double sqrt: 42891 (21062377537121.3)

64bit summing to native types:
Sqrt double: 13952 (21081851051977.8)
Fast uint sqrt: 28848 (2151556361)
Fast ulong sqrt: 24573 (21081851045129)
Fast Q3 float sqrt: 17068 (5.497558E+11)
Fast Q3 double sqrt: 5147 (21062377537121.3)

C# sqrt performance comparison

And as an appendix, source of all the algorithms used:

uint32_t FastSqrtUint(uint32_t a_nInput) // c++
{
    uint32_t op  = a_nInput;
    uint32_t res = 0;
    uint32_t one = 1uL << 30; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type

    // "one" starts at the highest power of four <= than the argument.
    while (one > op)
    {
        one >>= 2;
    }

    while (one != 0)
    {
        if (op >= res + one)
        {
            op = op - (res + one);
            res = res +  2 * one;
        }
        res >>= 1;
        one >>= 2;
    }
    return res;
}

uint64_t FastSqrtUlong(uint64_t a_nInput)
{
    uint64_t op  = a_nInput;
    uint64_t res = 0;
    uint64_t one = 4611686018427387904ul; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type

    // "one" starts at the highest power of four <= than the argument.
    while (one > op)
    {
        one >>= 2;
    }

    while (one != 0)
    {
        if (op >= res + one)
        {
            op = op - (res + one);
            res = res +  2 * one;
        }
        res >>= 1;
        one >>= 2;
    }
    return res;
}

#define SQRT_MAGIC_F 0x5f3759df
#define SQRT_MAGIC_D 0x5fe6ec85e7de30da

inline float invSqrtF(const float x)
{
    const float xhalf = 0.5f*x;

    union // get bits for floating value
    {
        float x;
        int i;
    } u;

    u.x = x;
    u.i = SQRT_MAGIC_F - (u.i >> 1);  // gives initial guess y0
    return u.x*(1.5f - xhalf*u.x*u.x);// Newton step, repeating increases accuracy
}

inline float fastSqrt_Q3(const float x)
{
    return x * invSqrtF(x);
}

inline double invSqrtD(const double x)
{
    const double xhalf = 0.5F*x;

    union // get bits for floating value
    {
        double x;
        long i;
    } u;

    u.x = x;
    u.i = SQRT_MAGIC_D - (u.i >> 1);  // gives initial guess y0
    return u.x*(1.5F - xhalf*u.x*u.x);// Newton step, repeating increases accuracy
}

inline double fastSqrt_Q3D(const double x)
{
    return x * invSqrt(x);
}

int ftbl[33]={0,1,1,2,2,4,5,8,11,16,22,32,45,64,90,128,181,256,362,512,724,1024,1448,2048,2896,4096,5792,8192,11585,16384,23170,32768,46340};
int ftbl2[32]={ 32768,33276,33776,34269,34755,35235,35708,36174,36635,37090,37540,37984,38423,38858,39287,39712,40132,40548,40960,41367,41771,42170,42566,42959,43347,43733,44115,44493,44869,45241,45611,45977};

int fisqrt(int val)
{
    int cnt=0;
    int t=val;
    while (t)
    {
        cnt++;
        t>>=1;
    }

    if (6>=cnt)
        t=(val<<(6-cnt));
    else
        t=(val>>(cnt-6));

    return (ftbl[cnt]*ftbl2[t&31])>>15;
}

static uint FastSqrtUint(uint a_nInput) // C#
{
    unchecked
    {
        uint op = a_nInput;
        uint res = 0;
        uint one = 1 << 30;
        // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint type

        // "one" starts at the highest power of four <= than the argument.
        while (one > op)
        {
            one >>= 2;
        }

        while (one != 0)
        {
            if (op >= res + one)
            {
                op = op - (res + one);
                res = res + 2 * one;
            }
            res >>= 1;
            one >>= 2;
        }

        /* Do arithmetic rounding to nearest integer */
        if (op > res)
        {
            res++;
        }

        return res;
    }
}

static ulong FastSqrtUlong(ulong a_nInput)
{
    unchecked
    {
        ulong op = a_nInput;
        ulong res = 0;
        ulong one = 1 << 62;
        // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint type

        // "one" starts at the highest power of four <= than the argument.
        while (one > op)
        {
            one >>= 2;
        }

        while (one != 0)
        {
            if (op >= res + one)
            {
                op = op - (res + one);
                res = res + 2 * one;
            }
            res >>= 1;
            one >>= 2;
        }

        /* Do arithmetic rounding to nearest integer */
        if (op > res)
        {
            res++;
        }

        return res;
    }
}

unsafe static float InvSqrtF(float x)
{
    float xhalf = 0.5f * x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i >> 1);
    x = *(float*)&i;
    x = x * (1.5f - xhalf * x * x);
    return x;
}

public static float SqrtF(float x)
{
    return x * InvSqrtF(x);
}

unsafe static double InvSqrtD(double x)
{
    double xhalf = 0.5 * x;
    long i = *(long*)&x;
    i = 0x5fe6ec85e7de30da - (i >> 1);
    x = *(double*)&i;
    x = x * (1.5 - xhalf * x * x);
    return x;
}

public static double SqrtD(double x)
{
    return x * InvSqrtD(x);
}

Posted by omeg in C#, C++, code, performance

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.

Posted by omeg in personal, rats

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

Posted by omeg in C#, code, GUI, gwen.net

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.

Posted by omeg in game development

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.

Posted by omeg in C#, code, entity systems, game development, Heimdall

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!

Posted by omeg in code, entity systems, game development, Heimdall

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 10¹¹ neurons and 10¹⁴ 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 10¹⁷ 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 10¹⁶ 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*10³³B (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*10³³ 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 Stross – Accelerando and other works.
Stanisław Lem
Jacek Dukaj
Peter Watts – Blindsight
Neal Stephenson
Bruce Sterling
William Gibson
Dan Simmons
Iain Banks
Walter Jon Williams – Aristoi
Ian McDonald

Posted by omeg in science