Post image

Простота данных залог производительности

Принимая участие в многочисленных проектах я заметил неприятную, непонятную мне тенденцию: “товарищи по цеху” часто городят страшные конструкции для описания сущностей, вместо простых данных используют сложные структуры с текстовыми полями, глубокими вложенностями. Как пример возьмем простую игру “три в ряд”, где у ячеек расположенных на игровом поле присутствуют, как минимум, три параметра описывающих их: цвет, тип, состояние. Вот самое “безобидное” описание логической ячейки что я видел:

public struct Cell
{
  public string Type;
  public string State;
  public Color Color;
}

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

Вот вам пример ужасненького кода (from RL):

public bool IsSameTypeAndState(Cell a, Cell b)
{
   return a.Type != null && b.Type != null && a.Type.Contains(b.Type)
          && a.State != null && b.State != null && a.State.Contains(b.State);
}

К счастью, существуют методы более удачного представления подобных данных.

Запись байтами

Рассмотрим пример структуры Cell приведенного выше. Есть три поля которые вряд ли выйдут за пределы диапазона 256 значений. При этом поле Color это логический цвет ячейки. Тогда эту структуру можно представить как массив из трех байт, записав в виде одно беззнакового числа uint (Даже останется место для четвертого значения)

byte color, type, state;
uint cell = color << 16 | state << 8 | type << 0;

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

if(a == b)...

Чтобы получить записанное значение type, state или color нужно всего лишь сдвинуть число на необходимое количество бит.

color = cell >> 16;

public bool IsSameTypeAndState(uint a, uint b)
{
   return a >> 8 == b >> 8 && (byte) a == (byte) b;
}

Этот метод можно применять не только к играм в стиле “три в ряд”. В своей игре Bubbly Tap я использую подобный подход чтобы компактно записать и сохранить граф уровня. Есть массив нод представленных с помощью ushort где первый байт - тип ноды, второй байт - её состояния. И массив связей, также ushort, где в оба байта записаны индексы из массива нодов. Итог: описание самого большого уровня помещается в файл размером 254 байта.

Чистый код

В этом методе есть один недостаток - код относительно плохо читается. Трудно запомнить байтовые значения всех типов, цветов, состояний, а сам код может превратиться в лапшу из битовых сдвигов. К счастью в c# (и в других популярных языках) есть Enum и расширения (Extension Methods).

Для удобства, при помощи enum можно записать все возможные варианты полей:

public enum CellColor:byte
{
   None = 0x0,
   Red = 0x1,
   Green,
   Blue,
   ...
}

С помощью расширения (Extension Methods) получать значение необходимого поля из целого числа:

public static CellColor ToColor(this uint value)
{
   return (CellColor)value >> 16;
}

CellColor color = cell.ToColor();

Вывод

Старайтесь использовать простые представления данных, чем проще формат данных, тем проще с ними работать, не только вам но и процессору с памятью. Думайте о данных в первую очередь! О способе обработки подумаете в будущем, когда появится четкое представление что необходимо обрабатывать. Правильный подбор структур данных даст вам прирост производительности, скорости написания логики, читаемости кода.

Небольшой бонус, код реализации описанного выше метода:

Author image

Саломатин Андрей

Инди разработчик с приличным стажем в game dev индустрии и тяжелой формой зависимости от игр. Со основатель независимой игровой студии Near Fancy. Программист, гейм дизайнер и уборщик в одном лице :)