Минимизация использования памяти за счет обмена данными с другими объектами
"Определение":
Легковес - это шаблон проектирования программного обеспечения. Легковес - это объект, который минимизирует использование памяти, разделяя как можно больше данных с другими подобными объектами; это способ использовать объекты в большом количестве, когда простое повторяющееся представление потребовало бы неприемлемого объема памяти. - Википедия
Далее я продемонстрирую схему наилегчайшего веса на двух примерах в Го. Сначала я оптимизирую два кэша на основе памяти, которые полагаются на одни и те же базовые данные, а затем я оптимизирую другой кеш, содержащий повторяющиеся данные.
Давай перейдем к делу. Все примеры написаны на голанге, полные примеры приведены в приложении.
Преамбула
Для обоих примеров рассмотрим этот тип:
Игроки на игровой платформе. Это немного надумано, но для наших целей довольно просто. Пример:
Первый пример: один кеш, три метода поиска
Предположим, что мы хотим кэшировать каждый Player в нашем приложении в памяти для быстрого доступа, и нам нужно иметь возможность искать их по ID, Handle и стране Code. Первая (наивная) реализация может выглядеть так:
Они заполняются данными из базы данных, перебирая отдельные строки таблицы и для каждой заполняя экземпляр Player полями из каждой строки и добавляя его к каждой карте.
Карты используются для поиска, потому что они эффективны: когда у вас уже есть ключ, вам не нужно каждый раз перебирать всю структуру данных - O (n) , но может выполнять прямой поиск за постоянное время, O (1).
Это важная оптимизация, когда есть тысячи или миллионы игроков.
Давайте быстро рассмотрим функции поиска для каждого из перечисленных выше:
Довольно просто.
Но есть проблема: каждый проигрыватель существует трижды, занимая в три раза больше памяти, чем необходимо.
Давайте вернемся к нашим объявлениям в кэше и исправим это, назначив одну из карт в качестве «основы истины» или «точки отсчета», если хотите.
Объявление, использующее Player ID, кажется подходящим по двум причинам: потому что ID служит первичным ключом и потому что uint32 занимает гораздо меньше места, чем Player Handle, строка произвольной длины. Давайте проведем рефакторинг, чтобы:
Теперь playerCountryMap и playerHandleMap служат ссылками на playerIDMap. Очевидно, нам потребуется немного реорганизовать наши функции поиска:
Обратите внимание, что первая функция, FindPlayerByID, не изменилась. Второй, FindPlayerByHandle, теперь получит Player ID вместо Player и перейдет к вызову FindPlayerByID для завершения поиска.
Из-за двух поисков сложность теперь составляет O (2), а не O (1), что по-прежнему является постоянным временем, и разница в производительности между этими двумя подходами поэтому можно считать незначительным.
Третья функция немного интереснее. Мы создаем срез, инициализированный размером ID, полученным при первом поиске, а затем перебираем ID, просматривая их по отдельности и добавляя Player к срезу.
Нам не нужно проверять наличие ID, потому что мы контролируем кеш; мы знаем, что он существует. Из-за цикла сложность составляет O (n + 1) или просто O (n).
Это хуже, чем прямой поиск, поэтому у вас есть две стратегии:
- Продолжите эту реализацию, которая работает немного медленнее, но экономит память, или:
- Придерживайтесь исходной реализации, которая требует больше памяти, но имеет более быстрый поиск.
Вы можете - и должны - смешивать и сочетать эти две стратегии в каждом конкретном случае; всегда выбирайте стратегию, соответствующую ситуации.
В качестве последнего примечания к этому примеру вы также можете использовать указатели для справки вместо uint32s. Концепция будет той же, и вы можете всегда использовать указатели, которые ссылаются на исходные структуры, а не выполнять несколько взаимозависимых поисков.
Но имейте в виду, что наличие кеша с тысячами или миллионами указателей также увеличивает количество указателей, которыми GC должен управлять соответственно, что может негативно повлиять на время паузы GC.
Значения предпочтительнее, если вам не нужно изменять данные.
Второй пример: репликация данных
Предположим, что мы все еще кэшируем Players, но для этой конкретной части приложения мы можем с абсолютной уверенностью сказать, что все они играли в одни и те же игры.
Возможно, потому, что один из издателей видеоигр, CrashyGames, Inc., запросил локально управляемый список всех игроков на платформе, которые играли во все их игры, - возможно, чтобы они могли извиниться перед ними за сомнительное качество их игр?
Сразу видно, что можно сэкономить много памяти, не сохраняя поле Games для каждого Player. Поскольку нам по-прежнему нужно, чтобы это поле было частью типа данных, мы сохраним его отдельно, а затем добавим его в специальный Player, когда он будет запрошен.
Для этого нам понадобится второй тип данных, который мы назовем cachedPlayer:
Вы могли заметить, что имя начинается с строчной буквы «c»; мы не будем экспортировать этот тип, а будем использовать его только для внутренних целей, в пределах нашего кеша.
Это наш кеш и список игр:
На этот раз мы просто найдем их напрямую по ID, который представлен uint32. Но у CrashyGames миллионы игроков, поэтому такая оптимизация стоит того.
Итак, давайте погрузимся в код. Это не займет много времени. Сначала мы объявим на cachedPlayer удобный метод, который преобразует его в обычный Player:
Теперь мы можем реализовать поиск в кеше:
Я сохранил метод cachedPlayer.convertWith в чистом виде, используя дополнительные поля в качестве параметров, а FindPlayerByID - это закрытие переменной games, которая просто хранится в переменной уровня пакета, но вы можете реализовать его любым удобным для вас способом.
И вуаля! Теперь храним все ровно один раз. Вы даже можете перейти на следующий уровень и сохранить Player имена в отдельной структуре данных, если есть много повторяющихся имен.
Но остерегайтесь накладных расходов, связанных с выполнением сравнения имен и расширением структуры данных с помощью имен. Делайте это только тогда, когда есть реальная экономия.
Заключение
Схема наилегчайшего веса - ваш друг, но, как и во многих других вещах, необходимо соблюдать баланс; слишком много оптимизируйте, и вы вводите нежелательную сложность; оптимизируйте слишком мало, и ваше приложение становится неуклюжим и медленным.
Прежде чем принять решение об использовании легковесного шаблона, подумайте о размере своей структуры данных, а также о влиянии на читаемость кода и ремонтопригодность вашего приложения. И помните старую поговорку Дональда Кнута:
«Преждевременная оптимизация - корень всех зол».
А теперь оптимизируйте свой код!
