Faster image rotation
in [General Programming]
|
From: nmm1 on 14 Apr 2010 14:25 In article <4bc601f5$0$22917$e4fe514c(a)news.xs4all.nl>, Casper H.S. Dik <Casper.Dik(a)Sun.COM> wrote: >EricP <ThatWouldBeTelling(a)thevillage.com> writes: > >>A[x] and C[y] are referenced only once so there is no reason >>for the compiler to enregister their values, and all other >>variables are locals or pass-by-value, and therefore >>no reason for aliasing to occur. > >A proper compiler will generate optimal code for: > > for (i = 0; i < len; i++) > C[i] = A[i]; > >or similar code and will generate about the same code for: > > pC = C; pA = A; > while (*pC < C[len]) > *pC++ = *pA++; Including when A, C and len are arguments? Oh, come now! Few start with a test for whether A and C overlap, which is what is needed. >If you can generate faster code by unrolling loops in C then you should get >a better compiler. You should know better than to post that nonsense. There is a LOT of C code where the programmer knows that two arrays can't overlap, but the compiler can't tell. C99 restrict brings programs that use it religiously and correctly up to about the optimisability of Fortran 77, but that's all. And, without it, the compiler has one hand tied behind its back. Regards, Nick Maclaren.
From: EricP on 14 Apr 2010 14:38 Casper H.S. Dik wrote: > EricP <ThatWouldBeTelling(a)thevillage.com> writes: > >> A[x] and C[y] are referenced only once so there is no reason >> for the compiler to enregister their values, and all other >> variables are locals or pass-by-value, and therefore >> no reason for aliasing to occur. > > > A proper compiler will generate optimal code for: > > > for (i = 0; i < len; i++) > C[i] = A[i]; > > or similar code and will generate about the same code for: > > pC = C; pA = A; > while (*pC < C[len]) > *pC++ = *pA++; > > > If you can generate faster code by unrolling loops in C then you should get > a better compiler. > > Casper Ok, but that isn't what he said or what I was commenting on. The MS compiler does a surprisingly good job on the original cache-hostile code: void Rotate90ToRight (int height, int width, const char *srcBuf, char *dstBuf) { int i, j; for (i = 0; i < height; i++) for (j = 0; j < width; j++) memcpy (dstBuf+(height*j+height-1-i)*3, srcBuf+(width*i+j)*3, 3); } tv410 = -4 ; size = 4 tv434 = 8 ; size = 4 _height$ = 8 ; size = 4 _width$ = 12 ; size = 4 _srcBuf$ = 16 ; size = 4 _dstBuf$ = 20 ; size = 4 _Rotate90ToRight(a)16 PROC ; COMDAT ; Line 3 push ecx ; Line 7 mov eax, DWORD PTR _height$[esp] test eax, eax jle SHORT $LN4(a)Rotate90To mov edx, DWORD PTR _dstBuf$[esp] push ebx push ebp mov ebp, DWORD PTR _srcBuf$[esp+8] push esi mov esi, DWORD PTR _width$[esp+12] push edi lea ecx, DWORD PTR [esi+esi*2] lea edi, DWORD PTR [eax+eax*2] mov DWORD PTR tv410[esp+20], ecx lea edx, DWORD PTR [edi+edx-3] mov DWORD PTR tv434[esp+16], eax npad 5 $LL13(a)Rotate90To: ; Line 8 test esi, esi jle SHORT $LN5(a)Rotate90To mov eax, ebp mov ecx, edx npad 8 $LL3(a)Rotate90To: ; Line 9 mov bx, WORD PTR [eax] mov WORD PTR [ecx], bx mov bl, BYTE PTR [eax+2] mov BYTE PTR [ecx+2], bl add eax, 3 add ecx, edi sub esi, 1 jne SHORT $LL3(a)Rotate90To ; Line 8 mov esi, DWORD PTR _width$[esp+16] $LN5(a)Rotate90To: ; Line 7 add ebp, DWORD PTR tv410[esp+20] sub edx, 3 sub DWORD PTR tv434[esp+16], 1 jne SHORT $LL13(a)Rotate90To pop edi pop esi pop ebp pop ebx $LN4(a)Rotate90To: ; Line 10 pop ecx ret 16 ; 00000010H Eric
From: Terje Mathisen "terje.mathisen at on 14 Apr 2010 15:07 EricP wrote: > Brett Davis wrote: >> Only one in a hundred programers know an optimizaton like that, for >> half of comp.arch to be that good says good things about comp.arch. > > Ok, well, I'm going to take the risk of seeming a total doofuss > on a global scale, but I don't see what you are getting at. > > A[x] and C[y] are referenced only once so there is no reason > for the compiler to enregister their values, and all other > variables are locals or pass-by-value, and therefore > no reason for aliasing to occur. > > The SH-4 has byte memory access instructions, so this is just the > difference between LD ST LD ST LD ST and LD LD LD ST ST ST. > The latter requires 2 extra temp regs, which on x86 causes > a var spill into the stack, but probably is ok on sh-4. > > So I don't see the 2x speedup here. The key is that without alias knowledge, it is perfectly possible for the two arrays to intersect, in which case it is illegal for the compiler to unroll the loads and stores. However, the huge advantage here is to load 12 bytes = 4 pixels into 3 registers, then do the same for the 3 following lines so that you have loaded a full 4x4 pixel block with 12 load instructions instead of 36. Next you do shifts & shuffles to rotate the 4x4 block, still ending up with 12 registers, before storing them back with 12 writes. This saves 2/3 of all the load/store operations. Terje -- - <Terje.Mathisen at tmsw.no> "almost all programming can be viewed as an exercise in caching"
From: robin on 14 Apr 2010 21:33 "Noob" <root(a)127.0.0.1> wrote in message news:hphm36$puk$1(a)speranza.aioe.org... | I need to rotate a picture clockwise 90 degrees. | | Conceptually, my picture is represented by a matrix | (W columns, H rows) of pixels, with each pixel | represented by 3 octets. | | pixel original_picture[W][H]; | pixel rotated_picture[H][W]; | | At the implementation level, I'm dealing with 1D integer arrays. | | int src[W*H*3]; | int dest[W*H*3]; | | Conceptually, the rotation operation comes down to | | rotated_picture[j][H-1-i] = original_picture[i][j] | | My actual code is | | for (i = 0; i < H; ++i) | for (j = 0; j < W; ++j) | memcpy(dest+(H*j+H-1-i)*3, src+(W*i+j)*3, 3); This is not going to be fast because:- 1. you are calling a subroutine 1,913,616 times to move 9 or 48 bits each time. 2. You are multiplying by 3 twice for each move. 3. You are using integer arrays. 1. Best to use ordinary assignment. 2. Eliminate *3 by changing to adds. 3. Use byte arrays (but I'm not clear about what you say. You say that you have octets. Now 3 octets will be 9 bits, not 3 integers equal to 48 bits.) This is how it would look in PL/I:- declare (src(m,n), dest(n,m)) char (3); do i = 1 to m; dest(*, m-i+1) = src(i,*); end; If the color information really is octets, then the declaration is changed to bit (9) aligned.
From: robin on 14 Apr 2010 21:34
"Noob" <root(a)127.0.0.1> wrote in message news:hphm36$puk$1(a)speranza.aioe.org... | I need to rotate a picture clockwise 90 degrees. | | Conceptually, my picture is represented by a matrix | (W columns, H rows) of pixels, with each pixel | represented by 3 octets. | | pixel original_picture[W][H]; | pixel rotated_picture[H][W]; | | At the implementation level, I'm dealing with 1D integer arrays. | | | Consider as an example, | W = 1644 | H = 1164 | size = 5.74 MB Seems to be an arithmetic error here. I get 15 Mb for 8-bit pixels, and 45Mb for 3 x 8-bit RGB pixels. |