Публикации Проекты Форум Работа
ПрограммированиеСтатьиОбщее

Строковые идентификаторы в движке. string pools.

Автор:

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

Введение
Обзор способов представления строки
  Способ представления: string
  Способ представления: string + static unordered_map
  Способ представления: указатель на строку в глобальном хранилище строк
  Способ представления: индекс типизированный
Исходники
Дополнение: имена объектов
Дополнение: типизация имён по типу ресурсов.

Введение

В этой статье рассмотрены различные способы представления строки, которые позволяют оптимизировать сравнение строк и размер одного инстанса строки.

Обзор способов представления строки

Рассматриваемые основные способы:

СпособПлюсыМинусы
string-просто-медленно
-много памяти занимает
string+static unordered_map-просто
-быстрое сравнение		-строки далеко друг от друга в памяти.
указатель на строку в глобальном хранилище строк-быстрое сравнение
-эффективное использование памяти		-сложно
индекс типизированный-быстрое сравнение
-самое эффективное использование памяти
sizeof(Name)-2(65536) или 3(16777216)		-в отладчике имя ресурса невидно
-вывести для отладки сложно

Способы через равенство "Str" == "Str", хеши, кодоген енама строк, COW строки рассмотрены не будут, так как ведут к множеству неочевидных проблем.

А теперь подробнее про эти методы.
Далее при представлении используются следующие обозначения:
D-длина строки
Памяти: байт на инстанс.
Время сравнения: временная сложность O(...).

Способ представления: string

Просто строка.

Для больших проектов, где имена ресурсов могут быть 500+ символов этот способ не подходит из-за его низкой скорости сравнения строк и большого использования памяти.

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

Памяти: 16(или больше) + D(если строка не влезла в хранилище самого класса).
Время сравнения: D.

class NameString
{
public:
  explicit NameString(const char* name): _s(name) {}

  string get()
  {
    return _s;
  }

  std::strong_ordering operator<=>(NameString const& b) const = default;
private:
  string _s;
};

Способ представления: string + static unordered_map

Первый же запрос из гугла выдаёт способ с помошью статической переменной и свойств emplace.
https://stackoverflow.com/questions/20938441/implementing-a-strin… d-not-to-move
Статическая переменная выступает в роли синглтона. Создаёт инстанс и даёт к нему доступ.
А emplace возвращает итератор на уже имеющийся элемент или создаёт новый.
Сам unordered_set не инвалидирует указатели при добавлении элементов.

В итоге пара строк и простейший пуул готов.

Эффективность такого пуула очень низка. Строки находятся очень далеко в памяти и от этого запрос к строке практически гарантированно кэш мисс, скорее всего по всем 3 уровням. В итоге очень долгий запрос к памяти.

Зато просто реализовать.

Памяти: 8.
Время сравнения: 1.

class NamePoolMap
{
public:
  explicit NamePoolMap(const char* name): _s(name)
  {
    //https://stackoverflow.com/questions/20938441/implementing-a-string-pool-that-is-guaranteed-not-to-move
    static unordered_set<string> map;
    _s = map.insert(name).first->c_str();
  }

  string get()
  {
    return _s;
  }

  std::strong_ordering operator<=>(NamePoolMap const& b) const = default;

private:
  const char* _s;
};

Способ представления: указатель на строку в глобальном хранилище строк

Можно улучшить прошлый вариант запихнув все строки в отдельный Storage или virtual vector.

При добавлении новой строки она просто записывается в конец массива, а её указатель в массиве в таблицу.

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

Str/0Str1/0Str..

Если же зачем-то нужно иметь нули в строке, то следует записывать: размер строки + сама строка.

Можно так-же посмотреть, что в анреале сделали, этот класс я написал основываясь на том, что там сделали:
Fname

Памяти: 8.
Время сравнения: 1.

class NamePooled
{
public:
  explicit NamePooled(const char* name)
  {
    _s = Pool::get().add(name);
  }

  string get()
  {
    return _s;
  }

  std::strong_ordering operator<=>(NamePooled const& b) const = default;

private:
  using IdType = uint16_t;

  class Pool
  {
  public:
    static Pool& get()
    {
      static Pool inst;
      return inst;
    }

    const char* add(const char* name)
    {
      if (auto it = _set.find(name); it != _set.end())
        return *it;
      auto str = _store.add(name);
      _set.insert(str);
      return str;
    }

  private:
    class Store
    {
    public:
      const char* add(string name)
      {
        if (auto opt = _segments.back().add(name)) return *opt;
        _segments.emplace_back(max(name.size() + 1, segmentSizeBase));
        return *_segments.back().add(name);
      }

    private:
      static constexpr size_t segmentSizeBase = 10000;

      class Segment
      {
      public:
        explicit Segment(size_t size)
        {
          _data.resize(size);
        }

        optional<const char*> add(string const& s)
        {
          if (s.size() + 1 + _used > _data.size()) return {};
          ranges::copy(s, _data.begin() + _used);
          // Vector initialized to 0 anyway
          //_data[_used + s.size()] = 0; 
          auto res = &_data[_used];
          _used += s.size() + 1;
          return res;
        }

      private:
        std::vector<char> _data;
        size_t _used = 0;
      };

      vector<Segment> _segments = { Segment(segmentSizeBase) };
    };

    // You can write hasher that not need std::string instance.
    static inline auto hash = [](const char* e)
    {
      return std::hash<std::string>()(e);
    };
    static inline auto equal = [](const char* a, const char* b)
    {
      return strcmp(a, b) == 0;
    };

    std::unordered_set<const char*, decltype(hash), decltype(equal)> _set{ 0, hash, equal };

    // Here better use virtual vector
    Store _store;
  };

  const char* _s = nullptr;
};

Способ представления: индекс типизированный

Всё бы хорошо, но 8 байт для имени слишком много, да даже 4 многовато. А что если постараться ужать до 2 байт?

В итоге получается ещё 1 вариант, когда сохраняется не указатель, а индекс.

Более 2^16(~65'000) различных строк так не уместить, но оно и не в каждой игре столько нужно. Можно взять 3 байта, уж 2^24(~16'000'000) строк должно хватить.

Как создать int24 думаю известно. Int24

Памяти: 2.
Время сравнения: 1.

class NameId
{
public:
  explicit NameId(const char* name)
  {
    _id = Pool::get().add(name);
  }

  string get()
  {
    return Pool::get().conv(_id);
  }

  std::strong_ordering operator<=>(NameId const& b) const = default;

private:
  using IdType = uint16_t;

  class Pool
  {
  public:
    static Pool& get()
    {
      static Pool inst;
      return inst;
    }

    IdType add(const char* name)
    {
      if (auto it = _map.find(name); it != _map.end())
        return it->second;
      size_t idFull = _map.size();
      if (idFull > std::numeric_limits<IdType>::max())
        std::terminate(); // So many names
      IdType id = IdType(idFull);
      _map[name] = id;
      _mapId[id] = &_map.find(name)->first;
      return id;
    }

    string conv(IdType id)
    {
      return *_mapId[id];
    }

  private:
    unordered_map<string, IdType> _map;
    // WARN if use not std::unordered_map force std::string
    // place data outside of class and use const char*
    unordered_map<IdType, string const*> _mapId;
  };

  IdType _id = -1;
};

Исходники

В этой статье не рассматривается правильный форвардинг, какую мапу взять на замену медленной std и прочие вещи относящиеся к ньюансам C++. В С# вообще есть встроенный пул строк String.intern

Используется MSVC, C++20, x64.

+ Весь код

Дополнение: имена объектов

А что если именовать игровые объекты? Пулл строк быстро засорится...

Но есть решение. От Анреала и их FName класса.
Создаём новую структуру со строкой из пуула и индексом.
При добавлении новой строки парсится число после _.
При запросе заново его ставим туда.

SomeName_1000 -> {"SomeName", 1000}
SomeName_-42 -> {"SomeName_-42", -1}
SomeName_100000000000000000 -> {"SomeName_100000000000000000", -1}
SomeName_0 -> {"SomeName", 0}

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

Так можно получить имена объектов умещающиеся в 8 байт(3 бита на имя и 5 на индекс) ну или же в 16 байт и без хитрых преобразований.

Дополнение: типизация имён по типу ресурсов.

Все варианты обёрнуты в классы, сделано это для того чтобы нельзя было случайно сравнить разные типы.

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

И это можно использовать.

class ResourceId:private Name{}
class ResourceIdTexture:public ResourceId{}
class ResourceIdMonster:public ResourceId{}

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

#C++

8 ноября 2022

Комментарии [39]

Участники Donate!
Контакт Сообщества Каталог сайтов Категории Архив новостей
GameDev.ru — Разработка игр
©2001—2024