Эффективная итерация больших объемов данных

Прежде всего, я должен сказать, что это делается для сервера онлайн-игр, который отслеживает каждый объект на карте, будь то игрок или ИИ (NPC или как вы хотите это называть).

Он должен не только следить за ними, но и уведомлять среди игроков своих ближайших игроков. Я решил это, и в настоящее время я использую многопоточный подход, который отлично работает.

Я храню все эти объекты в хэш-таблице. Мы можем считать эту хеш-таблицу unordered_mapхотя я на самом деле использую rde::hash_map, так как это быстрее при вставке и извлечении (самопроверка), хотя и занимает больше оперативной памяти (теперь это не проблема).

Дело в том, что карта хранит уникальный идентификатор объекта (64 бита) плюс указатель объекта, что-то вроде:
rde::hash_map<UInt64, Object*>

Моя проблема:

Мое приложение (сервер) должно выполняться в цикле (внутри потока), который должен вызываться каждые ~ 50 мс, чтобы все работало гладко. Код цикла выглядит следующим образом:

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;
}
}

А теперь, к сути, функция map::update() который вызывает увеличение цикла до значений 4500 мс.

Каждый раз, когда вызывается обновление, объект карты должен проверять, добавлен ли новый объект в хранилище. Если объект добавляется, этот объект должен уведомить все другие объекты о добавляемом объекте, что я и делаю (псевдокод):

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

Позже, внутреннее обновление каждого объекта должно быть вызвано, я делаю это (снова псевдокод):

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

И, если этого было недостаточно, вышеуказанный цикл должен быть расширен до:

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)

Объедините первый цикл (добавление и уведомление) с циклом обновления следующим образом:

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)

Это работает, пока количество объектов невелико, и как только оно увеличивается, циклы начинают занимать до 4 секунд, что выходит далеко за пределы 50 мс, которые я ищу.

Есть ли другой способ оптимизировать это еще больше? Я думал об использовании октодеревьев, чтобы отслеживать положение объектов на карте, но потом пришел к выводу, что это только усугубит проблему.

Я также разделил каждую карту на 35 единиц (35 — «диапазон просмотра», LOS) объекта, так что данный rde::hash_map содержит только единицы, которые должны быть видны друг другу, поэтому они нуждаются в обновлениях. Работает, пока количество объектов мало …

Что еще я мог сделать? Спасибо!

Заметка

Всех тех foreach являются циклами с использованием итераторов, таких как rde::hash_map<...>::iterator от objects.begin() в objects.end()

Другие варианты, такие как отсутствие обновления, если нет игрока (реальный пользователь, а не NPC), освобождение памяти, когда на данной карте нет игрока, и тому подобное, уже принимаются во внимание.

 |
|
\|/
V