Доброго времени суток. В данной статье я предлагаю ознакомиться с индексаторами в различных типах. Посмотрим код языка ассемблера для данных индексаторов и характеристики каждой инструкций по ее скорости. Также я предложу несколько очевидных выводов. Но что именно использовать в конкретно вашей ситуации решать вам — стоит ли жертвовать удобством ради скорости или наоборот.

Метрики

Код языка ассемблера приведен для 64 битных систем. В качестве метрик для каждой инструкции были выбраны: количество слитых микро-операций, общее количество микро-операций, задержка, пропускная способность и, разумеется, количество инструкций. Приводить какие-то цифры в целом для индексатора я не стал, т.к. ситуация может меняться в зависимости от способов работы с индексируемым типом и по-разному влиять на кеш.

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

Микро-операция (uop) — некая операция из которых состоит каждая инструкция. Концепция микро-операций используется для таких оптимизаций, как слияние, кеширование и переупорядочивание. Так, например, инструкция MOV состоит из 1 микро-операции, в то время как инструкция XCHG над двумя регистрами состоит из 3 микро-операций (используется подход через «временную переменную», то есть внутренний регистр, спасибо leotsarev за апдейт), инструкция XCHG над регистром и памятью состоит из 8 микро-операций.

Слитые микро-операции (fused uops) — как уже было упомянуто выше, слияние микро-операций — одна из оптимизаций. Заключается она в замене двух микро-операций одной более сложной.

Задержка (latency) — число тактов, после которого данные, используемые в этой инструкции станут доступны для использования другой инструкцией.

Пропускная способность (Reciprocal throughput) — число тактов, требуемое для выполнения одной инструкции, при условии, что выполняется последовательность одинаковых инструкций и они оперируют независимыми данными.

Опираясь на эти показатели можно оценить производительность того или иного набора инструкций. Прошу обратить внимание, что мы можем лишь «оценить», реальная производительность зависит от множества факторов, таких как попадание или промах кеша, зависимость по данным и т.п.

Данные показатели приведены для процессора Intel архитектуры Skylake-X. Это соответствует моему процессору Intel Core i7-6700.

Также стоит помнить, что fastcall для 64 битных систем обеспечивает передачу не 2, а 4 параметров в регистрах (rcx, rdx, r8, r9).

Индексаторы в цифрах

1. Индексатор массива

Рассматривать будем на примере методов следующего вида:

public int IndexerArray(int index, int[] array)
{
    return array[index];
}

Рассмотрим код языка ассемблера для этого фрагмента.

1. cmp     edx,dword ptr [r8+8]
2. jae     00007ff9`07288c78
3. movsxd  rax,edx
4. mov     eax,dword ptr [r8+rax*4+10h]

В первой строке проверяется, не выходит ли индекс за границы массива. Во второй строке кидается исключение, если выходит. Далее мы высчитываем позицию элемента в массиве. Первые поля в массиве являются служебной информацией, так что нам необходимо их пропустить (дополнительные 10h = 16 байт).

2. Любимый всеми List<>

Код болванки:

public int IndexerList(int index, List<int> list)
{
    return list[index];
}

Код языка ассемблера:

1. cmp     edx,dword ptr [r8+10h]
2. jae     M00_L00 
3. mov     rax,qword ptr [r8+8]
4. cmp     edx,dword ptr [rax+8]
5. jae     00007ff9`07268f56
6. movsxd  rdx,edx
7. mov     eax,dword ptr [rax+rdx*4+10h]
ret
M00_L00 call System.ThrowHelper.ThrowArgumentOutOfRange_IndexException()

Здесь инструкций явно больше. Отчетливо видно, что индексатор листа оборачивает индексатор массива. Интересный момент — проверка на выход за границы массива здесь осуществляется дважды. Итак, первая инструкция проверяет, выходит ли индекс за границы листа. Если выходит, то мы прыгаем (инструкция 2) на вполне очевидный вызов, кидающий исключение в случае выхода за границы массива. В этой проверке границ используется внутреннее поле листа, которое является вторым по порядку (смещение в 10h (16) байт от начала типа, 8 на указатель на таблицу методов и 8 на ссылку на внутренний массив — первое поле). В третей строке мы помещаем в регистр rax адрес внутреннего массива — первое поле (по аналогии смещение в 8 байт — указатель на таблицу методов). Далее следует уже знакомый участок — обращение по индексу для массива (строки 4 — 7). Здесь же для проверки границ используется внутреннее поле массива.
Я старался убирать вещи, не относящиеся непосредственно к индексации, но тут стоит оставить ret чтобы не казалось, что в конце каждого обращения к элементу листа будет исключение :D

Кстати, чтобы не мучить вас домыслами, прошу ознакомиться с реализацией листа по ссылке. Приведение типа к беззнаковому инту используется для уменьшения числа сравнений.

В итоге получаем 7 инструкций для успешного обращения по индексу, что на 3 больше чем в массиве.

Новинка — Span<>

Болванка:

public int IndexerSpan(int index, Span<int> span)
{
   return span[index];
}

И на языке ассемблера:

1. cmp     edx,dword ptr [r8+8]
2. jae     00007ff9`07278f69
3. mov     rax,qword ptr [r8]
4. movsxd  rdx,edx
5. mov     eax,dword ptr [rax+rdx*4]

При анонсе спанов нам обещали, что сделаны они по уму, с поддержкой рантайма. И не соврали, что сказать. По факту от классического массива отличается только одной инструкцией, дополнительным шагом обращения по адресу. Судя по этому коду внутри спана прячется адрес участка памяти, где располагаются элементы, который мы и получаем в строке 3. Это может быть адрес на определенное место какого-либо массива, строки или же фрагмент памяти на стеке.
По ссылке можно ознакомиться с реализацией индексатора спана ради интереса. Можно заметить, что там приведено 2 разные реализации, зависящие от переменной среды. PROJECTN — кодовое имя первой версии .NET Native для UWP. Поэтому нас больше интересует вторая версия индексатора. Она помечена [Intrinsic]. Более того, если посмотреть на статический класс Unsafe, используемый в реализации этого индексатора, можно найти информацию о том, что реализации большинства методов в этом файле представлены как Intrinsic.

Вызовы методов или ссылки на поля, помеченные атрибутом [Intrinsic] имеют поддержку со стороны рантайма.

В CoreCLR, тела таких методов заменяются EE (Execution engine) на небезопасный код (unsafe). Если нужно больше деталей, то можно начать копать с метода getILIntrinsicImplementationForUnsafe.

Информацию о том, как это работает в CoreRT (который меня мало интересует),
можно начать искать в Internal.IL.Stubs.UnsafeIntrinsics.

С учетом такой поддержки со стороны райнтайма, чтобы понять, что конкретно будет происходить за кулисами, имеет смысл смотреть на инструкции языка ассемблера, что мы и сделали.


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

Теперь попробуем посмотреть на разные способы, с помощью которых мы можем задать двумерный массив: массив массивов (jagged array) и многомерный массив (multidimensional array).

4. Многомерный массив (multidimensional array)

Код на шарпе:

public int IndexerDimensionalArray(int index1, int index2, int[,] demensionalArray)
{
    return demensionalArray[index1, index2];
}

Язык ассемблера:

1. mov     eax,edx
2. sub     eax,dword ptr [r9+18h]
3. cmp     eax,dword ptr [r9+10h]
4. jae     00007ff9`00098fe6
5. mov     edx,r8d
6. sub     edx,dword ptr [r9+1Ch]
7. cmp     edx,dword ptr [r9+14h]
8. jae     00007ff9`00098fe6
9. mov     ecx,dword ptr [r9+14h]
10. imul    rcx,rax
11. mov     rax,rdx
12. add     rax,rcx
13. mov     eax,dword ptr [r9+rax*4+20h]

Все в принципе понятно — 2 проверки на границы массива, дальше высчитывание индекса и обращение. Хранится этот массив в памяти одним фрагментом.

5. Массив массивов (jagged array)

public int IndexerJaggedArray(int index, int index2, int[][] jaggedArray)
{
    return jaggedArray[index][index2];
}

Ассемблер:

1. cmp     edx,dword ptr [r9+8]
2. jae     00007ff9`00098f95
3. movsxd  rax,edx
4. mov     rax,qword ptr [r9+rax*8+10h]
5. cmp     r8d,dword ptr [rax+8]
6. jae     00007ff9`00098f95
7. movsxd  rdx,r8d
8. mov     eax,dword ptr [rax+rdx*4+10h]

И самое интересное — мы имеем меньше инструкций, чем при специально сделанном для многомерности типа.


Но по поводу 2 последних примеров советую не спешить с выводами. За счет того, что двумерный массив является цельным типом, который инициализируется за 1 раз, память под весь массив выделится одним большим фрагментом. Это обеспечит лучшую работу кеша, который может в корне поменять ситуацию. В массиве массивов же память под каждый массив будет выделяться отдельно, поэтому велика вероятность, что массивы будут разнесены по памяти и вписаны в наиболее подходящие для них места.

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

Также при использовании массива массивов больше вероятность не спровоцировать сборщик мусора на компактинг (compacting), а обойтись свипом (sweep). Напоминалка: при фрагментации памяти, общий объем свободного места может быть достаточен для нового объекта, но непрерывного свободного участка нужного объема нет. В таком случае выполняется компактинг — перемещение объектов с целью дефрагментации. Если же мы в состоянии подобрать непрерывный участок свободной памяти для нового объекта, мы можем просто вписать объект в это свободное место. Это называется свипом.

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