[Перевод] Высокопроизводительный код на платформе .NET
Здравствуйте, дорогие читатели!
Не так давно мы занялись проработкой книги «Writing High-Performance .NET code», которая до сих пор не переведена на русский язык, хотя ей и скоро год.
Нас, конечно, не удивило, что такую книгу уже растаскивают на цитаты, однако выяснилось, что уважаемый автор Бен Уотсон, даже выложил на сайте «Codeproject» целую статью, написанную по мотивам одной из глав. К сожалению, объем этого материала слишком велик для хабропубликации, однако мы решили все-таки перевести первую часть статьи, чтобы вы могли оценить материал книги. Приглашаем к прочтению и к участию в опросе. Кроме того, если все-таки целесообразно перевести и вторую часть — пишите в комментариях, постараемся учесть ваши пожелания.
Контекст
Эта статья написана на основе главы 5 из моей книги Writing High-Performance .NET Code.
Введение
В статье рассмотрены общие принципы написания кода и дизайна типов. На платформе .NET имеются возможности для реализации разнообразных сценариев, и если некоторые из них в лучшем случае никак не отражаются на производительности, есть и такие, которые серьезно ее портят. Определенные сценарии ни хороши, ни плохи, а просто такие, каковы они есть. Приходится подбирать наиболее адекватное решение для каждой ситуации.
Если бы я попытался сформулировать общий принцип, лежащий в основе этой статьи, то он был бы таков:
Глубокая оптимизация производительности зачастую нарушает программные абстракции.
Это означает, что, пытаясь достичь экстремально высокой производительности, мы должны понимать детали реализации на всех уровнях и, возможно, пытаться сыграть на этих тонкостях. Многие подобные детали описаны в этой статье.
Сравнение классов и структур
Экземпляры класса всегда выделяются в куче, а доступ к этим экземплярам осуществляется путем разыменования указателя. Передавать их дешево, ведь речь идет всего лишь о копии указателя (4 или 8 байт). Однако у объекта также имеются некоторые фиксированные издержки: 8 байт для 32-битных процессов и 16 байт для 64-битных процессов. В эти издержки входит указатель на таблицу методов плюс поле блока синхронизации. Если создать объект без полей и просмотреть его в отладчике, то окажется, что на самом деле его размер составляет не 8, а 12 байт. В случае с 64-битными процессами объект будет иметь размер 24 байт. Дело в том, что минимальный размер зависит от выравнивания блоков памяти. К счастью, эти «лишние» 4 байт будут использоваться полем.
Структура struct не влечет издержек, а размер используемой ею памяти — это сумма размеров всех ее полей. Если struct объявляется как локальная переменная в методе, то struct выделяется в стеке. Если struct объявляется как часть класса, то память struct будет входить в состав фрагмента памяти, занимаемого этим классом (и, следовательно, находиться в куче). Если передать структуру struct методу, то она будет последовательно скопирована байт за байтом. Поскольку она не находится в куче, выделение структуры никогда не инициирует сборку мусора.
Следовательно, здесь приходится идти на компромисс. Вы можете встретить различные рекомендации о максимальном размере структуры, но я бы не привязывался к конкретному числу. Как правило, размер struct лучше держать очень небольшим, особенно если эта структура передается туда-сюда, однако структуры можно передавать и по ссылке, поэтому ее размер может не представлять существенной проблемы. Единственный способ уверенно определить, полезен ли будет такой прием — внимательно присмотреться к паттерну использования и самостоятельно выполнить профилирование.
В некоторых ситуациях эффективность может разительно отличаться. Пусть величина издержек на отдельно взятый объект и кажется мизерной, но попробуйте рассмотреть массив объектов, а потом сравните его с массивом структур. Предположим, в структуре данных содержится 16 байт данных, длина массива равна 1 000 000, и мы работаем в 32-разрядной системе.
Для массива объектов общий расход пространства составляет:
12 байт издержек массива +(размер указателя 4 байт × 1,000,000) +((издержки 8 байт + 16 байт данных) × 1,000,000)= 28 MB
Для массива структур получаем принципиально иной результат:
12 байт издержек массива +(16 байт данных × 1,000,000)= 16 MB
В случае с 64-битным процессом массив объектов занимает более 40 MB, тогда как массив struct требует всего 16 MB.
Как видите, в массиве struct аналогичный объем данных занимает меньше памяти, чем в массиве объектов. Вместе с издержками, связанными с использованием объектов, вы также получаете более интенсивную сборку мусора, что объясняется более высокой нагрузкой на память.
Кроме использования пространства есть еще и вопрос эффективности процессора. Процессор имеет несколько уровней кэширования. Те, что расположены ближе всего к процессору, очень невелики, но работают исключительно быстро и оптимизированы для последовательного доступа.
Массив struct содержит множество значений, последовательно расположенных в памяти. Обратиться к элементу в массиве struct очень просто. Как только корректная запись найдена, у нас уже есть верное значение. Таким образом, может возникать огромная разница в скорости доступа при переборе большого массива. Если значение уже находится в кэше процессора, то к нему можно обратиться на порядок быстрее, чем если оно расположено в оперативной памяти.
Для доступа к элементу объектного массива требуется обратиться к памяти массива, а затем разыменовать указатель на этот элемент, который может располагаться в любом месте кучи. Перебор объектных массивов сопряжен с разыменованием дополнительного указателя, «скачками» по куче и сравнительно частым опустошением кэша процессора, что потенциально приводит к растрате более нужных данных.
Отсутствие подобных издержек как на уровне процессора, так и в памяти — во многих случаях основная причина для предпочтения структур. При разумном использовании такой прием может дать значительный выигрыш в производительности, так как улучшается локальность памяти.
Поскольку структуры всегда копируются по значению, можно по неосторожности попасть и в более интересное положение. Например, следующий код написан с ошибками и не скомпилируется:
struct Point { public int x; public int y; }
public static void Main ()
{
List
Проблема возникает в последней строке, которая пытается изменить существующий Point в списке. Это невозможно, поскольку вызов points[0] возвращает копию оригинального значения, которая нигде дополнительно не сохраняется. Правильный способ изменения Point:
Point p = points[0]; p.x = 3; points[0] = p;
Однако может быть целесообразно реализовать еще более строгую политику: сделать структуры неизменяемыми. После создания структура такая структура уже не сможет получить новое значение. В таком случае вышеописанная ситуация становится в принципе невозможна, вся работа со структурами упрощается.
Выше упоминалось, что структуры должны быть компактными, чтобы не пришлось тратить много времени на их копирование, но иногда приходится использовать и большие структуры. Рассмотрим объект, в котором отслеживается масса деталей о каком-либо коммерческом процессе — например, ставится множество временных меток.
class Order { public DateTime ReceivedTime {get; set;} public DateTime AcknowledgeTime {get; set;} public DateTime ProcessBeginTime {get; set;} public DateTime WarehouseReceiveTime {get; set;} public DateTime WarehouseRunnerReceiveTime {get; set;} public DateTime WarehouseRunnerCompletionTime {get; set;} public DateTime PackingBeginTime {get; set;} public DateTime PackingEndTime {get; set;} public DateTime LabelPrintTime {get; set;} public DateTime CarrierNotifyTime {get; set;} public DateTime ProcessEndTime {get; set;} public DateTime EmailSentToCustomerTime {get; set;} public DateTime CarrerPickupTime {get; set;} // множество прочих данных … }
Чтобы упростить код, было бы неплохо выделить каждую из таких меток в собственную подструктуру, которая по-прежнему будет доступна через код класса Order следующим образом:
Order order = new Order (); Order.Times.ReceivedTime = DateTime.UtcNow;
Все эти подструктуры можно вынести в отдельный класс:
class OrderTimes { public DateTime ReceivedTime {get; set;} public DateTime AcknowledgeTime {get; set;} public DateTime ProcessBeginTime {get; set;} public DateTime WarehouseReceiveTime {get; set;} public DateTime WarehouseRunnerReceiveTime {get; set;} public DateTime WarehouseRunnerCompletionTime {get; set;} public DateTime PackingBeginTime {get; set;} public DateTime PackingEndTime {get; set;} public DateTime LabelPrintTime {get; set;} public DateTime CarrierNotifyTime {get; set;} public DateTime ProcessEndTime {get; set;} public DateTime EmailSentToCustomerTime {get; set;} public DateTime CarrerPickupTime {get; set;} }
class Order { public OrderTimes Times; }
Однако при этом дополнительно возникают 12 или 24 байт издержек на каждый объект Order.
Если вам требуется передавать различным методам объект OrderTimes целиком, то, возможно, такие издержки и оправданны, но почему бы просто не передать ссылку на целый объект Order? Если у вас одновременно обрабатываются тысячи объектов Order, это приведет к значительной активизации сборки мусора. Кроме того, в памяти пойдут дополнительные операции разыменования.
Попробуйте лучше сделать OrderTimes структурой. Обращение к отдельным свойствам структуры OrderTimes через свойство объекта Order (например, order.Times.ReceivedTime) не приводит к копированию структуры (в .NET этот вероятный сценарий специально оптимизирован). Таким образом, структура OrderTimes в сущности входит в состав участка памяти, отведенного под класс Order, словно здесь и нет никакой подструктуры. Сам код при этом также становится аккуратнее.
Такая техника не нарушает принципа неизменяемых структур, но весь фокус здесь заключается в следующем: мы обращаемся с полями структуры OrderTimes точно как если бы они были полями объекта Order. Если вам не требуется передавать структуру OrderTimes как цельную сущность, то предложенный механизм является чисто организационным.
Переопределение методов Equals и GetHashCode для структур
При работе со структурами исключительно важно переопределять методы Equals и GetHashCode. Если этого не сделать, то вы получите их версии, задаваемые по умолчанию, которые отнюдь не способствуют высокой производительности. Чтобы оценить, насколько это нехорошо, откройте просмотрщик промежуточного языка и взгляните на код метода ValueType.Equals. Он связан с рефлексией по всем полям структуры. Однако это оптимизация для двоично-совместимых типов. Двоично-совместимым (blittable) называется такой тип, который имеет одинаковое представление в памяти как в управляемом, так и в неуправляемом коде. К их числу относятся только примитивные числовые типы (например, Int32, UInt64, но не Decimal, не являющийся примитивным) и IntPtr/UIntPtr. Если структура состоит только из двоично-совместимых типов, то реализация Equals может фактически выполнять побайтное сравнение памяти в рамках всей структуры. Просто избегайте такой неопределенности и реализуйте собственный метод Equals.
Если просто переопределить Equals (object other), то у вас все равно получится неоправданно низкая производительность, поскольку данный метод связан с приведением и упаковкой типов значений. Вместо этого реализуйте Equals (T other), где T — тип вашей структуры. Для этого предназначен интерфейс IEquatable, и все структуры должны реализовывать его. Компилятор при работе всегда отдает предпочтение более строго типизированной версии, если это возможно. Рассмотрим пример:
struct Vector: IEquatable
public int Magnitude { get; set; }
public override bool Equals (object obj) { if (obj == null) { return false; } if (obj.GetType () != this.GetType ()) { return false; } return this.Equals ((Vector)obj); }
public bool Equals (Vector other) { return this.X == other.X && this.Y == other.Y && this.Z == other.Z && this.Magnitude == other.Magnitude; }
public override int GetHashCode () { return X ^ Y ^ Z ^ Magnitude; } }
Если тип реализует интерфейс IEquatable, то обобщенные коллекции .NET его обнаружат и станут использовать для более эффективного поиска и сортировки.
Возможно, вы также решите применять операторы == и != с типами ваших значений и заставите их вызывать метод existingEquals (T).
Даже если вы никогда не сравниваете структуры или не помещаете их в коллекции, все-таки рекомендую реализовать эти методы. Никогда не угадаешь, как они будут использоваться в будущем, а на написание методов уйдет всего несколько минут и считанные байты промежуточного языка, которые даже никогда не потребуют динамической компиляции.
Переопределять методы Equals и GetHashCode у классов не столь важно, поскольку в данном случае они лишь вычисляют равенство, исходя из ссылки на объект. Если вы полагаете, что в вашем коде будет вполне достаточно стандартной реализации этих методов — не меняйте ее.
Виртуальные методы и запечатанные классы
Не делайте методы виртуальными по умолчанию «просто на всякий случай». Однако, если виртуальные методы требуются для согласованного дизайна ваших программ, то, пожалуй, не переусердствуйте с их удалением.
Если сделать методы виртуальными, это препятствует определенным оптимизациям со стороны динамического компилятора, в частности, мешает встраивать методы. Методы могут встраиваться лишь в том случае, если компилятору на 100% известно, какой метод будет вызываться. Помечая метод как виртуальный, мы теряем такую определенность, хотя, существуют и другие факторы, которые могут вынудить отказаться от такой оптимизации.
К виртуальным методам концептуально близки запечатанные классы, например:
public sealed class MyClass {}
Класс, помеченный как запечатанный, объявляет, что никакие другие классы не могут от него наследовать.
Теоретически, динамический компилятор может использовать эту информацию и более активно заниматься встраиванием, но в настоящее время этого не происходит. Как бы то ни было, следует по умолчанию объявлять классы как запечатанные и не делать методы по умолчанию виртуальными, если в этом нет необходимости. В таком случае ваш код будет приспособлен к любым актуальным оптимизациям динамического компилятора, а также к тем, которые возможны в будущем.
Если вы пишете библиотеку классов, которую предполагается использовать в разнообразных ситуациях, особенно вне вашей организации, следует действовать осторожнее. В таком случае наличие виртуального API может быть важнее голой производительности — чтобы ваша библиотека была удобна для переиспользования и настраивания. Но если код пишется для внутрикорпоративных нужд и часто меняется, старайтесь обеспечить более высокую производительность.
Диспетчеризация интерфейсов
Когда вы в первый раз вызываете метод через интерфейс, .NET необходимо определить, к какому типу и методу делать вызов. Сначала делается вызов к заглушке, которая находит метод, вызываемый при работе с объектом, реализующим данный интерфейс. После того, как это произойдет несколько раз, CLR «усвоит», что все время вызывается один и тот же конкретный тип, и этот косвенный вызов через заглушку редуцируется до заглушки, состоящей всего из нескольких инструкций сборки, вызывающей нужный метод. Такая группа инструкций называется «мономорфной заглушкой», поскольку она знает, как вызывать метод лишь для одного-единственного типа. Это идеально в ситуациях, когда место вызова всегда вызывает интерфейсные методы на одном и том же типе.
Мономорфная заглушка также позволяет обнаружить, если что-то пойдет неправильно. Если в какой-то момент место вызова начнет использовать метод другого типа, то CLR в итоге заменит заглушку другой мономорфной заглушкой для нового типа.
Если ситуация еще сложнее, в нее вовлечены несколько типов, и она менее предсказуема (например, есть массив интерфейсного типа, но в этом массиве присутствуют несколько конкретных типов), то заглушка превратится в полиморфную и будет использовать хэш-таблицу, позволяющую выбирать, какой метод вызвать. Поиск по таблице быстр, но все-таки не настолько, как при работе с мономорфной заглушкой. Кроме того, размер такой хэш-таблицы строго ограничен, и если у вас слишком много типов, то, возможно, придется с самого начала откатиться к обобщенному коду поиска типов. Эта операция может оказаться очень затратной.
Если такая проблема возникнет, ее можно решить одним из двух способов:
- 1. Избегайте вызывать эти объекты через общий интерфейс
- 2. Выберите общий базовый интерфейс и замените его базовым классом abstract
Подобная проблема встречается не часто, однако она может приключиться, если у вас есть огромная иерархия типов, все они реализуют общий интерфейс, и вы вызываете методы через этот общий интерфейс. Можно заметить, что процессор работает на месте вызова этих методов столь активно, что это невозможно объяснить лишь той работой, которую делают сами методы.
История При проектировании большой системы мы заранее знали, что у нас, возможно, будут тысячи разных типов, и все они будут происходить от общего типа. В паре мест у нас должна была возникнуть необходимость обращаться к ним из базового типа. Поскольку в нашей команде был человек, разбиравшийся в диспетчеризации интерфейсов при решении проблем такого масштаба, мы решили использовать базовый класс abstract, а не корневой интерфейс.
Хорошая статья о диспетчеризации интерфейсов есть в блоге Ванса Моррисона.
Избегайте упаковки
Упаковка — это процесс обертывания значимого типа, например, примитива или структуры, в объект, находящийся в куче. В таком виде этот тип может передаваться методам, требующим ссылки на объект. Распаковка — это извлечение исходного значения.
На упаковку тратится процессорное время, необходимое на выделение, копирование и приведение объекта. Однако еще важнее, что при этом в куче активизируется сборка мусора. Если небрежно относиться к упаковке, то в программе может возникнуть множество операций выделения, и все они окажут дополнительную нагрузку на сборщик мусора.Явная упаковка происходит всякий раз, когда выполняются подобные операции:
int x = 32; object o = x;
Промежуточный язык здесь выглядит так:
IL_0001: ldc.i4.s 32 IL_0003: stloc.0 IL_0004: ldloc.0 IL_0005: box [mscorlib]System.Int32 IL_000a: stloc.1
Это означает, что относительно несложно найти большинство источников упаковки в вашем коде: просто воспользуйтесь ILDASM для преобразования всего вашего IL в текст и выполните поиск.
Очень распространенная ситуация, в которой возможна нерегулярная упаковка — это использование API, принимающего object или object[] в качестве параметра. Наиболее тривиальными из них являются String.Format или традиционные коллекции, в которых хранятся только ссылки на объекты, и работы с которыми требуется полностью избежать по той или иной причине.
Кроме того, упаковка может происходить при присваивании структуры интерфейсу, например:
interface INameable { string Name { get; set; } }
struct Foo: INameable { public string Name { get; set; } }
void TestBoxing () { Foo foo = new Foo () { Name = «Bar» }; // упаковка! INameable nameable = foo; … }
Если решите протестировать этот код — обратите внимание, что если на самом деле вы не используете упакованную переменную, то компилятор в порядке оптимизации просто уберет инструкцию упаковки, поскольку она так и не задействуется. Как только вы вызовете метод или используете значение еще каким-то образом, инструкция упаковки будет на месте.
Еще одна вещь, которая происходит при упаковке и которую необходимо учитывать — результат следующего кода:
int val = 13; object boxedVal = val; val = 14;
Каким будет значение boxedVal после этого?
При упаковке значение копируется, и между оригиналом и копией не остается никакой связи. Например, значение val может измениться на 14, но boxedVal сохранит исходное значение 13.
Иногда упаковку удается отследить в профиле процессора, но многие упаковочные вызовы попросту встраиваются, и надежного способа найти их не существует. При чрезмерной упаковке вы увидите в профиле процессора лишь массовое выделение памяти при помощи new.
Если вам приходится активно упаковывать структуры, и вы приходите к выводу, что без этого не обойтись, то, вероятно, просто следует превратить структуру в класс, что может оказаться даже дешевле.
Наконец, обратите внимание: передача значимого типа по ссылке упаковкой не является. Посмотрите IL и убедитесь, что никакой упаковки не происходит. Адрес значимого типа отправляется методу.
Сравнение for и foreach
Используйте программу MeasureIt, чтобы оценить, чем отличается перебор коллекций в циклах for и foreach. Работа со стандартными циклами for протекает значительно быстрее практически в любых случаях. Однако если вы попробуете провести собственный простой тест, то, в зависимости от сценария, можете обнаружить, что оба цикла имеют примерно равную производительность. Действительно, во многих ситуациях .NET преобразует простые инструкции foreach в стандартные циклы for.
Рассмотрим проект ForEachVsFor, в котором есть следующий код:
int[] arr = new int[100]; for (int i = 0; i < arr.Length; i++) { arr[i] = i; }
int sum = 0; foreach (int val in arr) { sum += val; }
sum = 0;
IEnumerable
Собрав его, попробуйте декомпилировать этот код при помощи инструмента для рефлексии IL. Вы увидите, что первый foreach на самом деле компилируется как цикл for. Промежуточный язык будет таков:
// Начало цикла (head: IL_0034) IL_0024: ldloc.s CS$6$0000 IL_0026: ldloc.s CS$7$0001 IL_0028: ldelem.i4 IL_0029: stloc.3 IL_002a: ldloc.2 IL_002b: ldloc.3 IL_002c: add IL_002d: stloc.2 IL_002e: ldloc.s CS$7$0001 IL_0030: ldc.i4.1 IL_0031: add IL_0032: stloc.s CS$7$0001 IL_0034: ldloc.s CS$7$0001 IL_0036: ldloc.s CS$6$0000 IL_0038: ldlen IL_0039: conv.i4 IL_003a: blt.s IL_0024 // Конец цикла
Здесь много операций сохранения, загрузки, добавления и одна ветка — все довольно просто.
Однако стоит нам привести массив к IEnumerable и выполнить ту же операцию, как работа оказывается гораздо более затратной:
IL_0043: callvirt instance class [mscorlib]System.Collections.Generic.IEnumerator`1 class [mscorlib]System.Collections.Generic.IEnumerable`1
IL_005a: ldloc.s CS$5$0002 IL_005c: callvirt instance bool [mscorlib]System.Collections.IEnumerator: MoveNext () IL_0061: brtrue.s IL_004c // конец цикла
IL_0063: leave.s IL_0071 } // конец блока .try finally { IL_0065: ldloc.s CS$5$0002 IL_0067: brfalse.s IL_0070
IL_0069: ldloc.s CS$5$0002 IL_006b: callvirt instance void [mscorlib]System.IDisposable: Dispose ()
IL_0070: endfinally } // конец обработчика
У нас 4 вызова виртуальных методов, блок try-finally и (здесь не показано) выделение памяти для локальной переменной перечислителя, в которой отслеживается состояние перечисления. Такая операция гораздо затратнее, чем обычный цикл for: используется больше процессорного времени и больше памяти!
Не забывайте, что базовая структура данных здесь — по-прежнему массив, а значит, цикл for использовать можно —, но мы идем на обфускацию, приводя тип к интерфейсу IEnumerable. Здесь важно учитывать факт, уже упоминавшийся в начале статьи: глубокая оптимизация производительности часто идет вразрез с абстракциями кода. Так, foreach — это абстракция цикла, IEnumerable — абстракция коллекции. Вместе они дают такое поведение, которое исключают простую оптимизацию с применением цикла for, перебирающего массив.
Приведение
В принципе, следует по возможности избегать приведения. Приведение часто свидетельствует о некачественном дизайне классов, но иногда оно действительно требуется. Так, к приведению приходится прибегать при преобразовании чисел со знаком в беззнаковые, например, когда мы работаем с различными сторонними API. Приведение объектов должно происходить гораздо реже.
Приведение объектов никогда не обходится без издержек, но стоимость такой операции может разительно отличаться в зависимости от отношений между объектами. Привести предка к нужному потомку значительно затратнее, чем выполнить обратную операцию, и стоимость такой операции тем выше, чем крупнее иерархия. Приведение к интерфейсу обходится дороже, чем приведение к конкретному типу.
Абсолютно недопустимо неверное приведение. Если оно произойдет, вы получите исключение InvalidCastException, стоимость которого на порядки превысит «цену» операции приведения.
См. проект CastingPerf в исходном коде к этой книге, где отмечено количество приведений тех или иных типов.
При тестовом прогоне на моем компьютере получился такой результат:
JIT (ignore): 1.00x No cast: 1.00x Up cast (1 gen): 1.00x Up cast (2 gens): 1.00x Up cast (3 gens): 1.00x Down cast (1 gen): 1.25x Down cast (2 gens): 1.37x Down cast (3 gens): 1.37x Interface: 2.73x Invalid Cast: 14934.51x as (success): 1.01x as (failure): 2.60x is (success): 2.00x is (failure): 1.98x
Оператор «is» — это приведение, тестирующее результат и возвращающее булево значение.
Оператор «as» напоминает стандартное приведение, но возвращает null, если приведение не срабатывает. Как видно из вышеприведенных результатов, эта операция гораздо быстрее, чем выдача исключения.Никогда не применяйте такой паттерн, где делается два приведения:
if (a is Foo) { Foo f = (Foo)a; }
Лучше используйте для приведения «as» и кэшируйте результат, а потом проверяйте возвращаемое значение:
Foo f = a as Foo; if (f!= null) { … }
Если приходится выполнить проверку для множества типов, то сначала указывайте наиболее распространенный тип.
Примечание: Мне приходится регулярно сталкиваться с одним неприятным преобразованием, когда используется MemoryStream.Length типа long. Большинство API, сталкивающихся с этим, используют ссылку на базовый буфер (извлекаемую из метода MemoryStream.GetBuffer), смещение и длину, которая часто относится к типу int. Таким образом, возникает необходимость нисходящего преобразования от long. Подобные преобразования могут быть регулярными и неизбежными.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.