MxN DCTFilter using MMX asm optimization (developmnent stage)

[squid_80]

jmp [reg] means the target address is in [reg], jg [reg] means the target address is the current address plus the displacement in [reg]. In other words jmp uses absolute addressing and jg uses relative.

[IanB]

For the conditional jumps there is only the relative8 and relative32 forms of the instruction.

Jmp has relative8, relative32, reg/mem32, far and far indirect forms of the instruction.

Use jng label01 ;; opposite test
jmp [ecx]
label01:

[redfordxx]

I have now something similar
jg label01
startloop
;code
js startloop
label01:
jmp ecx
labelswitch:
;case1
;case2
...
I only thought it might be faster with only one jump... from jg directly to case#

[IanB]

Yes, lots of things would be faster if there were single instructions to implement them :D :D :D :D :D

[Fizick]

and the best way to make a jump is do not jump :D

[redfordxx]

This thing slows my code down:add ebx, dst_pit //increase write endFunny, that in similar situation somewhere else in the procedure works fine. Probably is not cached. Can I tell the processor in advance to cache this variable for a moment?

This is some part of code, in the bottom is the problem line...it is copying the bytes from workarea;-)
mov edi, SX //inputpitch (sizex)
mov eax, OutputAddress8 //read
mov ebx, DstPoint //DstPoint...write
mov ecx, OutputLastPieceJump//precalculated jump address
mov esi, negY //reset counter y (-sizey)

LoopOutputY:
add eax, edi //increase read end
mov edx, 8
sub edx, edi //reset counter x
jg OutputLess8
LoopOutputXAlignedTop:
movq mm0, [eax+edx]
movq [ebx+edx], mm0
add edx, 8 //increase x counter
jle LoopOutputXAlignedTop
OutputLess8:
jmp ecx
OutputLastPiece:
mov dl, BYTE PTR [eax+1]
mov BYTE PTR [ebx+1], dl

mov dh, BYTE PTR [eax+2]
mov BYTE PTR [ebx+2], dh

mov dl, BYTE PTR [eax+3]
mov BYTE PTR [ebx+3], dl

mov dh, BYTE PTR [eax+4]
mov BYTE PTR [ebx+4], dh

mov dl, BYTE PTR [eax+5]
mov BYTE PTR [ebx+5], dl

mov dh, BYTE PTR [eax+6]
mov BYTE PTR [ebx+6], dh

mov dl, BYTE PTR [eax+7]
mov BYTE PTR [ebx+7], dl

add ebx, dst_pit //increase write end********!!!!!!!!!!!!!!!!!!!!!!!!!!!
add esi, 1 //increase y counter
jnz LoopOutputY

[EDIT]I tried to put dst_pit to esi and I used variable for the counter which was esi before...didn't help.
Commenting this line more then doubles the speed of the code... so, something is wrong:-(

[EDIT2]Further info:
When I comment the main processing part of the code, the cycle thru the blocks of each frame with CopyFromSrcToWorkArea and CopyFromWorkAreaToDst routines remain. The latter is shown above and contains the add ebx, dst_pit line, the former is similar and contains add eax, src_pit line. A test clip is processed in 53sec. If I comment one of those lines, the time drops to 24sec, if I comment both of them, time is 17sec.
If I replace either src_pit or dst_pit with an imm value the processing time of the clip is between 53 and 24 depending on the value (the bigger, the slower)
:(what will help it?

[IanB]

Apart from the obvious logic error in your code (The tail end repeat the begining of the line) it is called accessing real memory. Without in +=dst_pit you access the same memory every time, it will be in L1 cache and very fast. Otherwise you are writing to real memory which is slower. I take it that is the point of the exercise, so you are stuck.

Anyway the code looks like a Blit operation. Use the provided env->BitBlt() function, someone already worked very hard to make it as fast as possible.

[redfordxx]

Apart from the obvious logic error in your code (The tail end repeat the begining of the line)I don't see what you mean.

it is called accessing real memory. Without in +=dst_pit you access the same memory every time, it will be in L1 cache and very fast. Otherwise you are writing to real memory which is slower. I take it that is the point of the exercise, so you are stuck.Well I looked in the TBarrys DCTFilter and it has similar principle, except having it unrolled for 8x8 in mmx. It doesnot experience this kind of problem. I wonder why...

Anyway the code looks like a Blit operation. Use the provided env->BitBlt() function, someone already worked very hard to make it as fast as possible.But I have already the main loop completely in asm. Can I call this funciton from asm?

[IanB]

I don't see what you mean.add eax, edi //increase read end
mov edx, 8 <- Starts +8 from base
sub edx, edi
...
movq mm0, [eax+edx]
movq [ebx+edx], mm0
...
mov dl, BYTE PTR [eax+1] <- OutputAddress8+SX+1
mov BYTE PTR [ebx+1], dl:confused:

It is hard to analyze fully when you only give snippets here and there. When dealing with the Cache, scale is very important. i.e. are you moving 1000's, 100000's or 10000000's of bytes?
But I have already the main loop completely in asm. Can I call this function from asm?Yes. As always write some C, look at the asm listing to see how to do it.

[redfordxx]

:confused:

It is hard to analyze fully when you only give snippets here and there. Sure...The eight is okay there it is because <- OutputAddress8+SX+1
<- (OutputAddress-8)+SX+1
<- OutputAddress+SX-7I precalculated lot of things because I was not always sure how bad it would be to have it in the cycle.

When dealing with the Cache, scale is very important. i.e. are you moving 1000's, 100000's or 10000000's of bytes?this procedure moves blocks for DCT... probably will not be often bigger than (SX*Y)=(16*16)


I looked at BitBlt and saw this comment
//move backwards for easier looping and to disable hardware prefetch
what's the point...because I remember the recommendation here sooner in this thread

movntq [ebx+edx], mm0 helped a little...53sec-->48sec

...well the code is not perfectly ready to be shown...need som cleanup, but why not:
void DCTBytes2Bytes(const unsigned char *srcp, int src_pit, unsigned char *dstp, int dst_pit, int rowsize, int FldHeight)
{
int SX=sizex;
int negY=-sizey;
int TrigsAddress=(int)pTrigs;
int AreaToLoopInput=-iWorkInputSize;
int AreaToLoopOutput=-iWorkOutputSize;
int InputAddress16=(int)pWorkInput-16;
int OutputAddress8=(int)pWorkOutput-8;
int InputEndAddress=(int)pWorkInput+iWorkInputSize;
int OutputEndAddress=(int)pWorkOutput+iWorkOutputSize;
int TrigsChunkSize_8=iTrigsChunkSize*8;
int SrcPointY=((int)srcp)+sizex-8;
int DstPointY=((int)dstp)-8;
int SrcPoint=SrcPointY;
int DstPoint=DstPointY;
int SrcPointYBigStep=sizey*src_pit;
int DstPointYBigStep=sizey*dst_pit;
int SrcPointYEnd=SrcPointY+FldHeight*src_pit;
int SrcPointYLineEnd=SrcPointY+rowsize;
int InputLastPieceJump=(((((SX)>>3)+1)<<3)-SX-1)*6;
int OutputLastPieceJump=(((((SX)>>3)+1)<<3)-SX-1)*6;
unsigned __int64 ilScale=iScale;
unsigned __int64 i64SignMask = 0x8000000080000000;
unsigned __int64 i64Full = 0xFFFFFFFFFFFFFFFF;
_asm {
align 16
emms
pushad
//32-bit general registers: EAX is 0, ECX is 1, EDX is 2, EBX is 3, ESP is 4, EBP is 5, ESI is 6, and EDI is 7.
//16-bit general registers: AX is 0, CX is 1, DX is 2, BX is 3, SP is 4, BP is 5, SI is 6, and DI is 7.
//8-bit general registers: AL is 0, CL is 1, DL is 2, BL is 3, AH is 4, CH is 5, DH is 6 and BH is 7
movq mm1, i64SignMask
movq mm0, mm1
psrad mm1, ilScale
pandn mm0,i64Full
pxor mm0,mm1
movq i64SignMask, mm0

mov ecx, OutputLastPieceJump
add ecx, offset OutputLastPiece
mov OutputLastPieceJump,ecx
mov ecx, InputLastPieceJump
add ecx, offset InputLastPiece
mov InputLastPieceJump,ecx

mov edi, SX //inputpitch (sizex)
mov eax, SrcPoint //SrcPoint...read
LabelGlobalYLoop:
LabelGlobalXLoop:
/**/ //prepare data...Source is BYTE array, copy to workarea SHORT
mov ebx, InputAddress16 //write
mov esi, negY //reset counter y (-sizey)
mov ecx, InputLastPieceJump

LoopInputY:
lea ebx, [ebx+2*edi]//increase write end
mov edx, 8
sub edx, edi //reset counter x
jg InputLess8
LoopInputXAlignedTop:
movq mm0, [eax+edx]
movq mm1, mm0
pxor mm2, mm2
punpcklbw mm0, mm2
punpckhbw mm1, mm2
movq [ebx+2*edx], mm0
movq [ebx+2*edx+8], mm1
add edx, 8 //increase x counter
jle LoopInputXAlignedTop
InputLess8:
jmp ecx
InputLastPiece:
mov dl, BYTE PTR [eax+1]
mov BYTE PTR [ebx+2], dl

mov dh, BYTE PTR [eax+2]
mov BYTE PTR [ebx+4], dh

mov dl, BYTE PTR [eax+3]
mov BYTE PTR [ebx+6], dl

mov dh, BYTE PTR [eax+4]
mov BYTE PTR [ebx+8], dh

mov dl, BYTE PTR [eax+5]
mov BYTE PTR [ebx+10], dl

mov dh, BYTE PTR [eax+6]
mov BYTE PTR [ebx+12], dh

mov dl, BYTE PTR [eax+7]
mov BYTE PTR [ebx+14], dl

add eax, src_pit //increase read end
// add eax, 64 //increase read end
add esi, 1 //increase y counter
jnz LoopInputY
/**/
//main process on prepared data @pWorkInput...in one loop 4words (1 read) mul by 8x4 words (8 memory reads) and store in bytes
//to do pairing, mm1+mm2 can be coupled with mm3, or mm3 used for shuffled second part and remove 2x movq where is **1 (dunno what's better gain)
/**/
mov eax, InputEndAddress
mov ebx, TrigsAddress
mov edx, OutputEndAddress
mov edi, AreaToLoopOutput //outer counter

LoopTrigOutput:

add ebx, TrigsChunkSize_8
mov ecx, AreaToLoopInput //inner counter

pxor mm4, mm4 //(sum=0)
pxor mm5, mm5 //(sum=0)
pxor mm6, mm6 //(sum=0)
pxor mm7, mm7 //(sum=0)

movq mm0, [eax+ecx+0] //U pipe

LoopTrigInput:

movq mm1, [ebx+8*ecx+0] //(load 2+2 trig values)
pmaddwd mm1, mm0 //(multiply src*trig for 1+1 sum)
paddd mm4, mm1 //(add to 1+1 sum)

movq mm2, [ebx+8*ecx+8] //(load 2+2 trig values)
pmaddwd mm2, mm0 //(multiply src*trig for 1+1 sum)
paddd mm5, mm2 //(add to 1+1 sum)

movq mm1, [ebx+8*ecx+16] //(load 2+2 trig values)
pmaddwd mm1, mm0 //(multiply src*trig for 1+1 sum)
paddd mm6, mm1 //(add to 1+1 sum)

movq mm2, [ebx+8*ecx+24] //(load 2+2 trig values) **1
pmaddwd mm2, mm0 //(multiply src*trig for 1+1 sum)
paddd mm7, mm2 //(add to 1+1 sum) old block

pshufw mm3,mm0,01001110b

movq mm1, [ebx+8*ecx+32] //(load 2+2 trig values)
pmaddwd mm1, mm3 //(multiply src*trig for 1+1 sum)
paddd mm4, mm1 //(add to 1+1 sum)

movq mm2, [ebx+8*ecx+40] //(load 2+2 trig values)
pmaddwd mm2, mm3 //(multiply src*trig for 1+1 sum)
paddd mm5, mm2 //(add to 1+1 sum)

movq mm1, [ebx+8*ecx+48] //(load 2+2 trig values)
pmaddwd mm1, mm3 //(multiply src*trig for 1+1 sum)
paddd mm6, mm1 //(add to 1+1 sum)

movq mm2, [ebx+8*ecx+56] //(load 2+2 trig values) **1
pmaddwd mm2, mm3 //(multiply src*trig for 1+1 sum) old block
paddd mm7, mm2 //(add to 1+1 sum) old block

movq mm0, [eax+ecx+8] //U pipe

add ecx, 8 //Increase Counter

jnz LoopTrigInput

//here some downscaling mm4 - mm7 and packing to mm4
movq mm1, i64SignMask
movq mm2, ilScale

psrad mm4, mm2
pand mm4, mm1

psrad mm5, mm2
pand mm5, mm1

psrad mm6, mm2
pand mm6, mm1

psrad mm7, mm2
pand mm7, mm1

packssdw mm4, mm5
packssdw mm6, mm7

packuswb mm4, mm6

movq [edx+edi], mm4 //(saving all 4 values)

add edi, 8

jnz LoopTrigOutput
/**/
/**/ //copy data back...From workarea BYTE array, copy to dst BYTE
//mov ebp, dst_pit //dstpitch---crushes
mov edi, SX //inputpitch (sizex)
mov ebx, DstPoint //DstPoint...write
mov eax, OutputAddress8 //read
add ebx, edi //DstPoint+=SX
mov DstPoint, ebx //DstPoint...write
mov ecx, OutputLastPieceJump//precalculated jump address
mov esi, negY //reset counter y (-sizey)
/**/
LoopOutputY:
add eax, edi //increase read end
mov edx, 8
sub edx, edi //reset counter x
jg OutputLess8
LoopOutputXAlignedTop:
movq mm0, [eax+edx]
movntq [ebx+edx], mm0
add edx, 8 //increase x counter
jle LoopOutputXAlignedTop
OutputLess8:
jmp ecx
OutputLastPiece:
mov dl, BYTE PTR [eax+1]
mov BYTE PTR [ebx+1], dl

mov dh, BYTE PTR [eax+2]
mov BYTE PTR [ebx+2], dh

mov dl, BYTE PTR [eax+3]
mov BYTE PTR [ebx+3], dl

mov dh, BYTE PTR [eax+4]
mov BYTE PTR [ebx+4], dh

mov dl, BYTE PTR [eax+5]
mov BYTE PTR [ebx+5], dl

mov dh, BYTE PTR [eax+6]
mov BYTE PTR [ebx+6], dh

mov dl, BYTE PTR [eax+7]
mov BYTE PTR [ebx+7], dl

add ebx, dst_pit //increase write end
// add ebx,400 //increase write end
add esi, 1 //increase y counter
jnz LoopOutputY
/**/
// end loop LabelGlobalXLoop
mov eax, SrcPoint
add eax, edi ;SrcPoint+=SX
cmp eax, SrcPointYLineEnd ;SrcPoint<SrcPointYLineEnd
mov SrcPoint, eax
jl LabelGlobalXLoop
// end loop LabelGlobalYLoop
mov ecx, DstPointY
add ecx, DstPointYBigStep ;DstPointY+=DstPointYBigStep
mov DstPointY, ecx
mov DstPoint, ecx ;DstPoint=DstPointY

mov eax, SrcPointY
mov edx, SrcPointYBigStep
add eax, edx ;SrcPointY+=SrcPointYBigStep
add SrcPointYLineEnd, edx ;SrcPointYLineEnd+=SrcPointYBigStep
cmp eax, SrcPointYEnd ;SrcPointY<SrcPointYEnd
mov SrcPointY, eax
mov SrcPoint, eax ;SrcPoint=SrcPointY
jl LabelGlobalYLoop
popad
}//asm
}

[IanB]

Your original slow down problem is probably L1 cache saturation, you have memory references all over the shop. Each cache line is 64 bytes long and 64 byte aligned.

movq mm0, [eax+edx]
movq mm1, mm0
pxor mm2, mm2
punpcklbw mm0, mm2
Getting the pairing right can help a lot
movq mm0, [eax+edx]
pxor mm2, mm2 <- But it is constant and should be outside loop anyhow
movq mm1, mm0
punpcklbw mm0, mm2
If you have enough registers internally duplicate the loop. i.e. :-
pxor mm4, mm4
label:
movq mm0, [eax+edx]
movq mm2, [eax+edx+8]
movq mm1, mm0
movq mm3, mm2
punpcklbw mm0, mm4
punpckhbw mm1, mm4
punpcklbw mm2, mm4
punpckhbw mm3, mm4
...


Another example :-
movq mm1, [ebx+8*ecx+0] //(load 2+2 trig values)
pmaddwd mm1, mm0 //(multiply src*trig for 1+1 sum)
paddd mm4, mm1 //(add to 1+1 sum)

movq mm2, [ebx+8*ecx+8] //(load 2+2 trig values)
pmaddwd mm2, mm0 //(multiply src*trig for 1+1 sum)
paddd mm5, mm2 //(add to 1+1 sum)
Don't rely on the out of order execution, do it yourself, like this :-
movq mm1, [ebx+8*ecx+0] //(load 2+2 trig values)
movq mm2, [ebx+8*ecx+8] //(load 2+2 trig values)
pmaddwd mm1, mm0 //(multiply src*trig for 1+1 sum)
pmaddwd mm2, mm0 //(multiply src*trig for 1+1 sum)
paddd mm4, mm1 //(add to 1+1 sum)
paddd mm5, mm2 //(add to 1+1 sum)




How do you know [ebx+1] is zero
InputLastPiece:
mov dl, BYTE PTR [eax+1]
mov BYTE PTR [ebx+2], dl
Try this style instead

movzx edx, BYTE PTR [eax+1]
mov WORD PTR [ebx+1], dx


If the inner loop is looped many times dedicating 7 explicit end cases can be beneficial.
OutputLess8:
jmp ecx ;; Loaded from table of 7 routine addresses
align 16
OutputLastPiece7:
...
align 16
OutputLastPiece4:
mov edx, DWORD PTR [eax+4]
mov DWORD PTR [ebx+4], edx
add ebx, dst_pit //increase write end
add esi, 1 //increase y counter
jnz LoopOutputY
jmp NextOutputY
align 16
OutputLastPiece3:
...
align 16
OutputLastPiece1:
mov dl, BYTE PTR [eax+7]
mov BYTE PTR [ebx+7], dl
add ebx, dst_pit //increase write end
add esi, 1 //increase y counter
jnz LoopOutputY
align 16
NextOutputY:
...More latter ;) gotta run now

[redfordxx]

Thanx lotYour original slow down problem is probably L1 cache saturation, you have memory references all over the shop.You mean the variables I prepared in the beginning or that in one cycle I do src->(copy)->input->(process)->output->(copy)->dst
Each cache line is 64 bytes long and 64 byte aligned.Hm, and how can I control it, or how should I behave?
But it is constant and should be outside loop anyhow
OK
If you have enough registers internally duplicate the loop. i.e. :But I don't know whether there will be 16+,32+... values and not 8+,24+,40+... values. Or, more jumps?

Don't rely on the out of order execution, do it yourself, like thisYes, I wanted to ask about this one, because there are two pmaddwd next to each other which require FMUL, so there will be bottleneck anyway?


How do you know [ebx+1] is zeroI know;) --- it is not obvious here, but I prepared it in constructor.(saving here 1 cycle maybe)
InputLastPiece:
mov dl, BYTE PTR [eax+1]
mov BYTE PTR [ebx+2], dl
mov dh, BYTE PTR [eax+2]
mov BYTE PTR [ebx+4], dh
can be helpful to alter dh,dl?


If the inner loop is looped many times dedicating 7 explicit end cases can be beneficial.Yes, I will try...

But what to do with my cache problem?

[redfordxx]

LoopTrigInput:

movq mm1, [ebx+8*ecx+0] //(load 2+2 trig values)
movq mm2, [ebx+8*ecx+8] //(load 2+2 trig values)
pmaddwd mm1, mm0 //(multiply src*trig for 1+1 sum)
pshufw mm3,mm0,01001110b
pmaddwd mm2, mm0 //(multiply src*trig for 1+1 sum)
paddd mm4, mm1 //(add to 1+1 sum)
paddd mm5, mm2 //(add to 1+1 sum)

movq mm1, [ebx+8*ecx+16] //(load 2+2 trig values)
movq mm2, [ebx+8*ecx+24] //(load 2+2 trig values) **1
pmaddwd mm1, mm0 //(multiply src*trig for 1+1 sum)
pmaddwd mm2, mm0 //(multiply src*trig for 1+1 sum)
paddd mm6, mm1 //(add to 1+1 sum)
paddd mm7, mm2 //(add to 1+1 sum) old block

movq mm1, [ebx+8*ecx+32] //(load 2+2 trig values)
movq mm2, [ebx+8*ecx+40] //(load 2+2 trig values)
pmaddwd mm1, mm3 //(multiply src*trig for 1+1 sum)
pmaddwd mm2, mm3 //(multiply src*trig for 1+1 sum)
paddd mm4, mm1 //(add to 1+1 sum)
paddd mm5, mm2 //(add to 1+1 sum)

movq mm1, [ebx+8*ecx+48] //(load 2+2 trig values)
movq mm2, [ebx+8*ecx+56] //(load 2+2 trig values) **1
pmaddwd mm1, mm3 //(multiply src*trig for 1+1 sum)
pmaddwd mm2, mm3 //(multiply src*trig for 1+1 sum) old block
add ecx, 8 //Increase Counter
paddd mm6, mm1 //(add to 1+1 sum)
paddd mm7, mm2 //(add to 1+1 sum) old block

movq mm0, [eax+ecx] //U pipe


jnz LoopTrigInput
Trying reorganize pairs, tried many combinations and cannot measure any improvement (in CPU time in Task Manager)

[IanB]

Your original slow down problem is probably L1 cache saturation, you have memory references all over the shop.You mean the variables I prepared in the beginning or that in one cycle I do src->(copy)->input->(process)->output->(copy)->dst
It's all together. Going from just enough to 1 line short can be catastrophic. And yes you have over 160 bytes of local variables, this will be 3 cache lines. 16K of L1 cache is 256 lines and they are some-way associative, i.e. not all lines do all addresses.

Each cache line is 64 bytes long and 64 byte aligned.
Hm, and how can I control it, or how should I behave?
Just be aware there is a limit and know how it is allocated. Always be conservative. For stack based variables there is nothing really you can do, the assumption is your variables start and finish partway thru a cache line.

For special buffers when squeezing every last ounce of performance, you can align the buffer mod 64, this avoids the 2 wasted part cache lines at each end.

If you have enough registers internally duplicate the loop. i.e. :
But I don't know whether there will be 16+,32+... values and not 8+,24+,40+... values. Or, more jumps?
Well it has to be a case by case judgement call. Is the stuffing around in the end code worth doing 16 bytes per cycle instead of 8.

Don't rely on the out of order execution, do it yourself, like this
Yes, I wanted to ask about this one, because there are two pmaddwd next to each other which require FMUL, so there will be bottleneck anyway?
I try to avoid single unit stalls if I can, but I don't bust a hump if I can't arrange the code to avoid it. Out of order execution may handle the problem for you, the idea is to just do the best you readily can.

For some unknown reason PMADDWD's are like public transport, they hunt in packs. :D

InputLastPiece:
mov dl, BYTE PTR [eax+1]
mov BYTE PTR [ebx+2], dl
mov dh, BYTE PTR [eax+2]
mov BYTE PTR [ebx+4], dh
can be helpful to alter dh,dl?
For some processors using ah, bh, ch & dh to memory is slower, the movsx & movzx instructions are preferred for byte from memory operations.

If the inner loop is looped many times dedicating 7 explicit end cases can be beneficial.
Yes, I will try...
Also know your data. If the data is 95% probably going to be in 8 byte chunks then the end case code will only be used 5% of the times, so it may not be worth spending lots of time perfecting it. Most video clips are mod 16 width.

But what to do with my cache problem?
First prove it is a cache exhaustion problem, reduce the size of your data slightly. Is there a knee effect in speed? i.e. cropping off a few lines doubles the speed. This may be some entirely different phenominon here, I just made a guess here!

----------------------------

Also I am not sure you are getting good value pre-unpacking the data from 8bits to 16bit units. Your code is obtuse, but it seems to me that each unpacked element is only used once. If this is the case then unpacking on the fly would be no slower and more cache efficient i.e. you could fit twice as much data into the available cache. E.g. in the Horizontal resizer we pre-unpack the 8bit data to 16bit units. For the Point resizer each unit is only used once so there is only penalty. For the Lanczos4 resizer each unit is used 8 times so there is very much gain. Note the resizer core is general purpose.

Also adding offsets in address calculations is practically free, you could get rid of some of your precalculations by just doing [ebx+2*edx-16] instead of using InputAddress16=(int)pWorkInput-16;

[redfordxx]

First prove it is a cache exhaustion problem, reduce the size of your data slightly. Is there a knee effect in speed? i.e. cropping off a few lines doubles the speed. This may be some entirely different phenominon here, I just made a guess here!
Measurements:Block size: Time:
8x1 21
8x2 94
8x3 94
8x4 94

16x1 13
16x2 58
16x3 58
16x4 58

32x1 11
32x2 23
32x3 23

64x1 11
64x2 24
64x3 23

80x1 12
80x2 22

96x1 12
96x2 12
96x3 13
96x4 13
96x6 15
96x8 14

120x1 13
120x2 16
120x3 16
120x4 18

128x1 22
128x2 24
128x3 23

256x1 24


I commented everything except the last routine which copies data from workarea (X*Y) to dst (pitch*height)
Seems to me that there is problem saving more than one line in dst. This problem vanishes as the line lenght reaches 96. However, probably the caching of the source becomes problem for 128B and more?

[redfordxx]

Just be aware there is a limit and know how it is allocated. Always be conservative. For stack based variables there is nothing really you can do, the assumption is your variables start and finish partway thru a cache line.

For special buffers when squeezing every last ounce of performance, you can align the buffer mod 64, this avoids the 2 wasted part cache lines at each end.How can I control whether my variables are all in one line?

Or maybe it will be possible to prepare (among others) two sets of variables which will be saved with pushad in the beginning (I decide the 64 aligned place in memory with the stack registry) and read it every cycle with popad (once before "main process on prepared data @pWorkInput", once before "copy data back"). Might be faster than 4 mov's from memory to registers?

Can prefetch instruction help somwhere somehow? If it is for both AMD and Intel...

[IanB]

Measurements:This make absolutely no sense, please explain the numbers and what you have tested :confused:

How can I control whether my variables are all in one line?Allocate a struct and manually align it. i.e. Y = (X = malloc(sizeof(Y)+63)) & ~64; Y->a =10;... free(X);

But you are wasting your time, you should not need these local variables in the first place, registers are for storing your working variables. Memory is for your buffers.
Can prefetch instruction help somwhere somehow?Prefetching and movntq writes are for dealing with data set bigger than the L2 cache. Generally they are not compatible with data sets that easily fit in the L2 cache. i.e. small data sets perform worse than without them.

In avisynth dealing with 720x576 YV12 images you are looking at about 600K per frame so 2 input and 1 output buffer fit easily in a 2Mb L2 cache. With HiDef you are looking at about 3Mb per frame. Ideally the flow from 1 filter to the next, keeps all the current data in L2 cache.
If it is for both AMD and Intel...The theory is similar for both breeds, just the actual numbers change.

[redfordxx]

This make absolutely no sense, please explain the numbers and what you have tested
Basically I am testing speed of asm equivalent of this
for(y=0;y<height;y+=blockheight)
for(x=0;x<rowsize;x+=blockwidth)
//here is some processing, which is now omitted, so it does not make big sense
for(j=0;j<blockheight;j++)
for(i=0;i<blockwidth;i++)
dstptr[(y+j)*dstpitch+x+i]=workoutput[j*blockwidth+i];

these numbers 8x1 etc in my previous post are block sizes, i.e. blockwidth*blockheight. So, the results show that if the block is more than one line high, it slows down.
The block will mostly be 8x8 or 16x16...so one line is not really enough:(

[redfordxx]

Now I am fighting with stupid thing like this:

This works:
const unsigned char* sourcep [32];
for (int i=0;i<length;++i)
sourcep[i] = source[i]->GetReadPtr(plane);

but i need aligned variable lenght something like this:
const unsigned char* sourcep = (const unsigned char*) _aligned_malloc(sizeof(unsigned char*)*length, 64);
for (int i=0;i<length;++i)
sourcep[i] = source[i]->GetReadPtr(plane);
but is does not work...i got message on that third line:
error C2440: '=' : cannot convert from 'const BYTE *' to 'const unsigned char'

More or less I know why (sourcep[i] is already the the target of the pointer), but still not sure how to write it correctly.

[squid_80]

Looks like sourcep should be a const unsigned char **.

[IanB]

Okay the equivalent C code helps a lot. Perhaps it should be in your source as comments.

Have you got thismovntq [ebx+edx], mm0in the block you are testing? And you have an AMD beastie. Test with a normal movq.

Do not mix cached and non-temporal memory accesses, specially writes and make absolutly sure that they are 64 bit aligned.

Also as a baseline perhaps you should test the pure C code version.

------------------------

Also a possible hint for your end around code. As long as you have at least 8 bytes total to process just do a single unaligned movq at the end. i.e. offset the movq to match the end of the buffer and process the few overlapping bytes twice.

[redfordxx]

Have you got thismovntq [ebx+edx], mm0in the block you are testing? And you have an AMD beastie. Test with a normal movq.
I had it before... it was little slower.

Also as a baseline perhaps you should test the pure C code version.Had it before and was slower.
:confused:

Also a possible hint for your end around code. As long as you have at least 8 bytes total to process just do a single unaligned movq at the end. i.e. offset the movq to match the end of the buffer and process the few overlapping bytes twice.Will try...but have to be cautios about the end of row;)

[redfordxx]

Looks like sourcep should be a const unsigned char **.Thanks...ehm but now I can't access the members of the array easily like this anymoremov ecx, [sourcep+4*eax]where eax walks thru the array.

[squid_80]

Thanks...ehm but now I can't access the members of the array easily like this anymoremov ecx, [sourcep+4*eax]where eax walks thru the array.

Why not?

[IanB]

I meant that you should repeat the knee test with both movq and C code to get a comparitive baseline for the 50% slowdown. i.e. you are looking for the speed ratio to be constant.

I assume you are still trying to find why you have a performance knee.

--------------------

Oh and also about the end code stuff. For planar frames Avisynth guarantees that pitch is at least mod 8 (mod 16 on >= SSE2 machines). Use the PLANAR_Y_ALIGNED form of the RowSize(). Just remember that bytes beyond rowsize up to pitch contain uninitialized junk, you are free to overwrite it with good stuff or trash as you see fit.

[redfordxx]

Oh and also about the end code stuff. For planar frames Avisynth guarantees that pitch is at least mod 8 (mod 16 on >= SSE2 machines). Use the PLANAR_Y_ALIGNED form of the RowSize(). Just remember that bytes beyond rowsize up to pitch contain uninitialized junk, you are free to overwrite it with good stuff or trash as you see fit.But if block width is let's say 4 and rowsize=pitch, then I will write four bytes over...

[redfordxx]

_declspec(align(64)) const unsigned char* sourcep[64]
__asm{
mov ecx, [sourcep] ;=sourcep[0]
mov ecx, [sourcep+4] ;=sourcep[1]
}
but
const unsigned char** sourcep = (const unsigned char**) _aligned_malloc(sizeof(unsigned char*)*length, 64);
__asm{
mov ecx, [sourcep] ;=sourcep[0]
mov ecx, [sourcep+4] ;=&sourcep+4
}

[squid_80]

I don't see anything wrong with that. In C code *(sourcep+1) is the same as sourcep[1]. In assembly they both translate to [sourcep+4] (assuming pointers are 4 bytes).

[redfordxx]

In the second case I cant access directly sourcep[1].
Probably I have to get the pointer first and then the value...two memory reads instead of one. Is there workaround or not?

[redfordxx]

For special buffers when squeezing every last ounce of performance, you can align the buffer mod 64, this avoids the 2 wasted part cache lines at each end.Maybe I am missing, what exactly you mean by buffer...

[squid_80]

In the second case I cant access directly sourcep[1].
Sure you can... The same as before, sourcep[1] is [sourcep+4] in assembly.

[IanB]

@Squid, The 1st case is reallymov ecx, [ebp+sourcep+0]
mov edx, [ebp+sourcep+4]
the 2nd case ismov esi, [ebp+sourcep]
mov ecx, [esi+0]
mov edx, [esi+4]
--------------------------
But if block width is let's say 4 and rowsize=pitch, then I will write four bytes over...
Yes you would, but you can adjust the way you process it so that only the last loop has to deal with the problem.AWIDTH=rowsize;
if (AWIDTH+8-blockwidth > pitch)
AWIDTH-=8-blockwidth;
for(y=0;y<height;y+=blockheight) {
for(x=0;x<AWIDTH;x+=blockwidth)
for(j=0;j<blockheight;j++)
for(i=0;i<blockwidth;i++) {
FAST CODE (overlaps to mod 8)
}
for(x=AWIDTH;x<rowsize;x+=blockwidth)
for(j=0;j<blockheight;j++)
for(i=0;i<blockwidth;i++) {
END CODE (No overlaps!)
}
}
Maybe I am missing, what exactly you mean by buffer...buffer :- chunk of memory, work space, something you declare or malloc, where you read and/or write data to.

The point was in the very special case where you are trying to squeeze every last ounce of cache there is the option to waste some memory and align your buffer to cache lines. This is not normal practise for general purpose filters because you do not have enough control of the world, i.e. you do not know what size image the user will give you, you do not know what block size the user will choose.

For normal use being 4 aligned for cpu registers, 8 aligned for MMX registers and 16 aligned for SSE2 registers is adequate.

[IanB]

Or even more devious...
for(y=0;y<height-blockheight;y+=blockheight) {
for(x=0;x<rowsize;x+=blockwidth)
for(j=0;j<blockheight;j++)
for(i=0;i<blockwidth;i++) {
FAST CODE (overlaps to mod 8)
}
}
y=height-blockheight;
for(x=0;x<AWIDTH;x+=blockwidth)
for(j=0;j<blockheight;j++)
for(i=0;i<blockwidth;i++) {
FAST CODE (overlaps to mod 8)
}
for(x=AWIDTH;x<rowsize;x+=blockwidth)
for(j=0;j<blockheight;j++)
for(i=0;i<blockwidth;i++) {
END CODE (No overlaps!)
}

[redfordxx]

Would be maybe helpful, to copy first row of blocks from source to multiple workareas (for faster copying) then process all of them and then copy all of them to dst frame?

If that would be more cache-friendly.

If so which way (copying src to workarea):
1) copy block after block (copy all lines of first block, then second...)
2) go thru frame reading one whole line after each other and copy the pixel to different workareas where they belong...

1) seems to me more cachable for the writing part (in the workarea the pixel would be written aftereach other) but reads in src are random
2) seems to me more cachable for the reading part (going thru the src in line pixel after pixel, but writing is random)


By the way, how is it with the back direction reading? You recomended me to avoid it but there was notice in the BitBlt function that the author used it to avoid HW prefetch...:confused:

[IanB]

You are at the point where there is much unknown information to guess. It could work or it could exhaust the cache. You will have to test and time it.

Reading backwards applies to a special set of cases, search the AMD technotes for how and when to use it.

Also with using movntq you say your filter is faster, does your measure include a next filter in the chain. You may make your filter faster but the next filter might be slower because it must re-read that frame data just written back into cache, hence the whole script might run slower. Test carefully!

[redfordxx]

Hi...after years..
I came around and I thougnt I would share what I've done. Just as it is.
So, quick comment. It is based on the TBarrys one. Usage:DctFilter c[fac0]f[fac1]f[fac2]f[fac3]f[fac4]f[fac5]f[fac6]f[fac7]f[fac8]f[fac9]f[fac10]f[fac11]f[fac12]f[fac13]f[fac14]f[fac15]f[mode]s[blockyx]i[blockyy]i[shiftyx]i[shiftyy]i
Mode can be: showF, default, classic, freeDCT
-showF....shows frequency values in spatial domain (maps it on 0-255 range)
-other modes are just the frequency decimation, various kinds (classic is original 8x8 method, freeDCT is [blockyx]x[blockyy] transformation, default chooses automatically...I think
There are 16 factors to be adjusted.

I added dll and sources.
v8 works
v13 seems not to work

Issues and stupid things:
- I didn't rename the filter at that time, so ithas same name as theold one (probably that's why recompiled the old filter to name DCTFiler, so I can have both in AviSynth)
- DCTAddConstand doesnot work and I don't know why
- Newer version doesnot work and I dont know why...

So, maybe someone's interested. ShowF looks interesting...;-)