**EASTL Design**

## Введение

EASTL (EA Standard Template Library) — это шаблонная библиотека, которая включает и расширяет функциональность стандартной библиотеки C++ STL, улучшая её различными способами, полезными для разработки игр. Большая часть дизайна EASTL идентична стандартной STL, поскольку большая часть STL хорошо спроектирована для многих целей. Основные области, в которых EASTL отличается от стандартных реализаций STL:

*   EASTL имеет упрощённую и более гибкую схему пользовательского выделения памяти.
*   Код EASTL легче читать.
*   В EASTL есть контейнеры и алгоритмы расширения.
*   Оптимизации EASTL предназначены для разработки игр.

Из вышеперечисленного только метод выделения памяти является несовместимым отличием от STL. Метод определения пользовательского распределителя для EASTL немного отличается от метода стандартной STL, хотя они на 90% похожи. Однако эти 10% различий делают EASTL в целом проще и мощнее в использовании, чем стандартная STL. Контейнеры без пользовательских распределителей действуют одинаково в EASTL и стандартной STL.

## Мотивация

Наши мотивы для создания EASTL определяют его дизайн. Как указано в RFC (Request for Comment), основные причины для реализации собственной версии STL следующие:

*   <span class="458151900-03082005"><font><font>Некоторые реализации STL (особенно Microsoft STL) имеют характеристики производительности ниже среднего, что делает их непригодными для разработки игр. EASTL быстрее всех существующих реализаций STL.</font></font></span>
*   STL иногда трудно отлаживать, так как большинство реализаций STL используют загадочные имена переменных и необычные структуры данных.
*   Иногда с распределителями STL сложно работать, так как у них много требований, и их нельзя изменить после привязки к контейнеру.
*   STL включает избыточную функциональность, которая может привести к увеличению кода. Нелегко сказать программистам, чтобы они не использовали эту функциональность.
*   STL реализован с очень глубокими вызовами функций. Это приводит к неприемлемой производительности в неоптимизированных сборках, а иногда и в оптимизированных сборках.
*   STL не поддерживает выравнивание содержащихся объектов.
*   Контейнеры STL не позволяют вставлять запись в контейнер без предоставления записи для копирования. Это может быть неэффективно.
*   Полезные расширения STL (например, slist, hash_map, shared_ptr), найденные в существующих реализациях STL, таких как STLPort, не являются переносимыми, потому что их нет в других версиях STL или они непоследовательны между версиями STL.  

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

*   Существуют юридические проблемы, из-за которых нам трудно свободно использовать переносимые реализации STL, такие как STLPort.
*   Мы не можем влиять на дизайн и реализацию STL и поэтому не можем изменить её в соответствии с нашими потребностями.

## Основные принципы

Реализация EASTL прежде всего руководствуется следующими принципами, перечисленными в порядке важности.

1. Эффективность (скорость и использование памяти).
2. Правильность.
3. Переносимость. **Читаемость**

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

Переносимость важна, но не критична. Да, EASTL должен компилироваться и работать на всех платформах, для которых мы выпускаем игры. Но мы не имеем в виду все компиляторы, которые можно было бы использовать для таких платформ. Например, Microsoft VC6 можно использовать для компиляции Windows-программ, но поддержка C++ в VC6 слишком слаба для EASTL, поэтому вы просто не можете использовать EASTL под VC6.

Читаемость — это то, чего EASTL достигает лучше, чем многие другие шаблонные библиотеки, особенно Microsoft STL и STLPort. Мы прилагаем все усилия, чтобы сделать код EASTL чистым и разумным. Иногда наша потребность в оптимизации (особенно связанной с type_traits и типами итераторов) приводит к менее простому коду, но эффективность является нашей главной директивой, и поэтому она перевешивает все остальные соображения.

**Поточно-ориентированная работа**

Недостаточно просто сказать, что EASTL является потокобезопасным или небезопасным. Однако мы можем сказать, что с точки зрения безопасности потоков EASTL делает всё правильно.

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

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

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

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

**Дизайн контейнера**

Все контейнеры EASTL следуют набору согласованных соглашений. Здесь мы определяем прототипный контейнер, который имеет минимальную функциональность, которой должны обладать все контейнеры (не адаптеры). Некоторые контейнеры (например, стек) явно являются адаптерами контейнеров и, таким образом, оборачивают или наследуют свойства упакованного контейнера способом, специфичным для реализации. **Что делает EASTL**

allocator<T>::rebind<U>::other. Наконец, вы не можете получить доступ к этому распределителю после создания контейнера. Есть несколько веских академических причин, почему стандарт C++ работает таким образом, но это приводит к большому количеству ненужной боли и усложняет реализацию таких концепций, как отслеживание памяти.

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

В EASTL принято решение не копировать распределители между контейнерами во время операций обмена и назначения контейнеров. Это означает, что если контейнер A обменивается содержимым с контейнером B, оба контейнера сохраняют свои исходные распределители. Аналогично, назначение контейнера A контейнеру B приводит к тому, что контейнер B сохраняет свой исходный распределитель. Эквивалентные контейнеры должны сообщать об этом через оператор ==; EASTL выполнит интеллектуальный обмен, если распределители равны, и обмен грубой силой в противном случае.  

```cpp
// Распределитель EASTL  

class allocator  
{  
public:  
    allocator(const char* pName = NULL);  

    void* allocate(size_t n, int flags = 0);  
    void* allocate(size_t n, size_t alignment, size_t offset, int flags = 0);  
    void  deallocate(void* p, size_t n);  

    const char* get_name() const;  
    void        set_name(const char* pName);  
};  

allocator* GetDefaultAllocator();
```

## Дизайн контейнеров фиксированного размера

EASTL предоставляет набор контейнеров фиксированного размера, которые пользователь может использовать, хотя пользователь также может реализовать свои собственные версии. Таким образом, помимо класса list есть класс fixed_list. Класс fixed_list реализует связанный список через фиксированный пул непрерывной памяти, который не имеет накладных расходов пространства (в отличие от обычного heap), не вызывает фрагментации и выделяет очень быстро.

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

## Алгоритмический дизайн

Алгоритмы EASTL во многом следуют философии стандартных алгоритмов C++, поскольку эта философия надёжна и эффективна. Одним из основных аспектов алгоритмов является то, что они работают с итераторами, а не с контейнерами. Вы заметите, например, что алгоритм поиска принимает первый и последний итераторы в качестве аргументов, а не контейнер. Это имеет два основных преимущества: позволяет пользователю указать поддиапазон контейнера для поиска и позволяет пользователю применять алгоритм поиска к последовательностям, которые не являются контейнерами (например, массив C).

Алгоритмы EASTL оптимизированы, по крайней мере, так же хорошо, как лучшие алгоритмы STL, найденные в коммерческих библиотеках, и значительно оптимизированы по сравнению с алгоритмами, поставляемыми с первыми библиотеками STLs, которые поставляются с компиляторами. Наиболее важно то, что алгоритмы EASTL используют преимущества типов признаков содержащихся классов и типов итераторов для оптимизации генерации кода. Например, если вы изменяете размер массива целых чисел (или другого типа «pod»), EASTL обнаружит, что это можно сделать с помощью memcpy вместо медленного перемещения объекта за объектом, как это сделал бы Micrsoft STL. **Поддержка кода в EASTL**

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

**Дизайн интеллектуальных указателей**

EASTL реализует следующие типы интеллектуальных указателей:
* shared_ptr;
* shared_array;
* weak_ptr;
* intrusive_ptr;
* scoped_ptr;
* scoped_array;
* linked_ptr;
* linked_array.

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

1. Интеллектуальные указатели EASTL позволяют назначить им распределитель.
2. В EASTL shared_ptr удаление реализуется через шаблонный параметр вместо динамически выделяемого интерфейса объекта-члена.

Что касается назначения распределителя, это даёт EASTL больший контроль над распределением памяти и отслеживанием, поскольку интеллектуальные указатели Boost в одностороннем порядке используют глобальный оператор new для выделения памяти из глобальной кучи.

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

**list::size — O(n)**

На момент написания статьи в EASTL есть три класса связанных списков: list, slist и intrusive_list. В каждом из этих классов размер списка не кэшируется в переменной-члене size. В результате получение размера списка не является быстрой операцией, так как требует обхода списка и подсчёта узлов. Мы могли бы сделать функцию list::size быстрой, имея переменную-член mSize, которая отслеживает размер при вставке и удалении элементов. Есть причины иметь такую функциональность и причины её не иметь. Сейчас мы решили не использовать переменную-член mSize, так как это добавит четыре байта к классу, добавит небольшое количество обработки к таким функциям, как insert и erase, и будет служить только для улучшения функции size, а не других. В случае intrusive_list это нанесёт дополнительный вред. Альтернативный аргумент заключается в том, что стандарт C++ гласит, что std::list должен быть операцией O(1) (то есть иметь переменную-член size), что многие стандартные реализации библиотеки C++ делают это, что размер — это всего лишь целое число, которое быстро обновляется, и что многие пользователи ожидают иметь быструю функцию size. В конечном счёте мы разрабатываем библиотеку для разработки игр, и производительность имеет первостепенное значение, поэтому мы решили не кэшировать размер списка. Пользователь всегда может реализовать кэш размера самостоятельно.

**basic_string не использует копирование при записи**

Основное преимущество CoW заключается в том, что он позволяет совместно использовать строковые данные между двумя объектами строк. Таким образом, если вы скажете это:
```cpp
string a("hello");  
string b(a);
```
«привет» будет общим для a и b. Если вы затем скажете это:
```cpp
a = "world";
```
тогда a освободит свою ссылку на «привет» и оставит b с единственной ссылкой на него. Обычно эта функциональность достигается за счёт подсчёта ссылок и атомарных операций или мьютексов.

Стандарт C++ ничего не говорит о basic_string и CoW. Однако для того, чтобы реализация basic_string соответствовала стандартам, возникает ряд проблем, которые определяют некоторые вещи о том, как нужно было бы реализовать строку CoW. Обсуждение этих проблем здесь повторяться не будет, так как вы можете прочитать ссылки ниже для получения более подробной информации, чем можно предоставить здесь. Однако мы можем сказать, что C++...