performance puzzle

[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.

[Super Lloyd]

Thanks Daniel, this is all very enligthening comments! :-D Further I tried your suggestion and changed the setting to 1 as follow (remember prime is a stackalloc in C# so it's already a pointer)

var lprim = (long*)primes;
for (int i = 0; i < (end / 8); i++)
lprim[i] = 0x0101010101010101L;

and the speed is now very close to C++ (5% slower) overall it's quite good for C# after reflection hey! :)

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]

It's all clear now! :-D

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]

Hey, it's not so bad! Look at the latest comment from Daniel from the assembly code which has been found by attaching to a running process: http://www.codeproject.com/Lounge.aspx?msg=3657636#xx3657636xx[^] Further I managed to get quite close to C++ (5% slower) by changing the loop which sets the bytes to 1, by writing something close to what the C++ compiler did, thanks to Daniel's comment!

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]

It's not too bad, but it has an int3 in it

[Super Lloyd]

int3!?! I don't speak assembly :sigh: , please explain! ;)

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]

int3 is "debug break", on windows, if there is no debugger attached it causes the program to be halted and you will get a dialog asking you whether you want to debug the program.