performance puzzle

peterchen

Hey! Take stop reading my mind!

Agh! Reality! My Archnemesis![^]
| FoldWithUs! | sighist | WhoIncludes - Analyzing C++ include file hierarchy

Luc Pattyn

I agree. On my machine 10 iterations take 0.5 milliseconds, which DateTime.Now can't catch at all. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

Daniel Grunwald

You need to be careful, the JIT will turn off optimizations when running inside the Visual Studio debugger (even in release builds!). To get the optimized JITted assembly code, you need to run your program from the command line, then attach the debugger to the running process, and click Break.

Simon P Stevens

Well I've written a C# version that runs 15-20% faster that your original on my PC. It doesn't use unsafe either. But I don't think you'll like it.

private static void SafeTest_Improved1(string[] args)
{
int NUM = int.Parse(args[0]);
int end = 8193;
var primes = new byte[8193]{
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

Super Lloyd

To test the speed I was running each program from the command line! ^_^

A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station.... _________________________________________________________ My programs never have bugs, they just develop random features.

Daniel Grunwald

Yes but where did you get the disassembled C# code from? It looks like all locals are on the stack (never in registers), which the JIT normally does only when a debugger is attached.

Super Lloyd

Yes it! :( Is it that bad? I'm not that conversant in ASM, so I couldn't tell... But in a way that's good news, they have room for improvement! Now, what are they waiting for!?! :rolleyes:

A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station.... _________________________________________________________ My programs never have bugs, they just develop random features.

Super Lloyd

Ha, the disassembly I got it from VS! Not sure how to get it otherwise... Because on the disk it's not compiled, it's just MSIL, and even if I NGen I dunno where they store the compiled version! (BTW I just tried NGen and it was not faster!?!)

A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station.... _________________________________________________________ My programs never have bugs, they just develop random features.

Aamir Butt

Mechanical wrote:

I'll bet you are one of those that believe Java is the future of 3D.

Java... Hahahaha... well I can't stop laughing. I haven't worked in Java since school. And I bet you are the one who writes all his linked list, hashtable, search and sorting algorithm from scratch because he believes that he can do better than those retards.

Mechanical wrote:

How about ALL cases ?

Well, give me a case you are talking about but before that, give me the name of a NON-RETARD language as per your understanding.

Super Lloyd

well, I run 10000 thousand iteration to compare them, so DateTime seems precise enough! :) I did use StopWatch in the past but, I dunno, was never converted to it, I guess I never needed to make measurement precise enough!

A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station.... _________________________________________________________ My programs never have bugs, they just develop random features.

Daniel Grunwald

Super Lloyd wrote:

Ha, the disassembly I got it from VS! Not sure how to get it otherwise...

To get the optimized JITted assembly code, you need to run your program from the command line, then attach the debugger to the running process, and click Break. Because your Main function was already running before you attached the debugger, it will still have the real native code. .NET doesn't re-jit anything when attaching a debugger.

Aamir Butt

Dan Neely wrote:

The comments on that post were staggeringly stupid.

Yes, unfortunately. There are other performance comparisons as well but there is no point in posting the links here. As i said earlier, following the sheep..... :)

Super Lloyd

:laugh: you could have moved the "for(...) prims[i] = 1" statement out of the loop for the same (and more condensed) result! But this is an unfair comparison with C++, you removed a whole set a "required" operation for the algorithm! Although... I wonder if an array copy from an initialized array would speed up things....

A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station.... _________________________________________________________ My programs never have bugs, they just develop random features.

Mechanical

Derek Viljoen wrote:

In other words, you have yet to provide any empirical evidence for your worth to this site. No be a good boy and go away, please.

You have much to learn, little one.

NULL

Super Lloyd

okay, I ran it from the command line and attached a debugger, here is the release version, run and optimized at its best I guess. what do you think? (well, if you can read that! :~ ) (no inline C# comment this time!) ===============================================

00000000 push ebp
00000001 mov ebp,esp
00000003 push edi
00000004 push esi
00000005 push ebx
00000006 sub esp,48h
00000009 mov esi,ecx
0000000b lea edi,[ebp-54h]
0000000e mov ecx,12h
00000013 xor eax,eax
00000015 rep stos dword ptr es:[edi]
00000017 mov ecx,esi
00000019 mov dword ptr [ebp-10h],esp
0000001c mov dword ptr [ebp-54h],496CC9B0h
00000023 cmp dword ptr [ecx+4],1
00000027 je 00000043
00000029 call 620CD310
0000002e mov ecx,eax
00000030 mov edx,dword ptr ds:[03522030h]
00000036 mov eax,dword ptr [ecx]
00000038 call dword ptr [eax+000000D8h]
0000003e jmp 0000017B
00000043 cmp dword ptr [ecx+4],0
00000047 jbe 00000191
0000004d mov esi,dword ptr [ecx+0Ch]
00000050 call 620C0CC0
00000055 push eax
00000056 mov ecx,esi
00000058 mov edx,7
0000005d call 620CF2F0
00000062 mov ebx,eax
00000064 lea edi,[ebp-30h]
00000067 xor eax,eax
00000069 stos dword ptr es:[edi]
0000006a stos dword ptr es:[edi]
0000006b lea ecx,[ebp-30h]
0000006e call 62069650
00000073 call 62069730
00000078 mov ecx,eax
0000007a lea eax,[ebp-30h]
0000007d push dword ptr [eax+4]
00000080 push dword ptr [eax]
00000082 lea edx,[ebp-18h]
00000085 mov eax,dword ptr [ecx]
00000087 call dword ptr [eax+48h]
0000008a mov ecx,801h
0000008f push 0
00000091 dec ecx
00000092 jne 0000008F
00000094 mov ecx,esp
00000096 mov dword ptr [ebp-10h],esp
00000099 mov esi,ecx
0000009b jmp 000000DA
0000009d xor edx,edx
0000009f mov byte ptr [esi+edx],1
000000a3 inc edx
000000a4 cmp edx,2001h
000000aa jl 0000009F
000000ac mov ecx,2
000000b1 cmp byte ptr [esi+ecx],0
000000b5 je 000000D1
000000b7 mov edx,ecx
000000b9 add edx,edx
0000

Super Lloyd

Thanks, done! Posted there: http://www.codeproject.com/Lounge.aspx?msg=3657593#xx3657593xx[^] However, I'm not conversant in ASM, so I can't tell much from it...

A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station.... _________________________________________________________ My programs never have bugs, they just develop random features.

Lost User

Is it a Debug build?

Daniel Grunwald

That looks quite similar to the C++ assembler code! Here, compare the main loop bodies. I've added annotations to the C# assembler code. C#:

000000b1 cmp byte ptr [esi+ecx],0 // primes[i] != 0
000000b5 je 000000D1
// if (primes[i] != 0) {
000000b7 mov edx,ecx
000000b9 add edx,edx // int k = 2 * i
000000bb cmp edx,2001h // k < end
000000c1 jge 000000D1
// for {
000000c3 mov byte ptr [esi+edx],0 // primes[k] = 0;
000000c7 add edx,ecx // k += i
000000c9 cmp edx,2001h // k < end
000000cf jl 000000C3
// }
// }
000000d1 inc ecx // ++i
000000d2 cmp ecx,2001h // i < end
000000d8 jl 000000B1

C++:

                    if (primes\[i\] != 0)

002610A0 cmp byte ptr [esp+ecx+10h],bl
002610A4 je wmain+0BDh (2610BDh)
{
int p = i; // using this extra variable speeds up C++!!! (and slow down C# if I do it)
for (int k = i + p; k < end; k += p)
002610A6 lea eax,[ecx+ecx]
002610A9 cmp eax,2001h
002610AE jge wmain+0BDh (2610BDh)
primes[k] = 0;
002610B0 mov byte ptr [esp+eax+10h],bl
002610B4 add eax,ecx
002610B6 cmp eax,2001h
002610BB jl wmain+0B0h (2610B0h)

	for (int i = begin; i < end; ++i)

002610BD inc ecx
002610BE cmp ecx,2001h
002610C4 jl wmain+0A0h (2610A0h)

The C++ compiler was a bit more clever in combining mov+add into lea, but other than that, the instructions are identical. C++ also lifted the 0 literal into a register (bl), but I'm not sure if that gives you a performance advantage over immediates. (this optimization does give you a code size advantage though, at least for data types larger than 1 byte) So I'm not sure if this small optimization (lea) is causing the difference in performance, or if the reason for the difference is outside this loop. Because there's a major difference in the 'reset to 1' loop: C# resets each byte individually, whereas C++ calls the much faster memset. You could try rewriting that C# loop to:

            int\* primesInt = (int\*)primes;
	for (int i = 0; i < ((end-1)/sizeof(int))+1; i++)
		primesInt\[i\] = 0x01010101;

Maybe even try if long is faster on your machine. In fact, I have the suspicion that the C++ memset might use SSE registers to set 16 ele

Dan Neely

Super Lloyd wrote:

Well it's only tip #237, so I guess it's not the 1st thing I should rush to do! Smile

Yeah, but not for that reason. John's higher tips aren't in sequential order. A lot of the high priority ones are probably within this set: 9, 22, 32, 38, 44, 45, 50, 306, 308, 357, 454, 556, 762. :cool:

3x12=36 2x12=24 1x12=12 0x12=18

Richard A Dalton

Mechanical wrote:

You have much to learn, little one.

Ain't it grand....that whole internet anonymity thang?!? Helping people work out their inner troll issues. Go read 'Richter' and stop bothering the grown ups. -Richard

Hit any user to continue.