В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. Для примерa ниже приведен базовый код классa, который использовался в движке, я не буду касаться проблем инициализации из литералов. Этот код показывает как присваивание и копирование были сведены почти к нулю:
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;
}Execution build compiler returned: 0
Program returned: 0
Unreal the best engine ever!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.
}Execution build compiler returned: 0
Program returned: 0
r({!4uCM&&V^Pt58>~:@|~jk0r/N|YRTM1Fg*&8q#VSyBv6D5/Поскольку строка 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 года я не участвую в разработке движка, но вряд-ли принятый курс на унификацию программных решений слишком сильно изменился.
Спасибо, что дочитали!
Комментарии (41)
KyHTEP
30.10.2024 01:06Поскольку строка
strнаходится в состоянии совместного использования, принцип COW заставляет операциюstr[0]создать копию общего буфера, чтобы перейти в состояние владенияПочему вы считаете, что операция чтения должна создать копию буфера? )
mayorovp
30.10.2024 01:06Потому что эта операция может использоваться не только для чтения:
str[0] = 'x'; // Совершенно корректный код!
dalerank Автор
30.10.2024 01:06Код был так написан, видимо предполагалось что взятие элемента происходит для его изменения, что в 99% так и было. Про эти грабли все знали и просто не пускали такой код на ревью. Моя команда занималась оптимизацией симсов и немного компилятором шейдеров, а починка махрового легаси в задачи не входила :) Четвертый репорт об этой проблеме лег в список сотни аналогичных с пометкой "Wont fix, low prior".
KyHTEP
30.10.2024 01:06Но это очень странная конструкция:
1. Берем указатель на строку
2. Меняем строку
3. Работаем с указателем на строку
Это точно проблема архитектуры, а не программиста?
KyHTEP
30.10.2024 01:06Но в примере она используется для чтения (это разные перегруженные операторы). И вопрос остается открытым. )
dalerank Автор
30.10.2024 01:06ага, и в наловленных багах тоже было чтение, которое не должно было менять строку, но приводило к крашу (не всегда). Баг жил в коде около полугода и никак себя не проявлял, пока ниже не сделали вывод в лог и словили мусор. Т.е. две строки, одна в начале функции, вторая внутри скопа использовались в качестве ключей для поиска по мапе, так писать было стандартной практикой, потому что это дешево и не делало фактических копий.
KyHTEP
30.10.2024 01:06Извините за назойливость, но я не вижу проблем в архитектуре COW. Так же я не вижу бага.
1. Заводим строку 1
2. Берем указатель
3. Заводим внутри скопа вторую
4. Если меняем вторую, то это ее указатель станет другим а не первой
5. Читаем из первой
6. Выводим указатель первой, все хорошо, указатель не менялся
Где тут потенциальный баг изза архитектуры COW? Я вот этот момент хочу понять.
P.S.: Если мы получим указатель на строку из std::string, потом поменяем std::string, то будет ровно такая же ошибка, как в примере, что я писал вам в комментарии выше.dalerank Автор
30.10.2024 01:06KyHTEP
30.10.2024 01:06А зачем вы так делаете? Почему нету const char operator[]?
Тут проблема архитектуры реализации COW в юинити, а не самого COW.dalerank Автор
30.10.2024 01:06Это не я так делаю, это реализация COW-строк из Unity < 4.6. За причинами лучше к авторам движка, видимо были причины. Про баг знали, но не фиксили
mayorovp
30.10.2024 01:06А зачем вы так делаете? Почему нету const char operator[]?
Потому что в классе не могут одновременно существовать два метода, перегруженные только по возвращаемому типу:
<source>:53:20: error: functions that differ only in their return type cannot be overloaded char const operator[]( const USize i ) ~~~~ ^ <source>:47:15: note: previous definition is here char& operator[]( const USize i )KyHTEP
30.10.2024 01:06Так а зачем делать
char& operator[]?Это как раз тот метод, который не надо делать в COW строках.
mayorovp
30.10.2024 01:06Изначально вы писали:
Но в примере она используется для чтения (это разные перегруженные операторы).
Вы согласны, что погорячились с тем комментарием?
Да, если оператора модификации строки вообще не делать - всё будет работать. Правда, тут возникает вопрос что делать если модифицировать строку всё-таки надо.
KyHTEP
30.10.2024 01:06Я согласен с тем, что неполно сформулировал мысль. И, конечно, изза этого смысл комментария становится неверным, да.
Мой основной поинт, что в COW-строках нет проблем, а есть проблемы в конкретно этой реализации.Правда, тут возникает вопрос что делать если модифицировать строку всё-таки надо.
Делать через функу, а не оператор. Т.к. сам по себе в общем виде символ - это не char. У нас же есть к примеру, UTF-8.
dalerank Автор
30.10.2024 01:06Там должен был быть перегруженый const char&, но его почему-то не было, почему отдельный вопрос и не к пользователям движка. Возможно из-за кривого биндинга в моно, который не мог работать с таким перегрузками. Репортов на это поведение было вагон и тележка
const char& operator[]( const USize i ) const { return (*m_buffer)[i]; }
mayorovp
30.10.2024 01:06А разве C++ умеет выбирать перегрузку оператора в зависимости от его использования как lvalue/rvalue?
Нет, не умеет. Он умеет смотреть только на константность самой строки, а она в этом примере неконстантна.
KyHTEP
30.10.2024 01:06Уверены?
const char first_char = str[0];mayorovp
30.10.2024 01:06Ну вот написали вы
const char, что дальше-то? Как оно повлияло на выбранную перегрузку метода? Никак. Ну нет в С++ обратного вывода типов, это вам не Хаскель и не Раст.KyHTEP
30.10.2024 01:06Я не написал const char. Я процитировал код из статьи.
Прочитайте еще раз всю ветку.
Я спросил почему чтение вызывает COW?
Вы привели пример с записью.
Я спросил причем тут запись, если вопрос про чтение и привел код из статьи.
Вы вообще куда то в сторону ушли.
P.S.: Если вы имеете ввиду конкретную реализацию из статьи, то мне понятна ваша позиция. Я вопрос задавал, имея ввиду, зачем вообще так сделано.mayorovp
30.10.2024 01:06Это вы куда-то в сторону ушли.
Важно тут то, что
str[0] = 'x';- это совершенно корректный код. Да, если объявить его некорректным - некоторые проблемы уйдут, но он корректный, это данность.Оператор индексирования не знает, вызвали его для чтения или для записи, поэтому вынужден исходить из того, что возможна запись. Именно поэтому чтение вызывает копирование.
Если бы вы сразу написали, что запись через индексирование выглядит как плохая идея для COW-строк - я бы согласился. Но вы почему-то вместо этого начали рассказывать, что запись от чтения якобы можно отличить перегрузкой, что чушь.
KyHTEP
30.10.2024 01:06Но вы почему-то вместо этого начали рассказывать, что запись от чтения можно отличить перегрузкой, что чушь.
Вы мне приписали свою интерпретацию. Вот это точно чушь.
Объясняю, когда я говорил о перегрузке, я говорил что это разные подходы, разные перегруженные операторы в разных реализациях. Вы же обсуждали конкретную реализацию COW из статьи. Тогда как я имел ввиду , почему реализация сделана так, что чтение вызывает COW. Так что вам бы уточняющие вопросы научиться задавать, а не додумывать.
KyHTEP
30.10.2024 01:06Поскольку строка
strнаходится в состоянии совместного использования, принцип COW заставляет операциюstr[0]создать копию общего буфера, чтобы перейти в состояние владенияАвтор пишет, что принцип COW заставляет операцию чтения создать буфер.
Почему вы считаете, что операция чтения должна создать копию буфера? )
Я спрашиваю почему операция чтения должна создавать копию? Почему принцип COW заставляет операцию чтения создавать копию? Принцип, понимаете? Не реализация в статье, а принцип. Так написал автор статьи.
И вот ваш комментарий.Потому что эта операция может использоваться не только для чтения:
Причем тут это? Как это относится к тому что я спрашиваю? Вы ушли не туда. Это просто медицинский факт. Вы цепляетесь за дальнейшую фразу про перегрузку, тогда как именно ваш комментарий уводит разговор в "нитуда". Я надеюсь так вам станет яснее, почему вы не правы.
mayorovp
30.10.2024 01:06Только вот автор всю статью писал исключительно про конкретную реализацию COW в Unity, а не про абстрактный принцип.
KyHTEP
30.10.2024 01:06принцип COW заставляет операцию
В цитате он буквально пишет про принцип COW. А не про реализацию COW в юинити. И мой вопрос об этом. Внимательно прочитайте.
KivApple
30.10.2024 01:06Это решается тем, что оператор индексирования должен возвращать не ссылку, а служебный объект с перегруженными операторами конвертации в char, присваивания и взятия ссылки.
И внутри этого объекта можно сделать уже создание копии при присваивании.
Объект легковесный, содержит в себе только указатель на оригинальный объект строки и запрошенный индекс, в 99% случаев компилятор должен инлайнить всё это.
datacompboy
30.10.2024 01:06А зачем работа со строками на каждый фрейм нужна? Я как-то ожидал, что строки -- для удобства программирования, но в рантайме от них должен остаться только запах и указатели, не постоянное генерирование...
dalerank Автор
30.10.2024 01:06Например имена ресурсов генерятся рантайм, как это было в симсах, логи, разные идентификаторы, рантайм имена аи груп, динамические свойства. Должно не значит будет;)
mynameco
30.10.2024 01:06Логи может быть. Профайлер. Вывод информации в визуальную часть, то же строки. Это предположение.
uxgen
30.10.2024 01:06Был навигатор под древнее железо без ГПУ, вся рендер часть на интах (эмуляция фиксированной точки). Пару лет переходили на мобилки и С++11, так при попытке вернуться на древние навигаторы оказалось, что код замедлился в 10 раз и оптимизировать слишком дорого, проще отказаться от проекта.
VADemon
Могло ли взаимодействие с другими библиотеками повлиять на отказ от собственных реализаций?
dalerank Автор
Скорее переход на с++11 и избавление от легаси, пейпер по cow-строкам не зря отклонили в стандарт, не смотря на лобби со стороны Qt и GCC. Слишком много проблем и мало профита в итоге.
KyHTEP
cow это тоже самое, что пара std::string+string_view.
Проблемы есть и там и там, думать и понимать надо и там и там. А отклонили скорее всего, я предполагаю, изза легаси, а не по причине проблем cow. Какой смысл переделывать string на cow, если проще ввести string_view.
Я к тому, что cow ни хуже ни лучше. Это тоже самое, но с другой стороны. А проблемы и косяки и там и там. Тут вопрос удобства применения в конкретном случае. Вы же утверждаете, как я понял, что cow это плохо, а пара string+string_view хорошо. И я для себя хотел бы увидеть подтверждения этому тезису.
dalerank Автор
это не тоже самое, начнем хотя бы с механизма алокации памяти. Я не сказал, что cow-строки плохой механизм, как и у любого решения у него есть зона использования - которой была строковые хеши и иммутабельные строки, попытки расширить cow-строки для широкого использования и замены string привели к проблемам, которые не смогли решить, поэтому и отказались. В движке был и другой тип строк UStringUnique который являлся аналогом std::string.
KyHTEP
Это не то же самое с точки зрения внутренней реализации. Но то же самое, с точки зрения абстрактных строк. COW логически содержит в себе одновременно и string и string_vew как концепции.
Т.е. в юнити не смогли решить. Верно? Вы же пишите так, как будто сама концепция "больна". Поправьте если это не так.
dalerank Автор
std::string+std::string_view:std::string_viewне копирует и не владеет данными, а только предоставляет доступ к части строки (или строкоподобной структуре). Когда создается копияstd::string, данные копируются полностью, и каждая строка имеет свой буфер.std::string_viewже лишь хранит указатель на данные и длину, избегая дополнительных затрат на копирование, но при этом остается привязанным к сроку жизни исходной строки. Про концепцию COW строк рассказывать?KyHTEP
Давайте я расскажу.
Пока COW-строка одна владеет ресурсом, она не отличается от std::string;
Когда на один ресурс ссылается несколько COW-строк они являются std::string_view. Когда происходит сам COW процесс, идет ветвление. Строка получившая уникальность становится по сути std::string, остальные остаются std::string_view над прошлой строкой.
Как я уже сказал, концептуально они (COW и пара string+string_view) одно и тоже. Отличие в реализации.
dalerank Автор
Не совсем так, string_view это удобная обертка над const char*, не более.
Cow строки при копировании строки они не создают дублирующий буфер данных, а просто увеличивают счетчик ссылок на общий буфер, пока одна из строк не изменится. При изменении создается полная копия буфера, чтобы изменения не затронули другие строки, ссылающиеся на оригинальные данные. Вы не сможете добиться этого поведения на std::string
KyHTEP
Я вам говорю не про std::string, а про пару string+string_view. И без деталей реализации.
dalerank Автор
даже со связкой string+string_view не получится сделать аналог COW строк
KyHTEP
Вы опять про реализацию, когда говорите слово "аналог". А я вам про концепцию. А именно не создавать лишний раз копию.
В паре string+string_view - это делается через использование string_view. В COW это встроенно by-design.