Приспособленец (Flyweight)

Паттерн Приспособленец (Flyweight) — структурный шаблон проектирования, который позволяет использовать разделяемые объекты сразу в нескольких контекстах. Данный паттерн используется преимущественно для оптимизации работы с памятью.

В качестве стандартного применения данного паттерна можно привести следующий пример. Текст состоит из отдельных символов. Каждый символ может встречаться на одной странице текста много раз. Однако в компьютерной программе было бы слишком накладно выделять память для каждого отдельного символа в тексте. Гораздо проще было бы определить полный набор символов, например, в виде таблицы из 128 знаков (алфавитно-цифровые символы в разных регистрах, знаки препинания и т.д.). А в тексте применить этот набор общих разделяемых символов, вместо сотен и тысяч объектов, которые могли бы использоваться в тексте. И как следствие подобного подхода будет уменьшение количества используемых объектов и уменьшение используемой памяти.

Паттерн Приспособленец следует применять при соблюдении всех следующих условий:

  • Когда приложение использует большое количество однообразных объектов, из-за чего происходит выделение большого количества памяти
  • Когда часть состояния объекта, которое является изменяемым, можно вынести во вне. Вынесение внешнего состояния позволяет заменить множество объектов небольшой группой общих разделяемых объектов.

Ключевым моментом здесь является разделение состояния на внутренне и внешнее. Внутреннее состояние не зависит от контекста. В примере с символами внутреннее состояние описывается кодом символа из таблицы кодировки. Так как внутреннее состояние не зависит от контекста, то оно может быть разделяемым и поэтому выносится в разделяемые объекты.

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

При создании приспособленца внешнее состояние выносится. В приспособленце остается только внутреннее состояние. То есть в примере с символами приспособленец будет хранить код символа.

Отношения в данном паттерне можно описать следующей схемой:

Паттерн Приспособленец (Flyweight) в C# и .NET

Формальное определение паттерна на C#:

class FlyweightFactory
{
    Hashtable flyweights = new Hashtable();
    public FlyweightFactory()
    {
        flyweights.Add("X", new ConcreteFlyweight());
        flyweights.Add("Y", new ConcreteFlyweight());
        flyweights.Add("Z", new ConcreteFlyweight());
    }
    public Flyweight GetFlyweight(string key)
    {
        if (!flyweights.ContainsKey(key))
            flyweights.Add(key, new ConcreteFlyweight());
        return flyweights[key] as Flyweight;
    }
}
 
abstract class Flyweight
{
    public abstract void Operation(int extrinsicState);
}
 
class ConcreteFlyweight : Flyweight
{
    int intrinsicState;
    public override void Operation(int extrinsicState)
    {
    }
}
 
class UnsharedConcreteFlyweight : Flyweight
{
    int allState;
    public override void Operation(int extrinsicState)
    {
        allState = extrinsicState;
    }
}
 
class Client
{
    void Main()
    {
        int extrinsicstate = 22;
 
        FlyweightFactory f = new FlyweightFactory();
 
        Flyweight fx = f.GetFlyweight("X");
        fx.Operation(--extrinsicstate);
 
        Flyweight fy = f.GetFlyweight("Y");
        fy.Operation(--extrinsicstate);
 
        Flyweight fd = f.GetFlyweight("D");
        fd.Operation(--extrinsicstate);
 
        UnsharedConcreteFlyweight uf = new UnsharedConcreteFlyweight();
 
        uf.Operation(--extrinsicstate);
    }

Участники

  • Flyweight: определяет интерфейс, через который приспособленцы-разделяемые объекты могут получать внешнее состояние или воздействовать на него
  • ConcreteFlyweight: конкретный класс разделяемого приспособленца. Реализует интерфейс, объявленный в типе Flyweight, и при необходимости добавляет внутреннее состояние. Причем любое сохраняемое им состояние должно быть внутренним, не зависящим от контекста
  • UnsharedConcreteFlyweight: еще одна конкретная реализация интерфейса, определенного в типе Flyweight, только теперь объекты этого класса являются неразделяемыми
  • FlyweightFactory: фабрика приспособленцев — создает объекты разделяемых приспособленцев. Так как приспособленцы разделяются, то клиент не должен создавать их напрямую. Все созданные объекты хранятся в пуле. В примере выше для определения пула используется объект Hashtable, но это не обязательно. Можно применять и другие классы коллекций. Однако в зависимости от сложности структуры, хранящей разделяемые объекты, особенно если у нас большое количество приспособленцев, то может увеличиваться время на поиск нужного приспособленца — наверное это один из немногих недостатков данного паттерна.Если запрошенного приспособленца не оказалось в пуле, то фабрика создает его.
  • Client: использует объекты приспособленцев. Может хранить внешнее состояние и передавать его в качестве аргументов в методы приспособленцев

Рассмотрим пример. Допустим, мы проектируем программу для моделирования города. Город состоит из отдельных домов, поэтому нам надо создать объекты этих домов. Однако домов в городе может быть множество: сотни, тысячи. Они могут иметь разный вид, отличаться по различным признакам. Однако, как правило, многие дома делаются по стандартным проектам. И фактически мы можем выделить несколько типов домов, например, пятиэтажные кирпичные хрущевки, многоэтажные панельные высотки и так далее.

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

В этом случае реализация строительства домов на C# с применением паттерна Flyweight могла бы выглядеть следующим образом:

class Program
{
    static void Main(string[] args)
    {
        double longitude = 37.61;
        double latitude = 55.74;
 
        HouseFactory houseFactory = new HouseFactory();
        for (int i = 0; i < 5;i++)
        {
            House panelHouse = houseFactory.GetHouse("Panel");
            if (panelHouse != null)
                panelHouse.Build(longitude, latitude);
            longitude += 0.1;
            latitude += 0.1;
        }
 
        for (int i = 0; i < 5; i++)
        {
            House brickHouse = houseFactory.GetHouse("Brick");
            if (brickHouse != null)
                brickHouse.Build(longitude, latitude);
            longitude += 0.1;
            latitude += 0.1;
        }
 
        Console.Read();
    }
}
 
abstract class House
{
    protected int stages; // количество этажей
 
    public abstract void Build(double longitude, double latitude);
}
 
class PanelHouse : House 
{
    public PanelHouse()
    {
        stages = 16;
    }
 
    public override void Build(double longitude, double latitude)
    {
        Console.WriteLine("Построен панельный дом из 16 этажей; координаты: {0} широты и {1} долготы", 
            latitude, longitude);
    }
}
class BrickHouse : House
{
    public BrickHouse()
    {
        stages = 5;
    }
 
    public override void Build(double longitude, double latitude)
    {
        Console.WriteLine("Построен кирпичный дом из 5 этажей; координаты: {0} широты и {1} долготы",
            latitude, longitude);
    }
}
 
class HouseFactory
{
    Dictionary<string, House> houses = new Dictionary<string, House>();
    public HouseFactory()
    {
        houses.Add("Panel", new PanelHouse());
        houses.Add("Brick", new BrickHouse());
    }
 
    public House GetHouse(string key)
    {
        if (houses.ContainsKey(key))
            return  houses[key];
        else
            return null;
    }
}

В качестве интерфейса приспособленца выступает абстрактный класс House, который определяет переменную stages — количество этажей, поскольку количество этажей относится к внутреннему состоянию, которое присуще всем домам. И также определяется метод Build(), который в качестве параметра принимает широту и долготу расположения дома — внешнее состояние.

Конкретные классы разделяемых приспособленцев — PanelHouse и BrickHouse отвечают за построение конкретных типов домов. Поскольку архитектурный план проектирования может точно задавать количество этажей для определенного типа дома, то в данном случае количество этажей устанавливается в конструкторе.

Фабрика HouseFactory создает два объекта дома для каждого конкретного приспособленца и возвращает их в методе GetHouse() в зависимости от параметра.

В роли клиента выступает класс Program, который задает начальные широту и долготу — внешнее состояние домов и использует фабрику для создания домов. Причем в реальности мы будем оперировать всего лишь двумя объектами, которые будут храниться в словаре в HouseFactory.

Подробнее

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

О таких сценах внутри игры мы как игровые разработчики и мечтаем. И именно для таких сцен как нельзя лучше подходит скромный шаблон с именем Приспособленец (Flyweight).

Лес для деревьев

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

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

С каждым деревом связаны следующие данные:

  • Полигональная сетка, описывающая его ствол, ветви и листву.
  • Текстура коры и листьев.
  • Положение и ориентация в лесу.
  • Индивидуальные настройки, такие как размер и оттенок, благодаря которым каждое дерево в лесу будет выглядеть индивидуально.

Если набросать описывающий все это код, получится нечто подобное:

class Tree {
  private:
    Mesh mesh_;
  Texture bark_;
  Texture leaves_;
  Vector position_;
  double height_;
  double thickness_;
  Color barkTint_;
  Color leafTint_;
};

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

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

Обратите внимание что данные в прямоугольнике одинаковы для всех деревьев.

class TreeModel {
  private:
    Mesh mesh_;
  Texture bark_;
  Texture leaves_;
};

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

Это очень напоминает шаблон Объект тип (Type Object). Оба основаны на делегировании части состояния объекта другому объекту, разделяемому между многими экземплярами. Только области применения у этих шаблонов разные. Область применения шаблона Объект тип — это минимизация количества классов, которые вам нужно определять при добавлении «типов» в свою модель объектов. В качестве бонуса вы получаете разделение памяти. А вот шаблон Приспособленец в первую очередь предназначен для увеличения эффективности использования памяти.

class Tree {
  private:
    TreeModel * model_;

  Vector position_;
  double height_;
  double thickness_;
  Color barkTint_;
  Color leafTint_;
};

Результат можно изобразить следующим образом:

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

Тысяча экземпляров

Для того чтобы минимизировать количество данных, передаваемых видеокарте, мы будем передавать общие данные, т.е. TreeModel только один раз. После этого мы будем по отдельности передавать индивидуальные для каждого экземпляра данные — позицию, цвет и размер. А затем просто скомандуем видеокарте «Используй эту модель для отрисовки всех этих экземпляров».

К счастью API современных видеокарт такую возможность поддерживает. Детали конечно гораздо сложнее и выходят за рамки рассмотрения этой книги, однако и в Direct3D и в OpenGL присутствует возможность рендеринга экземпляров (instanced rendering).

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

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

Шаблон приспособленец

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

При использовании метода рендеринга экземпляров (instanced rendering) дело даже не в том, что нужно много памяти, а в том что требуется слишком много времени чтобы прокачать данные о каждом дереве через шину видеокарты. Главное что базовая идея общая.

Шаблон решает эту проблемы с помощью разделения данных объекта на два типа: первый тип данных — это неуникальные для каждого экземпляра объекта данные, которые можно иметь в одном экземпляре для всех объектов. Банда четырех называет их внутренним (intrinsic) состоянием, но мне больше нравится название «контекстно-независимые». В нашем примере это геометрия и текстура дерева.

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

То что мы до сих пор видели, выглядит как простое разделение ресурсов и вряд ли заслуживает того чтобы называться шаблоном. Частично это вызвано тем, что в нашем примере присутствует очевидное свойство (identity), выделяемое в качестве разделяемого ресурса — TreeModel.

Я считаю этот шаблон менее очевидным (и поэтому более хитрым), когда он используется в случае где выделить свойства для разделяемого объекта не так легко. В таком случае возникает впечатление что объект магическим образом оказывается в нескольких местах одновременно. Давайте я продемонстрирую это на примере.

Место где можно пустить корни

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

Каждый из типов местности имеет ряд параметров, влияющих на геймплей:

  • Стоимость перемещения, определяющая скорость с которой игроки могут по ней двигаться.
  • Флаг, означающий что местность залита водой и по ней можно перемещаться на лодке.
  • Используемая для рендеринга текстура.

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

В конце концов мы усвоили наш урок с этим лесом.

enum Terrain {
  TERRAIN_GRASS,
  TERRAIN_HILL,
  TERRAIN_RIVER
  // другие типы местности...
};

А сам мир хранит здоровенный массив этих значений:

class World {
  private:
    Terrain tiles_[WIDTH][HEIGHT];
};

Чтобы получить полезную информацию о тайле используется нечто наподобие:

int World::getMovementCost(int x, int y) {
  switch (tiles_[x][y]) {
  case TERRAIN_GRASS:
    return 1;
  case TERRAIN_HILL:
    return 3;
  case TERRAIN_RIVER:
    return 2;
    // другие типы местности...
  }
}

bool World::isWater(int x, int y) {
  switch (tiles_[x][y]) {
  case TERRAIN_GRASS:
    return false;
  case TERRAIN_HILL:
    return false;
  case TERRAIN_RIVER:
    return true;
    // другие типы местности...
  }
}

Я использую для хранения 2D сетки многомерный массив. В C++ это эффективно, потому что все элементы упакованы в одном месте. В Java и других managed языках, мы бы получили просто массив строк, каждый из элементов которого был бы ссылкой на массив элементов столбика. Т.е. особой эффективностью в работе с памятью здесь не пахнет. В любом случае в реальном коде реализацию 2D сетки лучше спрятать. В примере такой подход выбран исключительно ради простоты.

Я использую для хранения 2D сетки многомерный массив. В C++ это эффективно, потому что все элементы упакованы в одном месте. В Java и других managed языках, мы бы получили просто массив строк, каждый из элементов которого был бы ссылкой на массив элементов столбика. Т.е. особой эффективностью в работе с памятью здесь не пахнет. В любом случае в реальном коде реализацию 2D сетки лучше спрятать. В примере такой подход выбран исключительно ради простоты.

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

Было бы здорово иметь настоящий класс для местности наподобие такого:

class Terrain {
  public:
    Terrain(int movementCost,
      bool isWater,
      Texture texture): movementCost_(movementCost),
    isWater_(isWater),
    texture_(texture) {}

  int getMovementCost() const {
    return movementCost_;
  }
  bool isWater() const {
    return isWater_;
  }
  const Texture & getTexture() const {
    return texture_;
  }

  private:
    int movementCost_;
  bool isWater_;
  Texture texture_;
};

Вы можете заметить что все методы здесь объявлены как const. Это не совпадение. Так как один и тот же объект используется в различном контексте, если мы его изменим, изменения одновременно произойдут и во всех остальных местах. Возможно это не то что вам нужно. Разделение объектов в целях экономии памяти — это оптимизация, не влияющая на видимое поведение приложения. Вот поэтому объект Приспособленец практически всегда делают неизменным (immutable).

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

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

class World {
  private:
    Terrain * tiles_[WIDTH][HEIGHT];

  // Другие вещи...
};

Каждый из тайлов, относящихся к одному типу местности указывает на один и тот же экземпляр местности.

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

class World {
  public:
    World(): grassTerrain_(1, false, GRASS_TEXTURE),
    hillTerrain_(3, false, HILL_TEXTURE),
    riverTerrain_(2, true, RIVER_TEXTURE) {}

  private:
    Terrain grassTerrain_;
  Terrain hillTerrain_;
  Terrain riverTerrain_;

  // Другие вещи...
};

Теперь мы можем использовать их для отрисовки земли следующим образом:

void World::generateTerrain() {
  // Fill the ground with grass.
  for (int x = 0; x < WIDTH; x++) {
    for (int y = 0; y < HEIGHT; y++) {
      // Добавляем немного холмиков.
      if (random(10) == 0) {
        tiles_[x][y] = & hillTerrain_;
      } else {
        tiles_[x][y] = & grassTerrain_;
      }
    }
  }

  // добавляем реку.
  int x = random(WIDTH);
  for (int y = 0; y < HEIGHT; y++) {
    tiles_[x][y] = & riverTerrain_;
  }
}

Могу сказать что это не самый лучший в мире алгоритм процедурной генерации местности.

Дальше вместо методов в World для доступа к параметрам местности мы можем просто возвращать объект Terrain напрямую:

const Terrain & World::getTile(int x, int y) const {
  return *tiles_[x][y];
}

Таким образом World больше не перегружен различной информацией о местности. Если вам нужны некоторые параметры тайла, вы можете получить их у самого объекта:


int cost = world.getTile(2, 3).getMovementCost();

Мы снова вернулись к приятному API работы с реальным объектом и добились этого практически без дополнительных накладных расходов: указатель обычно занимает не больше места чем перечисление.

Что насчет производительности?

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

Более подробно о прыганье по указателям (pointer chasing) и про промахи кеша (cache misses) можно почитать в главе Локализация данных (Data Locality.).

Как всегда при оптимизации стоит пользоваться золотым правилом сперва выполняем профилирование. Современное железо настолько сложно что производительность уже нельзя оценивать на глазок. Мои собственные тесты показали что применение шаблона приспособленец не дает падения производительности по сравнению с применением последовательностей. Более того приспособленец даже быстрее. Но тут стоит учитывать и то, насколько часто данные выгружаются из памяти.

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

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

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

    Обычно это значит что вам следует инкапсулировать их создание внутри некоторого интерфейса, который вначале будет производить поиск уже загруженных объектов. Пример такого сокрытия конструктора демонстрирует шаблон Фабричный метод (Factory Method)GOF.

    Чтобы иметь возможность возвратить ранее созданного приспособленцы, вам нужно хранить пул уже загруженных объектов. Если называть имена, то для их хранения можно использовать Пул объектов (Object Pool).
  • Когда вы используете шаблон Состояние (State), у вас часто возникает объект «состояние», который не имеет никаких полей, специфичных для машины, на которой это состояние используется. Для этого вполне достаточна сущность и методы состояния. В этом случае вы можете легко применять этот шаблон и переиспользовать один и тот же экземпляр состояния одновременное во множестве машин состояний.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *