Efficiently iterating large amounts of data

Question

Introduction

First of, I must say this is being done for an online game server, which keeps track of every object in a map, be it a player or an AI (NPC or however you want to call it).

It must not only keep track of them, but notify among the players their near players. I've solved this, and I'm currently using a multi-threaded approach, which perfectly works.

My problem

I'm storing all that objects in an hash table. We could consider that hash table to be an unordered_map, though I'm in fact using the rde::hash_map, as it is faster on inserting and fetching (self tested), though takes more RAM (not an issue now).

The thing is, that map stores a unique ID for the object (64 bits), plus the object pointer, something like: rde::hash_map<UInt64, Object*>

My problem is:

My application (a server) must run in a loop (inside a thread) which must be called every ~50ms, as to keep things runing smooth. The loop code looks as follows:

void loop()
{
    UInt32 prev = clock();
    UInt32 prevSleep = 0;
    while (1)
    {
        UInt32 diff = clock() - prev;
        prev = clock();

        maps.update() // Suppose map is a class, which stores the objects map

        if (diff <= 50 + prevSleep)
        {
            prevSleep = 50 + prevSleep - diff;
            sleep(prevSleep);
        }
        else
            prevSleep = 0;
    }
}

And now, to the point, the function map::update() which is the one causing the loop increasing to values of 4500ms.

Each time an update is called, the map object must check for new object being added to the store, if an object is added, that object must notify all the other objects of it being added, which I do by (pseudocode):

foreach obectsToBeAdded as joiner:
    foreach objectsList as object:
        joiner->notify(object);
        object->notify(joiner);

Later on, an internal update of each object must be called, I do it by (pseudocode again):

foreach objectsList as object:
    object->update();

And, if that was not enough, the above loop must be expanded to:

foreach objectsList as object:
    object->update()
    
    // Visit all the other objects
    // Called once every 1 sec for the object, not on every call
    foreach objectsList as other:
        if other != object:
            object->visit(other)

My attemp to optimize this

Merge the first loop (adding and notifying) with the update loop, as it follows:

foreach objectsList as object:
    foreach objectsToBeAdded as joiner:
        object->notify(joiner)
        joiner->notify(object)

    object->update()

    // Called once every 1 sec for the object, not on every call
    foreach objectsList as other:
        if other != object
            object->visit(other)

This works while the objects count is not big, as soon as it increases the loops start to take up to 4 seconds, which goes far beyond to the 50ms I'm looking for.

My question

Is there any other way of optimizing this even more? I've though about using octrees to keep track of the objects positions in the map, but then came to the conclusion that it would only worsen the problem.

I've also divided each map to 35 units (35 is the "view range", LOS) of an entity, so that a given rde::hash_map only contains units which are to be seen by each other, thus that need updates. Works as long as objects count is low...

What else could I do? Thank you!

Note

All those foreach are loops using iterators, like rde::hash_map<...>::iterator from objects.begin() to objects.end()

Other optimitzations, such as not updating if there's is no player (a real user, and not a NPC), freeing memory when no player is on a given map, and such, are already being taken into account.

Answer 1

The first optimization that comes to mind besides spatial segmentation so objects are only informed about changes near them (such as with a quadtree) is: Does EVERY object have to be informed about EVERY change? Why not tell each object, 'Every frame, I'll run your update method. In your update method you can look for everything you want to (for example, there might be a buffer of all changes that occurred this frame/in recent frames) and update yourself as you please'. This way you don't spend CPU cycles notifying objects about things they don't actually need to know or care about.

Also, have you run a CPU profiler on your program, and verified that the hot spots (where the most CPU time is being spent) are where you think they are?

See comments for further discussion:

 |
 |
\|/
 V