Сейчас я покажу как можно создать массив, у которого можно менять размер, не используя для этого нативные возможности языка. Т.е. вместо Array.Resize и var array = new int[100] только прямой доступ к памяти через unsafe контекст, который поможет избежать копирования и выделения новой памяти.

Эта заметка носит академический характер. Никогда не используйте этот код в реальном проекте.

Сначала начну с результатов. Чтобы лучше было понятно, ради чего всё это.

Вот так выглядит хранилище после первого цикла с заполнением данными.
Вот так выглядит хранилище после первого цикла с заполнением данными.
И вот что получилось после второго цикла.
И вот что получилось после второго цикла.

Этот пример показывает, что фактически мы работаем с хранилищем внутри экземпляра класса ArrayNoGarbage. Но делаем это через полноценный массив, который существует как отдельная сущность.

Реализация

Подготовка. Нужно разрешить unsafe контекст. И установить через NuGet пакет System.Runtime.CompilerServices.Unsafe если его ещё нет в проекте. Класс Unsafe содержит универсальные низкоуровневые функции для управления управляемыми и неуправляемыми указателями.

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

Устройство массива в памяти. Иллюстрация с сайта microsoft.
Устройство массива в памяти. Иллюстрация с сайта microsoft.

Создаём generic класс ArrayNoGarbage, конструктор будет принимать значение, указывающее ёмкость. В дальнейшем эту ёмкость будем увеличивать если она меньше запрашиваемой длины.

В качестве generic типов будем принимать только unmanaged типы.

Хранилищем будет generic массив. Это поможет упростить код чтобы избавить себя от ручного менеджмента через класс Marshal. А также поможет избежать ручного объявления служебных данных, таких как Object Header и Method Table Ptr. Часть этого хранилища будет зарезервирована под служебные данные для нашего динамического массива. Под хранилище будет выделяться память один раз в конструкторе. Либо при создании массива если запрашиваемая длина больше, чем ёмкость хранилища. Кроме этого, никаких выделений памяти не будет.

Ниже полный код класса ArrayNoGarbage с подробными комментариями.

using System;
using System.Runtime.CompilerServices;

//Компилятор ругается на то, что массив является null поэтому подавляем эти предупреждения.
#pragma warning disable CS8618
#pragma warning disable CS8601
public sealed unsafe class ArrayNoGarbage<T> where T : unmanaged
{
    //Хранилище для служебных и пользовательских данных.
    private T[] storage;
    
    //Этот массив будет создаваться вручную и являться частью хранилища данных.
    //Фактически он не занимает места в памяти.
    private T[] array;
    
    //Количество элементов хранилища выделенное под служебные данные.
    private readonly int elementOffset;
    
    //Размер служебных данных таких как Object Header, Method Table Ptr и длина массива.
    private readonly int ptrOffset;
    
    //Минимальная вместимость хранилища.
    private const int MIN_CAPACITY = 64;

    public ArrayNoGarbage(int capacity = MIN_CAPACITY)
    {
        //Инициализация хранилища с заданной ёмкостью. Хранилище – не массив, который мы будем создавать вручную. 
        storage = new T[capacity < MIN_CAPACITY ? MIN_CAPACITY : capacity];
        
        //Ссылка на хранилище.
        var storageObjPtr = (IntPtr*) Unsafe.AsPointer(ref storage);
        //Ссылка на заголовк хранилища.
        var storageHeaderPtr = (*storageObjPtr).ToPointer();
        //Ссылка на первый элемент хранилища.
        var storageElement0Ptr = Unsafe.AsPointer(ref storage[0]);

        //Находим размер служебных данных.
        ptrOffset = (int) ((((IntPtr) storageElement0Ptr).ToInt64() -
                            ((IntPtr) storageHeaderPtr).ToInt64()) / sizeof(nint));
        //Вычисляем в какое количество элементов хранилища поместятся служебные данные.
        elementOffset = sizeof(nint) * ptrOffset <= sizeof(T)
            ? 1
            : sizeof(nint) * ptrOffset / sizeof(T);
        
        //Ссылка на первый элемент создаваемого массива.
        //Unsafe.Add и Unsafe.Subtract вычисляют смещение в памяти относительно текущего.
        var arrayElement0Ptr = Unsafe.Add<T>(storageElement0Ptr, elementOffset);
        //Ссылка на заголовок массива.
        var arrayHeaderPtr = (nint*) Unsafe.Subtract<nint>(arrayElement0Ptr, ptrOffset);

        //Копируем служебные данные массива,
        //на данном этапе они полностью совпадают с данными хранилища,
        //а потом начинают жить своей жизнью.
        for (var i = 0; i < ptrOffset; i++)
        {
            arrayHeaderPtr[i] = ((nint*) storageHeaderPtr)[i];
        }

        //Ссылка на участок памяти в котором хранится длина массива.
        var lengthPtr = (int*) Unsafe.Subtract<nint>(arrayElement0Ptr, 1);
        //Устаналиваем длину массива за вычетом служебных данных.
        lengthPtr[0] = storage.Length - elementOffset;
        
        //Ссылка на массив. Сейчас он равен null. И ссылается на IntPtr.Zero.
        var arrayObjPtr = (nint*) Unsafe.AsPointer(ref array);
        //Записываем новую ссылку на заголовок массива. Теперь массив больше не null.
        arrayObjPtr[0] = (nint) arrayHeaderPtr;
    }

    public T[] GetArray(int length)
    {
        //Если запрашиваемая длина совпадает с длиной массива, то ничего не делаем.
        if (length == array.Length) return array;
        
        //Если запрашиваемая длина больше, чем емкость выделенная под пользовательские данные,
        //то изменяем размер хранилища.
        if (length > storage.Length - elementOffset)
        {
            //Array.Resize используется только для увеличения ёмкости хранилища, когда запрашиваемая длина превышает доступную ёмкость.
            //Эта часть кода не имеет никакого отношения к манипуляциям с памятью для создания массива в существующем хранилище.
            Array.Resize(ref storage, length + elementOffset);
            
            //Ссылка на первый элемент хранилища.
            var storageElement0Ptr = Unsafe.AsPointer(ref storage[0]);
            //Ссылка на первый элемент массива.
            var arrayElement0Ptr = Unsafe.Add<T>(storageElement0Ptr, elementOffset);
            //Ссылка на заголовок массива.
            var arrayHeaderPtr = Unsafe.Subtract<nint>(arrayElement0Ptr, ptrOffset);
            //Ссылка на массив.
            var arrayObjPtr = (nint*) Unsafe.AsPointer(ref array);

            //Размер хранилища был изменён,
            //наш массив сейчас ссылается на старый участок памяти.
            //Записываем новую ссылку на заголовок массива.
            //Старый участок памяти будет очищен сборщиком мусора
            //на него больше не ссылается ни хранилище, ни наш массив.
            arrayObjPtr[0] = (nint) arrayHeaderPtr;
        }
        
        {
            //Ссылка на первый элемент массива.
            var arrayElement0Ptr = Unsafe.AsPointer(ref array[0]);
            //Ссылка на участок памяти в котором хранится длина массива.
            var lengthPtr = (int*) Unsafe.Subtract<IntPtr>(arrayElement0Ptr, 1);
            //Устанавливаем новую длину массива.
            lengthPtr[0] = length;
        }
        
        return array;
    }
}
#pragma warning restore CS8618
#pragma warning restore CS8601

Я не проводил тестирования в 32 битной среде. Возможно, есть какие-то проблемы.

Заключение

На этом всё. С помощью нехитрых манипуляций с памятью мы создали свой массив внутри другого массива и полностью управляем его размером без нагрузки на сборщик мусора.

Комментарии (31)


  1. ValeriyPu
    06.02.2023 08:47
    +3

    Сейчас я покажу как можно создать массив, у которого можно менять размер, не используя для этого нативные возможности языка. Т.е. вместо Array.Resize и var array = new int[100] только прямой доступ к памяти через unsafe контекст, который поможет избежать копирования и выделения новой памяти.

    Ого, и тут

    //Если запрашиваемая длина больше, чем емкость выделенная под пользовательские данные,
    //то изменяем размер хранилища.
    if (length > storage.Length - elementOffset)
    {
    Array.Resize(ref storage, length + elementOffset);


    1. viruseg Автор
      06.02.2023 08:56

      Этот код работает только в том случае, когда требуется увеличить размер хранилища. Тот же самый принцип, что и у всех нативных List, Dictionary и прочее. Волшебства в мире программирования не существует. И память под хранилище нужно как-то выделить. После того как она выделена уже идёт работа напрямую с памятью в обход нативных методов языка.


      1. ValeriyPu
        06.02.2023 08:59

        А что мешает использовать нативные средства языка? )
        https://learn.microsoft.com/ru-ru/dotnet/api/system.array.resize?view=net-7.0

        Вообще, если вызвать GetArray дважды для различных массивов, это приведет к созданию двух связанных массивов. Даже использование IDisposable и using() не поможет )


        1. viruseg Автор
          06.02.2023 09:32

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

          Если увеличения ёмкости хранилища не происходит. То GetArray можно вызвать хоть 100 раз, это будет один и тот же массив, но у него будет меняться длина.


      1. raptor
        06.02.2023 09:01

        Могли бы сделать нормальный динамический список внутри вашей структуры, чисто академически, и не делать ресайз с полный копированием всех элементов. Так честнее было бы. И вообще не нужен вам Unsafe для этого.


        1. viruseg Автор
          06.02.2023 09:29

          Покажете как можно сделать тоже самое без unsafe?


          1. ValeriyPu
            06.02.2023 09:35
            +1

            перегрузка индексатора, поиск нужного массива с динамическом списке и обращение к нему.
            Естественно, теперь вы работаете не с массивом, а со своим классом, реализующем индексатор.

            И т.д.


            1. viruseg Автор
              06.02.2023 09:42

              Если у вас есть метод в качестве аргумента принимающий массив. Как вы сможете этому методу скормить свой класс? Вся суть моего кода сводится к созданию нативного массива c#.


              1. centralhardware2
                06.02.2023 09:49
                +1

                хотите подложить подлянку колеге, вместо явного указания в сигнатуре метода, что поведение у вашего массива отличается от того, что в stdlib?


                1. viruseg Автор
                  06.02.2023 09:59
                  +1

                  Чем поведение массива, полученного из моего кода, отличается от стандартного? Да и речи об использовании в реальном проекте вообще не идёт. Цель была создать нативный массив и менять его размер без выделения памяти. Это сделано.

                  В начале статьи специально написано:

                  Эта заметка носит академический характер. Вряд ли вы будете это использовать в реальном проекте.


                  1. yarosroman
                    06.02.2023 11:22

                    менять его размер без выделения памяти

                    У вас почти это получилось.


                    1. viruseg Автор
                      06.02.2023 11:29

                      Почему "почти"? Запустите код, посмотрите, как он работает. Если не запрашивать длину массива превышающую ёмкость. То выделений памяти – нет.


                      1. yarosroman
                        06.02.2023 12:24

                        Вы сами ответили на свой вопрос, почему почти.


                      1. viruseg Автор
                        06.02.2023 12:28

                        Нет – не ответил. И вы на мой вопрос тоже не ответили. Я вам ниже уже объяснил всё. Неужели нужно по новой расписывать?


              1. a-tk
                06.02.2023 13:11

                Попутный вопрос: у Вас точно не возникает ситуации, когда сборщику мусора срывает крышу при остановке? Не возникает ли GC holes? Есть ощущение. что тут не всё хорошо с этим.


                1. viruseg Автор
                  06.02.2023 13:43

                  Скорее всего вы правы. И использовать массив в массиве плохая идея. Для хранилища лучше использовать Marshal.AllocHGlobal.


                  1. a-tk
                    06.02.2023 13:52

                    Не лучше. При попытке сделать аналогичную вещь рантам ругается на память.


  1. yarosroman
    06.02.2023 11:09
    +1

    без нагрузки на сборщик мусора.

    И неожиданно

    storage = new T[capacity < MIN_CAPACITY ? MIN_CAPACITY : capacity];

    А что мешает мне сделать поле с массивом в моем классе и использовать его и без всякого колхоза с unsafe или статический класс с полем массива сделать и работать с ним, а могу через stackalloc, создать буфер на стеке и работать с ним через Span или Memory, вот где реально без нагрузки на сборщик мусора.

    Да и самое главное, вернее где главное? Где создаем руками? Громкое название, не имеющее общего с содержанием.


    1. viruseg Автор
      06.02.2023 11:27

      Если не читать статью по диагонали, то все ваши вопросы исчезнут.

      Да и самое главное, вернее где главное? Где создаем руками? Громкое название, не имеющее общего с содержанием.

      Руками создаётся не storage, а array который объявлен там же рядом. storage служит хранилищем и об этом написано. Метод GetArray возвращает именно массив созданный вручную. И да, для storage конечно же выделяется память, но делается это один раз в конструкторе. И возможно ещё раз если изначально была выбрана неправильная ёмкость для хранилища. В остальное время метод GetArray меняет длину массива без выделения памяти.

      Хранилищем будет generic массив. Это поможет упростить код чтобы избавить себя от ручного менеджмента через класс Marshal. А также поможет избежать ручного объявления служебных данных, таких как Object Header и Method Table Ptr. Часть этого хранилища будет зарезервирована под служебные данные для нашего динамического массива.

      А что мешает мне сделать поле с массивом в моем классе и использовать его и без всякого колхоза с unsafe или статический класс с полем массива сделать и работать с ним, через Span или Memory.

      Тем, что это уже будет не создание массива. И писать о таких банальностях нет смысла.


      1. yarosroman
        06.02.2023 11:53

        Метод GetArray возвращает именно массив созданный вручную

        Я бы не сказал что вручную, скопировать заголовок объекта, это создание вручную.

        В остальное время метод GetArray меняет длину массива без выделения памяти.

        Array.Resize, это не без выделения памяти?

        Тем, что это уже будет не создание массива

        Как это нет? это будет массив, последовательное размещение элементов в памяти.


        1. viruseg Автор
          06.02.2023 12:16

          Я бы не сказал что вручную, скопировать заголовок объекта, это создание вручную.

          Ваше право так считать.

          Array.Resize, это не без выделения памяти?

          Array.Resize используется для изменения ёмкости хранилища если запрашиваемая длина массива больше этой ёмкости. Память в шарпе не берётся из воздуха, её надо зарезервировать под свои нужды. Если бы я сделал выделение памяти через класс Marshal, то суть не изменилась бы. Хочется ёмкость большую, чем указали в конструкторе. Придётся выделить память под свои нужды. Я уже пожалел, что вообще в коде добавил возможность увеличения хранилища если она слишком мала. Если из кода выкинуть эту часть, где меняется размер хранилища вопросы после этого, останутся у вас?

          Как это нет? это будет массив, последовательное размещение элементов в памяти.

          Я имел ввиду конечно же нативный массив var array = new int[100]. Span или Memory тоже по своей сути массив, но речь в статье вообще не о них.


          1. yarosroman
            06.02.2023 12:30
            +1

            Конечно останутся, зачем городить велосипед, если есть, например, ArrayPool. А что будет, если я массив передал, в другой метод, который в другом потоке его обрабатывает, а потом поменял размер?


            1. viruseg Автор
              06.02.2023 12:36

              Этот код не для реального проекта. И это отвечает разом на все ваши вопросы.

              зачем городить велосипед, если есть, например, ArrayPool. 

              Затем, что цель создать массив тем способом, что есть в статье. Использовать ArrayPool можно и нужно. Но статья не об этом.

              А что будет, если я массив передал, в другой метод, который в другом потоке его обрабатывает, а потом поменял размер?

              Ничего хорошего не будет. Но возвращаемся к моему первому предложению. Этот код не для реального проекта.

              Вы можете понять, что цель была показать, что так можно сделать? И, возможно, это кому-то пригодится. Это даже не близко код, который можно воткнуть в готовый проект.


              1. yarosroman
                06.02.2023 13:06

                Так интереснее было бы, если бы вы показали, как поменять через unsafe размер массива и к каким бы проблемам это привело бы, а может и нет. Например, если я через unsafe поменяю в заголовке размер, сборщик освободит всю память? Если да, то нет смысла в копировании заголовка объекта в другой буфер и работы уже с ним.


                1. viruseg Автор
                  06.02.2023 13:27

                  Если взять массив, созданный без плясок с бубном, который лежит в отдельной области памяти. И поменять его размер через unsafe в меньшую сторону, то для сборщика мусора просто появится свободный участок памяти, а сам массив для него будет занимать ровно то место, которое указано в его длине. А вот в большую сторону менять размер не надо, таким изменением размера вы скорее всего захватите уже занятый участок памяти и это приведёт к непредвиденным последствиям.


                  1. yarosroman
                    06.02.2023 13:48

                    А вот я думаю, что наоборот, ничего не произойдёт, так как выделяется блок, и соответственно блок удаляется, ведь при выделении памяти мы указываем размер, а при удалении просто указатель на блок, не указывая размер. Значит система хранит размер выделенного блока. GC при очистке вызывает внутренние методы работы с памятью


  1. Nagg
    06.02.2023 13:31
    +2

    КРАЙНЕ не рекомендую где либо это использовать кроме как побаловаться. Ваш код ArrayNoGarbage конструктора напичкан так называемыми GC hole - при удачном стечении обстоятельтв GC остановит ваш метод, произведет компактирование кучи и переместит объекты, обновив managed ссылки, но часть ваших unmanaged поинтеров будут смотреть на старое место - привет NullRef/AVE краш. И вероятность этого далеко не нулевая, а вполне реальная. Например, приложение будет падать раз в пару дней с непонятным стек трейсом.

    Пример в вашем коде:

    storage = new T[capacity < MIN_CAPACITY ? MIN_CAPACITY : capacity];
            
    //Ссылка на хранилище.
    var storageObjPtr = (IntPtr*) Unsafe.AsPointer(ref storage);
    
    // тут происходит интеррупт, регистр/стек хранящий storage
    // объект обновляется, а storageObjPtr - нет.
    


    1. yarosroman
      06.02.2023 13:57

      Для этого есть волшебное слово fixed.


    1. viruseg Автор
      06.02.2023 14:01

      Спасибо. Сделал предупреждение более заметным. Речи об использовании этого кода в реальном проекте никогда и не шло.


      1. Nagg
        06.02.2023 14:07

        Проблема в том что я вижу такие эксперименты чаще и чаще в серьезных проектах :-(


        1. viruseg Автор
          06.02.2023 14:10

          Я теперь в замешательстве. Есть ощущение, что сообщество восприняло этот пост как руководство к действию. Возможно, стоит его спрятать в черновики.