[DotNetBook] Stackalloc: забытая команда C#

  • Tutorial
С этой статьей я продолжаю публиковать целую серию статей, результатом которой будет книга по работе .NET CLR, и .NET в целом. Вся книга будет доступна на GitHub (ссылка в конце статьи).

В C# существует достаточно интересное и очень редко используемое ключевое слово stackalloc. Оно настолько редко встречается в коде (тут я даже со словом «редко» преуменьшил. Скорее, «никогда»), что найти подходящий пример его использования достаточно трудно а уж придумать тем более трудно: ведь если что-то редко используется, то и опыт работы с ним слишком мал. А все почему? Потому что для тех, кто наконец решается выяснить, что делает эта команда, stackalloc становится более пугающим чем полезным: темная сторона stackalloc — unsafe код. Тот результат, что он возвращает не является managed указателем: значение — обычный указатель на участок не защищенной памяти. Причем если по этому адресу сделать запись уже после того как метод завершил работу, вы начнете писать либо в локальные переменные некоторого метода или же вообще перетрете адрес возврата из метода, после чего приложение закончит работу с ошибкой. Однако наша задача — проникнуть в самые уголки и разобраться, что в них скрыто. И понять, в частности, что если нам дали этот инструмент, то не просто же так, чтобы мы смогли найти секретные грабли и наступить на них со всего маху. Наоборот: нам дали этот инструмент чтобы мы смогли им воспользоваться и делать поистине быстрый софт. Я, надеюсь, вдохновил вас? Тогда начнем.

Чтобы найти правильные примеры использования этого ключевого слова надо проследовать прежде всего к его авторам: компании Microsoft и посмотреть как его используют они. Сделать это можно поискав полнотекстовым поиском по репозиторию coreclr. Помимо различных тестов самого ключевого слова мы найдем не более 25 использований этого ключевого слова по коду библиотеки. Я надеюсь что в предыдущем абзаце я достаточно сильно вас мотивировал чтобы вы не остановили чтение, увидев эту маленькую цифру и не закрыли мой труд. Скажу честно: команда CLR куда более дальновидная и профессиональная чем команда .NET Framework и если она что-то сделала то нам сильно в чем-то должно помочь. А если это не использовано в .NET Framework… Ну, тут можно предположить, что там не все инженеры в курсе что есть такой мощный инструмент оптимизации. Иначе бы объемы его использования были бы гораздо больше.

Класс Interop.ReadDir

unsafe
{
    // s_readBufferSize is zero when the native implementation does not 
    // support reading into a buffer.
    byte* buffer = stackalloc byte[s_readBufferSize];
    InternalDirectoryEntry temp;
    int ret = ReadDirR(dir.DangerousGetHandle(), buffer, s_readBufferSize, out temp);

    // We copy data into DirectoryEntry to ensure there are no dangling references.
    outputEntry = 
        ret == 0
                ? new DirectoryEntry() { 
                      InodeName = GetDirectoryEntryName(temp), 
                      InodeType = temp.InodeType 
                } 
                : default(DirectoryEntry);

    return ret;
}

Для чего здесь используется stackalloc? Как мы видим, после выделения памяти код уходит в unsafe метод для заполнения созданного буфера данными. Т.е. unsafe метод, которому необходим участок для записи выделяется место прямо на стеке: динамически. Это отличная оптимизация если учесть что альтернативы: запросить участок памяти у Windows или fixed (pinned) массив .NET, который помимо нагрузки на кучу нагружает GC тем что массив прибивается гвоздями чтобы GC его не пододвинул во время доступа к его данным. Выделяя память на стеке мы не рискуем ничем: выделение происходит почти моментально и мы можем совершенно спокойно заполнить его данными и выйти из метода. А вместе с выходом из метода исчезнет и stack frame метода. В общем, экономия времени значительнейшая.

Давайте рассмотрим еще один пример:

Класс Number.Formatting::FormatDecimal


public static string FormatDecimal(
       decimal value,
       ReadOnlySpan<char> format, 
       NumberFormatInfo info)
{
    char fmt = ParseFormatSpecifier(format, out int digits);

    NumberBuffer number = default;
    DecimalToNumber(value, ref number);

    ValueStringBuilder sb;
    unsafe
    {
        char* stackPtr = stackalloc char[CharStackBufferSize];
        sb = new ValueStringBuilder(new Span<char>(stackPtr, CharStackBufferSize));
    }

    if (fmt != 0)
    {
        NumberToString(ref sb, ref number, fmt, digits, info, isDecimal:true);
    }
    else
    {
        NumberToStringFormat(ref sb, ref number, format, info);
    }

    return sb.ToString();
}

Это — пример форматирования чисел, опирающийся на еще более интересный пример класса ValueStringBuilder, работающий на основе Span<T>. Суть данного участка кода в том что для того чтобы собрать текстовое представление форматированного числа максимально быстро, код не использует выделения памяти под буфер накопления символов. Этот прекрасный код выделяет память прямо в стековом кадре метода, обеспечивая тем самым отсутствие работы сборщика мусора по экземплярам StringBuilder если бы метод работал на его основе. Плюс уменьшается время работы самого метода: выделение памяти в куче тоже время занимает. А использование типа Span<T> вместо голых указателей вносит чувство безопасности в работу кода, основанного на stackalloc.

И на последок давайте разберем еще один пример: сам класс ValueStringBuilder, который спроектирован использовать stackalloc. Без него не было бы и этого класса.

Класс ValueStringBuilder


    internal ref struct ValueStringBuilder
    {
        private char[] _arrayToReturnToPool;
        private Span<char> _chars;
        private int _pos;

        public ValueStringBuilder(Span<char> initialBuffer)
        {
            _arrayToReturnToPool = null;
            _chars = initialBuffer;
            _pos = 0;
        }

        public int Length
        {
            get => _pos;
            set
            {
                int delta = value - _pos;
                if (delta > 0)
                {
                    Append('\0', delta);
                }
                else
                {
                    _pos = value;
                }
            }
        }

        public override string ToString()
        {
            var s = new string(_chars.Slice(0, _pos));
            Clear();
            return s;
        }


        public void Insert(int index, char value, int count)
        {
            if (_pos > _chars.Length - count)
            {
                Grow(count);
            }

            int remaining = _pos - index;
            _chars.Slice(index, remaining).CopyTo(_chars.Slice(index + count));
            _chars.Slice(index, count).Fill(value);
            _pos += count;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Append(char c)
        {
            int pos = _pos;
            if (pos < _chars.Length)
            {
                _chars[pos] = c;
                _pos = pos + 1;
            }
            else
            {
                GrowAndAppend(c);
            }
        }

        [MethodImpl(MethodImplOptions.NoInlining)]
        private void GrowAndAppend(char c)
        {
            Grow(1);
            Append(c);
        }

        [MethodImpl(MethodImplOptions.NoInlining)]
        private void Grow(int requiredAdditionalCapacity)
        {
            Debug.Assert(requiredAdditionalCapacity > _chars.Length - _pos);

            char[] poolArray = ArrayPool<char>.Shared.Rent(
                Math.Max(_pos + requiredAdditionalCapacity, _chars.Length * 2));

            _chars.CopyTo(poolArray);

            char[] toReturn = _arrayToReturnToPool;
            _chars = _arrayToReturnToPool = poolArray;
            if (toReturn != null)
            {
                ArrayPool<char>.Shared.Return(toReturn);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void Clear()
        {
            char[] toReturn = _arrayToReturnToPool;

            // for safety, to avoid using pooled array if this instance is erroneously appended to again
            this = default;
            if (toReturn != null)
            {
                ArrayPool<char>.Shared.Return(toReturn);
            }
        }

        // Пропущенные методы
        private void AppendSlow(string s);
        public bool TryCopyTo(Span<char> destination, out int charsWritten);
        public void Append(string s);
        public void Append(char c, int count);
        public unsafe void Append(char* value, int length);
        public Span<char> AppendSpan(int length);
    }

Этот класс по своему функционалу сходен со своим старшим собратом `StringBuilder`, обладая при этом одной интересной и очень важной особенностью: он является значимым типом. Т.е. передается целиком по значению. А новейший модификатор типа `ref`, который приписан к сигнатуре объявления типа говорит нам о том что данный тип обладает дополнительным ограничением: он имеет право находиться только на стеке. Т.е. вывод его экземпляров в поля классов приведет к ошибке. К чему все эти приседания? Для ответа на этот вопрос достаточно посмотреть на класс `StringBuilder`:

Класс StringBuilder


public sealed class StringBuilder : ISerializable
{
    // A StringBuilder is internally represented as a linked list of 
    // blocks each of which holds a chunk of the string.  It turns 
    // out string as a whole can also be represented as just a chunk,
    // so that is what we do.

    // The characters in this block
    internal char[] m_ChunkChars;

    // Link to the block logically before this block
    internal StringBuilder m_ChunkPrevious;

    // The index in m_ChunkChars that represent the end of the block
    internal int m_ChunkLength;

    // The logical offset (sum of all characters in previous blocks)
    internal int m_ChunkOffset;
    internal int m_MaxCapacity = 0;

    // ...

    internal const int DefaultCapacity = 16;

StringBuilder — это класс, внутри которого находится ссылка на массив символов. Т.е. когда вы создаете его то по сути создается как минимум два объекта: сам StringBuilder и массив символов в как минимум 16 символов (кстати именно поэтому так важно задавать предполагаемую длину строки: ее построение будет идти через генерацию односвязного списка 16-символьных массивов. Согласитесь, это — расточительство). Что это значит в контексте нашего разговора о типе ValueStringBuilder: capacity по-умолчанию отсутствует, т.к. он заимствует память извне плюс он сам является значимым типом и заставляет пользователя расположить буфер для символов на стеке. Как итог весь экземпляр типа ложится на стек вместе с его содержимым и вопрос оптимизации здесь становится решенным. Нет выделения памяти в куче? Нет проблем с проседанием производительности по куче. Но вы мне скажите: почему тогда не пользоваться ValueStringBuilder (или его самописной версией: сам он internal и нам не доступен) всегда? Ответ такой: надо смотреть на задачу, которая вами решается. Будет ли результирующая строка известного размера? Будет ли она иметь некий известный максимум по длине? Если ответ «да» и если при этом размер строки не выходит за некоторые разумные границы, то можно использовать значимую версию StringBuilder. Иначе, если мы ожидаем длинные строки, переходим на использование обычной версии.

Также, перед тем как перейти к выводам стоит упомянуть как делать нельзя или просто опасно. Другими словами, какой код может работать хорошо, но в один прекрасный момент выстрелит в самый не подходящий момент. Опять же, рассмотрим пример:


void GenerateNoise(int noiseLength)
{
    var buf = new Span(stackalloc int[noiseLength]);
    // generate noise
}

Код мал да удал: нельзя вот так брать и принимать размер для выделения памяти на стеке извне. Если вам так нужен заданный снаружи размер и при этом ваш код известен только известному вам потребителю, примите, например, сам буфер:

void GenerateNoise(Span<int> noiseBuf)
{
    // generate noise
}

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

Вторая проблема, которую я вижу: если нам случайным образом не удалось попасть в размер того буфера, который мы сами себе выделили на стеке, а терять работоспособность мы не хотим, то, конечно, можно пойти несколькими путями: либо довыделить памяти опять же на стеке либо выделить ее в куче. Причем скорее всего второй вариант в большинстве случаев окажется более предпочтительным (так и поступили в случае `ValueStringBuffer`), т.к. более безопасен с точки зрения получения `StackOverflowException`.

Выводы к stackalloc


Итак, для чего же лучше всего использовать `stackalloc` и как?

  • Для работы с неуправляемым кодом, когда необходимо заполнить неуправляемым методом некоторый буфер данных или же принять от неуправляемого метода некий буфер данных, который будет использоваться в рамках жизни тела метода;
  • Для методов, которым нужен массив, но опять же на время работы самого метода. Пример с форматированием очень хороший: этот метод может вызываться слишком часто чтобы он выделял временные массивы в куче.
  • Если используется unsafe версия взаимодействия, необходимо тщательно проверять работу тех методов, в которые уходит ссылка (void *) т.к. если они куда-то ее отдают, то возникает дальнейшая возможность порчи стека: вы ведь не можете гарантировать что внешний метод не решит передать ссылку, например для кэширования. Если же вы уверены что такое исключено, то использование будет безопасным
  • Если вы имеете возможность пользоваться ref struct типами или же Span типом, то работа со stackalloc переходит в область managed кода, а это значит что компилятор просто не даст вам использовать тип не так как задумано

Использование данного аллокатора может сильно повысить производительность ваших приложений.

Ссылка на всю книгу


Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 16
  • +2

    В Ignite.NET использование stackalloc для передачи JNI аргументов (varargs / va_list) вместо params JavaValue[] подняло перформанс реальных кэшовых операций на 15% и избавило от лишних аллокаций / GC.


    Код на гитхабе: UnmanagedUtils.cs


    Ещё пример, перетасовка байт: WriteGuidSlow

    • +1
      Спасибо, сделаю отсылку на вариант использования
    • +1

      Думаю, что stackalloc используется так редко, потому что либо размер буфера предопределён и данные структурированы, тогда просто заполняется struct и берётся указатель, либо размер буфера непредсказуем.

      • –8
        необходимо тщательно проверять работу тех методов, в которые уходит ссылка
        (void *) т.к.
        О, за решётку в буханке протянули двуствольный ногострел!

                        int* buff = stackalloc int[Random.Next(100500)];
                        if (buff == null) RainbowFire();


        • 0
          А сколько памяти так можно выделить?
          • 0

            Сколько в стеке свободного места есть. Размер стека по умолчанию на винде 1 или 4 метра (32/64 бит), на Линухе по-разному, частый вариант — 8 метров.


            Ну и часть этого места наверняка занята самим стеком вызовов.

          • 0

            Хочу отдельно отметить, что стиль изложения в этой части лучше. Текст гораздо легче читается.

            • 0
              Для C/C++ это массивы переменной длинны и alloca. (Но в основном их все ругают.)
              • 0
                Я бы сказал, что это C#-овская замена прежде всего для обычных (фиксированной длины) массивов C/C++ (которые чаще располагаются на стеке). Массивы переменной длины и alloca — это уже следующий уровень.
              • 0
                Может кто-то подскажет, есть ли подобные книги с качественным материалом на английском? Помимо Рихтера.
              • 0

                Иногда (например в этом докладе) stackalloc не рекомендуют использовать, говоря, что он заполняет выделенную память нулями, и из-за этого работает медленно. На гитхабе coreclr эта тема тоже обсуждалась, и там есть пример, когда stackalloc не заполняет память нулями (я немного модифицировал этот пример):


                const int Size = 16384;
                
                static unsafe void Main() {
                    Foo();
                    byte* p = stackalloc byte[Size];
                    Console.WriteLine(p[0]);
                }
                
                static unsafe void Foo() {
                    byte* p = stackalloc byte[Size];
                    for (int i = 0; i < Size; i++)
                        p[i] = 42;
                }

                Если в этом коде менять Size на разные значения — можно получить разный результат. На моей машине с .NET Framework 4.7.1 результаты такие:
                RyuJit x64:


                • Size: 1-48, значение: 0
                • Size: 49-64 — «случайное» число,
                • Size >=65 — 42

                LegacyJit x86:


                • Size 1-24 — 0
                • Size >=25 — 42

                При этом в машинном коде Foo заполнение нулями присутствует.


                Отсюда появляются вопросы — в каких случаях при использовании stackalloc память обнуляется, как это влияет на производительность, и зачем вообще нужно обнуление, если на него нельзя полагаться?

                • 0
                  У меня было предположение по этому вопросу что должны быть оптимизации на этот счет. Например, есть JIT видит что сначала идет запись, а потом — чтение, то смысла обнулять нет вообще. Но пока не успел заняться этим вопросом
                • +1

                  Сейчас в coreclr память не обнуляется для любых размеров буфера. Это было сделано для эффективного использования Span в случае когда нужна производительность.
                  https://github.com/dotnet/coreclr/pull/13728
                  https://github.com/dotnet/coreclr/issues/1279

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

                  Самое читаемое