Почему суммирование массива типов значений медленнее, чем суммирование массива ссылочных типов?

Ответ 1

В Haswell корпорация Intel представила дополнительные стратегии прогнозирования ветвлений для небольших циклов (вот почему мы не можем наблюдать эту ситуацию на IvyBridge). Кажется, что конкретная стратегия ветвления зависит от многих факторов, включая выравнивание собственного кода. Различие между LegacyJIT и RyuJIT можно объяснить разными стратегиями выравнивания для методов. К сожалению, я не могу предоставить всю необходимую информацию об этих явлениях производительности (Intel хранит детали реализации в секрете; мои выводы основаны только на моих собственных экспериментах по реверс-инжинирингу ЦП), но я могу рассказать вам, как сделать этот тест лучше.

Основной трюк, который улучшает ваши результаты, - это ручное развертывание цикла, что очень важно для нанобенчмарков на Haswell+ с RyuJIT. Вышеуказанные явления затрагивают только маленькие циклы, поэтому мы можем решить проблему с огромным телом циклы. На самом деле, когда у вас есть тест, как

[Benchmark]
public void MyBenchmark()
{
    Foo();
}

BenchmarkDotNet генерирует следующий цикл:

for (int i = 0; i < N; i++)
{
    Foo(); Foo(); Foo(); Foo();
    Foo(); Foo(); Foo(); Foo();
    Foo(); Foo(); Foo(); Foo();
    Foo(); Foo(); Foo(); Foo();
}

Вы можете контролировать количество внутренних вызовов в этом цикле через UnrollFactor. Если у вас есть небольшой цикл внутри теста, вы должны развернуть его таким же образом:

[Benchmark(Baseline = true)]
public int ReferenceTypeSum()
{
    var sum = 0;

    for (var i = 0; i < Size; i += 16)
    {
        sum += _referenceTypeData[i].Value;
        sum += _referenceTypeData[i + 1].Value;
        sum += _referenceTypeData[i + 2].Value;
        sum += _referenceTypeData[i + 3].Value;
        sum += _referenceTypeData[i + 4].Value;
        sum += _referenceTypeData[i + 5].Value;
        sum += _referenceTypeData[i + 6].Value;
        sum += _referenceTypeData[i + 7].Value;
        sum += _referenceTypeData[i + 8].Value;
        sum += _referenceTypeData[i + 9].Value;
        sum += _referenceTypeData[i + 10].Value;
        sum += _referenceTypeData[i + 11].Value;
        sum += _referenceTypeData[i + 12].Value;
        sum += _referenceTypeData[i + 13].Value;
        sum += _referenceTypeData[i + 14].Value;
        sum += _referenceTypeData[i + 15].Value;
    }

    return sum;
}

Другой трюк - агрессивная разминка (например, 30 итераций). Вот так выглядит этап прогрева на моей машине:

WorkloadWarmup   1: 4194304 op, 865744000.00 ns, 206.4095 ns/op
WorkloadWarmup   2: 4194304 op, 892164000.00 ns, 212.7085 ns/op
WorkloadWarmup   3: 4194304 op, 861913000.00 ns, 205.4961 ns/op
WorkloadWarmup   4: 4194304 op, 868044000.00 ns, 206.9578 ns/op
WorkloadWarmup   5: 4194304 op, 933894000.00 ns, 222.6577 ns/op
WorkloadWarmup   6: 4194304 op, 890567000.00 ns, 212.3277 ns/op
WorkloadWarmup   7: 4194304 op, 923509000.00 ns, 220.1817 ns/op
WorkloadWarmup   8: 4194304 op, 861953000.00 ns, 205.5056 ns/op
WorkloadWarmup   9: 4194304 op, 862454000.00 ns, 205.6251 ns/op
WorkloadWarmup  10: 4194304 op, 862565000.00 ns, 205.6515 ns/op
WorkloadWarmup  11: 4194304 op, 867301000.00 ns, 206.7807 ns/op
WorkloadWarmup  12: 4194304 op, 841892000.00 ns, 200.7227 ns/op
WorkloadWarmup  13: 4194304 op, 827717000.00 ns, 197.3431 ns/op
WorkloadWarmup  14: 4194304 op, 828257000.00 ns, 197.4719 ns/op
WorkloadWarmup  15: 4194304 op, 812275000.00 ns, 193.6615 ns/op
WorkloadWarmup  16: 4194304 op, 792011000.00 ns, 188.8301 ns/op
WorkloadWarmup  17: 4194304 op, 792607000.00 ns, 188.9722 ns/op
WorkloadWarmup  18: 4194304 op, 794428000.00 ns, 189.4064 ns/op
WorkloadWarmup  19: 4194304 op, 794879000.00 ns, 189.5139 ns/op
WorkloadWarmup  20: 4194304 op, 794914000.00 ns, 189.5223 ns/op
WorkloadWarmup  21: 4194304 op, 794061000.00 ns, 189.3189 ns/op
WorkloadWarmup  22: 4194304 op, 793385000.00 ns, 189.1577 ns/op
WorkloadWarmup  23: 4194304 op, 793851000.00 ns, 189.2688 ns/op
WorkloadWarmup  24: 4194304 op, 793456000.00 ns, 189.1747 ns/op
WorkloadWarmup  25: 4194304 op, 794194000.00 ns, 189.3506 ns/op
WorkloadWarmup  26: 4194304 op, 793980000.00 ns, 189.2996 ns/op
WorkloadWarmup  27: 4194304 op, 804402000.00 ns, 191.7844 ns/op
WorkloadWarmup  28: 4194304 op, 801002000.00 ns, 190.9738 ns/op
WorkloadWarmup  29: 4194304 op, 797860000.00 ns, 190.2246 ns/op
WorkloadWarmup  30: 4194304 op, 802668000.00 ns, 191.3710 ns/op

По умолчанию BenchmarkDotNet пытается обнаружить такие ситуации и увеличить количество итераций прогрева. К сожалению, это не всегда возможно (при условии, что мы хотим провести "быструю" стадию прогрева в "простых" случаях).

И вот мои результаты (вы можете найти полный список обновленных тестов здесь: https://gist.github.com/AndreyAkinshin/4c9e0193912c99c0b314359d5c5d0a4e):

BenchmarkDotNet=v0.11.3, OS=macOS Mojave 10.14.1 (18B75) [Darwin 18.2.0]
Intel Core i7-4870HQ CPU 2.50GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.0.100-preview-009812
  [Host]     : .NET Core 2.0.5 (CoreCLR 4.6.0.0, CoreFX 4.6.26018.01), 64bit RyuJIT
  Job-IHBGGW : .NET Core 2.0.5 (CoreCLR 4.6.0.0, CoreFX 4.6.26018.01), 64bit RyuJIT

IterationCount=30  WarmupCount=30  

               Method | Size |     Mean |     Error |    StdDev |   Median | Ratio | RatioSD |
--------------------- |----- |---------:|----------:|----------:|---------:|------:|--------:|
     ReferenceTypeSum |  256 | 180.7 ns | 0.4514 ns | 0.6474 ns | 180.8 ns |  1.00 |    0.00 |
         ValueTypeSum |  256 | 154.4 ns | 1.8844 ns | 2.8205 ns | 153.3 ns |  0.86 |    0.02 |
 ExtendedValueTypeSum |  256 | 183.1 ns | 2.2283 ns | 3.3352 ns | 181.1 ns |  1.01 |    0.02 |

Ответ 2

Это действительно очень странное поведение.

Сгенерированный код для основного цикла для ссылочного типа выглядит следующим образом:

M00_L00:
mov     r9,rcx
cmp     edx,[r9+8]
jae     ArrayOutOfBound
movsxd  r10,edx
mov     r9,[r9+r10*8+10h]
add     eax,[r9+8]
inc     edx
cmp     edx,r8d
jl      M00_L00

в то время как для цикла типа значения:

M00_L00:
mov     r9,rcx
cmp     edx,[r9+8]
jae     ArrayOutOfBound
movsxd  r10,edx
add     eax,[r9+r10*4+10h]
inc     edx
cmp     edx,r8d
jl      M00_L00

Таким образом, разница сводится к:

Для справки:

mov     r9,[r9+r10*8+10h]
add     eax,[r9+8]

Для типа значения:

add     eax,[r9+r10*4+10h]

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

Я попытался запустить это через Intel Architecture Code Analyzer, и вывод IACA для ссылочного типа:

Throughput Analysis Report
--------------------------
Block Throughput: 1.72 Cycles       Throughput Bottleneck: Dependency chains
Loop Count:  35
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
|  Port  |   0   -  DV   |   1   |   2   -  D    |   3   -  D    |   4   |   5   |   6   |   7   |
--------------------------------------------------------------------------------------------------
| Cycles |  1.0     0.0  |  1.0  |  1.5     1.5  |  1.5     1.5  |  0.0  |  1.0  |  1.0  |  0.0  |
--------------------------------------------------------------------------------------------------

DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3)
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion occurred
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected
X - instruction not supported, was not accounted in Analysis

| Num Of   |                    Ports pressure in cycles                         |      |
|  Uops    |  0  - DV    |  1   |  2  -  D    |  3  -  D    |  4   |  5   |  6   |  7   |
-----------------------------------------------------------------------------------------
|   1*     |             |      |             |             |      |      |      |      | mov r9, rcx
|   2^     |             |      | 0.5     0.5 | 0.5     0.5 |      | 1.0  |      |      | cmp edx, dword ptr [r9+0x8]
|   0*F    |             |      |             |             |      |      |      |      | jnb 0x22
|   1      |             |      |             |             |      |      | 1.0  |      | movsxd r10, edx
|   1      |             |      | 0.5     0.5 | 0.5     0.5 |      |      |      |      | mov r9, qword ptr [r9+r10*8+0x10]
|   2^     | 1.0         |      | 0.5     0.5 | 0.5     0.5 |      |      |      |      | add eax, dword ptr [r9+0x8]
|   1      |             | 1.0  |             |             |      |      |      |      | inc edx
|   1*     |             |      |             |             |      |      |      |      | cmp edx, r8d
|   0*F    |             |      |             |             |      |      |      |      | jl 0xffffffffffffffe6
Total Num Of Uops: 9

Для типа значения:

Throughput Analysis Report
--------------------------
Block Throughput: 1.74 Cycles       Throughput Bottleneck: Dependency chains
Loop Count:  26
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
|  Port  |   0   -  DV   |   1   |   2   -  D    |   3   -  D    |   4   |   5   |   6   |   7   |
--------------------------------------------------------------------------------------------------
| Cycles |  1.0     0.0  |  1.0  |  1.0     1.0  |  1.0     1.0  |  0.0  |  1.0  |  1.0  |  0.0  |
--------------------------------------------------------------------------------------------------

DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3)
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion occurred
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected
X - instruction not supported, was not accounted in Analysis

| Num Of   |                    Ports pressure in cycles                         |      |
|  Uops    |  0  - DV    |  1   |  2  -  D    |  3  -  D    |  4   |  5   |  6   |  7   |
-----------------------------------------------------------------------------------------
|   1*     |             |      |             |             |      |      |      |      | mov r9, rcx
|   2^     |             |      | 1.0     1.0 |             |      | 1.0  |      |      | cmp edx, dword ptr [r9+0x8]
|   0*F    |             |      |             |             |      |      |      |      | jnb 0x1e
|   1      |             |      |             |             |      |      | 1.0  |      | movsxd r10, edx
|   2      | 1.0         |      |             | 1.0     1.0 |      |      |      |      | add eax, dword ptr [r9+r10*4+0x10]
|   1      |             | 1.0  |             |             |      |      |      |      | inc edx
|   1*     |             |      |             |             |      |      |      |      | cmp edx, r8d
|   0*F    |             |      |             |             |      |      |      |      | jl 0xffffffffffffffea
Total Num Of Uops: 8

Таким образом, для ссылочного типа есть небольшое преимущество (1,72 цикла на цикл против 1,74 цикла)

Я не эксперт в расшифровке выходных данных IACA, но я думаю, что это связано с использованием порта (лучше распределено для ссылочного типа между 2-3)

"Порт" - это микропроцессорные блоки в CPU. Например, для Skylake они делятся следующим образом (из таблиц с инструкциями от Agner оптимизировать ресурсы)

Port 0: Integer, f.p. and vector ALU, mul, div, branch
Port 1: Integer, f.p. and vector ALU
Port 2: Load
Port 3: Load
Port 4: Store
Port 5: Integer and vector ALU
Port 6: Integer ALU, branch
Port 7: Store address

Это похоже на очень тонкую оптимизацию микроинструкций (uop), но не могу объяснить почему.

Обратите внимание, что вы можете улучшить codegen для цикла следующим образом:

[Benchmark]
public int ValueTypeSum()
{
    var sum = 0;

    // NOTE: Caching the array to a local variable (that will avoid the reload of the Length inside the loop)
    var arr = _valueTypeData;
    // NOTE: checking against 'array.Length' instead of 'Size', to completely remove the ArrayOutOfBound checks
    for (var i = 0; i < arr.Length; i++)
    {
        sum += arr[i].Value;
    }

    return sum;
}

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

Ответ 3

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

В вашем тестовом коде только элементы массива объектов выделяются из кучи (*), таким образом MemoryAllocator может размещать каждый элемент последовательно (**) в куче. Когда тестовый код начинает выполняться, данные будут считываться из кэшей ram в ЦП, и поскольку элементы массива вашего объекта записываются в ram в последовательном (в непрерывном блоке) порядке, они будут кэшироваться, и поэтому вы не получаете никаких ошибок кэша.

Чтобы лучше это видеть, у вас может быть другой массив объектов (желательно с большими объектами), который будет выделяться в куче для фрагментации элементов массива объектов, которые вы сравниваете. Это может привести к тому, что пропадание кэша произойдет раньше, чем ваша текущая настройка В реальном сценарии будут другие потоки, которые будут размещать в той же куче и дополнительно фрагментировать фактические объекты массива. Кроме того, доступ к оперативной памяти занимает гораздо больше времени, чем доступ к кэшу процессора (или циклу процессора). (Проверьте этот пост по этой теме).

(*) Массив ValueType выделяет все пространство, необходимое для элементов массива, когда вы инициализируете его new ValueType[Size]; Элементы массива ValueType будут смежными в оперативной памяти.

(**) objectArr [i] объектный элемент и objectArr [i + 1] (и т.д.) будут располагаться рядом в куче, когда блок кэша ram, вероятно, все элементы массива объектов будут считаны в кэш процессора, поэтому при выполнении итерации по массиву доступ к оперативной памяти не требуется.

Ответ 4

Я посмотрел на разборку на.NET Core 2.1 x64.

Код типа ref выглядит для меня оптимальным. Машинный код загружает каждую ссылку на объект, а затем загружает поле из каждого экземпляра.

Варианты типа значения имеют проверку диапазона массива. Петлевое клонирование не удалось. Эта проверка диапазона происходит потому, что верхней границей цикла является Size. Это должен быть array.Length чтобы JIT мог распознавать этот шаблон и не генерировать проверку диапазона.

Это ссылка на версию. Я пометил основной цикл. Хитрость в поиске основного цикла заключается в том, чтобы сначала найти обратный переход к вершине цикла.

Это вариант значения:

jae - проверка дальности.

Так что это ограничение JIT. Если вы заботитесь об этом, откройте проблему GitHub в репозитории coreclr и скажите им, что клонирование цикла завершилось неудачно.

Унаследованный JIT на 4.7.2 имеет такое же поведение проверки диапазона. Сгенерированный код выглядит одинаково для версии ref:

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