Assembly optimization?

Just for fun, if anyone wants to help.
So I have this little code:

Code:

Stuff::CArray<char> Array; double max_ = pow(10.0, 8.6); DWORD dwTick1 = GetTickCount(); int max = (int)max_; for (int i = 0; i < max; i++) Array[i] = 12; //12345678; DWORD dwTick2 = GetTickCount(); DWORD dwTick3 = dwTick2 - dwTick1; cout << "Took " << dwTick3 << " ms total.\n";

...And I want to optimize it a little further, but it's kind of out of my hands right now.
It's blazingly fast and according to the profiler, the loop is the culprit.

Code:

Address Line Trace Source Code Bytes Total % Timer samples 0x401de6 cmp edi,[esp+14h] 3B 7C 24 14 0x401dea jnz $+15h (0x401dff) 75 13 5.76 218 0x401dec lea esp,[esp+00h] 8D 64 24 00 0x401df0 lea esi,[esp+14h] 8D 74 24 14 0x401df4 call $-00000c24h (0x1004011d0) E8 D7 F3 FF FF 0x401df9 cmp [esp+14h],edi 39 7C 24 14 0x401dfd jbe $-0dh (0x100401df0) 76 F1 0x401dff mov ecx,[esp+24h] 8B 4C 24 24 0x401e03 mov [ecx+edi],0ch C6 04 39 0C 5.61 212 0x401e07 inc edi 47 11.03 417 0x401e08 cmp edi,ebx 3B FB 0.03 1 0x401e0a jl $-24h (0x100401de6) 7C DA 5.24 198 1 file, 1 function, 1 line, 12 instructions, Summary: 1046 samples, 100.00% of module samples, 27.66% of total samples

If anyone have any pointers on how to optimize the loop in assembly? It's blazingly fast considering what it's actually doing, so I just wanted to see how much more performance can be gained through this code, to decrease the execution time from 1.6s to lower!

What it does is a dynamic array that allocates more memory on-the-fly as you insert elements. Considering it's actually adding 10 ^ 8.6 bytes of memory, I say it's pretty efficient!

Pretty please? ^_^
I'm not an assembly expert.

A few things off the top of my head:
- Set the array size first - assuming MFC, that would be Array.SetSize(max).
- If you can access Array's buffer directly, use memset() on it. memset() should already be somewhat optimized.

gg

It's not an MFC class (otherwise it wouldn't be in the namespace Stuff, would it?). It's my homebrew class and it does not require me to set a size first. It changes the size if the current buffer in not big enough to hold all the data automatically. And besides that, I don't think it will matter if I do or not since it seems the time is spent in the loop and the processor driver and not the class implementation itself.
It's not possible to access the buffer directly. Even doing so, I'd have to do some precautions... Dunno if I actually might do that. But I'll think about it...
I would also add additional functionality such as writing and serializing into it.

5.76 + 5.61 + 11.03 + 0.03 + 5.24 == 27.67% (or 27.66% according to your output).

Looks to me like the other 72.34% of the time is being spent in your CArray[] operator.

gg

Actually not. Here's what the profiler says (again):

Code:

Module Name 64-bit Total % Timer samples Help.exe 24.87 1038 AmdK8.sys 21.45 895 ntkrnlpa.exe 18.72 781 msvcr90.dll 6.76 282 hal.dll 6.37 266 win32k.sys 4.86 203 unknown module pid(2464) 1.82 76 ntdll.dll 1.82 76 SandBox.sys 1.65 69 Unknown Kernel Samples 1.46 61 qt-mt333.dll 1.13 47 11 modules, Total: 3794 samples, 90.92% of total session samples

For Help.exe:

Code:

CS:EIP Symbol + Offset 64-bit Total % Timer samples 0x401d30 wmain 24.87 1038 0x401e07 wmain+215 10.02 418 0x401e0a wmain+218 5.18 216 0x401e03 wmain+211 4.94 206 0x401dea wmain+186 4.65 194 0x401e08 wmain+216 0.05 2 0x401dff wmain+207 0.02 1 0x401de6 wmain+182 0.02 1 1 function, 7 instructions, Total: 1038 samples, 100.00% of samples in the module, 24.87% of total session samples

I don't see what that is supposed to show.

I still don't see how much time is being spent in CArray[]. Your original profile data suggests to me that the CArray[] call wasn't profiled at all - since there's no data in the Total% and TimerSamples columns.

gg

Now there's just the thing - it shows that all the time spent in Help.exe is spent in the for loop.
The rest of the time is spent outside the program in API calls and such, which is not calculated towards Help.exe.
I can post code for the array too, if that's required, but as I mentioned, the only samples are for Help.exe.

Here is for Debug:

Code:

Address Line Trace Source Code Bytes Total % Timer samples 46 CArrayImpl(T&)::operator [] (DWORD dwIndex) 0x412430 47 { 27.14 9134 0x412453 48 if (dwIndex == m_dwSize) 5.80 1953 0x41245d 49 while (m_dwSize <= dwIndex) Realloc(); 0x412471 50 return m_pArray[dwIndex]; 1.11 372 0x41247a 51 } 4.64 1563 1 file, 1 function, 5 lines, 0 instructions, Summary: 3888 samples, 26.51% of module samples, 11.55% of total samples

And

Code:

CS:EIP Symbol + Offset 64-bit Total % Timer samples 0x412430 Stuff::CArray<char>::operator[] 38.70 13022 0x411720 wmain 3.16 1064 0x411271 ILT+620(__RTC_CheckEsp) 0.64 214 0x411131 ILT+300(??A?$CArrayDStuffQAEAADKZ) 0.57 193 0x413990 _RTC_CheckEsp 0.51 173 5 functions, 29 instructions, Total: 14666 samples, 100.00% of samples in the module, 43.58% of total session samples

Code:

0x411720 wmain 3.16 1064

Was your for loop done in wmain() in this case?

gg

Code:

lea esp,[esp+00h]

This is one funny line. It does absolutely nothing. (it says, store in ESP the adress of the element at [esp + 0], basically, store in esp the value of esp).

Anyway, you won't win much by removing only a single instruction heh. But i have to say, reading assembly produced by compiler is rather confusing, i mean it doesn't look really natural.

Writing your loop in assembly would be rather straightforward if the code was written in C, but since it's not, with that [] operator whos translated in a function call, well, i just don't know (i'm really far from being a C++ expert). Could only help you if it was a "c style" array where the for loop could be write as...

Code:

__asm { // Assume that your array is char (1 byte) array push eax push ecx push edi mov ecx, max dec ecx mov al, 12 mov edi, array rep stosb stosb pop edi pop ecx pop eax }

Anyway.

Quote:

Originally Posted by Codeplug

Code:

0x411720 wmain 3.16 1064

Was your for loop done in wmain() in this case?

gg

Yes, the code is the same:

Code:

Address Line Trace Source Code Bytes Total % Timer samples 0x411800 72 for (int i = 0; i < max; i++) 1.14 383 0x41181a 73 Array[i] = 12; //12345678; 2.02 681 1 file, 1 function, 2 lines, 0 instructions, Summary: 1064 samples, 7.25% of module samples, 3.16% of total samples

As for C++... Well, basically ecx contains the address of the class (the this pointer) and arguments are simply pushed on the stack (this one's __cdecl.)

Code:

Address Line Trace Source Code Bytes Total % Timer samples 0x41181a mov eax,[ebp-68h] 8B 45 98 0x41181d push eax 50 0x41181e lea ecx,[ebp-34h] 8D 4D CC 0.54 181 0x411821 call $-000006f0h (0x100411131) E8 0B F9 FF FF 1 file, 1 function, 1 line, 4 instructions, Summary: 181 samples, 1.23% of module samples, 0.54% of total samples

From this sample code we can see that it pushes the argument, the index to the stack and puts the this pointer (the class address) into ecx and calls the operator [].

Code:

CS:EIP Symbol + Offset 64-bit Total % Timer samples 0x412430 Stuff::CArray<char>::operator[] 38.70 13022 0x411720 wmain 3.16 1064

>>>> Was your for loop done in wmain() in this case?
>> Yes, the code is the same

If your for loop was in wmain(), then wouldn't it contributed to the 3.16%?. Still looks like most of your time is spent in CArray[].

Code:

CArrayImpl(T&)::operator [] (DWORD dwIndex) { if (dwIndex == m_dwSize) while (m_dwSize <= dwIndex) Realloc(); return m_pArray[dwIndex]; }

Get rid of the 'if'. A 'compare/jump' is going to be done regardless. Adding the 'if' only introduces the possibility of a bug (by calling with a dwIndex > m_dwSize).

I would optimize this by reducing the number of possible iterations that the while loop has to make. One way to do that is to pass a minimum-size "hint" to Realloc(). Then you operator[] would be reduced to:

Code:

CArrayImpl(T&)::operator [] (DWORD dwIndex) { if (dwIndex >= m_dwSize) Realloc(dwIndex); return m_pArray[dwIndex]; }

Then with that in place. you can simulate the MFC CArray equivalent of SetSize() by calling "Array[max] = 12;" prior to looping through the rest of the elements. Or add an explicit SetSize()-type of member function for pre-allocation.

Another option is to add a "memset" member function to CArray, which could then be optimized accordingly based on the underlying implementation. This member function could even Realloc() as needed.

In the end, I think your point of optimization is going to lie within Realloc().

gg

Sorry for this little off topic, but i wanted to compare between C and Assembly on a simple string operation. What's interesting is that Assembly was roughly 7.5 times faster. Here's the code snippet

Code:

#include <time.h> #include <stdlib.h> #include <stdio.h> #define TAILLE 100000000 #define VALEUR 30 int main() { clock_t debut, fin; char *tab = malloc(TAILLE); int i; if (tab == NULL) exit(1); // Classic debut = clock(); for (i = 0; i < TAILLE; i++) { tab[i] = VALEUR; } fin = clock(); printf(" %u\n", fin - debut); // Assembleur debut = clock(); __asm { push eax push ecx push edi mov ecx, TAILLE - 1 mov al, VALEUR mov edi, tab rep stosb stosb pop edi pop ecx pop eax } fin = clock(); printf(" %u\n", fin - debut); // Quasi classique debut = clock(); i = TAILLE; while (i) { tab[--i] = VALEUR; } fin = clock(); printf(" %u\n", fin - debut); free(tab); return 0; }

Every "loop" does the same thing. Test was done on my old Pentium 3 (which has enough memory for this test, don't worry). Value returned (average): 2200, 280, 2200

I wanted to share that...

Code:

// Classic // Assembleur // Quasi classique

These should be done in 3 separate runs. Otherwise, CPU cache hits/misses could skew your results. Also be sure to turn on all possible compiler optimizations - to be fair :)

gg

Quote:

Originally Posted by Codeplug

>>>> Was your for loop done in wmain() in this case?
>> Yes, the code is the same

If your for loop was in wmain(), then wouldn't it contributed to the 3.16%?. Still looks like most of your time is spent in CArray[].

Code:

CArrayImpl(T&)::operator [] (DWORD dwIndex) { if (dwIndex == m_dwSize) while (m_dwSize <= dwIndex) Realloc(); return m_pArray[dwIndex]; }

Get rid of the 'if'. A 'compare/jump' is going to be done regardless. Adding the 'if' only introduces the possibility of a bug (by calling with a dwIndex > m_dwSize).

I missed that. Initially, I did >= I think. But it hit a speed barrier, so I did only == since it worked just as fine in my code. Didn't consider calling a higher index, though.
Still, I removed the IF and left the while. The Realloc function commits one page (as I like to call it) of memory and not more. Further, it does not hurt performance very much due to the function is not called often. Even removing the if and letting while be, I saw no performance degradation (and no performance gain either). I have the check there to make sure you don't call an index that's higher than the buffer and so if I allocate the buffer and it turns out it's not enough...

Quote:

I would optimize this by reducing the number of possible iterations that the while loop has to make. One way to do that is to pass a minimum-size "hint" to Realloc(). Then you operator[] would be reduced to:

Code:

CArrayImpl(T&)::operator [] (DWORD dwIndex) { if (dwIndex >= m_dwSize) Realloc(dwIndex); return m_pArray[dwIndex]; }

Then with that in place. you can simulate the MFC CArray equivalent of SetSize() by calling "Array[max] = 12;" prior to looping through the rest of the elements. Or add an explicit SetSize()-type of member function for pre-allocation.

I could take that into consideration since the function is fully designed now. But I don't think it will have much of an impact at all. If you call a high index, pages will be allocated (committed) and it won't happen again. Tests show that when using an initial size, I save 500ms. So the Realloc isn't that expensive.

Quote:

Another option is to add a "memset" member function to CArray, which could then be optimized accordingly based on the underlying implementation. This member function could even Realloc() as needed.

In the end, I think your point of optimization is going to lie within Realloc().

gg

Will take into consideration. Will also do a new profile analyze pass.

Quote:

Originally Posted by foxman

Sorry for this little off topic, but i wanted to compare between C and Assembly on a simple string operation. What's interesting is that Assembly was roughly 7.5 times faster. Here's the code snippet

Are you sure you enabled all optimizations for the compiler? It should be pretty much equal in speed for that little sample I would believe.

UPDATE:
OK, so new data:

Code:

Address Line Trace Source Code Bytes Total % Timer samples 49 CArrayImpl(T&)::operator [] (DWORD dwIndex) 0x412430 50 { 27.56 8989 0x412453 51 if (dwIndex >= m_dwSize) 6.45 2105 0x41245d 52 /*while (m_dwSize <= dwIndex) */Realloc(dwIndex - m_dwSize); 0x41246e 53 return m_pArray[dwIndex]; 1.14 373 0x412477 54 } 4.68 1525 1 file, 1 function, 6 lines, 0 instructions, Summary: 12992 samples, 89.16% of module samples, 39.84% of total samples

The evil function call is sucking up the CPU time here and Release only shows the loop as the bottleneck.

Where are the timer samples for the call to Realloc()? Can you run a profile session that shows samples and percentages for:
- the outer for loop
- the call to Array[]
- the call to Realloc()
So we can get a "big picture" of where time is being spent?

[Edit]
In release mode.
[/Edit]

gg

For the outer loop (in debug):

Code:

Address Line Trace Source Code Bytes Total % Timer samples 0x41180c 73 for (int i = 0; i < max; i++) 1.17 380 0x411826 74 Array[i] = 12; //12345678; 1.94 633 0x411826 mov eax,[ebp-68h] 8B 45 98 0.00 1 0x411829 push eax 50 0x41182a lea ecx,[ebp-34h] 8D 4D CC 0.60 195 0x41182d call $-000006fch (0x100411131) E8 FF F8 FF FF 0x411832 mov [eax],0ch C6 00 0C 0.60 195 0x411835 jmp $-20h (0x100411815) EB DE 0.74 242 1 file, 1 function, 2 lines, 6 instructions, Summary: 1013 samples, 6.95% of module samples, 3.11% of total samples

For Array[], you have it, I posted it above.
There are no samples for Realloc (which would make sense, since it's never called due that I set the size before starting the loop).
If I don't set size, it takes about 400ms longer, but no samples for Realloc. I'm not sure if I'm just using the profiler wrong in this case. I use Codeanalyst in case anyone needs to know.

I found out why it wasn't getting symbols for operator [] in Release. Simple. The compiler inlined the code, saving 1000ms. If I don't, here's the samples for Release:

Code:

Address Line Trace Source Code Bytes Total % Timer samples 49 CArrayImpl(T&)::operator [] (DWORD dwIndex) 0x401070 50 { 7.57 399 0x401073 51 if (dwIndex >= m_dwSize) 3.23 170 0x401079 52 Realloc(dwIndex - m_dwSize); 0x401083 53 return m_pArray[dwIndex]; 4.82 254 0x401089 54 } 3.15 166 1 file, 1 function, 6 lines, 0 instructions, Summary: 989 samples, 52.83% of module samples, 18.77% of total samples

>> There are no samples for Realloc...
Well, will Realloc() not being called and Array[] being inlined, there's not much more you can do except add a "memset" style of method that utilizes a highly optimized version of memset() with SIMD instructions.

Keeping your original for loop, you could try manually unrolling the loop.

gg

I'm back with my little off-topic.

The test i did was done using MSVC++ 6.0, with build configuration set to "Release" and optimization set to "maximize speed" (default with release configuration). Couldn't do the test using gcc since i don't know how to write assembly for it. I redid the test in 3 separate runs (4 runs for each version) and got similar results:

Code:

Classic (for loop) : 2213, 2173, 2163, 2233 Assembly : 260, 250, 250, 250 Classic (while loop): 2203, 2133, 2133, 2143

Note that it's possible to tweak the assembly version even more by writing doubleword instead of byte at a time. (but you could also do that in C)

If you want, you could test it on your own comp. Would be curious of the result if someone does so. But i'm not really surprise of the result, since the IA-32 instruction set comes with some really efficient string instruction that i bet compiler make only minor use (because of their really specific nature).

I mean, just take a look at the code generated by the compiler (i added comments):

Code:

193: for (i = 0; i < TAILLE; i++) 0040C6AA C7 45 F0 00 00 00 00 mov dword ptr [ebp-10h],0 // i = 0 0040C6B1 EB 09 jmp main+5Ch (0040c6bc) 0040C6B3 8B 45 F0 mov eax,dword ptr [ebp-10h] // EAX = i 0040C6B6 83 C0 01 add eax,1 // EAX++ 0040C6B9 89 45 F0 mov dword ptr [ebp-10h],eax // i = EAX 0040C6BC 81 7D F0 00 E1 F5 05 cmp dword ptr [ebp-10h],5F5E100h // if (i >= TAILLE) 0040C6C3 7D 0B jge main+70h (0040c6d0) // jump out of the loop 194: { 195: tab[i] = VALEUR; 0040C6C5 8B 4D F4 mov ecx,dword ptr [ebp-0Ch] // ECX = tab 0040C6C8 03 4D F0 add ecx,dword ptr [ebp-10h] // ECX = ECX + i 0040C6CB C6 01 1E mov byte ptr [ecx],1Eh // [ecx] = 12 196: } 0040C6CE EB E3 jmp main+53h (0040c6b3) // jmp at start of the loop

vs

Code:

rep stosb

I think it's pretty clear why it's so fast. ;)

Out of curiosity: Do a run using just memset(). Also, in project settings -> C/C++ -> Code Generation, set the Processor to pentium pro.

gg

Haha. Well, this is a bit ankward. From the start i was in debug mode, i didn't switch configuration correctly. Sorry, my bad. :rolleyes:

Well, in fact, everything is quite similar in release mode, there's no really significative difference between the different version, except for the while version who is considerably slower (close to 2 times slower). Do you know if there's a way to see dissassembly in release mode ? I'm curious to know what the compiler generates.

But in debug mode, memset is as fast as the assembly version. What's also strange, is that both memset and assembly are a bit slower in release mode.

Anyway. I won't investigate any further. :)

Quote:

Originally Posted by Elysia

Just for fun, if anyone wants to help.
So I have this little code:

Code:

Stuff::CArray<char> Array; double max_ = pow(10.0, 8.6); DWORD dwTick1 = GetTickCount(); int max = (int)max_; for (int i = 0; i < max; i++) Array[i] = 12; //12345678; DWORD dwTick2 = GetTickCount(); DWORD dwTick3 = dwTick2 - dwTick1; cout << "Took " << dwTick3 << " ms total.\n";

...And I want to optimize it a little further, but it's kind of out of my hands right now.
It's blazingly fast and according to the profiler, the loop is the culprit.

Just for my own curiosity, what happens to the speed if you replace Stuff::CArray<char> with std::vector<char> and change the Array[i] = 12; to Array.push_back( (char)12 );

Quote:

Originally Posted by foxman

Haha. Well, this is a bit ankward. From the start i was in debug mode, i didn't switch configuration correctly. Sorry, my bad. :rolleyes:

Well, in fact, everything is quite similar in release mode, there's no really significative difference between the different version, except for the while version who is considerably slower (close to 2 times slower). Do you know if there's a way to see dissassembly in release mode ? I'm curious to know what the compiler generates.

But in debug mode, memset is as fast as the assembly version. What's also strange, is that both memset and assembly are a bit slower in release mode.

Anyway. I won't investigate any further. :)

Actually, MSVC6 generates pretty poor code. I could try on 2008 and see what happens.

Quote:

Originally Posted by cpjust

Just for my own curiosity, what happens to the speed if you replace Stuff::CArray<char> with std::vector<char> and change the Array[i] = 12; to Array.push_back( (char)12 );

For vector: best time was 3218 ms.
For non-inline release CArray - 2500 ms.
For inline release CArray - 1600 ms.
If I set size before loop, inline release CArray - 1200 ms.

Quote:

Originally Posted by foxman

Sorry for this little off topic, but i wanted to compare between C and Assembly on a simple string operation. What's interesting is that Assembly was roughly 7.5 times faster. Here's the code snippet

Code:

#include <time.h> #include <stdlib.h> #include <stdio.h> #define TAILLE 100000000 #define VALEUR 30 int main() { clock_t debut, fin; char *tab = malloc(TAILLE); int i; if (tab == NULL) exit(1); // Classic debut = clock(); for (i = 0; i < TAILLE; i++) { tab[i] = VALEUR; } fin = clock(); printf(" %u\n", fin - debut); // Assembleur debut = clock(); __asm { push eax push ecx push edi mov ecx, TAILLE - 1 mov al, VALEUR mov edi, tab rep stosb stosb pop edi pop ecx pop eax } fin = clock(); printf(" %u\n", fin - debut); // Quasi classique debut = clock(); i = TAILLE; while (i) { tab[--i] = VALEUR; } fin = clock(); printf(" %u\n", fin - debut); free(tab); return 0; }

Every "loop" does the same thing. Test was done on my old Pentium 3 (which has enough memory for this test, don't worry). Value returned (average): 2200, 280, 2200

I wanted to share that...

Here are my results of 5 runs on MSVC .Net 2003 with /Og /O2
78 47 78
93 32 78
78 47 78
93 32 93
93 47 78

I enabled every possible optimization I could find and the result was... *drum roll please*

109
94
109

Assembly for classic loop:

Code:

debut = clock(); 00401827 mov esi,dword ptr [__imp__clock (40209Ch)] 0040182D call esi for (i = 0; i < TAILLE; i++) { tab[i] = VALEUR; 0040182F push 5F5E100h 00401834 push 1Eh 00401836 push ebx 00401837 mov edi,eax 00401839 call memset (4018B0h) } fin = clock(); 0040183E call esi

It even optimizes away your loop with memset.

Second loop assembly:

Code:

0040187E call esi 00401880 mov edi,eax i = TAILLE; 00401882 mov eax,5F5E100h while (i) { tab[--i] = VALEUR; 00401887 sub eax,1 0040188A mov byte ptr [eax+ebx],1Eh 0040188E jne $LN14+60h (401887h) } fin = clock(); 00401890 call esi

There's not much of a difference on today's compilers. Sure, there's some, so when really, really time critical, it might help, but otherwise...