Какова аргументация x64, имеющая такой же результат производительности от x86?

Ответ 1

Я хотел сделать анализ сгенерированного кода сборки, чтобы узнать, что происходит. Я схватил ваш пример кода и запустил его в режиме Release. Это использует Visual Studio 2015 с .NET Framework 4.5.2. CPU - это Intel Ivy Bridge i5-3570K, если JIT делает очень конкретные оптимизации. Я провел один и тот же тест, но без набора тестов, просто используя простой Stopwatch и деля время на тики по количеству итераций. Вот что я заметил:

RawModulo_5, x86:                 13721978 ticks, 13.721978 ticks per iteration
OptimizedModulo_ViaMethod_5, x86: 24641039 ticks, 24.641039 ticks per iteration

RawModulo_5, x64:                 23275799 ticks, 23.275799 ticks per iteration
OptimizedModulo_ViaMethod_5, x64: 13389012 ticks, 13.389012 ticks per iteration

Это несколько отличается от ваших измерений - производительность каждого метода более или менее переворачивается в зависимости от x86 и x64. Ваши измерения имеют гораздо более резкие отличия, особенно между каждой реализацией и другим аналогом. RawModulo_5 немного меньше, чем в два раза медленнее в x64, а OptimizedModulo_ViaMethod_5 - в 3,8 раза быстрее в x64!

Кроме того, надеюсь, вы не ожидаете, что выходы RawModulo_5 и OptimizedModulo_ViaMethod_5 будут равны, потому что это не так! Правильная реализация Mersenne5 ниже:

static public ulong Mersenne5(ulong dividend)
{
    dividend = (dividend >> 32) + (dividend & 0xFFFFFFFF);
    dividend = (dividend >> 16) + (dividend & 0xFFFF);
    dividend = (dividend >> 8) + (dividend & 0xFF);
    dividend = (dividend >> 4) + (dividend & 0xF);
    // there was an extra shift by 4 here
    if (dividend > 14) { dividend = dividend - 15; } // mod 15
    // the 9 used to be a 10
    if (dividend > 9) { dividend = dividend - 10; }
    if (dividend > 4) { dividend = dividend - 5; }
    return dividend;
}

Чтобы собрать инструкции в моей системе, я добавил System.Diagnostics.Debugger.Break() внутри каждого метода непосредственно перед циклами и телом Mersenne5, чтобы у меня была определенная точка останова для захвата сгенерированной сборки. Кстати, вы можете захватить сгенерированный ассемблерный код из интерфейса Visual Studio - если вы находитесь в точке останова, вы можете щелкнуть правой кнопкой мыши окно редактора кода и выбрать "Go To Disassembly" из контекстного меню. Я аннотировал сборку, чтобы объяснить, что она делает. Извините за безумную подсветку синтаксиса.

x86, метод RawModulo_5

            System.Diagnostics.Debugger.Break();
00242DA2  in          al,dx  
00242DA3  push        edi  
00242DA4  push        ebx  
00242DA5  sub         esp,10h  
00242DA8  call        6D4C0178  
            ulong r = 0;
00242DAD  mov         dword ptr [ebp-10h],0  ; setting the low and high dwords of 'r'
00242DB4  mov         dword ptr [ebp-0Ch],0  
            for (ulong i = 0; i < 1000; i++)
; set the high dword of 'i' to 0
00242DBB  mov         dword ptr [ebp-14h],0
; clear the low dword of 'i' to 0 - the compiler is using 'edi' as the loop iteration var
00242DC2  xor         edi,edi  
            {
                r += i % 5;
00242DC4  mov         eax,edi  
00242DC6  mov         edx,dword ptr [ebp-14h]  
; edx:eax together are the high and low dwords of 'i', respectively

; this is a short circuit trick so it can avoid working with the high
; dword - you can see it jumps halfway in to the div/mod operation below
00242DC9  mov         ecx,5  
00242DCE  cmp         edx,ecx  
00242DD0  jb          00242DDC  
; 64 bit div/mod operation
00242DD2  mov         ebx,eax  
00242DD4  mov         eax,edx  
00242DD6  xor         edx,edx  
00242DD8  div         eax,ecx  
00242DDA  mov         eax,ebx  
00242DDC  div         eax,ecx  
00242DDE  mov         eax,edx  
00242DE0  xor         edx,edx
; load the current low and high dwords from 'r', then add into
; edx:eax as a pair forming a qword
00242DE2  add         eax,dword ptr [ebp-10h]  
00242DE5  adc         edx,dword ptr [ebp-0Ch]  
; store the result back in 'r'
00242DE8  mov         dword ptr [ebp-10h],eax  
00242DEB  mov         dword ptr [ebp-0Ch],edx  
            for (ulong i = 0; i < 1000; i++)
; load the loop variable low and high dwords into edx:eax
00242DEE  mov         eax,edi  
00242DF0  mov         edx,dword ptr [ebp-14h]  
; increment eax (the low dword) and propagate any carries to
; edx (the high dword)
00242DF3  add         eax,1  
00242DF6  adc         edx,0  
; store the low and high dwords back to the high word of 'i' and
; the loop iteration counter, 'edi'
00242DF9  mov         dword ptr [ebp-14h],edx  
00242DFC  mov         edi,eax
; test the high dword  
00242DFE  cmp         dword ptr [ebp-14h],0  
00242E02  ja          00242E0E  
00242E04  jb          00242DC4  
; (int) i < 1000
00242E06  cmp         edi,3E8h  
00242E0C  jb          00242DC4  
            }
            return r;
; retrieve the current value of 'r' from memory, return value is
; in edx:eax since the return value is 64 bits
00242E0E  mov         eax,dword ptr [ebp-10h]  
00242E11  mov         edx,dword ptr [ebp-0Ch]  
00242E14  lea         esp,[ebp-8]  
00242E17  pop         ebx  
00242E18  pop         edi  
00242E19  pop         ebp  
00242E1A  ret  

x86, OptimizedModulo_ViaMethod_5

            System.Diagnostics.Debugger.Break();
00242E33  push        edi  
00242E34  push        esi  
00242E35  push        ebx  
00242E36  sub         esp,8  
00242E39  call        6D4C0178  
            ulong r = 0;
; same as above, initialize 'r' to zero using low and high dwords
00242E3E  mov         dword ptr [ebp-10h],0  
; this time we're using edi:esi as the loop counter, rather than
; edi and a memory location. probably less register pressure in this
; function, for reasons we'll see...
00242E45  xor         ebx,ebx  
            for (ulong i = 0; i < 1000; i++)
; initialize 'i' to 0, esi is the loop counter low dword, edi is the high dword
00242E47  xor         esi,esi  
00242E49  xor         edi,edi  
; push 'i' to the stack, high word then low word
00242E4B  push        edi  
00242E4C  push        esi  
; call Mersenne5 - it got put in the data section since it static
00242E4D  call        dword ptr ds:[3D7830h]  
; return value comes back as edx:eax, where edx is the high dword
; ebx is the existing low dword of 'r', so it accumulated into eax
00242E53  add         eax,ebx  
; the high dword of 'r' is at ebp-10, that gets accumulated to edx with
; the carry result of the last add since it 64 bits wide
00242E55  adc         edx,dword ptr [ebp-10h]
; store edx:ebx back to 'r'  
00242E58  mov         dword ptr [ebp-10h],edx  
00242E5B  mov         ebx,eax  
; increment the loop counter and carry to edi as well, 64 bit add
00242E5D  add         esi,1  
00242E60  adc         edi,0  
; make sure edi == 0 since it the high dword
00242E63  test        edi,edi  
00242E65  ja          00242E71  
00242E67  jb          00242E4B  
; (int) i < 1000
00242E69  cmp         esi,3E8h  
00242E6F  jb          00242E4B  
            }
            return r;
; move 'r' to edx:eax to return them
00242E71  mov         eax,ebx  
00242E73  mov         edx,dword ptr [ebp-10h]  
00242E76  lea         esp,[ebp-0Ch]  
00242E79  pop         ebx  
00242E7A  pop         esi  
00242E7B  pop         edi  
00242E7C  pop         ebp  
00242E7D  ret  

x86, метод Mersenne5()

            System.Diagnostics.Debugger.Break();
00342E92  in          al,dx  
00342E93  push        edi  
00342E94  push        esi  
; esi is the low dword, edi is the high dword of the 64 bit argument
00342E95  mov         esi,dword ptr [ebp+8]  
00342E98  mov         edi,dword ptr [ebp+0Ch]  
00342E9B  call        6D4C0178  
            dividend = (dividend >> 32) + (dividend & 0xFFFFFFFF);
; this is a LOT of instructions for each step, but at least it all registers.

; copy edi:esi to edx:eax
00342EA0  mov         eax,esi  
00342EA2  mov         edx,edi
; clobber eax with edx, so now both are the high word. this is a
; shorthand for a 32 bit shift right of a 64 bit number.  
00342EA4  mov         eax,edx
; clear the high word now that we've moved the high word to the low word  
00342EA6  xor         edx,edx
; clear the high word of the original 'dividend', same as masking the low 32 bits  
00342EA8  xor         edi,edi  
; (dividend >> 32) + (dividend & 0xFFFFFFFF)
; it a 64 bit add, so it the usual add/adc
00342EAA  add         eax,esi  
00342EAC  adc         edx,edi
; 'dividend' now equals the temporary "variable" that held the addition result  
00342EAE  mov         esi,eax  
00342EB0  mov         edi,edx  
            dividend = (dividend >> 16) + (dividend & 0xFFFF);
; same idea as above, but with an actual shift and mask since it not 32 bits wide
00342EB2  mov         eax,esi  
00342EB4  mov         edx,edi  
00342EB6  shrd        eax,edx,10h  
00342EBA  shr         edx,10h  
00342EBD  and         esi,0FFFFh  
00342EC3  xor         edi,edi  
00342EC5  add         eax,esi  
00342EC7  adc         edx,edi  
00342EC9  mov         esi,eax  
00342ECB  mov         edi,edx  
            dividend = (dividend >> 8) + (dividend & 0xFF);
; same idea, keep going down...
00342ECD  mov         eax,esi  
00342ECF  mov         edx,edi  
00342ED1  shrd        eax,edx,8  
00342ED5  shr         edx,8  
00342ED8  and         esi,0FFh  
00342EDE  xor         edi,edi  
00342EE0  add         eax,esi  
00342EE2  adc         edx,edi  
00342EE4  mov         esi,eax  
00342EE6  mov         edi,edx  
            dividend = (dividend >> 4) + (dividend & 0xF);
00342EE8  mov         eax,esi  
00342EEA  mov         edx,edi  
00342EEC  shrd        eax,edx,4  
00342EF0  shr         edx,4  
00342EF3  and         esi,0Fh  
00342EF6  xor         edi,edi  
00342EF8  add         eax,esi  
00342EFA  adc         edx,edi  
00342EFC  mov         esi,eax  
00342EFE  mov         edi,edx  
            dividend = (dividend >> 4) + (dividend & 0xF);
00342F00  mov         eax,esi  
00342F02  mov         edx,edi  
00342F04  shrd        eax,edx,4  
00342F08  shr         edx,4  
00342F0B  and         esi,0Fh  
00342F0E  xor         edi,edi  
00342F10  add         eax,esi  
00342F12  adc         edx,edi  
00342F14  mov         esi,eax  
00342F16  mov         edi,edx  
            if (dividend > 14) { dividend = dividend - 15; } // mod 15
; conditional subtraction
00342F18  test        edi,edi  
00342F1A  ja          00342F23  
00342F1C  jb          00342F29  
; 'dividend' > 14
00342F1E  cmp         esi,0Eh  
00342F21  jbe         00342F29  
; 'dividend' = 'dividend' - 15
00342F23  sub         esi,0Fh 
; subtraction borrow from high word 
00342F26  sbb         edi,0  
            if (dividend > 10) { dividend = dividend - 10; }
; same gist for the next two
00342F29  test        edi,edi  
00342F2B  ja          00342F34  
00342F2D  jb          00342F3A  
00342F2F  cmp         esi,0Ah  
00342F32  jbe         00342F3A  
00342F34  sub         esi,0Ah  
00342F37  sbb         edi,0  
            if (dividend > 4) { dividend = dividend - 5; }
00342F3A  test        edi,edi  
00342F3C  ja          00342F45  
00342F3E  jb          00342F4B  
00342F40  cmp         esi,4  
00342F43  jbe         00342F4B  
00342F45  sub         esi,5  
00342F48  sbb         edi,0  
            return dividend;
; move edi:esi into edx:eax for return
00342F4B  mov         eax,esi  
00342F4D  mov         edx,edi  
00342F4F  pop         esi  
00342F50  pop         edi  
00342F51  pop         ebp  
00342F52  ret         8  

Первая большая вещь, которую я замечаю, это то, что Mersenne5 на самом деле не встраивается, хотя в нее перечислены теги AggressiveInlining. Я предполагаю, что это связано с тем, что встроенная функция внутри OptimizedModulo_ViaMethod_5 вызовет ужасающее распространение реестра, а большой объем чтения и записи памяти полностью разрушит точку вложения метода, поэтому компилятор выбрал (совершенно разумно!) Не сделайте это.

Во-вторых, Mersenne5 получает call 'd 1000 раз на OptimizedModulo_ViaMethod_5, так что там испытывается 1000 единиц лишних накладных расходов/накладных расходов, включая необходимые нажатия и всплывающие окна для сохранения состояний регистров по границе вызова. RawModulo_5 не выполняет никаких внешних вызовов, и даже 64-разрядное разделение немного оптимизировано, поэтому он пропускает высокий dword, где он может.

x64, метод RawModulo_5

            System.Diagnostics.Debugger.Break();
000007FE98C93CF0  sub         rsp,28h  
000007FE98C93CF4  call        000007FEF7B079C0  
            ulong r = 0;
; the compiler knows the high dword of rcx is already 0, so it just
; zeros the low dword. this is 'r'
000007FE98C93CF9  xor         ecx,ecx  
            for (ulong i = 0; i < 1000; i++)
; same here, this is 'i'
000007FE98C93CFB  xor         r8d,r8d  
            {
                r += i % 5;
; load 5 as a dword to the low dword of r9
000007FE98C93CFE  mov         r9d,5  
; copy the loop counter to rax for the div below
000007FE98C93D04  mov         rax,r8  
; clear the lower dword of rdx, upper dword is clear already
000007FE98C93D07  xor         edx,edx  
; 64 bit div/mod in one instruction! but it slow!
000007FE98C93D09  div         rax,r9  
; rax = quotient, rdx = remainder
; throw away the quotient since we're just doing mod, and accumulate the
; modulus into 'r'
000007FE98C93D0C  add         rcx,rdx  
            for (ulong i = 0; i < 1000; i++)
; 64 bit increment to the loop counter
000007FE98C93D0F  inc         r8  
; i < 1000
000007FE98C93D12  cmp         r8,3E8h  
000007FE98C93D19  jb          000007FE98C93CFE  
            }
            return r;
; return 'r' in rax, since we can directly return a 64 bit var in one register now
000007FE98C93D1B  mov         rax,rcx  
000007FE98C93D1E  add         rsp,28h  
000007FE98C93D22  ret  

x64, OptimizedModulo_ViaMethod_5

            System.Diagnostics.Debugger.Break();
000007FE98C94040  push        rdi  
000007FE98C94041  push        rsi  
000007FE98C94042  sub         rsp,28h  
000007FE98C94046  call        000007FEF7B079C0  
            ulong r = 0;
; same general loop setup as above
000007FE98C9404B  xor         esi,esi  
            for (ulong i = 0; i < 1000; i++)
; 'edi' is the loop counter
000007FE98C9404D  xor         edi,edi  
; put rdi in rcx, which is the x64 register used for the first argument
; in a call
000007FE98C9404F  mov         rcx,rdi  
; call Mersenne5 - still no actual inlining!
000007FE98C94052  call        000007FE98C90F40  
; accumulate 'r' with the return value of Mersenne5
000007FE98C94057  add         rax,rsi  
; store back to 'r' - I don't know why in the world the compiler did this
; seems like add rsi, rax would be better, but maybe there a pipelining
; issue I'm not seeing.
000007FE98C9405A  mov         rsi,rax  
; increment loop counter
000007FE98C9405D  inc         rdi  
; i < 1000
000007FE98C94060  cmp         rdi,3E8h  
000007FE98C94067  jb          000007FE98C9404F  
            }
            return r;
; put return value in rax like before
000007FE98C94069  mov         rax,rsi  
000007FE98C9406C  add         rsp,28h  
000007FE98C94070  pop         rsi  
000007FE98C94071  pop         rdi  
000007FE98C94072  ret  

x64, метод Mersenne5

            System.Diagnostics.Debugger.Break();
000007FE98C94580  push        rsi  
000007FE98C94581  sub         rsp,20h  
000007FE98C94585  mov         rsi,rcx  
000007FE98C94588  call        000007FEF7B079C0  
            dividend = (dividend >> 32) + (dividend & 0xFFFFFFFF);
; pretty similar to before actually, except this time we do a real
; shift and mask for the 32 bit part
000007FE98C9458D  mov         rax,rsi  
; 'dividend' >> 32
000007FE98C94590  shr         rax,20h  
; hilariously, we have to load the mask into edx first. this is because
; there is no AND r/64, imm64 in x64
000007FE98C94594  mov         edx,0FFFFFFFFh  
000007FE98C94599  and         rsi,rdx  
; add the shift and the masked versions together
000007FE98C9459C  add         rax,rsi  
000007FE98C9459F  mov         rsi,rax  
            dividend = (dividend >> 16) + (dividend & 0xFFFF);
; same logic continues down
000007FE98C945A2  mov         rax,rsi  
000007FE98C945A5  shr         rax,10h  
000007FE98C945A9  mov         rdx,rsi  
000007FE98C945AC  and         rdx,0FFFFh  
000007FE98C945B3  add         rax,rdx  

; note the redundant moves that happen every time, rax into rsi, rsi
; into rax. so there still not ideal x64 being generated.
000007FE98C945B6  mov         rsi,rax  
            dividend = (dividend >> 8) + (dividend & 0xFF);
000007FE98C945B9  mov         rax,rsi  
000007FE98C945BC  shr         rax,8  
000007FE98C945C0  mov         rdx,rsi  
000007FE98C945C3  and         rdx,0FFh  
000007FE98C945CA  add         rax,rdx  
000007FE98C945CD  mov         rsi,rax  
            dividend = (dividend >> 4) + (dividend & 0xF);
000007FE98C945D0  mov         rax,rsi  
000007FE98C945D3  shr         rax,4  
000007FE98C945D7  mov         rdx,rsi  
000007FE98C945DA  and         rdx,0Fh  
000007FE98C945DE  add         rax,rdx  
000007FE98C945E1  mov         rsi,rax  
            dividend = (dividend >> 4) + (dividend & 0xF);
000007FE98C945E4  mov         rax,rsi  
000007FE98C945E7  shr         rax,4  
000007FE98C945EB  mov         rdx,rsi  
000007FE98C945EE  and         rdx,0Fh  
000007FE98C945F2  add         rax,rdx  
000007FE98C945F5  mov         rsi,rax  
            if (dividend > 14) { dividend = dividend - 15; } // mod 15
; notice the difference in jumping logic - the pairs of jumps are now singles
000007FE98C945F8  cmp         rsi,0Eh  
000007FE98C945FC  jbe         000007FE98C94602 
; using a single 64 bit add instead of a subtract, the immediate constant
; is the 2 complement of 15. this is okay because there no borrowing
; to do since we can do the entire sub in one operation to one register. 
000007FE98C945FE  add         rsi,0FFFFFFFFFFFFFFF1h  
            if (dividend > 10) { dividend = dividend - 10; }
000007FE98C94602  cmp         rsi,0Ah  
000007FE98C94606  jbe         000007FE98C9460C  
000007FE98C94608  add         rsi,0FFFFFFFFFFFFFFF6h  
            if (dividend > 4) { dividend = dividend - 5; }
000007FE98C9460C  cmp         rsi,4  
000007FE98C94610  jbe         000007FE98C94616  
000007FE98C94612  add         rsi,0FFFFFFFFFFFFFFFBh  
            return dividend;
000007FE98C94616  mov         rax,rsi  
000007FE98C94619  add         rsp,20h  
000007FE98C9461D  pop         rsi  
000007FE98C9461E  ret  

<ч/" > Все методы x64 выглядят лучше, чем их x86-аналоги, но все еще возникает вопрос, почему RawModulo_5 в x64 по сравнению с x86 вдвое медленнее, и особенно почему OptimizedModulo_ViaMethod_5 почти в четыре раза быстрее, чем x64, чем x86. Чтобы получить полное объяснение, я думаю, нам нужен кто-то вроде Питера Кордеса - он гораздо более осведомлен, чем я, в отношении таймингов инструкций и конвейерной обработки. Вот мои интуиции относительно того, откуда исходят преимущества и недостатки.

• [x64 con] div в x86 по сравнению с x64, поскольку это относится к RawModulo_5

  В соответствии с таблицами инструкций, представленными Agner Fog здесь, на Broadwell 32-разрядный div принимает 10 микроопераций и имеет задержку от 22 до 29 тактов, а 64 бит div занимает 36 микроопераций и имеет задержку от 32 до 95 часов.

  Компилятор также сделал оптимизацию в x86 RawModulo_5, которая в каждом случае обходит высокий dword div, так как цикл остается ниже int.MaxValue, поэтому на самом деле он просто делает один 32-разрядный div для каждого итерация. Таким образом, латентность 64 бит div находится между 1,45 и 3,27 раза выше, чем 32-разрядная задержка div. Обе версии имеют общие зависимости от результатов div, поэтому код x64 платит гораздо больший штраф за производительность из-за более высокой задержки. Я бы рискнул, что пара инструкций add/adc для 64-битных добавлений в x86 RawModulo_5 - это крошечный штраф в сравнении с огромным недостатком производительности 64-битной ширины div.

• [x64 pro] Сокращение накладных расходов на звонки в x64 OptimizedModulo_ViaMethod_5

  Это, вероятно, не большая разница в производительности, но стоит упомянуть. Поскольку OptimizedModulo_ViaMethod_5 вызывает Mersenne5 1000 раз в обеих версиях, 64-разрядная версия платит гораздо меньше штрафа в терминах стандартного соглашения о вызове x86 и x64. Подумайте, что версия x86 должна вытолкнуть два регистра в стек для передачи 64-битной переменной, тогда Mersenne5 должна сохранить esi и edi, а затем вытащить из стека высшие и низшие слова для edx и eax соответственно. В конце Mersenne5 необходимо восстановить esi и edi. В версии x64 значение i передается непосредственно в ecx, поэтому никакой доступ к памяти не задействован вообще. X64 Mersenne5 сохраняет и восстанавливает rsi, другие регистры сбиты.

• [x64 pro] Множество команд в x64 Mersenne5

  Mersenne5 более эффективен в x64, так как он может выполнять все операции с 64-разрядным dividend в отдельных инструкциях по сравнению с требуемыми парами инструкций в x86 для операций mov и add/adc. У меня есть подозрение, что сети зависимостей лучше в x64, но я недостаточно осведомлен, чтобы говорить по этому вопросу.

• [x64 pro] Улучшение поведения перехода в x64 Mersenne5

  Три условных вычитания, которые Mersenne5 делают в конце, реализованы намного лучше при x64, чем x86. На x86 каждый имеет два сравнения и три возможных условных перехода, которые можно выполнить. На x64 существует только одно сравнение и один условный скачок, что, несомненно, более эффективно.

С учетом этих соображений, это имеет смысл для Ivy Bridge, мы увидим производительность каждого триггера от x86 до x64. Вероятно, что штраф за латентность 64-битного разделения (что немного хуже на мосту Айви, чем у Бродвелла, но не много) сильно вредит RawModulo_5, а почти половина инструкций в Mersenne5 ускоряется OptimizedModulo_ViaMethod_5 в то же время.

Что не имеет смысла - это результаты на Broadwell - я все еще немного удивлен, насколько быстрее x64 OptimizedModulo_ViaMethod_5, даже по сравнению с x86 RawModulo_5. Я полагаю, что ответ был бы микрооперационным слиянием, а конвейерная обработка для метода Mersenne5 значительно лучше на x64, или, возможно, JIT в вашей архитектуре использует знания Broadwell для вывода очень разных инструкций.

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

Кстати, если вы хотите посмотреть, что может сделать действительно встроенная версия, вы здесь:

RawModulo_5, x86:                  13722506 ticks, 13.722506 ticks per iteration
OptimizedModulo_ViaMethod_5, x86:  23640994 ticks, 23.640994 ticks per iteration
OptimizedModulo_TrueInlined, x86:  21488012 ticks, 21.488012 ticks per iteration
OptimizedModulo_TrueInlined2, x86: 21645697 ticks, 21.645697 ticks per iteration

RawModulo_5, x64:                 22175326 ticks, 22.175326 ticks per iteration
OptimizedModulo_ViaMethod_5, x64: 12822574 ticks, 12.822574 ticks per iteration
OptimizedModulo_TrueInlined, x64:  7612328 ticks,  7.612328 ticks per iteration
OptimizedModulo_TrueInlined2, x64: 7591190 ticks,  7.59119 ticks per iteration

И код:

public ulong OptimizedModulo_TrueInlined()
{
    ulong r = 0;
    ulong dividend = 0;

    for (ulong i = 0; i < 1000; i++)
    {
        dividend = i;
        dividend = (dividend >> 32) + (dividend & 0xFFFFFFFF);
        dividend = (dividend >> 16) + (dividend & 0xFFFF);
        dividend = (dividend >> 8) + (dividend & 0xFF);
        dividend = (dividend >> 4) + (dividend & 0xF);
        dividend = (dividend >> 4) + (dividend & 0xF);
        if (dividend > 14) { dividend = dividend - 15; } // mod 15
        if (dividend > 10) { dividend = dividend - 10; }
        if (dividend > 4) { dividend = dividend - 5; }
        r += dividend;
    }
    return r;
}

public ulong OptimizedModulo_TrueInlined2()
{
    ulong r = 0;
    ulong dividend = 0;

    for (ulong i = 0; i < 1000; i++)
    {
        dividend = (i >> 32) + (i & 0xFFFFFFFF);
        dividend = (dividend >> 16) + (dividend & 0xFFFF);
        dividend = (dividend >> 8) + (dividend & 0xFF);
        dividend = (dividend >> 4) + (dividend & 0xF);
        dividend = (dividend >> 4) + (dividend & 0xF);
        if (dividend > 14) { dividend = dividend - 15; } // mod 15
        if (dividend > 10) { dividend = dividend - 10; }
        if (dividend > 4) { dividend = dividend - 5; }
        r += dividend;
    }
    return r;
}

Ответ 2

  r += i % 5;

Это оператор узкого места в фрагменте кода, как хорошо объяснил @ozeanix. Я буду комментировать его обширный ответ.

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

Джиттер x86, которому приходится генерировать громоздкий код для выполнения математики только с 32-разрядными регистрами, взял ярлык для случая, когда верхние 32-биты ulong равны 0. Это оказалось хорошо в этом конкретный случай, 999 и 5 достаточно малы. Обратите внимание на то, насколько быстрее 64-разрядный код находится в методе Mersenne5(), имея возможность использовать один регистр для хранения промежуточных значений и одну команду смены, чтобы перемещать 64-битные данные за один раз, придает ей большую ногу.

Джиттер x64 не может использовать тот же трюк, который использует джиттер x86, но не делает код медленнее, верхние 32-битные из 64-битного регистра не адресуются напрямую. Это не значит, что вы застряли с более медленным перфомансом, имея достаточное доверие, чтобы любая свинья могла летать. Я покажу трюк для кодирования, который я перепроектировал из оптимизатора компилятора C. Он работает в этом конкретном случае, потому что вы неоднократно используете один и тот же делитель. Чтобы проиллюстрировать трюк, это машинный код, который такой компилятор генерирует во внутреннем цикле с отключением цикла и смешением команд:

00007FF603121006  mov         rax,0CCCCCCCCCCCCCCCDh    ; magic!
00007FF603121010  mul         rax,r9                    ; magic * i
00007FF603121013  shr         rdx,2                     ; rdx = (magic * i) / 4 / 2^64 
00007FF603121017  lea         rcx,[rdx+rdx*4]           ; 5 * rdx
00007FF60312101B  mov         rdx,r9                    ; i
00007FF60312101E  sub         rdx,rcx                   ; i - 5 * ((magic * i) / 4 / 2^64)
00007FF603121024  add         r8,rdx                    ; r += i % 5

Это, кашель, трудно понять. Ключевым моментом является то, что код вообще не использует инструкцию DIV, но может делать это с помощью SHR, что делает его очень быстрым. SHR - точный эквивалент оператора >> в С#, правое смещение эквивалентно делению на степени 2.

Большой трюк состоит в том, чтобы преобразовать деление на 5 в деление на степень 2. Это вообще не возможно, но оно может быть аппроксимировано. Для этого требуется несколько переписывающих трюков. Он начинается с идентичности, которая преобразуется по модулю в деление:

A % B == A - B * (A / B)

Преобразуйте деление, умножив левую и правую стороны на N/B, где N - удобная степень 2:

A % B == A - B * ((A * N / B) / N)

Так как N/B известно спереди, его можно вытащить из петли. Я должен подчеркнуть, что эта идентичность применима только для деления с плавающей запятой. Вместо этого мы хотим использовать целочисленное деление. Таким образом:

A % B ~= A - B * (A * K / N)   where K ~= N / B

Аппроксимация для K является более точным, чем больше значение, которое мы выбираем для N. Код компилятора C использует очень большое значение для N, 4 * 2 ^ 64, используя 64-битное умножение, создающее 128- бит. Что-то, что мы не можем сделать в С#, нам нужно выбрать значение для N, которое является достаточно маленьким, чтобы результат никогда не переполнялся. Кодирование этого подхода в классе-помощнике:

public class FastModulo {
    public FastModulo(ulong maxdividend, ulong divisor) {
        div = divisor;
        int dividendbits = 1 + (int)(Math.Log(maxdividend - 1) / Math.Log(2));
        shift = 64 - dividendbits;
        mult = (ulong)Math.Round((double)(1UL << shift) / divisor);
        //TODO: verify that the approximation is accurate enough.
    }
    public ulong Modulo(ulong value) {
        return value - (div * ((value * mult) >> shift));
    }
    int shift;
    ulong mult, div;
}

И используя его:

public ulong RawModulo_5() {
    var fm = new FastModulo(1000, 5);
    ulong r = 0;
    for (uint i = 0; i < 1000; i++) {
        r += fm.Modulo(i);
    }
}

Или менее читаемый:

        r += i - (5 * ((i * 3602879701896397UL) >> 54));

Совсем немного быстрее в 64-битном режиме (не использовать в 32), я вижу грубое улучшение x3 на моем мобильном хасуэлле. Достигнутый путем замены дорогостоящего мультициклического деления на 2 умножения, сдвиг и вычитание. Каждый из них принимает только 1 цикл.

Существует//TODO, ему нужна проверка, чтобы убедиться, что аппроксимация не вызывает ошибок, когда дивиденд или делитель становятся слишком большими. Не на 100% уверен, как это сделать правильно, модульная математика дает мне головную боль. Но я уверен, что большинство программистов считают это любопытством вместо практического кода:) Если кто-то хочет копать, пожалуйста, отредактируйте код, чтобы добавить проверку, иначе просто запустите код в обоих случаях, чтобы убедиться, что результат тот же.