Как Unity отказались от своих строк

В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 года я не участвую в разработке движка, но вряд-ли принятый курс на унификацию программных решений слишком сильно изменился.

Спасибо, что дочитали!