Покорение 40к

Эта заметка есть разбор методик и приёмов, которые я использовал для решения проблемы производительности при генерации мира в рамках этой задачи в репозитории проекта.

Статья содержит немного кода, размышления и разбор собственных ошибок. Очевидными и не очень способами мне удалось ускорить генерацию на 1958%.

Кратко о генерации мира.

Итоговый мир в Last Imperial Vagabond получен путём инкрементальных изменений, выполняемых некоторыми сущностями — агентами — над данными мира. Я постарался отобразить основные объекты понимания последующих обсуждений.

Весь процесс можно рассматривать как историю реального мира:

1. Начиная с некоторой отсчётной точки в мире есть государства со своими городами (населёнными пунктами) и деятелями (агентами).
2. Деятели мира проявляют какую-то активность: возводят/улучшают/захватывают города, помогаю или мешают друг другу, воспитывают последователей и т.д.
3. Этот цикл (итерация) многократно повторяется, создавая ход времени. Мир меняется.

В результате чего появляются густонаселённые города, выделяются специализации. Часть городов переходят из рук в руки между государствами, эмулируя войны. Деятели взаимодействуют друг с другом, становятся более влиятельными и знаменитыми или исчезают с мировой арены.

Я поставил себе цель выполнить 40 000 итераций, прежде чем персонаж игрока появится в мире.

Постановка проблемы

В результате множества итераций мир на клиенте Unity генерируется недопустимо слишком долго. Субъективно, игра просто зависает. Фактически, можно дождаться завершения генерации. Но для этого нужно быть очень терпеливым. Всё это неудовлетворительно. Ну кто будет долго ждать, чтобы поиграть?

Вообще, странное обстоятельство. Как будет показано далее, по замерам код должен работать не более 3,5 секунд в среде Mono. Что сильно расходится с действительностью при запуске клиента на Unity. Может дело не в генерации мира? Я пробовал всякое: отключение, сокращение итераций, фиктивные пустые итерации. Все варианты работают, кроме желаемых 40 000 итераций.

Измерение проблемы

Хорошей практикой является выполнения оптимизаций по требованию. То есть никаких преждевременных оптимизаций. Обычно понятность, надёжность и корректность кода прекрасно дополняют друг друга. Чем понятнее решение, тем сложнее в нём ошибиться и сделать что-то не так. И наоборот, производительность может выступать конкурирующей метрикой. Может увеличиться и объём кода и использованы более сложные алгоритмы, что даёт дополнительные шансы оступиться при кодировании или неправильно понять код при чтении и модификации.

Такая позиция обязывает измерять внесённые изменения, чтобы получать хоть какую-то уверенность в положительном влиянии на производительность. Хорошо бы знать, за что было заплачено простотой и надёжностью.

Для измерения времени выполнения кода на C# я использую библиотеку BenchmarkDotnet. О достоинствах библиотеки можно ознакомиться на оффициальном сайте. Каждый бенчмарк (далее, бенч, для простоты) я запускаю, как NUnit-тест. Первоначально мне казалось, что так проще аккумулировать, искать и запускать бенчи. Сейчас я больше склонен к отдельному консольному приложению.

Код бенча выглядит следующим образом:

[Benchmark(Description = "CreateGlobeBench")]
public async Task Run()
{
        // Это то, что будет измеряться.
	await _generator.GenerateGlobeAsync();
}

[IterationSetup]
public void IterationSetup()
{
        // Это код предварительной подготовки.
        // Он не будет учитываться при замерах.
	var container = new ServiceContainer();

	// инстанцируем явно, чтобы обеспечить одинаковый рандом для всех запусков.
	container.Register<IDice>(factory => new Dice(1), new PerContainerLifetime());
	container.Register<ISchemeLocator>(factory => CreateSchemeLocator(), new PerContainerLifetime());
	container.Register<ISchemeService, SchemeService>(new PerContainerLifetime());
	container.Register<ISchemeServiceHandlerFactory, SchemeServiceHandlerFactory>(new PerContainerLifetime());

	// Для мира
	container.Register<IWorldGenerator, WorldGenerator>(new PerContainerLifetime());

	_generator = container.GetInstance<IWorldGenerator>();
}

Конфигурирование самого бенча я выполняю в отдельном классе. Мне важно знать время выполнения кода в среде CRL и Mono. Знания о работе кода в CLR используются в разработке корневого функционала, например, в unit-тестах. Время работы в Mono — даёт представление, как код будет работать в клиенте Unity, то есть в итоговой игре. Да и в целом интересно сравнить производительность в разных средах. К счастью, библиотека позволяет запускать код в разных окружениях. Кроме всего прочего можно замерить работу кода в окружении Core, просто добавив соответствующий job. Нет. С этим есть определённые трудности. И я постараюсь рассказать о них в одной из последующих заметок.

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

Что нам говорит эта таблица? Все сравнения по ходу заметки будут производится по столбцу Median. Это медиана среди 100 запусков. Согласно этой статье медиана даёт более адекватное представление, нежели среднее арифметическое (Mean в таблице). Потому что медиана меньше подвержена колебаниям. К сожалению, серьезные разлёты по времени очень даже могут быть.

Второй момент, на который можно обратить внимание — это стандартное отклонение (StdDev). Это «плюс-минус» от среднего, если я правильно понимаю. Если это значение начинает возрастать относительно среднего, значит код теряет стабильность.

Ну и последнее. Меня удивляет тот факт, что под Mono код выполняется быстрее, чем под CLR. В другой задаче, где я проводил замеры, Mono всегда проигрывал. Возможно позже я разберу, почему такая ситуация возникает.

Ещё пару слов о том, каким образом фиксируются изменения кодовой базы. Каждый раз, когда я получаю логически законченный набор изменений, я их проталкиваю его в репозиторий. И только после этого запускаю замеры. Такой подход был выбран, потому что замеры могут длиться достаточно долго. И пока бенчи выполняются, я работаю над следующими изменения, насколько это возможно. А в случае деградации производительности вернуться к проблемному фрагменту, благодаря магии git.

Обнаружение проблемы. Профилировщик студии.

Разумно предположить, что подавляющую часть времени должны отрабатывать как раз эти 40 000 итераций. Гипотеза есть. Ай-да исправлять всё, что кажется непроизводительным и глупым. Нет? Признаюсь честно, я так делал. И это были не самые эффективные исправления.

Для разработки я обычно использую Microsoft Visual Studio в качестве IDE. Меню Analyze -> Performance Profiler. Крутой и мощный инструмент. Он может показывать горячие точки при выполнении кода. И он оказался бесполезным.

Профилировщик говорит, что большую часть времени выполняется метод Run бенча. Это потому что библиотека BenchmarkDotnet для каждого окружения создаёт отдельную сборку, к которой залинкована тестируемая библиотека. Об этом упоминается в документации. Для профилировщика наш код считается внешним (external) при запуске бенча. Никаких выводов сделать невозможно.

По этой же причине отладка бенчей может стать трудной задачей. Наш код будет считаться сторонним, если его запустить из бенча. И инструменты отладки, такие как точки останова, не будут работать. Это одна из причин, почему я создаю по тесту на каждый бенч. Тесты запускают методы бенча явно, из тестового окружения. Так я могу заручиться всей мощью IDE для отладки бенчей.

Воспользуемся отладкой бенчей для профилирования нашего кода. У IDE есть такой инструмент, как Diagnostic Tools. Там множество всяких интересных метрик во время выполнения кода. На вкладке CPU Usage можно зафиксировать использование ресурсов процессора. Формирование отчёта будет происходить, когда выполнение кода остановится, например на точке останова. Чтобы по максимуму отсеять влияние всех прочих факторов сделаем так:

1. Поставим точки останова до и после вызова метода генерации мира. Назовём из т1 и т2 соответственно.
2. Запускаем отладку теста с бенчем. Когда произойдёт останов в т1, запустим запись использования CPU. И продолжим выполнение.
3. При остановке на т2 начнёт формироваться отчёт.

Ну вот. Хоть и полу-ручная методика, но уже похоже на наш код. Дальнейший переход подтверждает гипотезу. 95% времени генерации мира отъедают 40 000 итераций.

Более того, теперь есть представление, как именно распределяется время выполнения итераций. В топе две операции агентов (в коде называемых картами) — основание населённого пункта и смена места деятельности. 70% всего времени приходится на них. Выглядит, что над этими методами можно работать дальше.

Раунд 1. Linq2Foreach.

Дерево вызовов нам показывает, что в обоих картах самая ресурсоёмкие операции похожи. Это фильтрации населённых пунктов через linq:

// Карта ChangeLocality
// Съедает 29% общего времени.
var realmLocalities = globe.Localities.Where(x => x.Owner == agent.Realm && currentLocality != x).ToArray();

// Карта CreateLocality 
// Съедает 25% общего времени.
var realmLocalities = globe.Localities.Where(x => x.Owner == agent.Realm).ToArray();

Что делают эти строки? В обоих случаях они выбирают все населённые пункты, доступные для перемещения агента. То есть все населённые пункты того же государства, что и агент. Дальше из этого набора выбирается случайный населённый пункт. Второй метод выглядит некорректным с этой точки зрения. Карта создания населённого пункта перемещает агента в произвольный населённый пункт, если нет возможности основать новое поселение. Другими словами, агент, который попытался и не смог основать поселение, отправляется дальше искать подходящее место. То есть в случае неудачи должно происходить то же, что и в первой карте — простое перемещение агента.

Перенесём это выражение в отдельный метод и попробуем переписать на цикл foreach.

public static Locality RollTargetLocality(Globe globe, IDice dice, Agent agent, Locality currentLocality)
{
	var availableTransportLocalities = new List<Locality>();
	foreach (var locality in globe.Localities)
	{
		if (locality == currentLocality)
		{
			continue;
		}

		if (locality.Owner == agent.Realm)
		{
			availableTransportLocalities.Add(locality);
		}
	}

	if (!availableTransportLocalities.Any())
	{
		return null;
	}

	var rolledTransportLocalityIndex = dice.Roll(0, availableTransportLocalities.Count() - 1);
	var rolledTransportLocality = availableTransportLocalities[rolledTransportLocalityIndex];

	return rolledTransportLocality;
}

Бонусом — локализация кода в едином месте позволяет сократить дублирование кода. Выполним замеры после изменения.

Вот это да! 31% прироста в окружении Mono. Это при том, что кардинально ничего не изменилось. Вероятно, linq требуются дополнительные ресурсы чтобы быть проще и удобнее, что без деталей описано в этой статьей.

Пробуем запустить на клиенте. Всё ещё неприемлемо долго. По ощущениям ничего не изменилось. Что ж, шоу продолжается.

Изменения. Раунд 2. Linq2Foreach.

Дальнейший анализ вызовов привёл к карте захвата населённого пункта. Эта карта переводит населённый пункт под контроль государства, от лица которого действовал агент. Если в населённом пункте были чужие агенты, то они выполняют перемещение в произвольные населённые пункты своего государства. Словом, выполняются такие же действия, что были описаны выше, в раунде 1.

Заменяем linq новым методом.

Деградация на 6% для Mono. Но с точки зрения качества кода, изменение положительное — убирает дублирование. Сложно сделать какие-то выводы, почему так произошло, особенно с учётом предыдущего объяснения.

Раунд 3. Удар в память.

На глаза попадается график использования памяти.

Целая куча отметок наверху говорит о том, что сборщик мусора непрерывно пытается освободить память. Это потому, что объем требуемой памяти все время растёт. Воспользуемся другим инструментом диагностики — Memory Usage. Этот инструмент позволяет сделать слепок памяти и показать объекты, которые в нём хранятся.

Всё понятно. Каждое действие агента создаёт объект истории. Каждая запись истории содержит строковое описание и номер итерации. Посмотрим, насколько сильно это влияет.

Прирост производительности на 39% для Mono. Неплохо. Но клиент на Unity исполняет этот код всё ещё долго.

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

Раунд 4. Повторный удар в память.

Зацепившись за память, я так же обнаружил 1601 подозрительных списков агентов.

Ответственным за всё был следующий код:

public static class Helper
{
	public static void AddAgentToCell(Dictionary<TerrainCell, List<Agent>> cells, TerrainCell cell, Agent agent)
	{
		if (cells.TryGetValue(cell, out var list))
		{
			list.Add(agent);
		}
		else
		{
			list = new List<Agent> { agent };
			cells[cell] = list;
		}
	}

	public static void RemoveAgentFromCell(Dictionary<TerrainCell, List<Agent>> cells, TerrainCell cell, Agent agent)
	{
		if (cells.TryGetValue(cell, out var list))
		{
			list.Remove(agent);
		}
	}
}

Этот вспомогательный класс использовался для кеширования списков агентов по узлу на глобальной карте. Списки нужны, чтобы потом быстро получить список агентов, например, в населённом пункте. Кеш заполняется по мере того, как агенты начинают распространяться по миру. Но когда агент удаляется из узла, может оказаться, что он последний. Тогда в памяти хранится просто пустой список. Попробуем подчищать пустые списки.

public static void RemoveAgentFromCell(Dictionary<TerrainCell, List<Agent>> cells, TerrainCell cell, Agent agent)
{
	if (cells.TryGetValue(cell, out var list))
	{
		list.Remove(agent);

		// ---- Новый код
		if (!list.Any())
		{
			cells.Remove(cell);
		}
	}
}

Неоднозначное изменение. Так можно снизить объём потребляемой памяти. Но, возможно, это будет отъедать время на создание нового списка в случае. Если все агенты вышли из определённого узла, а затем один из агентов опять перешёл в этот узел. Проверяем, насколько это повлияло.

9% деградация в Mono. Что подтверждает опасения, сделанные перед замером. Значит к этому фрагменту нужно будет ещё раз вернуться и, возможно, откатить изменения.

Раунд 5. Linq2Foreach.

Обнаружены родственные блоки кода в картах взаимодействия между агентами. Linq-выражения, которые выбирают доступных агентов. Затем из доступных выбирается случайный. Попробуем переписать их аналогичным образом.

Запускаем. И…

Что?! 36 секунд?!

Общее время выполнения бенча заняло более 2 часов.

Конечно, в процессе разработки я не ждал 2 часа. Сам метод генерации фиксирует время своего выполнения через Stopwatch. И запуск одиночного теста на бенч мне уже дал грубую оценку. Но, для заметки, ради чистоты эксперимента, я выполнил всё те же 100 запусков для каждой среды.

Раунд 6. NoTempLists.

Далее я сделал не совсем логичное действие. Позже этот шаг помог. Но конкретно в этот момент он был просто лишним. Разумно было предположить, что эти изменения не окажут особого влияния. Тем не менее я попробовал отыграться и реализовать выбор агентов без промежуточного списка доступных.

Идея алгоритма такая:

1. Выбираем произвольное значение индекса для всех агентов. Это будет текущий индекс.
2. Если агент в мире под этим индексом удовлетворяет условиям, то возвращаем его.
3. Если нет, то смещаем индекс на 1. Индекс нужно закольцевать. Потому что справа может и не оказаться подходящих элементов.
4. Заканчиваем поиск если вернулись к индексу, с которого начали.

private Agent GetTargetAgent(Agent currentAgent,
                             List<Agent> agents,
							 IDice dice)
{
	var agentCount = agents.Count();
	var agentIndex = dice.Roll(0, agentCount - 1);
	var startIndex = agentIndex;
	Agent targetAgent = null;
	while (targetAgent != null)
	{
		var agent = agents[agentIndex];

		if (agent != currentAgent && 0 < agent.Hp)
		{
			targetAgent = agent;
		}

		agentIndex++;
		if (agentIndex >= agentCount)
		{
			agentIndex = 0;
		}

		if (startIndex == agentIndex)
		{
			// Достигли точки, с которой начали обход.
			// Значит не нашли подходящего агента.

			break;
		}
	}

	return targetAgent;
}

По замерам становится всё хуже. Откатываем последние два раунда.

Раунд 7. RollCardUse.

Дальше я решил пойти на уменьшение действий агентами. Для каждого агента будем пробрасывать 2D6. На 7+ агент пропускает ход. Таким образом останется 40 000 итераций, но на каждой из них будет активными произвольные 2/3 агентов мира.

Итоговый результат не должен измениться, потому что итераций достаточно много.

Небольшой выхлоп. 10% в среднем от раунда 4, как последнего адекватного. Но в целом, изменение интересное. Потенциально, можно додумать что-то типа инициативы агентов. Чтобы агенты с разной вероятностью получали шанс выполнить действие.

Кроме того, бенч выступил тестом. Выполнение под Mono стало падать с ошибкой. Это произошло из-за того, что обращение к генератору рандома стало выполняться по-другому. Значит, изменилась и последовательность. Главный вывод, который я сделал — рандом работает по-разному в CLR и Mono. Позже можно будет это явно проверить.

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

Раунд 8. FixNRE.

Если речь идёт о производительности, то исключения — это совершенный убийца. Просто выделим отдельный метод. Его назначением будет выбор случайных координат и перемещение агента со всеми необходимыми проверками и кешированием.

Замеры:

* для Mono взят последний удачный замер

Итого, в Mono 13% прироста по сравнению с последним удачным замером.

Раунд 9. NoTempLists.

Итак, вернёмся к здравомыслию. Всё ещё самым долгим является выбор случайного населённого пункта. Значит нужно работать над ним. 50% времени выполняются 5% кода, цитируя Макконнелла.

Метод используется в 3 картах из 7. То есть почти в половине случаев. Краткое описание метода в его текущем состоянии:

1. Перебираем все населённые пункты.
2. Подходящие для перемещения помещаем в промежуточный список.
3. Выбираем элемент со случайным индексом из промежуточного списка.

Инженерное сообщество рекомендует всегда рассматривать сначала существующие решения. Для нашего алгоритма есть 2 ключевых требования: это случайный выбор и наличие условия, которому должен удовлетворять элемент. Один из самых эффективных способов тасовки элементов массива является алгоритм Фишера — Йетса. Но для этого нужно будет перетасовать весь массив. В то время, как мне нужен только один случайный элемент. К тому же, допустимо, но не желательно искажать первоначальный список.

Позже я нашёл решение через FindIndex(Int32, Int32, Predicate<T>), которое было бы компактнее и более универсальное. Но его я рассмотрю в рамках отдельно заметки.

А вообще, выбор алгоритмов обычно происходит исходя из данных. Рассмотрим краткие характеристики данных, с которыми предстоит работать:

• Количество элементов:
  • от 8 (стартовые города);
  • до 1600 (когда в сетке 40х40 везде есть города).
• Отношение подходящих элементов в массиве:
  • 16% (когда среди всех городов нужны только города текущего государства среди 8 государств, то есть одна восьмая).
  • 1% (когда государство подавлено и имеет только один город из 1600).
  • 99% (противоположно 1%).
• Упорядочить набор данных в каком-то виде не представляется возможным из-за условия.

В общем, могут быть достаточно разнообразные данные.

Я принял решение осторожно вернуться к наработкам позорного раунда 6. Ещё раз краткое описание алгоритма:

1. Выбираем случайный индекс из списка всех элементов.
2. Закольцовываем обход по всему списку (если достигли конца, то начинаем с начала). Для этого инкрементируем выбранный случайный индекс.
3. Условием выхода является нахождение подходящего элемента.
4. На случай, если подходящего элемента в списке нет, то проверяем, не вернулись ли мы к индексу, с которого начали обход.

Как видно из рисунка ниже, список и индекс может быть в 4 состояниях:

1. Подходящий элемент находится после случайно выбранного индекса. В этом случае мы просто перебираем все элементы, пока не наткнёмся на подходящий.
2. Сразу выбран подходящий элемент. Наиболее благоприятный исход.
3. Подходящий элемент находится перед случайно выбранным индексом. Для этого обход закольцовывается.
4. Список вообще не содержит подходящий элемент. Для этого мы отслеживаем момент, когда обошли все элементы и вернулись к индексу, с которого начали.

Создание промежуточных коллекций не требуется. Сложность алгоритма получается O(n). Вроде, основным характеристикам удовлетворяет. Забегая немного вперёд, с первого раза я его не реализовал без ошибок. Чтобы не вносить путаницу, здесь я не буду приводить код. Корректный код в следующем раунде.

Замеряем эффект от изменений.

Вероятно, это начало победы. Никогда не отчаивайтесь в поиске подходящего решения. И, может быть, найдёте лучшее. Как видно по замерам, алгоритм, который был бесполезен в одном случае, оказался сокрушительно эффективным в другом.

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

Раунд 10. Fix.

Такой страшный прирост производительности лично меня сразу заставляет всё перепроверять. Генерация, наконец-то, запустилась на клиенте. Теперь большая часть времени уходит просто на инициализацию игровых объектов и рендеринг. Однако карта выглядит нерабочей.

На самом деле я внёс новый баг. Это как раз тот случай, когда более производительная версия метода имеет больший простор для ошибок. Ошибка глупая, но серьезная. Корректная версия, проверенная на тестах, выглядит так:

public static Locality RollTargetLocality(List<Locality> localities,
IDice dice,
Realm agentRealm,
Locality currentLocality)
{
	var count = localities.Count();
	var currentIndex = dice.Roll(0, count - 1);
	var startIndex = currentIndex;
	Locality targetLocality = null;
	while (targetLocality == null)
	{
		var locality = localities[currentIndex];

		currentIndex++;

		// Зацикливаем индекс
		if (currentIndex >= count)
		{
			currentIndex = 0;
		}

		// Проверяем обход всего набора
		if (startIndex == currentIndex)
		{
			// Достигли точки, с которой начали обход.
			// Значит не нашли подходящего агента.

			break;
		}

		if (locality == currentLocality)
		{
			continue;
		}

		if (locality.Owner == agentRealm)
		{
			targetLocality = locality;
			break;
		}
	}

	return targetLocality;
}

Замеры

Корректный вариант работает быстрее, что не может не радовать.

Раунд 11. NoGuid.

На раунде 10 можно было бы остановиться. Но я решил выполнить финальный анализ вызовов методов в CPU Usage. В карточке на захват локации выбирается случайная соседняя локация. Для этого все соседние узлы сортируются в случайном порядке и берётся первый элемент:

var nextCoords = HexHelper.GetOffsetClockwise().OrderBy(item => Guid.NewGuid()).ToArray();
...
for (var i = 0; i < nextCoords.Length; i++)
{
// Если nextCoords[i] подходит для захвата, то результат найден.
// Прерываем цикл, возвращаем результат.
}

Обратим внимание на выражение OrderBy. Это решение было взято из ответа на Stackoverflow. Само по себе решение быстрое и компактное. Но как я несколько раз убедился на своём опыте, оно не так очевидно при объяснении. Однако из статьи на Stackoverflow можно попасть на другой ответ, где рассматривается другой алгоритм.

Документация говорит, что Guid.NewGuid является обёрткой на системной функцией Windows CoCreateGuid. Тут есть исходный код, который это подтверждает. Фунция CoCreateGuid, в свою очередь, удалённо вызывает UuidCreate. Не сомневаюсь, что инженеры Microsoft реализовали генерацию Guid лучшим способом, но использование двух и саму генерацию Guid для простой рандомизации 6 элементов выглядит перебором.

Вынесем этот фрагмент в отдельный метод и перепишем без Guid.NewGuid. Мне не нужна такая уж рандомизация всего набора координат. Достаточно будет, чтобы их обход начинался с произвольного смещения. Это будет означать, что агент будет выбирать случайный населенный пункт для захвата из доступных.

private static CubeCoords[] GetRandomCoords(int coordRollIndex)
{
	var coords = HexHelper.GetOffsetClockwise();
	var shuffledCoords = new CubeCoords[6];
	for (var i = 0; i < 6; i++)
	{
		var coordRollIndexOffset = (coordRollIndex + i) % 6;
		shuffledCoords[coordRollIndexOffset] = coords[i];
	}

	return shuffledCoords;
}

Это метод на вход будет принимать случайное число от 0 до 5. Этот же метод будет использовать в CanUse с аргументом 0 для проверки, есть ли вообще доступные для захвата населённые пункты.

Финальный и сокрушительный удар позволил ещё получить 2х скорости.

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

Итоговый анализ всех изменений

Здесь я привёл замеры всех изменений.

На графиках я ввёл ограничения, чтобы раунды 5-6 не растягивали шкалу. Определённо, некоторые изменения требуют отката или доработок.

Выводы

Какие выводы можно было сделать из всех этих изменений:

1. Перевод linq не всегда менее производителен, чем аналогичный foreach. Хоть это и противоречит логике. Но, безусловно, linq более читабелен.
2. Чтобы работало правило «50% времени выполняется в 5% кода», нужно больше времени уделять объединению кода в общих методах. По грубой оценке, можно было добиться аналогичных результатов в 3 раза быстрее (3 из 11 изменений оказались наиболее эффективными).
3. Быстрые временные решения лучше сразу локализовать в отдельный метод. Так временный код не будет размазан по стабильному коду и его проще будет заменить более надёжным и производительным.
4. В коде, который предполагается часто выполнять, не нужно использовать генерацию guid без лишней надобности.
5. Всегда нужно стараться сохранять хладнокровие и методично работать над горячими точками. Это позволяет быстрее решать проблему (закапитанил).

P.S.

Для сравнения, замеры на релизной сборке:

Для CLR есть весомые различия. Для Mono — не очень. Но глядя на цифры, различиями вообще можно пренебречь.

P.P.S.

Решение через List<T>.FindIndex(int startIndex, int count, Predicate<T> match):

* Замеры проводились на другой машине, поэтому цифры разные относительно замеров в теле статьи. Но важно знать разлёт.

В итоге был получен универсальный метод для выбора произвольного элемента списка. Хороший кандидат на слияние. Изменения в коммите aa96c5a реализация.

public static class ListHelper
    {
        public static T RollRandom<T>(List<T> list, IDice dice, Predicate<T> predicate) where T: class
        {
            var count = list.Count;
            var currentIndex = dice.Roll(0, count - 1);

            var foundIndex = list.FindIndex(currentIndex, predicate);
            if (foundIndex > -1)
            {
                return list[foundIndex];
            }

            if (foundIndex >= 0)
            {
                foundIndex = list.FindIndex(0, currentIndex, predicate);
                return list[foundIndex];
            }
            else
            {
                return null;
            }
        }
    }

А вот предварительное заполнение словаря списков агентов оказалось менее эффективным (см. раунд 3). Ключевая идея: создать пустые списки для всех возможных ключей. Потому что так или иначе хоть один агент попадёт в каждый узел. В конце все пустые списки одним махом будут вычищены.

* Замеры проводились на другой машине, поэтому цифры разные относительно замеров в теле статьи. Но важно знать разлёт.

Здесь код не буду приводить, так как он распределён по нескольким файлам. Итоговые изменения в e69f79c. По замерам выглядит эффективнее при каждом обращении проверять наличие элемента в словаре. А так же подчищать данные вместе с ключом, если они больше не нужны.