[редактировать 2017: см. важные комментарии относительно C# 7 в конце этого поста]
После многих лет борьбы именно с этой проблемой я суммирую несколько методов и решений, которые я нашел. Помимо стилистических вкусов, массивы структур на самом деле являются единственным методом массового хранения в памяти, доступным в C#. Если ваше приложение действительно обрабатывает миллионы объектов среднего размера в условиях высокой пропускной способности, другой управляемой альтернативы нет.
Я согласен с @kaalus в том, что заголовки объектов и давление GC могут быстро возрасти; тем не менее, моя система обработки грамматики НЛП может манипулировать 8-10 гигабайтами (или более) структурного анализа менее чем за минуту при анализе и/или создании длинных предложений на естественном языке. Подсказка: «C# не предназначен для решения таких задач...», «Переключитесь на язык ассемблера...», «Обмотайте FPGA...» и т. д.
Что ж, вместо этого давайте проведем несколько тестов. Во-первых, крайне важно иметь полное представление обо всем спектре вопросов управления типом значения (struct) и class против struct компромиссов. Также, конечно, упаковка, закрепление/небезопасный код, фиксированные буферы, GCHandle, IntPtr, и многое другое, но самое главное, на мой взгляд, разумное использование управляемых указателей (иначе внутренние указатели ).
Ваше мастерство в этих темах также будет включать в себя знание того факта, что если вы включите в свой struct одну или несколько ссылок на управляемые типы (в отличие от просто преобразовываемых примитивов), то ваши возможности доступа к struct с unsafe указателями значительно расширятся. уменьшенный. Это не проблема для метода управляемого указателя, о котором я расскажу ниже. Так что, в общем случае, включение ссылок на объекты — это нормально, и это мало что меняет в этом обсуждении.
О, и если вам действительно нужно сохранить доступ unsafe, вы можете использовать GCHandle в режиме «Нормальный» для хранения ссылок на объекты в вашей структуре на неопределенный срок. К счастью, добавление GCHandle в вашу структуру не приводит к срабатыванию запрета на небезопасный доступ. (Обратите внимание, что GCHandle сам по себе является типом значения, и вы даже можете определить и отправиться в город с помощью
var gch = GCHandle.Alloc("spookee",GCHandleType.Normal);
GCHandle* p = &gch;
String s = (String)p->Target;
...и так далее. Как тип значения, GCHandle отображается непосредственно в вашей структуре, но, очевидно, любые ссылочные типы, которые он хранит, не являются таковыми. Они находятся в куче, не включены в физическую структуру вашего массива. Наконец, в GCHandle остерегайтесь его семантики копирования, потому что у вас будет утечка памяти, если вы в конечном итоге не Free каждый GCHandle, который вы выделяете.
@Ani напоминает нам, что некоторые люди считают изменяемые экземпляры struct злом, но на самом деле проблема заключается в том, что они склонны к несчастным случаям. Действительно, пример ОП...
s[543].a = 3;
... точно иллюстрирует то, чего мы пытаемся достичь: получить доступ к нашим записям данных на месте. (Внимание: синтаксис для массива экземпляров 'class' ссылочного типа имеет идентичный вид, но в этой статье мы конкретно обсуждаем только не-зубчатые массивы пользовательских типов значений здесь.) Для моих собственных программ я обычно считаю это серьезной ошибкой если я столкнусь с негабаритной преобразуемой структурой, которая (случайно) была полностью отображена из строки хранения массива:
rec no_no = s[543]; // don't do
no_no.a = 3 // it like this
Что касается того, насколько большим (широким) может или должен быть ваш struct, это не имеет значения, потому что вы будете осторожны, чтобы никогда не позволять struct делать то, что было только что показано в предыдущем примере, то есть мигрировать in-toto из массива вложений. На самом деле, это указывает на фундаментальную предпосылку всей этой статьи:
правило:
для массивов из struct всегда обращайтесь к отдельным полям на месте; никогда не упоминайте (в C#) сам экземпляр struct в целом.
К сожалению, язык C# не предлагает возможности систематически помечать или запрещать код, нарушающий это правило, поэтому успех здесь обычно зависит от тщательной дисциплины программирования.
Поскольку наши гигантские структуры никогда не отображаются вне своего массива, они на самом деле являются просто шаблонами в памяти. Другими словами, правильно думать о struct как о наложении элементов массива. Мы всегда думаем о каждом из них как о пустом шаблоне памяти, а не о переносимом или переносимом инкапсуляторе или контейнере данных. Для связанных с массивом типов значений jumbo мы никогда не хотим использовать самую важную характеристику struct, а именно передачу по значению.
Пример:
public struct rec
{
public int a, b, c, d, e, f;
}
Здесь мы накладываем 6 ints, всего 24 байта на запись. Вы должны рассмотреть и знать о вариантах упаковки, чтобы получить размер, удобный для выравнивания. Но чрезмерное заполнение может сократить ваш бюджет памяти, потому что более важным соображением является ограничение в 85 000 байтов для объектов, отличных от LOH. Убедитесь, что размер вашей записи, умноженный на ожидаемое количество строк, не превышает этого предела.
Поэтому для приведенного здесь примера вам лучше всего порекомендовать, чтобы ваш массив recs не превышал 3000 строк каждый. Надеюсь, ваше приложение может быть разработано с учетом этого сладкого места. Это не так уж ограничивает, если вы помните, что в качестве альтернативы каждая строка может быть отдельным объектом, удаляемым сборщиком мусора, а не одним массивом. Вы сократили количество объектов на три порядка, что хорошо для дневной работы. Таким образом, среда .NET здесь сильно навязывает нам довольно специфическое ограничение: кажется, что если вы нацелите дизайн памяти вашего приложения на монолитное распределение в диапазоне 30-70 КБ, тогда вы действительно можете обойтись большим и большим их количеством, и на самом деле вместо этого вы будете ограничены более сложным набором узких мест в производительности (а именно, пропускной способностью на аппаратной шине памяти).
Итак, теперь у вас есть один ссылочный тип .NET (массив) с 3000 6-кортежей в физически непрерывном табличном хранилище. Прежде всего, мы должны быть очень осторожны, чтобы никогда не выбрать одну из структур. Как отмечает выше Джон Скит, массивные структуры часто будут работать хуже, чем классы, и это абсолютно правильно. Нет лучшего способа парализовать вашу шину памяти, чем волей-неволей начать разбрасывать пухлые типы значений.
Итак, давайте воспользуемся редко упоминаемым аспектом массива структур: все объекты (и поля этих объектов или структур) всех строк всего массива всегда инициализируются значениями по умолчанию. Вы можете начать вставлять значения по одному в любую строку или столбец (поле) в любом месте массива. Вы можете оставить некоторые поля со значениями по умолчанию или заменить соседние поля, не нарушая одно из полей посередине. Исчезла эта надоедливая ручная инициализация, необходимая для резидентных в стеке (локальных переменных) структур перед использованием.
Иногда трудно поддерживать подход «поле за полем», потому что .NET всегда пытается заставить нас взорвать всю структуру new'd-up — но для меня эта так называемая инициализация — просто нарушение нашего табу. (против выдергивания всей структуры из массива) в другом обличье.
Теперь мы подходим к сути дела. Очевидно, что доступ к вашим табличным данным на месте сводит к минимуму рутинную работу по перетасовке данных. Но часто это доставляет неудобства. Доступ к массиву может быть медленным в .NET из-за проверки границ. Итак, как сделать работу указателя внутри массива, чтобы система не пересчитывала смещения индексации постоянно.
Оценка
Давайте оценим производительность пяти различных методов манипулирования отдельными полями в строках хранилища массива значений. Приведенный ниже тест предназначен для измерения эффективности интенсивного доступа к полям данных структуры, расположенной в некотором индексе массива, in situ, то есть там, где они лежат, без извлечения или перезаписи всей структуры ( элемент массива). Сравниваются пять различных методов доступа, при этом все остальные факторы остаются неизменными.
Пять методов заключаются в следующем:
- Обычный, прямой доступ к массиву с помощью квадратных скобок и точки в описателе поля. Обратите внимание, что в .NET массивы — это особый и уникальный примитив системы общих типов. Как упоминалось выше @Ani, этот синтаксис нельзя использовать для изменения отдельного поля ссылочного экземпляра, такого как список, даже если он параметризован типом значения.
- Использование недокументированного ключевого слова языка
__makeref C#.
- Управляемый указатель через делегата, который использует ключевое слово
ref
- Небезопасные указатели
- То же, что и № 3, но с использованием C# функции вместо делегата.
Прежде чем я приведу результаты теста C#, вот реализация тестового жгута. Эти тесты проводились на .NET 4.5, сборке выпуска AnyCPU, работающей на x64, Workstation gc. (Обратите внимание, что, поскольку тест не интересует эффективность выделения и освобождения самого массива, упомянутое выше соображение LOH не применяется.)
const int num_test = 100000;
static rec[] s1, s2, s3, s4, s5;
static long t_n, t_r, t_m, t_u, t_f;
static Stopwatch sw = Stopwatch.StartNew();
static Random rnd = new Random();
static void test2()
{
s1 = new rec[num_test];
s2 = new rec[num_test];
s3 = new rec[num_test];
s4 = new rec[num_test];
s5 = new rec[num_test];
for (int x, i = 0; i < 5000000; i++)
{
x = rnd.Next(num_test);
test_m(x); test_n(x); test_r(x); test_u(x); test_f(x);
x = rnd.Next(num_test);
test_n(x); test_r(x); test_u(x); test_f(x); test_m(x);
x = rnd.Next(num_test);
test_r(x); test_u(x); test_f(x); test_m(x); test_n(x);
x = rnd.Next(num_test);
test_u(x); test_f(x); test_m(x); test_n(x); test_r(x);
x = rnd.Next(num_test);
test_f(x); test_m(x); test_n(x); test_r(x); test_u(x);
x = rnd.Next(num_test);
}
Debug.Print("Normal (subscript+field): {0,18}", t_n);
Debug.Print("Typed-reference: {0,18}", t_r);
Debug.Print("C# Managed pointer: (ref delegate) {0,18}", t_m);
Debug.Print("C# Unsafe pointer: {0,18}", t_u);
Debug.Print("C# Managed pointer: (ref func): {0,18}", t_f);
}
Поскольку фрагменты кода, реализующие тест для каждого конкретного метода, довольно длинные, я сначала приведу результаты. Время «тикает»; ниже значит лучше.
Normal (subscript+field): 20,804,691
Typed-reference: 30,920,655
Managed pointer: (ref delegate) 18,777,666 // <- a close 2nd
Unsafe pointer: 22,395,806
Managed pointer: (ref func): 18,767,179 // <- winner
Я был удивлен, что эти результаты были настолько однозначными. TypedReferences работают медленнее всего, по-видимому, потому, что они несут информацию о типе вместе с указателем. Учитывая вес IL-кода для разрекламированной версии Normal, он работал на удивление хорошо. Переходы режима, кажется, вредят небезопасному коду до такой степени, что вам действительно нужно обосновывать, планировать и измерять каждое место, где вы собираетесь его развернуть.
Но самое быстрое время достигается за счет использования ключевого слова ref в передаче параметров функций с целью указания на внутреннюю часть массива, что исключает вычисление индексации массива для каждого поля доступа.
Возможно, дизайн моего теста благоприятствует этому, но тестовые сценарии отражают эмпирические шаблоны использования в моем приложении. Что меня удивило в этих числах, так это то, что преимущество пребывания в управляемом режиме — при наличии ваших указателей — не было отменено необходимостью вызывать функцию или вызывать через делегата.
Победитель
Самый быстрый: (И, возможно, самый простой?)
static void f(ref rec e)
{
e.a = 4;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.b = 5;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.c = 6;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.d = 7;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.e = 8;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.f = 9;
e.a = e.c;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.a = 10;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.c = e.b;
}
static void test_f(int ix)
{
long q = sw.ElapsedTicks;
f(ref s5[ix]);
t_f += sw.ElapsedTicks - q;
}
Но у него есть недостаток, заключающийся в том, что вы не можете объединить связанную логику в своей программе: реализация функции разделена на две функции C#, f и test_f.
Мы можем решить эту конкретную проблему, лишь немного пожертвовав производительностью. Следующий в основном идентичен предыдущему, но встраивает одну из функций в другую как лямбда-функцию...
Близкая секунда
Замена статической функции в предыдущем примере встроенным делегатом требует использования ref аргументов, что, в свою очередь, исключает использование лямбда-синтаксиса Func<T>; вместо этого вы должны использовать явный делегат из .NET старого стиля.
Добавив это глобальное объявление один раз:
delegate void b(ref rec ee);
...мы можем использовать его во всей программе, чтобы напрямую ref входить в элементы массива rec[], получая к ним встроенный доступ:
static void test_m(int ix)
{
long q = sw.ElapsedTicks;
/// the element to manipulate "e", is selected at the bottom of this lambda block
((b)((ref rec e) =>
{
e.a = 4;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.b = 5;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.c = 6;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.d = 7;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.e = 8;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.f = 9;
e.a = e.c;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.a = 10;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.c = e.b;
}))(ref s3[ix]);
t_m += sw.ElapsedTicks - q;
}
Кроме того, хотя может показаться, что при каждом вызове создается новая лямбда-функция, этого не произойдет, если вы будете осторожны: при использовании этого метода убедитесь, что вы не закрываете какие-либо локальные переменные (т. переменные, которые находятся вне лямбда-функции, внутри ее тела), или делать что-либо еще, что запрещает вашему экземпляру делегата быть статическим. Если локальная переменная попадает в вашу лямбду, и лямбда, таким образом, повышается до экземпляра/класса, вы, вероятно, заметите разницу, когда она попытается создать пять миллионов делегатов.
Пока вы держите лямбда-функцию свободной от этих побочных эффектов, не будет нескольких экземпляров; что здесь происходит, так это то, что всякий раз, когда C# определяет, что лямбда не имеет неявных зависимостей, он лениво создает (и кэширует) статический синглтон. Немного жаль, что такое резкое изменение производительности скрыто от нашего взгляда как тихая оптимизация. В целом, мне нравится этот метод. Это быстро и без помех — за исключением причудливых круглых скобок, ни одну из которых здесь нельзя опустить.
И остальные
Для полноты, вот остальные тесты: обычный брекетинг плюс точка; типизированная ссылка; и небезопасные указатели.
static void test_n(int ix)
{
long q = sw.ElapsedTicks;
s1[ix].a = 4;
s1[ix].e = s1[ix].a;
s1[ix].b = s1[ix].d;
s1[ix].f = s1[ix].d;
s1[ix].b = s1[ix].e;
s1[ix].a = s1[ix].c;
s1[ix].b = 5;
s1[ix].d = s1[ix].f;
s1[ix].c = s1[ix].b;
s1[ix].e = s1[ix].a;
s1[ix].b = s1[ix].d;
s1[ix].f = s1[ix].d;
s1[ix].c = 6;
s1[ix].b = s1[ix].e;
s1[ix].a = s1[ix].c;
s1[ix].d = s1[ix].f;
s1[ix].c = s1[ix].b;
s1[ix].e = s1[ix].a;
s1[ix].d = 7;
s1[ix].b = s1[ix].d;
s1[ix].f = s1[ix].d;
s1[ix].b = s1[ix].e;
s1[ix].a = s1[ix].c;
s1[ix].d = s1[ix].f;
s1[ix].e = 8;
s1[ix].c = s1[ix].b;
s1[ix].e = s1[ix].a;
s1[ix].b = s1[ix].d;
s1[ix].f = s1[ix].d;
s1[ix].b = s1[ix].e;
s1[ix].f = 9;
s1[ix].a = s1[ix].c;
s1[ix].d = s1[ix].f;
s1[ix].c = s1[ix].b;
s1[ix].e = s1[ix].a;
s1[ix].b = s1[ix].d;
s1[ix].a = 10;
s1[ix].f = s1[ix].d;
s1[ix].b = s1[ix].e;
s1[ix].a = s1[ix].c;
s1[ix].d = s1[ix].f;
s1[ix].c = s1[ix].b;
t_n += sw.ElapsedTicks - q;
}
static void test_r(int ix)
{
long q = sw.ElapsedTicks;
var tr = __makeref(s2[ix]);
__refvalue(tr, rec).a = 4;
__refvalue(tr, rec).e = __refvalue( tr, rec).a;
__refvalue(tr, rec).b = __refvalue( tr, rec).d;
__refvalue(tr, rec).f = __refvalue( tr, rec).d;
__refvalue(tr, rec).b = __refvalue( tr, rec).e;
__refvalue(tr, rec).a = __refvalue( tr, rec).c;
__refvalue(tr, rec).b = 5;
__refvalue(tr, rec).d = __refvalue( tr, rec).f;
__refvalue(tr, rec).c = __refvalue( tr, rec).b;
__refvalue(tr, rec).e = __refvalue( tr, rec).a;
__refvalue(tr, rec).b = __refvalue( tr, rec).d;
__refvalue(tr, rec).f = __refvalue( tr, rec).d;
__refvalue(tr, rec).c = 6;
__refvalue(tr, rec).b = __refvalue( tr, rec).e;
__refvalue(tr, rec).a = __refvalue( tr, rec).c;
__refvalue(tr, rec).d = __refvalue( tr, rec).f;
__refvalue(tr, rec).c = __refvalue( tr, rec).b;
__refvalue(tr, rec).e = __refvalue( tr, rec).a;
__refvalue(tr, rec).d = 7;
__refvalue(tr, rec).b = __refvalue( tr, rec).d;
__refvalue(tr, rec).f = __refvalue( tr, rec).d;
__refvalue(tr, rec).b = __refvalue( tr, rec).e;
__refvalue(tr, rec).a = __refvalue( tr, rec).c;
__refvalue(tr, rec).d = __refvalue( tr, rec).f;
__refvalue(tr, rec).e = 8;
__refvalue(tr, rec).c = __refvalue( tr, rec).b;
__refvalue(tr, rec).e = __refvalue( tr, rec).a;
__refvalue(tr, rec).b = __refvalue( tr, rec).d;
__refvalue(tr, rec).f = __refvalue( tr, rec).d;
__refvalue(tr, rec).b = __refvalue( tr, rec).e;
__refvalue(tr, rec).f = 9;
__refvalue(tr, rec).a = __refvalue( tr, rec).c;
__refvalue(tr, rec).d = __refvalue( tr, rec).f;
__refvalue(tr, rec).c = __refvalue( tr, rec).b;
__refvalue(tr, rec).e = __refvalue( tr, rec).a;
__refvalue(tr, rec).b = __refvalue( tr, rec).d;
__refvalue(tr, rec).a = 10;
__refvalue(tr, rec).f = __refvalue( tr, rec).d;
__refvalue(tr, rec).b = __refvalue( tr, rec).e;
__refvalue(tr, rec).a = __refvalue( tr, rec).c;
__refvalue(tr, rec).d = __refvalue( tr, rec).f;
__refvalue(tr, rec).c = __refvalue( tr, rec).b;
t_r += sw.ElapsedTicks - q;
}
static void test_u(int ix)
{
long q = sw.ElapsedTicks;
fixed (rec* p = &s4[ix])
{
p->a = 4;
p->e = p->a;
p->b = p->d;
p->f = p->d;
p->b = p->e;
p->a = p->c;
p->b = 5;
p->d = p->f;
p->c = p->b;
p->e = p->a;
p->b = p->d;
p->f = p->d;
p->c = 6;
p->b = p->e;
p->a = p->c;
p->d = p->f;
p->c = p->b;
p->e = p->a;
p->d = 7;
p->b = p->d;
p->f = p->d;
p->b = p->e;
p->a = p->c;
p->d = p->f;
p->e = 8;
p->c = p->b;
p->e = p->a;
p->b = p->d;
p->f = p->d;
p->b = p->e;
p->f = 9;
p->a = p->c;
p->d = p->f;
p->c = p->b;
p->e = p->a;
p->b = p->d;
p->a = 10;
p->f = p->d;
p->b = p->e;
p->a = p->c;
p->d = p->f;
p->c = p->b;
}
t_u += sw.ElapsedTicks - q;
}
Резюме
Для интенсивной работы с памятью в крупномасштабных приложениях C# используйте управляемые указатели для прямого доступа к полям элементов массива с типизированным значением на месте. это путь.
Если вы действительно серьезно относитесь к производительности, это может быть достаточной причиной для использования C++/CLI (или CIL, если на то пошло) вместо C# для соответствующих частей вашего приложения, потому что эти языки позволяют вам напрямую объявлять управляемые указатели в теле функции. .
В C# единственный способ создать управляемый указатель — это объявить функцию с аргументом ref или out, после чего вызываемый объект будет наблюдать за управляемым указателем. Таким образом, чтобы получить преимущества производительности в C#, вы должны использовать один из (двух лучших) методов, показанных выше. [см. C#7 ниже]
К сожалению, они используют кладж разделения функции на несколько частей только для того, чтобы получить доступ к элементу массива. Хотя это значительно менее элегантно, чем эквивалентный код C++/CLI, тесты показывают, что даже в C# для приложений с высокой пропускной способностью мы по-прежнему получаем большой выигрыш в производительности по сравнению с простым доступом к массиву значений.
[изменить 2017 г. Хотя, возможно, и придается небольшая степень предвидения наставлениям в этой статье в целом, выпуск C# 7 в Visual Studio 2017 одновременно делает конкретные методы, описанные выше, полностью устаревшими. Короче говоря, новый ref locals в языке позволяет вам объявить собственный управляемый указатель как локальную переменную и использовать его для консолидации операции разыменования одного массива. Итак, учитывая, например, тестовую структуру сверху...
public struct rec { public int a, b, c, d, e, f; }
static rec[] s7 = new rec[100000];
...вот как теперь можно написать ту же тестовую функцию, что и выше:
static void test_7(int ix)
{
ref rec e = ref s7[ix]; // <--- C#7 ref local
e.a = 4; e.e = e.a; e.b = e.d; e.f = e.d; e.b = e.e; e.a = e.c;
e.b = 5; e.d = e.f; e.c = e.b; e.e = e.a; e.b = e.d; e.f = e.d;
e.c = 6; e.b = e.e; e.a = e.c; e.d = e.f; e.c = e.b; e.e = e.a;
e.d = 7; e.b = e.d; e.f = e.d; e.b = e.e; e.a = e.c; e.d = e.f;
e.e = 8; e.c = e.b; e.e = e.a; e.b = e.d; e.f = e.d; e.b = e.e;
e.f = 9; e.a = e.c; e.d = e.f; e.c = e.b; e.e = e.a; e.b = e.d;
e.a = 10; e.f = e.d; e.b = e.e; e.a = e.c; e.d = e.f; e.c = e.b;
}
Обратите внимание, что это полностью устраняет необходимость в кладжах, подобных тем, о которых я говорил выше. Более изящное использование управляемого указателя позволяет избежать ненужного вызова функции, который использовался в победителе, наиболее эффективной методологии из рассмотренных мной. Таким образом, производительность с новой функцией может быть только лучше, чем у лучших методов, сравниваемых выше.
Как ни странно, C# 7 также добавляет локальные функции, функция, которая напрямую решит жалобу на плохую инкапсуляцию, которую я выдвинул для двух из вышеупомянутых взломов. К счастью, вся эта затея по распространению выделенных функций только для того, чтобы получить доступ к управляемым указателям, теперь совершенно неактуальна.
person
Glenn Slayden
schedule
11.01.2013
