В 2014 году в движке Unity набралось столько критических изменений и новинок, что "пятерка" фактически была другим движком. И хотя многие за одинаковым фасадом не особо этого и заметили, но изменения коснулись всех компонентов движка, начиная от файловой системы и заканчивая рендером. Питерский офис EA имел свою ветку основного репозитария, отставая от мастера максимум на месяц. Я уже писал про различные реализации и типы строк в игровых движках, но в Unity была своя реализация, имевшая и положительные и отрицательные стороны, которая использовалась практически во всех подсистемах. К ней привылки, знали слабые стороны и плохие "use cases" и хорошие "best practices". Поэтому когда эту систему стали выпиливать из движка много чего поломалось, и если у обычных пользователей был сразу переход на новую версию и наблюдались только отголоски шторма, то допущенные до "тела" наловили много прикольных багов.
В движке были реализованы модные и удобные на тот момент COW (copy-on-write) - строки, «копирование при записи». Модные, потому что и Qt и GCC также имели свои реализации и продвигали их в стандарт, не случилось и хорошо, удобные - при создании и копировании таких строк алокации фактически сводились к нулю.
Основное отличие от общей реализации такого механизма в Qt/GCC было частичное копирование данных. Т.е. если было две строки "abcde" и "abc", то вторая ссылалась на буфер первой, но имела нужный размер. На момент профилирования уровня в `Sims Mobile`, было около 3к алокаций строк на старте, и далее примерно 1 алокация новой строки, каждые 40-50 фреймов, фактически раз в секунду. Все создания и копирования новых строк нивелировались этой системой, а чтобы понять насколько это все было круто - для сравнения похожий уровень на пк в какой-то внутренней технодемке на свежем UE4 на том же уровне, выдавал под 200 алокаций на фрейм, только на строках. Каждый фрейм! Какой-нибудь не очень свежий iPhone 5 банально загибался в попытке это все переварить на анриале.
Почему COW
Основная идея COW (copy-on-write) заключается в том, чтобы разделять один и тот же буфер данных между разными экземплярами строк и делать копию только тогда, когда данные в конкретном экземпляре изменяются. Это называется «копирование при записи», основная стоимость такой реализации — это дополнительная косвенная адресация при доступе к значениям строк, Unity поддерживал поддерживал COW-реализации с самой первой версии судя по истории коммитов. Ходили байки что сам Йоахимом Анте (CTO компании) лично писал и проектировал этот класс, и вообще всю систему локализации в движке, первые комиты с реализацией действительно датировались 2006-2007 годом, но авторства там не было, поэтому продаю за то, за что купил.
Почему убрали
Причина была в начавшемся переписывании кода движка на C++11, переводе местами нового кода на std::string и возникшем серьезном несоответствии между дизайном std::string и собственной реализацией COW. Стандартная библиотека стала больше использоваться в движке и местами это приводило к ситуациям, когда с COW строками начинали работать как с `const char*` и передавать его в виде сырых данных, т.е. фактически вы передали сырой указатель из shared_ptr и работаете с ним, а сам умный указатель продолжил жить своей жизнью. Когда оно свалится было только вопросом нескольких фреймов.
COW-строка имеет два возможных состояния: эксклюзивное владение буфером или совместное использование буфера с другими COW-строками. Операции присваивания и копирования могут перевести её в состояние совместного использования и обратно. А вот перед выполнением операции «запись» необходимо убедиться, что строка находится в состоянии владения и переход этот приводит к созданию новой копии и копированию содержимого буфера данных родительской в новый эксклюзивно используемый буфер.
В строке, предназначенной для COW, любая операция будет либо немодифицирующей («чтение»), либо напрямую модифицирующей («запись»). Это делает легким определение необходимости перевода строки в состояние владения перед выполнением операции. Однако в std::string ссылки, указатели и итераторы на изменяемое содержимое передаются более свободно, потому что каждая строка находится в состоянии эксклюзивного владения буфером, если выражаться терминами COW-строк. Даже простое индексирование значений в неконстантной строке (s[i]) возвращает ссылку, которую можно использовать для изменения строки.
Поэтому для неконстантной std::string каждая такая операция фактически может считаться операцией «записи» и должна рассматриваться как таковая в реализации COW. Для пример ниже приведен базовый код класс, который использовался в движке, я не буду касаться проблем инициализации из литералов. Это код показывает как присваивание и копирование были сведены почти к нулю:
using C_str = const char*;
using C_ref = const char&;
namespace uengine
{
class UString
{
using Buffer = vector<char>;
shared_ptr<Buffer> m_buffer;
USize m_length;
void ensureIsOwning()
{
if( m_buffer.use_count() > 1 )
{
m_buffer = make_shared<Buffer>( *m_buffer );
}
}
public:
C_str c_str() const
{
return m_buffer->data();
}
USize length() const
{
return m_length;
}
C_ref operator[]( const USize i ) const
{
return (*m_buffer)[i];
}
char& operator[]( const USize i )
{
ensureIsOwning();
return (*m_buffer)[i];
}
template< USize n >
UString( Raw_array_of_<n, const char>& literal ):
m_buffer( make_shared<Buffer>( literal, literal + n ) ),
m_length( n - 1 )
{}
};
}Здесь используется оператор присваивания по умолчанию, который просто делает копирование данных m_buffer и m_length. Точно так же работает и копирование при инициализации. Теперь посмотрим пример правильного использования таких строк:
int main()
{
UString str = "Unreal the best engine ever!";
C_str cstr = str.c_str();
// contents of `str` are not modified.
{
const char first_char = str[0];
auto ignore = first_char;
}
cout << cstr << endl;
}COW-строка находится в состоянии владения, инициализация переменной first_char просто копирует значение символа - всё в порядке. Но если разработчик случайно, как это происходило постоянно при работе с std::string, добавляет логическую копию строки, но не меняет значение строки, то начинаются проблемы:
int main()
{
UString str = "Unreal the best engine ever!";
C_str cstr = str.c_str();
// contents of `str` are not modified.
{
UString other = str;
// .... some works
const char first_char = str[0];
auto ignore = first_char;
// .... some works
}
cout << cstr << endl; //! Undefined behavior, cstr is dangling.
}Поскольку строка str находится в состоянии совместного использования, принцип COW заставляет операцию str[0] создать копию общего буфера, чтобы перейти в состояние владения. Затем в конце блока единственный оставшийся владелец оригинального буфера, другая строка, уничтожается и уничтожает буфер. Это приводит к тому, что указатель cstr становится висячим. Это близкий к реальным случаям пример, который мы десятками ловили в переходный период, самое странные случаи были, когда миксовали std::string и UString и часть данных оставалась на стеке, какое то время они еще были доступны, а в определенный момент становились мусором. В итоге редактор немного подумав выдавал что-то в стиле скриншота ниже и падал без дампов.
Godbolt (пример ошибки)
Это трактовалось как ошибка программиста и незнание основ движка, но по факту тип просто был плохо спроектирован, что и делало его очень легким для неверного использования. Для исправления такой ошибки, если бы её начали чинить, чтобы избежать вышеупомянутых случаев, было необходимо переходить в состояние владения при любом обращении к элементу строки, что повлекло бы за собой копирование данных строки в каждом случае, когда выдается ссылка, указатель или итератор, независимо от константности строки. Попытки сделать это в движке привели к тому, что все положительные стороны использования этого механизма пропали и остались только негативные в виде необходимости сопровождения не самого простого для реализации класса и набора алгоритмов и умения аккуратно работать с этим классом.
Где-то после 4.3 и ближе к 4.6 техлиды признали, что стоимость сопровождения стала слишком высока, а оставшиеся преимущества слишком малы, чтобы продолжать поддержку своей реализации COW-строк в движке. А там уже и в основных компиляторах подоспели string_view и дешевая реализация коротких строк.
О потоках
Вы наверное можете вспомнить про достаточно широко гулявшее заблуждение, что COW-строки плохо работали с потоками, или что они были неэффективными, потому что при таком подходе обычное копирование строки не давало фактической копии, и другой поток мог получить свободный доступ к данным и менять их независимо от основного.
Чтобы разрешить использование экземпляров строк, которые используются различными потоками, и обеспечить совместное использование буфера, почти каждая функция доступа, включая простую индексацию с помощью [], должна будет использовать мьютекс.
В движке же было сделано простое решение с проверкой индекса текущего треда в операторе присвоения, и если он не совпадал, то создавалась новая копия строки. Это конечно вызывало некоторые неудобства, но такие случаи были достаточно редкие, а ошибок с этим связанных я и вообще не могу вспомнить.
Иммутабельные строки
Лучше всего этот тип данных показывал себя на неизменяемых строках, вроде строковых хешах, идентификаторах и ключах, которых было подавляющее большинство в коде движка. Это когда строки не предполагают операции, где происходит изменение данных. Строки по-прежнему могут быть присвоены, но нельзя напрямую изменить данные строки, например, заменить «H» на «B» в слове «Hurry». В случае с COW-строками в движке они поддерживали амортизированное константное время инициализации из строковых литералов через hash ключ для операций сравнения и различные операции подстрок с константным временем работы, например в качестве ключа в map. И это было наверное самым большим плюсом таких COW-строк - отсутствие операций сравнения строк при поиске в массиве или map'e . В пятерке разработка стала отходить от велосипедов и кастомных решений, даже если это приводило к снижению производительности и увеличению расхода памяти, как в случае с контейнерами стандартной библиотеки. Сейчас движок и вовсе опирается на стандартную библиотеку.
З.Ы. C 2017 года я не участвую в разработке движка, но вряд-ли принятый курс на унификацию программных решений слишком сильно изменился.
Спасибо, что дочитали!
Автор: dalerank
