Menu
Below is a simple program that with a small change, makes a significant performance impact and I don't understand why.
What the program does is not really relevant, but it calculates PI in a very convoluted way by counting collisions between two object of different mass and a wall. What I noticed as I was changing the code around was a quite large variance in performance.
The rows in question are the commented ones which are mathematically equivalent. Using the slow version makes the entire program take roughly twice as long as using the fast version.
int iterations = 0;
for (int i = 4; i < 9; i++)
{
Stopwatch s = Stopwatch.StartNew();
double ms = 1.0;
double mL = Math.Pow(100.0, i);
double uL = 1.0;
double us = 0.0;
double msmLInv = 1d / (ms + mL);
long collisions = 0;
while (!(uL < 0 && us <= 0 && uL <= us))
{
Debug.Assert(++iterations > 0);
++collisions;
double vs = (2 * mL * uL + us * (ms - mL)) * msmLInv;
//double vL = (2 * ms * us - uL * (ms - mL)) * msmLInv; //fast
double vL = uL + (us - vs) / mL; //slow
Debug.Assert(Math.Abs(((2 * ms * us - uL * (ms - mL)) * msmLInv) - (uL + (us - vs) / mL)) < 0.001d); //checks equality between fast and slow
if (vs > 0)
{
++collisions;
vs = -vs;
}
us = vs;
uL = vL;
}
s.Stop();
Debug.Assert(collisions.ToString() == "314159265359".Substring(0, i + 1)); //check the correctness
Console.WriteLine($"i: {i}, T: {s.ElapsedMilliseconds / 1000f}, PI: {collisions}");
}
Debug.Assert(iterations == 174531180); //check that we dont skip loops
Console.Write("Waiting...");
Console.ReadKey();
My intuition says that because the fast version has 7 operations compared to 4 operations of the slow one, the slow one should be faster, but it is not.
I disassembled the program using .NET Reflector which shows that they are mostly equal, as expected, except for the part shown below. The code before and after an identical
//slow
ldloc.s uL
ldloc.2
ldloc.s us
ldloc.s vs
sub
mul
ldloc.3
div
add
//fast
ldc.r8 2
ldloc.2
mul
ldloc.s us
mul
ldloc.s uL
ldloc.2
ldloc.3
sub
mul
sub
ldloc.2
ldloc.3
add
div
This also shows that more code is executing with the fast version which also would lead me to expect it to be slower.
The only guess I have right now is that the slow version causes more cache misses, but I don't know how to measure that (a guide would be welcome). Other than that I am at a loss.
EDIT 1. As per the request of @EricLippert here is the disassembly from the JIT for the inner while loop where the difference is.
EDIT 2. Solved how to break in the release program and updated the disassembly so now there seems to be some difference. I got these results by running the release version, stopping the program in the same function with a ReadKey, attaching the debugger, making the program continue execution, breaking on the next row, going into disassembly window (ctrl+alt+d)
EDIT 3. Change the code to an updated example base on all the suggestions.
//slow
78:
79: vs = (2 * mL * uL + us * (ms - mL)) / (ms + mL);
00C10530 call CA9AD013
00C10535 fdiv st,st(3)
00C10537 faddp st(2),st
80:
81: //double vL = (2 * ms * us - uL * (ms - mL)) / (ms + mL); //fast
82: double vL = uL + ms * (us - vs) / mL; //slow
00C10539 fldz
00C1053B fcomip st,st(1)
00C1053D jp 00C10549
00C1053F jae 00C10549
00C10541 add ebx,1
00C10544 adc edi,0
00C10547 fchs
00C10549 fld st(1)
73:
74: while (!(uL < 0 && us <= 0 && uL <= us))
00C1054B fldz
00C1054D fcomip st,st(3)
00C1054F fstp st(2)
00C10551 jp 00C10508
00C10553 jbe 00C10508
00C10555 fldz
00C10557 fcomip st,st(1)
00C10559 jp 00C10508
00C1055B jb 00C10508
00C1055D fxch st(1)
00C1055F fcomi st,st(1)
00C10561 jnp 00C10567
00C10563 fxch st(1)
00C10565 jmp 00C10508
00C10567 jbe 00C1056D
00C10569 fxch st(1)
00C1056B jmp 00C10508
00C1056D fstp st(1)
00C1056F fstp st(0)
00C10571 fstp st(0)
92: }
93:
94: s.Stop();
00C10573 mov ecx,esi
00C10575 call 71880260
95:
96: Console.WriteLine($"i: {i}, T: {s.ElapsedMilliseconds / 1000f}, PI: {collisions}");
00C1057A mov ecx,725B0994h
00C1057F call 00B930C8
00C10584 mov edx,eax
00C10586 mov eax,dword ptr [ebp-14h]
00C10589 mov dword ptr [edx+4],eax
00C1058C mov dword ptr [ebp-34h],edx
00C1058F mov ecx,725F3778h
00C10594 call 00B930C8
00C10599 mov dword ptr [ebp-38h],eax
00C1059C mov ecx,725F2C10h
00C105A1 call 00B930C8
00C105A6 mov dword ptr [ebp-3Ch],eax
00C105A9 mov ecx,esi
00C105AB call 71835820
00C105B0 push edx
00C105B1 push eax
00C105B2 push 0
00C105B4 push 2710h
00C105B9 call 736071A0
00C105BE mov dword ptr [ebp-48h],eax
00C105C1 mov dword ptr [ebp-44h],edx
00C105C4 fild qword ptr [ebp-48h]
00C105C7 fstp dword ptr [ebp-40h]
00C105CA fld dword ptr [ebp-40h]
00C105CD fdiv dword ptr ds:[0C10678h]
00C105D3 mov eax,dword ptr [ebp-38h]
00C105D6 fstp dword ptr [eax+4]
00C105D9 mov edx,dword ptr [ebp-38h]
00C105DC mov eax,dword ptr [ebp-3Ch]
00C105DF mov dword ptr [eax+4],ebx
00C105E2 mov dword ptr [eax+8],edi
00C105E5 mov esi,dword ptr [ebp-3Ch]
00C105E8 lea edi,[ebp-30h]
00C105EB xorps xmm0,xmm0
00C105EE movq mmword ptr [edi],xmm0
00C105F2 movq mmword ptr [edi+8],xmm0
00C105F7 push edx
00C105F8 push esi
00C105F9 lea ecx,[ebp-30h]
00C105FC mov edx,dword ptr [ebp-34h]
00C105FF call 724A2ED4
00C10604 lea eax,[ebp-30h]
00C10607 push dword ptr [eax+0Ch]
00C1060A push dword ptr [eax+8]
00C1060D push dword ptr [eax+4]
00C10610 push dword ptr [eax]
00C10612 mov edx,dword ptr ds:[3832310h]
00C10618 xor ecx,ecx
00C1061A call 72497A00
00C1061F mov ecx,eax
00C10621 call 72571934
61: for (int i = 4; i < 9; i++)
00C10626 inc dword ptr [ebp-14h]
00C10629 cmp dword ptr [ebp-14h],9
00C1062D jl 00C10496
97: }
98:
99: Console.WriteLine(loops);
00C10633 mov ecx,dword ptr [ebp-10h]
00C10636 call 72C583FC
100: Console.Write("Waiting...");
00C1063B mov ecx,dword ptr ds:[3832314h]
00C10641 call 724C67F0
00C10646 lea ecx,[ebp-20h]
00C10649 xor edx,edx
00C1064B call 72C57984
00C10650 lea esp,[ebp-0Ch]
00C10653 pop ebx
00C10654 pop esi
00C10655 pop edi
00C10656 pop ebp
00C10657 ret
//fast
80:
81: double vL = (2 * ms * us - uL * (ms - mL)) / (ms + mL); //fast
02FD0550 or al,83h
80:
81: double vL = (2 * ms * us - uL * (ms - mL)) / (ms + mL); //fast
02FD0552 ret
02FD0553 add dword ptr [ebx-3626FF29h],eax
02FD0559 fchs
02FD055B fxch st(1)
02FD055D fld st(0)
73:
74: while (!(uL < 0 && us <= 0 && uL <= us))
02FD055F fldz
02FD0561 fcomip st,st(2)
02FD0563 fstp st(1)
02FD0565 jnp 02FD056B
02FD0567 fxch st(1)
02FD0569 jmp 02FD050B
02FD056B ja 02FD0571
02FD056D fxch st(1)
02FD056F jmp 02FD050B
02FD0571 fldz
02FD0573 fcomip st,st(2)
02FD0575 jnp 02FD057B
02FD0577 fxch st(1)
02FD0579 jmp 02FD050B
02FD057B jae 02FD0581
02FD057D fxch st(1)
02FD057F jmp 02FD050B
02FD0581 fcomi st,st(1)
02FD0583 jnp 02FD0589
02FD0585 fxch st(1)
02FD0587 jmp 02FD050B
02FD0589 jbe 02FD0592
02FD058B fxch st(1)
02FD058D jmp 02FD050B
02FD0592 fstp st(1)
02FD0594 fstp st(0)
92: }
93:
94: s.Stop();
02FD0596 mov ecx,esi
02FD0598 call 71880260
95:
96: Console.WriteLine($"i: {i}, T: {s.ElapsedMilliseconds / 1000f}, PI: {collisions}");
02FD059D mov ecx,725B0994h
02FD05A2 call 013830C8
02FD05A7 mov edx,eax
02FD05A9 mov eax,dword ptr [ebp-14h]
02FD05AC mov dword ptr [edx+4],eax
02FD05AF mov dword ptr [ebp-3Ch],edx
02FD05B2 mov ecx,725F3778h
02FD05B7 call 013830C8
02FD05BC mov dword ptr [ebp-40h],eax
02FD05BF mov ecx,725F2C10h
02FD05C4 call 013830C8
02FD05C9 mov dword ptr [ebp-44h],eax
02FD05CC mov ecx,esi
02FD05CE call 71835820
02FD05D3 push edx
02FD05D4 push eax
02FD05D5 push 0
02FD05D7 push 2710h
02FD05DC call 736071A0
02FD05E1 mov dword ptr [ebp-50h],eax
02FD05E4 mov dword ptr [ebp-4Ch],edx
02FD05E7 fild qword ptr [ebp-50h]
02FD05EA fstp dword ptr [ebp-48h]
02FD05ED fld dword ptr [ebp-48h]
02FD05F0 fdiv dword ptr ds:[2FD06A8h]
02FD05F6 mov eax,dword ptr [ebp-40h]
02FD05F9 fstp dword ptr [eax+4]
02FD05FC mov edx,dword ptr [ebp-40h]
02FD05FF mov eax,dword ptr [ebp-44h]
02FD0602 mov dword ptr [eax+4],ebx
02FD0605 mov dword ptr [eax+8],edi
02FD0608 mov esi,dword ptr [ebp-44h]
02FD060B lea edi,[ebp-38h]
02FD060E xorps xmm0,xmm0
02FD0611 movq mmword ptr [edi],xmm0
02FD0615 movq mmword ptr [edi+8],xmm0
02FD061A push edx
02FD061B push esi
02FD061C lea ecx,[ebp-38h]
02FD061F mov edx,dword ptr [ebp-3Ch]
02FD0622 call 724A2ED4
02FD0627 lea eax,[ebp-38h]
02FD062A push dword ptr [eax+0Ch]
02FD062D push dword ptr [eax+8]
02FD0630 push dword ptr [eax+4]
02FD0633 push dword ptr [eax]
02FD0635 mov edx,dword ptr ds:[4142310h]
02FD063B xor ecx,ecx
02FD063D call 72497A00
02FD0642 mov ecx,eax
02FD0644 call 72571934
61: for (int i = 4; i < 9; i++)
02FD0649 inc dword ptr [ebp-14h]
02FD064C cmp dword ptr [ebp-14h],9
02FD0650 jl 02FD0496
97: }
98:
99: Console.WriteLine(loops);
02FD0656 mov ecx,dword ptr [ebp-10h]
02FD0659 call 72C583FC
100: Console.Write("Waiting...");
02FD065E mov ecx,dword ptr ds:[4142314h]
02FD0664 call 724C67F0
02FD0669 lea ecx,[ebp-28h]
02FD066C xor edx,edx
02FD066E call 72C57984
02FD0673 lea esp,[ebp-0Ch]
02FD0676 pop ebx
02FD0677 pop esi
02FD0678 pop edi
02FD0679 pop ebp
02FD067A ret
727
It is a well-known fact that statically typed programming languages are faster than dynamic ones. C is a statically typed programming language, which gives it an edge over other dynamic languages. Also, unlike Java and Python, which are interpreter-based, C is a compiler-based program.
There are 5 different types of errors in C programming language: Syntax error, Runtime error, Logical error, Semantic error, and Linker error. Syntax errors, linker errors, and semantic errors can be identified by the compiler during compilation.
This is why Fortran is often faster than C. This is why numerical libraries are still written in Fortran. However, it comes at the cost of pointer arithmetic.
I think the reason is CPU instruction pipelining. your slow equation depends on vs, that means vs must be calculated first, then vl is calculated.
but in your fast equation, more instructions can be pipelined as vs and vl can be calculated at same time because they don't depend on each other.
Please don't confuse this with multi threading. Instruction pipelining is some thing implemented at very low hardware level and tries to exploit as many CPU modules as possible at the same time to achieve maximum instruction throughput.
146
You calculations are not equal
double vL = (2 * ms * us - uL * (ms - mL)) / (ms + mL); //fast
double vL = uL + ms * (us - vs) / mL; //slow
Example: I miss vs in the fast version
I expect your while loop doing more iterations because of this?
30
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
