Printable View
Hi,
How can i convert an Integer buffer of size 176x144 in to unsigned char of size 176x144
I set all the data in the integer buffer comes in the Range [0,255]
Is there any faster method for this ?
When using for() loop there is critical performence issue.
Any library function available for this ?
Rgds
Dave
I can't see anyway that a loop won't be involved somewhere.
Do you want the result in the same buffer or copied to a different one?
If it's time critical, then you can't use a for loop. For loops take too much memory and processing power.
pseudocode
In this pseudocode you are doing four items at a time. This will be many many times faster than doing it in C. It might be even faster to loop only 1584 times and do 8 at a time using 2 registers.Code:allocate your new buffer
mov ecx, 6336 (176 x 144 / 4) //you'll see why divide by four below
mov the pointer to your int array in a register
mov the pointer to your char array in a register
label:
mov the first byte of the int array in a lolo register
mov the first byte of the next int in the hilo register
mov the first byte of the next next int int to the lohi register
mov the first byte of the next next next int to the hihi register
write the entire register to the char array
increment the int array pointer by 16
increment the char array pointer by 4
LOOP label
This is for all you you guys who occasionally tell me that an optimizing compiler will always beat an assembly programmer. For small pieces of code a good assembly engineer will always beat the compiler. :P Knowledge of how processor pipelines and caching works is the key.
This sounds like a challenge, and I accept! :)Quote:
Originally Posted by ninja9578
Let’s take some measurable buffer size of 1,000,000 integers and transfer them into unsigned char array.
I suggest this benchmark (timing is Windows-specific, you can substitute with your OS’s favorite).
And here is what I have in stdafx.h:Code:#include "stdafx.h"
double PCFreq = 0.0;
__int64 CounterStart = 0;
void StartCounter()
{
LARGE_INTEGER li;
if(!QueryPerformanceFrequency(&li))
std::cout << "QueryPerformanceFrequency failed!\n";
PCFreq = double(li.QuadPart)/1000.0;
QueryPerformanceCounter(&li);
CounterStart = li.QuadPart;
}
double GetCounter()
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
return double(li.QuadPart-CounterStart)/PCFreq;
}
const int TABLE_SIZE = 1000000;
volatile int src[TABLE_SIZE];
volatile unsigned char dst[TABLE_SIZE];
void Simple()
{
for(int i = 0; i < TABLE_SIZE; i++)
dst[i] = src[i];
}
void YourFunction()
{
}
int main()
{
std::cout << "Simple loop" << std::endl;
StartCounter();
Simple();
std::cout << GetCounter() << std::endl << std::endl;
std::cout << "Your function here" << std::endl;
StartCounter();
YourFunction();
std::cout << GetCounter() << std::endl << std::endl;
return 0;
}
Just add your code to YourFunction() and run, then post your result here.Code:#pragma once
#ifndef _WIN32_WINNT // Allow use of features specific to Windows XP or later.
#define _WIN32_WINNT 0x0501 // Change this to the appropriate value to target other versions of Windows.
#endif
#include <windows.h>
#include <iostream>
Please leave Simple() function in so that we can eliminate differences in hardware.
Everybody is welcome to participate. Since Dave stated that this issue is performance-critical, I think that doing it in this thread is appropriate.
Vlad
Consider though...
Time slices here are also critical in determining which function is faster. I've written a function in C++ for YourFunction() defined as follows.
Also, the frequency returned from QueryPerformanceFrequency shouldn't be divided by 1000.0, that frequency IS the amount ticks in a second. Dividing it by 1000.0 results in how many "performance ticks" are in a millisecond. Unless you're wanting that? Which is what I assume.
And I get different results, sometimes YourFunction() is faster, sometimes Simple() is faster. It happens when I reverse the order of the calls. Which would tell me something.Code:void YourFunction()
{
const int nCount = TABLE_SIZE >> 2;
int * pSource = (int *)&src[0];
int * pDest = (int *)&dst[0];
for (int i = 0; i < nCount; ++i)
{
int nTemp = pSource[3];
nTemp <<= 8;
nTemp |= pSource[2];
nTemp <<= 8;
nTemp |= pSource[1];
nTemp <<= 8;
nTemp |= pSource[0];
*pDest = nTemp;
pSource += 4;
++pDest;
}
}
I'd recommend dropping the volatile qualifiers from the data. It won't do anything except kill possible optimizations.
I was only trying to prevent "optimizing out"...Quote:
Originally Posted by Lindley
But it looks like you are correct, it works fine (loops 1,000,000 times) without it.
Hey, if the compiler can optimize out the loop and still get the data where it needs to be, then mission accomplished. Optimizing out is really only a problem in truly trivial speed tests which probably won't mean much anyway.
Oh fun :)
I will write my function tonight or tomorrow.
I too have noticed this variation. Looks like it has something to do with the memory being “touched”.Quote:
Originally Posted by CppCoder2010
I’ve fixed it by calling Init() first thing from the main() function:
I can then call both functions repeatedly in different order but still get consistent results.Code:void Init()
{
for(int i = 0; i < TABLE_SIZE; i++)
{
src[i] = i & 0xFF;
dst[i] = 0;
}
}
My first attempt at “4 elements in 1 iteration” looks almost like yours:
But it only gets minimal benefit over the Simple() function – about 0.5% <edited> I meant - 5% </edited>Code:void FourInOne()
{
int* p = (int*)dst;
for(int i = 0, j = 0; i < TABLE_SIZE; i += 4)
{
*p++ = src[i] | src[i+1] << 8 | src[i+2] << 16 | src[i+3] << 24;
}
}
I am working on my “optimized” implementation, but interested to see the ASM results as well.
If we're assuming that the input integers are already in the proper range [0,255], then I doubt it'll be easy to get much faster than this....
Code:unsigned char *srcptr = src;
unsigned char *dstptr = reinterpret_cast<unsigned char*>(dst);// assumes little endian; +3 if BE.
for (int i = 0; i < TABLE_SIZE; i++, ++dstptr, srcptr += 4)
{
*dstptr = *srcptr;
}
Well, this all is pretty sad, actually :(
Below are asm listings for four functions:
1. Simple – assigning one byte at a time, in a loop.
2. Lindley’s code (see above).
3. My 4-in-1 code.
4. My super-secret SSE implementation:
- looping over 16 elements at a time;
- load two groups of 4 ints into two XMM registers;
- pack into one XXM register (16-bit values);
- repeat for the third and fourth group of 4 ints;
- pack two XXM registers with 16-bit values into one with 8-bit values.
Code:Simple();
00401436 xor eax,eax
00401438 jmp main+3B0h (401440h)
0040143A lea ebx,[ebx]
00401440 mov dl,byte ptr src (6362480h)[eax*4]
00401447 mov byte ptr dst (404380h)[eax],dl
0040144D add eax,1
00401450 cmp eax,5F5E100h
00401455 jl main+3B0h (401440h)
Code:Lindley();
00401555 mov ecx,offset src (6362480h)
0040155A mov eax,offset dst (404380h)
0040155F mov esi,5F5E100h
00401564 mov dl,byte ptr [ecx]
00401566 mov byte ptr [eax],dl
00401568 add eax,1
0040156B add ecx,4
0040156E sub esi,1
00401571 jne 00401564
Code:void FourInOne()
{
int* p = (int*)dst;
for(int i = 0, j = 0; i < TABLE_SIZE; i += 4)
00401050 xor eax,eax
{
*p++ = src[i] | src[i+1] << 8 | src[i+2] << 16 | src[i+3] << 24;
00401052 mov ecx,dword ptr src+0Ch (636248Ch)[eax*4]
00401059 shl ecx,8
0040105C or ecx,dword ptr src+8 (6362488h)[eax*4]
00401063 add eax,4
00401066 shl ecx,8
00401069 or ecx,dword ptr [eax*4+6362474h]
00401070 shl ecx,8
00401073 or ecx,dword ptr [eax*4+6362470h]
0040107A cmp eax,5F5E100h
0040107F mov dword ptr ___@@_PchSym_@00@UxlwvUgvhgDCglIUgvhgDCglIUivovzhvUhgwzucOlyq@+4 (40437Ch)[eax],ecx
00401085 jl FourInOne+2 (401052h)
}
}
00401087 ret
And here are the <sad> results:Code:void SSE()
{
for(int i = 0, j = 0; i < TABLE_SIZE; i += 16)
00401000 xor ecx,ecx
00401002 mov eax,offset src+20h (63624A0h)
00401007 jmp SSE+10h (401010h)
00401009 lea esp,[esp]
{
pack(&src[i], &dst[i]);
00401010 movdqu xmm1,xmmword ptr [eax-10h]
00401015 movdqu xmm0,xmmword ptr [eax-20h]
0040101A movdqu xmm2,xmmword ptr [eax+10h]
0040101F packssdw xmm0,xmm1
00401023 movdqu xmm1,xmmword ptr [eax]
00401027 packssdw xmm1,xmm2
0040102B packuswb xmm0,xmm1
0040102F movdqa xmmword ptr dst (404380h)[ecx],xmm0
00401037 add eax,40h
0040103A add ecx,10h
0040103D cmp eax,offset ___onexitbegin (1E0DA8A0h)
00401042 jl SSE+10h (401010h)
}
}
00401044 ret
Your mileage may vary, but the ratio should be the same.Code:Simple loop 88.9159
Lindley 91.1238
4-in-1 loop 85.364
Vlad's SSE 81.8267
I *REALLY* had bigger hopes for SSE… I guess if there was an instruction to pack 32-bit values directly into 8-bit (bypassing 16-bit), we would get a little better results. Or did I miss such an instruction? Any SSE experts here?
<edited>
@ninja9578 - Looking at generated asm, I doubt that you will be able to shave anything off. But – good luck!
I would guess that no mater how you try to do it, you are going to be limited by memory performance. Also, if the memory isn't aligned properly, SSE is going to run dog slow.Quote:
Originally Posted by VladimirF
You might be right. Reading 400,000,000 bytes and writing 100,000,000 bytes must take some time.Quote:
Originally Posted by Chris_F
And I think my arrays are aligned OK; the addresses end with 80h – what else could you wish for?
Does anyone see the bus error? I hate writing 32-bit assembly on a 64-bit machine:
It runs fine for small arrays, but once I try doing one over 1000, it starts throwing bus errors.Code:inline void Assembly(){
__asm__ __volatile__(
" movl $1000000, %%ecx ;\n" //put the size of the table in here, don't reference it
" myloop: ;\n" //beginning of my loop
" movb 12(%0), %%ah ;\n" //char 4
" movb 8(%0), %%al ;\n" //char 3
" shl $16, %%eax ;\n" //can't access high bits directly, so shift these there for now
" movb 4(%0), %%ah ;\n" //char 2
" movb (%0), %%al ;\n" //char 1
" movl %%eax, (%1) ;\n" //push it out to the destination
" add $4, %1 ;\n" //move the dst ptr by 4 because we did 4 ata time
" add $16, %0 ;\n" //move the src ptr by 16
" loop myloop ;\n" //loop until ecx is zero
: //No output
: "r" (src), //Let CGG decide what registers to assign these to
"r" (dst) //Let GCC decide what registers to assign these to
: "eax", "ecx" //these two get explicitly clobbred
);
}
Oh god, I hate GCCs representation of inline asm, and AT&T syntax in general. I'm not even sure what that does. :(Quote:
Originally Posted by ninja9578
I kind of do too, it would be much nicer if they used intels, but oh well. A few years ago I was going PPC assembly using AT&T's syntax. That was a nightmare. It's not as bad as it looks, looks like the forum software did some weird things with my tabs.
It thought it worked for me, but I have little experience with this matter, but I updated your code a tad bit.Quote:
Originally Posted by ninja9578
and converted to msvcCode:const int TABLE_SIZE_DIV_4 = TABLE_SIZE / 4;
inline void Assembly()
{
__asm__ __volatile__
(
" movl %2, %%ecx \n" //put the size of the table in here, don't reference it
" myloop: \n" //beginning of my loop
" movb 12(%0), %%ah \n" //char 4
" movb 8(%0), %%al \n" //char 3
" shl $16, %%eax \n" //can't access high bits directly, so shift these there for now
" movb 4(%0), %%ah \n" //char 2
" movb 0(%0), %%al \n" //char 1
" movl %%eax, (%1) \n" //push it out to the destination
" add $4, %1 \n" //move the dst ptr by 4 because we did 4 ata time
" add $16, %0 \n" //move the src ptr by 16
" loop myloop "
: //No output
: "r" (src), //Let CGG decide what registers to assign these to
"r" (dst), //Let GCC decide what registers to assign these to
"r" (TABLE_SIZE_DIV_4) //Let GCC decide what registers to assign these to
: "eax", "ecx" //these two get explicitly clobbred
);
}
I make no promises this is 100% right. You need to test these for yourself.Code:const int TABLE_SIZE_DIV_4 = TABLE_SIZE / 4;
inline void Assembly()
{
__asm
{
push edx
push ebx
push ecx
mov edx, offset src
mov ebx, offset dst
mov ecx, TABLE_SIZE_DIV_4
myloop:
mov ah, [edx] + 12
mov al, [edx] + 8
shl eax, 16
mov ah, [edx] + 4
mov al, [edx] + 0
mov [ebx], eax
add ebx, 4
add edx, 16
loop myloop
pop edx
pop ebx
pop ecx
}
}
dunno how the performance compares, but I believe it to work.
Code:inline void int_to_char(int *pInts, char *pChars, int arrSize)
{
_asm {
mov esi, pInts
mov edi, pChars
mov ebx, arrSize
xor ecx, ecx
myloop:
mov eax, [esi]
mov byte ptr [edi], al
add esi, 4
inc edi
inc ecx
cmp ecx, ebx
jne myloop
}
}
The division by four, that's what what causing my bus error. Bloody hell, I can't believe that I missed that.
Well, I finished my code:
And sorry guys betting on the optimizer ;) :Code:#include <iostream>
#include <ctime>
const int TABLE_SIZE = 1000000;
const unsigned int LOOPS = 0xFF;
volatile int src[TABLE_SIZE];
volatile unsigned char dst[TABLE_SIZE];
void Simple(){
for(int i = 0; i < TABLE_SIZE; i++)
dst[i] = src[i];
}
inline void Assembly(){
__asm__ __volatile__(
" movl $250000, %%ecx ;\n" //put the size of the table in here, don't reference it
" myloop: ;\n" //beginning of my loop
" movb 12(%0), %%ah ;\n" //char 4
" movb 8(%0), %%al ;\n" //char 3
" shl $16, %%eax ;\n" //can't access high bits directly, so shift these there for now
" movb 4(%0), %%ah ;\n" //char 2
" movb (%0), %%al ;\n" //char 1
" movl %%eax, (%1) ;\n" //push it out to the destination
" add $4, %1 ;\n" //move the dst ptr by 4 because we did 4 ata time
" add $16, %0 ;\n" //move the src ptr by 16
" loop myloop ;\n" //loop until ecx is zero
: //No output
: "r" (src), //Let CGG decide what registers to assign these to
"r" (dst) //Let GCC decide what registers to assign these to
: "eax", "ecx"
);
}
int main (int argc, char * const argv[]) {
clock_t start = clock();
for (unsigned int i = 0; i < LOOPS; ++i)
Simple();
std::cout << clock() - start << std::endl;
start = clock();
for (unsigned int i = 0; i < LOOPS; ++i)
Assembly();
std::cout << clock() - start << std::endl;
return 0;
}
Yes, used maximum optimizations, not the default release build on XCode, and I ran it in the console, not the dev environment. Looks like I beat the compiler. :D I know some of you guys wrote some more advanced routines, but you all said that they run either on par or slightly faster than the simple one, no one posts that it ran 3x faster, so I didn't bother benchmarking them.Code:Ninjas-MacBook-Pro:Release ninja9578$ ./AssemblyChallenge
1059456
366081
@Chris_F: Your code looks good. But I'm concerned about the registers that you use. I've never done inline with VC++, is the assembler smart enough to realize that you clobbered those registers? Because you didn't push their state. Also it won't run as fast as mine for two reasons:
1) You are only doing one integer at a time, where as I'm doing 4. Registers are 32 bit, so use the whole thing, registers are almost a million times faster than RAM.
2) You and the compiler both increment a register, do a compare, then a jump. The processor has a built in function to do all of that in a single tick: loop.
Another thing, is that my code above uses volatile to keep the assembly as it is. If I didn't have that the optimizer could come in and change the assembly, perhaps making it even faster. So it's important when writing assembly to benchmark it with and without the volatile keyword. Sometimes the compiler can make it faster, sometimes it makes it slower, sometimes it does nothing.
What happens when you swap the calls to simple and assembly? Do you notice the assembly getting slower and the simple getting faster?
Uh oh. ***? I hate when weird things like that happen :( Someone want to run the thing on Windows and use that magical process query function?
Its because of the cache. the first function is paying to load the cache, the second is using the data already loaded. Makes your asm look much faster than the C, but much of that cost is cache loading.
Hmmm... Do you have 400MB cache on your processor? :confused:Quote:
Originally Posted by Russco
Itanium 3???Quote:
Originally Posted by VladimirF
Is it this one? Tukwila (processor)Quote:
Originally Posted by Chris_F
Than it tops at “puny” 24MiB, not anywhere near 400MB.
1 mill ints = 4 mill bytes = 4Mb (well a touch less).
My cpu has 4mb of l2 cache. Isn't l2 used for data?? I was under the impression l1 was for code, l2/3 were data caches.
Why would you need 420Mb to store 1 mill ints?
L1 is Harvard model, which means data and code are separate. L2 is not, it's both. L3 is just a slower and larger L2.Quote:
Originally Posted by Russco
Sorry, this thread became too long. I thought I've mentioned that I bumped the array size to 100,000,000 to reduce fluctuation in results (at the time of post #13). Looks like I didn’t say it here.Quote:
Originally Posted by Russco
Anyway, even with 100,000,000 ints the first pass through it takes almost 3 times longer. I don’t know why; I think I read something about “hot” vs. “cold” memory. Are there electrical engineers here who can confirm / deny that?
Regardless, in the current code I run through both arrays before each measurement, so that difference is eliminated: each function runs on a “hot” memory.
OK, here are new results.
I have used Joeman’s adoptation of ninja9578’s asm. I don’t speak GCC’s asm, but the code looks very similar (to a naked eye).
Anyway, here is machine code, see if there is anything you don’t like about it:
And results:Code:Asm();
004013F1 push edx
004013F2 push ebx
004013F3 push ecx
004013F4 mov edx,offset src (6362480h)
004013F9 mov ebx,offset dst (404380h)
004013FE mov ecx,dword ptr ds:[403158h]
00401404 mov ah,byte ptr [edx+0Ch]
00401407 mov al,byte ptr [edx+8]
0040140A shl eax,10h
0040140D mov ah,byte ptr [edx+4]
00401410 mov al,byte ptr [edx]
00401412 mov dword ptr [ebx],eax
00401414 add ebx,4
00401417 add edx,10h
0040141A loop main+374h (401404h)
0040141C pop edx
0040141D pop ebx
0040141E pop ecx
For lucky owners of Visual Studio 2005 (or above) I am attaching zipped solution so that you can verify my findings.Code:Init array
291.013
Simple loop
88.0397
4-in-1 loop
85.2146
ninja9578's Asm
105.585
Chris F's Asm
90.5299
Lindley
90.5767
Vlad's SSE
81.3531
My conclusion: it is VERY HARD (if not impossible) to beat optimizing compiler with hand-coded asm. I bet it (at least the good one) knows everything about cache, pipeline, prefetch, etc.
So the bottom line (as I see it) is: in a fight for performance choose the best algorithm and implement it in as simple as possible way, so the compiler doesn’t get confused and is able to optimize it nicely.
Visual Studio 2008 express EDIT: it wasn't 2010..
I ran the test at least 4 times to make sure the numbers didn't fluctuate too much.Code:Init array
598.937
Simple loop
250.653
4-in-1 loop
128.359
ninja9578's Asm
116.295
Chirs F's Asm
94.1516
Lindley
311.069
Vlad's SSE
140.421
Seems like some assembly versions won pretty good.
Just to be clear, I ran it in release mode without starting the debugger. I did not make any changes to the build configurations.
I even moved the function calls in different orders to make sure the order didn't effect overall timings
Overall I don't recommend placing assembly in c++ just for that fact it makes it specific to a certain type of processor, compiler and etc.
if speed is a must and you know what platform and compiler you are using your code for, I suppose this wouldn't be bad as long as you make sure it is faster
I screwed up and said the last result where 2010. I have now corrected my previous post and now for the Visual Studio 2010 express
The numbers did fluctuate a good bit though :S so this is the averaged run time :(Code:Init array
352.502
Simple loop
93.4141
4-in-1 loop
83.0259
ninja9578's Asm
104.253
Chirs F's Asm
97.9349
Lindley
96.6014
Vlad's SSE
84.4739
Seems like the simple loop is the best choice in this case
That defiantly seems as if it's getting close to the memory bandwidth limit. I have yet to write a inline asm function that out performs the compiler at the same task.
I once thought that I could write a SSE memcpy function that would be lightning fast... but its results were identical to the std library which I'm pretty sure didn't compile to SSE. ;)
I'm no expert on cache lines and such, but I've found that the way in which you access memory can make a world of difference.
You had me going mad for almost half an hour! :)Quote:
Originally Posted by Joeman
I am even installing Express to verify your results.
Could it be that you screwed up more than once and ran Debug build (or simply not optimized) in your first test? Because your numbers are inline with my Debug.
Anyway, I too screwed up (a little).
I can shave another 5% off my SSE implementation by replacing four calls to _mm_loadu_si128 (unaligned) with calls to _mm_load_si128 (aligned). Should have listen more carefully to Chris F in post # 14. For some reason, I thought that having memory aligned was enough :(
Also, as a benchmark, I call mamcpy() between two 400,000,000 MB buffers, and in my test it takes 42ms. THIS must be limited by memory speed.
Actually, if you trace into memcpy (and I think std library uses it), you'll see that it tests for alignment and presence of SSE2, and in such case does use SSE.Quote:
Originally Posted by Chris_F
As soon has I realized I messed up, I corrected asap :DQuote:
Originally Posted by VladimirF
Well I ran it in release mode without debugger, BUT some how my configurations weren't correct. I think they weren't transferred over from your 2005 solution :blush:. now that I checked and fixed them, here are the resultsQuote:
Originally Posted by VladimirF
Visual Studio 2008 express with proper release configuration
EDIT: I hope this is right now :)Code:Init array
383.338
Simple loop
85.3905
4-in-1 loop
82.2526
ninja9578's Asm
105.795
Chirs F's Asm
97.2565
Lindley
92.2891
Vlad's SSE
80.3013
I think it will run faster if you hard coded the size of the table in. I think it's only fair, seeing that the compiler does that :P
Looks like the compiler beat me here though :-\ Perhaps we should come up with something more complicated for it. We did a big contest in college where we each had to write a piece of software that could solve some type of math problem. I wrote C with inline assembly and it beat all the others pretty easily, the only one that came close was fortran believe it or not. One guy used java... not sure what he was thinking.
Perhaps a SURF feature extractor? First thing that comes to mind. I have a GPU implementation (proprietary) which runs at 30+ fps, 1280x1024 images, on an NVIDIA 8-series GPU. Might be interesting to see what highly optimized CPU approaches can do. On the other hand, that might be rather ambitious.
GPU will always beat a CPU implementation, it has special hardware for matrix and vector math. I'll bet in software, that would run about about 1 frame every couple of seconds :P
I have to say I am a bit disappointed with this thread. No interest in over two weeks! Anyone saw Dave1024? Hope he is OK. ;)
And I would *REALLY* like to see GPU implementation!