В дотнете строки (и массивы) размещаются в динамической памяти. У меня в программе их очень много поэтому при большой нагрузке программа захлёбывается от мусора (сборщик мусора не успевает разгребать). Хочу value type строки (или массивы байтов — не важно). Как это реализовать?

Пробовал заводить структуры навроде следующей:

public struct RAW256: System.Collections.Generic.IEnumerable<byte>, System.Collections.IEnumerable
{
  public byte byte0, byte1, ..., byte255;

  public int Length { get { return 256; } }
  public void Internalize (byte[] input, int offset);
  public void Externalize (byte[] output, int offset);
  public void Internalize (System.IO.Stream input);
  public void Externalize (System.IO.Stream output);
  public byte[] ToArray ();
  public bool IsEqual (ref RAW256 raw);
  public byte this[int index];
  public System.Collections.Generic.IEnumerator<byte> GetEnumerator ();
  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ();
  public void Clear ();
}

(я написал кодогенератор который порождает код для таких структур любого заданного размера, в данном случае 256).

Да вот беда, если не использовать unsafe, то слишком медленно эта штука работает.
Но использовать-то unsafe не получается!!! Ведь невозможно получить адрес &this.byte0 потому, что оператор & работает только если объект fixed, но невозможно структуру зафиксить находясь внутри её метода. Как быть?

Здравствуйте, Аноним, Вы писали:

А>В дотнете строки (и массивы) размещаются в динамической памяти. У меня в программе их очень много поэтому при большой нагрузке программа захлёбывается от мусора (сборщик мусора не успевает разгребать).
Хм, а Вы уверены, что тормозит именно это? Как Вы это определили?

А>Хочу value type строки (или массивы байтов — не важно). Как это реализовать?
Если-таки Вы твёрдо уверены, что тормозит GC и хотите делать закат солнца вручную, то напишите свой менеджер мамяти, который будет откусывать большими кусками блоки у стандартного менеджера. Типа, выделяете массив байт в мегабайт размером и раскладываете туда свои строки. Если мало — берёте ещё один.
Так можно реализовать любую логику. Только выигрыш будет уж в очень специфических случаях.

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

Здравствуйте, Аноним, Вы писали:

А>У меня в программе их очень много поэтому при большой нагрузке программа захлёбывается от мусора (сборщик мусора не успевает разгребать).

Это каким образом Вы выяснили, профайлером или гаданием на кофейной гуще?

Давайте разберёмся с манипуляциями, производимыми Вами над строки и путями, которыми Вы их осуществляете.
Вполне возможно, что immutable-строки + StringBuilder всё же обеспечат приемлимую производительность

Здравствуйте, vmpire, Вы писали:

А>>Хочу value type строки (или массивы байтов — не важно). Как это реализовать?
V>Если-таки Вы твёрдо уверены, что тормозит GC и хотите делать закат солнца вручную, то напишите свой менеджер мамяти, который будет откусывать большими кусками блоки у стандартного менеджера. Типа, выделяете массив байт в мегабайт размером и раскладываете туда свои строки. Если мало — берёте ещё один.

Гораздо проще затюнить существующий. Например, сказать ему, что сборку надо производить каждые 256/512 метров оперативы, а не 2/4 как по умолчанию (кучи 0 и 1 поколения, афаик, соответственно).

Здравствуйте, Аноним, Вы писали:

А>В дотнете строки (и массивы) размещаются в динамической памяти. У меня в программе их очень много поэтому при большой нагрузке программа захлёбывается от мусора (сборщик мусора не успевает разгребать). Хочу value type строки (или массивы байтов — не важно). Как это реализовать?

Ты все очень много строк хочешь держать на стеке? О_о...


А>Пробовал заводить структуры навроде следующей:
А>

А>public struct RAW256: System.Collections.Generic.IEnumerable<byte>, System.Collections.IEnumerable
А>{
А>  public byte byte0, byte1, ..., byte255;

А>  public int Length { get { return 256; } }
А>  public void Internalize (byte[] input, int offset);
А>  public void Externalize (byte[] output, int offset);
А>  public void Internalize (System.IO.Stream input);
А>  public void Externalize (System.IO.Stream output);
А>  public byte[] ToArray ();
А>  public bool IsEqual (ref RAW256 raw);
А>  public byte this[int index];
А>  public System.Collections.Generic.IEnumerator<byte> GetEnumerator ();
А>  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ();
А>  public void Clear ();
А>}
А>

А>(я написал кодогенератор который порождает код для таких структур любого заданного размера, в данном случае 256).

Какая прелесть

Как бы еще узнать длину строки не зная ее тип/длину? Или очистить строку, не зная ее тип/длину?

Здравствуйте, Aen Sidhe, Вы писали:

А>>>Хочу value type строки (или массивы байтов — не важно). Как это реализовать?
V>>Если-таки Вы твёрдо уверены, что тормозит GC и хотите делать закат солнца вручную, то напишите свой менеджер мамяти, который будет откусывать большими кусками блоки у стандартного менеджера. Типа, выделяете массив байт в мегабайт размером и раскладываете туда свои строки. Если мало — берёте ещё один.

AS>Гораздо проще затюнить существующий. Например, сказать ему, что сборку надо производить каждые 256/512 метров оперативы, а не 2/4 как по умолчанию (кучи 0 и 1 поколения, афаик, соответственно).
Гораздо проще вообще не трогать менеджер памяти, а посмотреть, где реально теряется производительность

Здравствуйте, Аноним, Вы писали:

А>невозможно структуру зафиксить находясь внутри её метода.

Почему невозможно?

fixed(RAW256* a = &this)
{

}

А> public byte byte0, byte1, ..., byte255;

public fixed byte b[256];

Здравствуйте, vmpire, Вы писали:

V>Здравствуйте, Aen Sidhe, Вы писали:

А>>>>Хочу value type строки (или массивы байтов — не важно). Как это реализовать?
V>>>Если-таки Вы твёрдо уверены, что тормозит GC и хотите делать закат солнца вручную, то напишите свой менеджер мамяти, который будет откусывать большими кусками блоки у стандартного менеджера. Типа, выделяете массив байт в мегабайт размером и раскладываете туда свои строки. Если мало — берёте ещё один.

AS>>Гораздо проще затюнить существующий. Например, сказать ему, что сборку надо производить каждые 256/512 метров оперативы, а не 2/4 как по умолчанию (кучи 0 и 1 поколения, афаик, соответственно).
V>Гораздо проще вообще не трогать менеджер памяти, а посмотреть, где реально теряется производительность

В моём случае — именно на GC.

Здравствуйте, gecko

Спасибо!

Здравствуйте, gecko.

Короче, получилось что-то вроде следующего:

    public unsafe struct X256
    {
        private fixed byte buffer[256];

        public int Length { get { return 256; } }

        public unsafe byte this[int index]
        {
            get
            {
                fixed (byte* address = this.buffer)
                {
                    return *(address + (index & 255));
                }
            }
            set
            {
                fixed (byte* address = this.buffer)
                {
                    *(address + (index & 255)) = value;
                }
            }
        }
    }

Измерил время доступа по индексу:

        private static void Test ()
        {
            const int N = 100000;
            //byte[] x = new byte[256];
            X256 x;
            System.DateTime t0 = System.DateTime.Now;
            for (int i = 0; i < N; i++)
            {
                int j = 0;
                while (j < x.Length)
                {
                    byte tmp = x[j];
                    x[j] = tmp;
                    j++;
                }
            }
            System.DateTime t1 = System.DateTime.Now;
            double dt = 1000000000 * (t1 - t0).TotalSeconds / (N * x.Length * 2);
            System.Console.WriteLine("dt = {0} ns, cycles = {1}", dt, dt * 2.21);
            System.Console.ReadLine();
        }

(2.21 — это частота в ГГц моего проца)

Получилось в среднем примерно 9.45 такта, в то время как индексация массива 1.35 такта (ну там погрешность ещё организация цикла вносит, так что наверное 9:1).

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, gecko.

А>Короче, получилось что-то вроде следующего:
А>

А>    public unsafe struct X256
А>    {
А>        private fixed byte buffer[256];

А>        public int Length { get { return 256; } }

А>        public unsafe byte this[int index]
А>        {
А>            get
А>            {
А>                fixed (byte* address = this.buffer)
А>                {
А>                    return *(address + (index & 255));
А>                }
А>            }
А>            set
А>            {
А>                fixed (byte* address = this.buffer)
А>                {
А>                    *(address + (index & 255)) = value;
А>                }
А>            }
А>        }
А>    }
А>

А>Измерил время доступа по индексу:
А>

А>        private static void Test ()
А>        {
А>            const int N = 100000;
А>            //byte[] x = new byte[256];
А>            X256 x;
А>            System.DateTime t0 = System.DateTime.Now;
А>            for (int i = 0; i < N; i++)
А>            {
А>                int j = 0;
А>                while (j < x.Length)
А>                {
А>                    byte tmp = x[j];
А>                    x[j] = tmp;
А>                    j++;
А>                }
А>            }
А>            System.DateTime t1 = System.DateTime.Now;
А>            double dt = 1000000000 * (t1 - t0).TotalSeconds / (N * x.Length * 2);
А>            System.Console.WriteLine("dt = {0} ns, cycles = {1}", dt, dt * 2.21);
А>            System.Console.ReadLine();
А>        }
А>

А>(2.21 — это частота в ГГц моего проца)

А>Получилось в среднем примерно 9.45 такта, в то время как индексация массива 1.35 такта (ну там погрешность ещё организация цикла вносит, так что наверное 9:1).

Неудивительно, ведь фиксация занимает время.
А она вообще не нужна, если массив размещается в стеке — просто нужно напрямую обращаться к нему из метода Test.

Здравствуйте, gecko, Вы писали:

G>Неудивительно, ведь фиксация занимает время.

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

Здравствуйте, hexamino, Вы писали:

H>Здравствуйте, gecko, Вы писали:

G>>Неудивительно, ведь фиксация занимает время.

H>Почему? Ведь это всего лишь флажок на сигнатуре локальной переменной, проявляющийся только при сборке мусора.

А где находится этот флажок? Где-то в служебных структурах сборщика, а их ещё надо найти по ссылке на объект.

P.S. Действительно, следовало написать "вызов методов доступа и фиксация занимают время"

Здравствуйте, vmpire, Вы писали:

V>Хм, а Вы уверены, что тормозит именно это? Как Вы это определили?

Да, вполне уверен. По мере увеличения количества объектов и объёма используемой памяти сборщик мусора начинает работает всё медленнее и запускаться всё чаще. Представьте себе программу, которая сначала, например, каждые полминуты полностью останавливается на 3 секунды только для того, чтобы тупо почистить мусор; при увеличении нагрузки, останавливается всё чащё и чащё и собирает мусор всё дольше и дольше.

Кстати, я под Mono работаю, там у сборщика мусора свои особенности (консервативный, медленный). Микрософтовская виндовая реализация по качеству его сильно превосходит.

V>...напишите свой менеджер мамяти...

Нет, нет, нет. Никаких своих менеджеров памяти писать не надо, всё гораздо проще. Просто все объекты которые могут быть value type -- должны ими быть. В частности, строки могут и должны быть value type. Это дёшево и сердито.

Здравствуйте, Аноним, Вы писали:

А> Просто все объекты которые могут быть value type -- должны ими быть. В частности, строки могут и должны быть value type. Это дёшево и сердито.

Как бы не так Почитайте Framework Design Guidelines по поводу сценариев применения value type
Там при размерах больше 16 байт их уже не советуют использовать, Вы сами не заметите когда будете ловить постоянные копирования...

Знаете почему System.Tuple в .NET 4.0 является ссылочным типом?
почитайте при каких размерах кортежа value type даёт выигрыш...

По мне так immutable-строки это как раз дёшево и сердито

Здравствуйте, Аноним, Вы писали:

А>Да, вполне уверен. По мере увеличения количества объектов и объёма используемой памяти сборщик мусора начинает работает всё медленнее и запускаться всё чаще. Представьте себе программу, которая сначала, например, каждые полминуты полностью останавливается на 3 секунды только для того, чтобы тупо почистить мусор; при увеличении нагрузки, останавливается всё чащё и чащё и собирает мусор всё дольше и дольше.
Значит, у Вас высокая интенсивность создания новых объектов.
А Вы пробовали понять, в каком куске кода каких объектов создаётся больше всего и почему? Может, есть возможность изменить реализацию, избавившись от причины?
Если нет, то ещё можно посмотреть, можно ли как-то покрутить параметры GC.

А>Нет, нет, нет. Никаких своих менеджеров памяти писать не надо, всё гораздо проще. Просто все объекты которые могут быть value type -- должны ими быть. В частности, строки могут и должны быть value type. Это дёшево и сердито.
Я понимаю, Вы хотите что-то типа _malloca. Такое можно сделать только с помощью извращений типа как Вы описали.
Но в этом случае каждое присваивание будет копированием, Вы уверены, что это не ухудшит ситуацию ещё сильнее?
Может, возможно вместо постоянного создания новых строк реюзать какой-то один объект? Например, заранее выделенный массив байт или StringBuilder.

Здравствуйте, Аноним, Вы писали:

V>>Хм, а Вы уверены, что тормозит именно это? Как Вы это определили?

А>Да, вполне уверен. По мере увеличения количества объектов и объёма используемой памяти сборщик мусора начинает работает всё медленнее и запускаться всё чаще. Представьте себе программу, которая сначала, например, каждые полминуты полностью останавливается на 3 секунды только для того, чтобы тупо почистить мусор; при увеличении нагрузки, останавливается всё чащё и чащё и собирает мусор всё дольше и дольше.

А>Кстати, я под Mono работаю, там у сборщика мусора свои особенности (консервативный, медленный). Микрософтовская виндовая реализация по качеству его сильно превосходит.

V>>...напишите свой менеджер мамяти...

А>Нет, нет, нет. Никаких своих менеджеров памяти писать не надо, всё гораздо проще. Просто все объекты которые могут быть value type -- должны ими быть. В частности, строки могут и должны быть value type. Это дёшево и сердито.

По-моему, у Вас налицо все признаки сильной фрагментации памяти, то есть очень часто имеет место создание вперемешку короткоживущих объектов и долгожителей, в результате чего, как я понимаю, сборщику из-за большого количества новых долгожителей часто приходится выполнять копирование памяти. Кроме того, долгожители занимают место в куче, а их постоянное увеличение приводит к необходимости частой реаллокации памяти под второе поколение. Стоит посмотреть, нет ли непредусмотренных долгоживущих объектов, то есть таких, которые уже не нужны, но на них ещё где-то остаются ссылки, фактически — утечки памяти. Может быть стоит попробовать принудительно инициировать сборку нулевого поколения после активной работы с локальными переменными ссылочных типов. Вы ведь сами говорите: "По мере увеличения количества объектов и объёма используемой памяти сборщик мусора начинает работает всё медленнее" Но само по себе обилие короткоживущих объектов вроде-бы, по логике, не должно отрицательно сказываться на работе сборщика, а Ваша замена массивов на структуры никак не может уменьшить количество долгожителей, всё равно память под переменные, не являющиеся локальными, выделяется в куче. Мне кажется, это направление более перспективно, чем попытки имитации чужеродных для платформы типов.

В любом случае, прежде стоит провести более детальное исследование проблемы.

Здравствуйте, Мизантроп, Вы писали:

М> По-моему, у Вас налицо все признаки сильной фрагментации памяти, то есть очень часто имеет место создание вперемешку короткоживущих объектов и долгожителей,

Вы совершенно правы. Вперемешку идут долгоживущие и короткоживущие объекты.

М> в результате чего, как я понимаю, сборщику из-за большого количества новых долгожителей часто приходится выполнять копирование памяти. Кроме того, долгожители занимают место в куче, а их постоянное увеличение приводит к необходимости частой реаллокации памяти под второе поколение.

Здесь Вы не правы. Это только в микрософтовской реализации сборщик мусора перемещает объекты в памяти. Сборщик мусора в Mono 2.4.2.3 не перемещает объекты в памяти, там используется чуть подкрученный "классический" консервативный Boehm garbage collector.

М> Стоит посмотреть, нет ли непредусмотренных долгоживущих объектов, то есть таких, которые уже не нужны, но на них ещё где-то остаются ссылки, фактически — утечки памяти.

Относительно долгоживущих объектов много, но они все предусмотренные, это не утечка. Кроме того, для борьбы с последствиями консервативности приходится использовать кэширование (переиспользование) объектов.

М> Может быть стоит попробовать принудительно инициировать сборку нулевого поколения после активной работы с локальными переменными ссылочных типов.

Даже если бы сборщик мусора в Mono ранжировал объекты по поколениям (но он этого не делает, это только микрософтовский умеет), принудительно вызывать сборку мусора не следовало бы, потому, что моновский сборщик мусора работает по принципу Stop the World -- когда он запускается, то останавливает работу всех потоков в программе. У меня программа многопоточная и очень нежелательно, чтобы без особой надобности все потоки часто вставали.

М> Вы ведь сами говорите: "По мере увеличения количества объектов и объёма используемой памяти сборщик мусора начинает работает всё медленнее" Но само по себе обилие короткоживущих объектов вроде-бы, по логике, не должно отрицательно сказываться на работе сборщика

Да, в микрософтовском сборщике это так (до определённых пределов), а в моновском совсем не так. При каждом запуске он обходит все объекты, то есть чем больше объектов, тем дольше длится обход. Мне необходимо (почти любой ценой, в том числе и за счёт быть может лишних копирований) минимизировать количество объектов управляемых сборщиком мусора.

М> Ваша замена массивов на структуры никак не может уменьшить количество долгожителей, всё равно память под переменные, не являющиеся локальными, выделяется в куче.

Нет, это решает проблему в корне. Одно дело когда каждый "логический" долгожитель представляет собой один большой объект (многочисленные компоненты которого есть value type объекты внедрённые внутрь него), и совсем другое дело когда каждый "логический" долгожитель представляет собой совокупность большого количества (несколько десятков) мелких объектов, каждый из которых требует постоянного внимания со стороны сборщика мусора.

М> попытки имитации чужеродных для платформы типов.

О да, Хелсберг и Ко драмматически облажались когда забыли добавить в создаваемую ими платформу такую принципиальную вещь как value type массивы, теперь они являются чужеродными

Здравствуйте, Пельмешко, Вы писали:

П>Как бы не так Почитайте Framework Design Guidelines по поводу сценариев применения value type
П>Там при размерах больше 16 байт их уже не советуют использовать, Вы сами не заметите когда будете ловить постоянные копирования...

Я не рекомендую Вам читать устаревшую литературу писанную для процессоров десятилетней давности. Вместо этого возьмите и измерьте скорость копирования сами на том компьютере за которым Вы работаете. Вот, например, на моём (довольно старом) компьютере на базе процессора Athlon 64 X2 4200+ результаты следующие.

Скорость копирования 32 — 128 байтов на моём компьютере совершенно одинакова и составляет примерно 60 наносекунд. То есть нет никакой разницы, что скопировать 32 байта или 128 байтов. Если строка будет состоять не более чем из 128 байтов, то ей на моём компьютере АБСОЛЮТНО выгодно быть value type.

Далее, 256 байтов копируются в два раза медленнее чем 128 -- примерно за 120 наносекунд, но 512 байтов копируются вовсе не в два раза медленнее чем 256, а всего лишь за 190 наносекунд, то же самое каксается копирования 1024 байтов -- 310 наносекунд.

Вот после размера в 1024 байта, на моём компьютере начинается сильный рост времени копирования, который стабилизируется на отметке в 2048 байтов.

Далее, при размере больше 2048 байтов время копирования растёт линейно одинаково.

Итак, на моём компьютере:
1) копирование от 32 до 128 байтов осуществляется с одинаковой скоростью;
2) копирование от 128 до 1024 байтов осуществляется достаточно быстро;
3) копирование от 1024 до 2048 байтов -- так, не рыба не мясо;
4) копирование от 2048 байтов -- идёт "медленно", со скоростью примерно равной 7 байтов за 10 тактов.

Можете построить график {байты, микросекунды}: {{32,0.06},{64,0.06},{128,0.06},{256,0.12},{512,0.19},{1024,0.31},{2048,1.31},{4096,2.5},{8192,5},{16384,9.94},{32768,20.3},{65536,41.3}};

Так вот, это всё на моём довольно старом Athlon 64 X2 4200+, а на современных процессорах, тем более в их серверных вариантах скорость копирования больше. Таким образом, можно утверждать, что value type строки размером 128 (для старых персоналок), 256 (для современных рабочих станций), или даже быть может 512 байтов для серверных процессоров с огромным кэшем и "гипертранспортной шиной" АБСОЛЮТНО побеждают свои ссылочные аналоги, так как не требуют к себе внимания со стороны менеджера памяти.

Здравствуйте, Аноним, Вы писали:

А>Так вот, это всё на моём довольно старом Athlon 64 X2 4200+, а на современных процессорах, тем более в их серверных вариантах скорость копирования больше. Таким образом, можно утверждать, что value type строки размером 128 (для старых персоналок), 256 (для современных рабочих станций), или даже быть может 512 байтов для серверных процессоров с огромным кэшем и "гипертранспортной шиной" АБСОЛЮТНО побеждают свои ссылочные аналоги, так как не требуют к себе внимания со стороны менеджера памяти.

Ниужели вся эта куча value строк будет лежать на стеке? Подразумеваются алгоритмы с большой глубиной рекурсии?

Или может value строки будут лежать в массивах (которые все-таки в куче) для возможности подмены "строк"? Может в этом случае проще использовать предвыделенные массивы char/byte?