MxN DCTFilter using MMX asm optimization (developmnent stage)

[IanB]

You probably meantmovq mm0, [eax]
...
movq mm1, mm0On a P4pxor mm0, mm0
movq mm1, [eax]
...
por mm0, mm1is faster, on most other machines the difference is indeterminate (other factors prevail)

You really need to test and measure a stream of code for speed, out of order execution make absolutes difficult to predict. Also don't worry to much about lock step pairing your instruction, instructions all have different latency and execution times, as long as there are at least 2 loosly independant flows through most of your code the chip will keep itself busy.

A convention to map the flows and stall points in your source is to indent one flow by a spacemovd mm0, [eax]
movd mm1, [eax+4]
punpuklbw mm0, mm7
punpuklbw mm1, mm7
pmaddwd mm0, mm6
pmaddwd mm1, mm6
paddd mm0, mm1 ; stall
add eax, 8
packssdw mm0, mm7
movq [eax-8], mm0 ; stall
jmp loop

[redfordxx]

I better say the idea behind:
I process the bytes from video multiple times so the question is
1- copy to work area unpacked to words and then process (processing 8 bytes require 2 mm reads --- first example)
2- copy to work area as it is and unpack during processing
(processing 8 bytes require 1 mm read but needs unpacking --- second example)
More and more I think number one is better...

About pairing:
Will be 2 3-cycles-long-instructions, paire with 3 2-cycles-long-instructions and all together (if lucky) processed in 6 cycles (if all rules fulfilled)?

And, looking at the Appendix F tables, little confused about some things...but what is important to me about pipes:
If I want to combine two instructions they have to have together two pipes (FSTORE, FMUL or FADD). So at least one instruction has to have more than one pipe possible, eg. FMUL/FADD, or every instruction has to have different pipe, eg. FSTORE for one and FMUL for the other.
If that is correct, two PADDD instructions can be processed simultaneously...which is not what I thought....so....am I correct?

[redfordxx]

Is there any worse performance when reading 4 bytes aligned memory instead of 8 bytes aligned?
It would be cycle containing some 25-30 pairs of mmx ops with about 20 reads of memory, where 2 of them would be dword aligned. If it will decrease performance, I can rearange data before the cycle…but I don’t know if it is worth it.

Other thing: which more registers than eax-edx can I use? (To control cycles mainly)

Huh, few days ago I said I don’t want anything with asm, and now…;-)

[IanB]

Whether to unpack into a temp buffer or not depends on the algorithm. The punpuk instruction can tend to stall waiting for the shifter. You probably need to code up both approaches and time them.

As a rule of thumb if you need the data unpacked from the temp buffer 3 times or more then unpacking to the temp buffer will mostly be faster. Unfortuantely the converse is unpredictable, even for a single 1 off access it might be faster or it might not. You really need to measure the speed.

About pairing :- If you are talking about a P3 then you can approximately make that statement. With a P3 the amount of out of order possible is limited enough for us to follow. With any of the later chips the level of out of order processing is astounding, so worrying about what can truely actually be paired become somewhat mote, mearly making the effort to provide 2 streams of code interlaced as best we can is usually enough.

Remember the pipes can be the combined length of both pipes apart in actual execution.

And yes a PADD can happen is either pipe simultaneously.

:Snap:Edit:

If the data is aligned a movd and movq are about the same speed, so the movq moves twice as much data for the same clocks. But if you end up adding extra instructions to unpack the data you may loose that advantage. Count the cycles for both code alternatives. And don't forget to include any overhead in getting data into the right shape for each approach.

And you can use all the registers in your code, just put them back at the end.

[redfordxx]

Whether to unpack into a temp buffertemp buffer…you mean memory?
If the data is aligned a movd and movq are about the same speed, so the movq moves twice as much data for the same clocks. But if you end up adding extra instructions to unpack the data you may loose that advantage. Count the cycles for both code alternatives. And don't forget to include any overhead in getting data into the right shape for each approach.
To explain better the movq issue (there won't be any movd):
I have data in memory:
aaaa|bbbb||cccc|dddd||eeee|ffff||
First I wanted (process each dword hi and low:
movq mm0, [eax]
…process
pswapd mm0
...process
add eax, 8
;loop cycle here
but pswapd is
a) AMD specific…and maybe other users will use my filter
b) it seems to me that MS VC6 does not accept 3DNow!
So other options are:
1. replace pswapd with mmx code
movq mm0, [eax]
…process
movq mm1, mm0
punpckldq mm0, mm0
punpckhdq mm1, mm0
...process
add eax, 8
;loop cycle here
no memory access but might be slow…it takes some 6 cycles

2. maybe prepare data like this:
ffff|aaaa||bbbb|cccc||dddd|eeee||ffff|0000||
and read it like this
movq mm0, [eax] ; here is the 4-aligned read every second loop
...process
add eax, 4
;loop cycle here

3. maybe prepare data like this:
aaaa|bbbb||bbbb|aaaa||cccc|dddd||dddd|cccc||eeee|ffff||ffff|eeee||
and process like
movq mm0, [eax]
…process
movq mm0, [eax+8]
...process
add eax, 16
;loop cycle here

It seems to me that 2 and 3 could be faster than 1.
2. requires less preparation time than 3, less memory but there are 4-only-aligned movq reads mixed with 8-aligned movq reads on same data.
3. requires double memory of 2, more prep time but there are only 8-aligned movq reads

Sooner in this thread there was commment about conditional jumps and nightmares. When I use the jnz, is it that slow that it is worth unrolling the cycle 2 or 4 times (and therefore risk of uselessly processing zeroes if there is odd number of steps? (which is not probable when speaking about 2D video data…)

Currently, I have the approach to prepare block of data into working area process and put back.
Maybe faster would be prepare full plane, process and put back.
That would be eg. on full HD video 4MB to 5.3MB depending on alignment requirements.
If I will have 2, maybe 3 input clips in later version of this filter it will make 12MB of data. Output will be packed to bytes probably so it makes another 2-3MB.
Is it within "good manners" to require 15MB memory for one filter?

[sh0dan]

* Pairing.
U/V pipes are for scalar code, and is something from the Pentium age. Now there are usually 3 scalar pipes. There is a

* Timing: Moves from memory have at LEAST a 4 cycle latency (if reading from same cacheline as previous reads), usually much more, something like 12 from cache level 1. MMX multiply has 3, most others have 2, but allocate either the FADD and/or FMULL pipepine, or shifter on Intel.

Since timing is immensely complex, and individual operation timing varies a lot, just try not to make your code too dependent. If so, the processor has a much freedom, and will look ahead for unblocked instructions to execute while a read stall is blocking one unit.

* Temp buffers are only a good idea if you can do it on a limited set of data and keep data in the cache. The resizer and planar converter in 2.6 unpacks one line, that will fit nicely into cache, and converts this line.

If your filter requires more lines (2 or 3), you just unpack the needed numer of lines and unpack one line for each additional line you need as you process downwards. This also makes in-place processing a lot easier, since you can write to the original image and still have the original picture data.

* pswapd can be done by using pshufw mm0,mm0,01001110b

* No it is not good manner to allocate 15MB, unless strictly needed.

[redfordxx]

Temp buffers are only a good idea if you can do it on a limited set of data and keep data in the cache.Not sure whether I am missing something, but I prepare data not to have it fitting into cache but to have it packed and aligned.

* pswapd can be done by using pshufw mm0,mm0,01001110bOoops, something new…I have to study up. So when I want to produce code (with Visual C++ 6.0) which is good for most machines today and my AthlonXP too, I should study up MMX, MMXExt, SSE…nothing more…?

* No it is not good manner to allocate 15MB, unless strictly needed.OK

[sh0dan]

Uncached memory reads are very expensive, keep your temp buffer well below 64k (L1 size of Athlon XP), otherwise unaligned reads are very much preferable.

For not, 99% of all processors will have MMX+iSSE (MMXExt), so go for that and have a C fallback for the rest.

A misaligned read isn't that bad, but try to avoid it, if possible. Aligned reads are nice, but not essential. The horizontal resizer has lots of unaligned reads, but it is still very fast.

[redfordxx]

pshufw mm1,mm1,01001110bcauses


Compiler Error C2400
inline assembler syntax error in 'context'; found 'token'

The given token caused a syntax error within the given context.

Specifying a Pentium instruction can cause this error. Choosing the Pentium option (/G5) causes the compiler to generate instruction sequences optimized for the Pentium, but does not allow instructions specific to the Pentium.


Is it possible that VC++ 6.0 does not know SSE or it is about the options...? I dont understand much of the error message.

[sh0dan]

VC6 SP5 shouldn't have problems with SSE1 or SSE2. Have you installed SP5?

Maybe you should consider upgrading to VC2005 Express. It's free, and fixes a lot of VC6 problems, plus VC6 is EOL and more than 10 years old.

[redfordxx]

VC6 SP5 shouldn't have problems with SSE1 or SSE2. Have you installed SP5?

Maybe you should consider upgrading to VC2005 Express. It's free, and fixes a lot of VC6 problems, plus VC6 is EOL and more than 10 years old.
Thanks for reminding.

Is there anything I should fear in the newer version?...AthlonXP 2600+ MS WinXP and C-beginner here ;-)

I checked MS page...there is already 2008 to download... is there any particular reason why you mentioned 2005?

My old code will be accepted smoothly, right?

[Fizick]

For VCToolkit2003 you need in .Net1.1. You can integrate it in old VC6 shell with some tricks (dirs in path).
For VC2005 you need in .NET2.0 to run,
For VC2008 you need in .NET3.5 (?) to run it. Not so many people tried it (me not). Generally, it is the same as 2005. IMO it is better to wait some time for hotfixes (SP1 ?) and use 2005 SP1 now. :)



But you did not answer about SP5 and processor pack. :)

[redfordxx]

For VCToolkit2003 you need in .Net1.1. You can integrate it in old VC6 shell with some tricks (dirs in path).
For VC2005 you need in .NET2.0 to run,
For VC2008 you need in .NET3.5 (?) to run it. Not so many people tried it (me not). Generally, it is the same as 2005. IMO it is better to wait some time for hotfixes (SP1 ?) and use 2005 SP1 now. :)



But you did not answer about SP5 and processor pack. :)Where can I find? It is usually in the about box, but there is nothing...or it means that there are no packs installled;-)

OK...I go for 2005, hope I find offline install somewhere...

[redfordxx]

OK, I am on VC2005... according to AVSTimer it seems to perform slower...could you advice the max optimization settings for the release configuration? (if there is something else than Maximize Speed (/O2)...

[foxyshadis]

Target Prescott or Core2 to generate appropriate SIMD, enable Link Time Code Generation (or even the profiling). If there's a lot of floating point, maybe change that to fast. Other optimizations give only very minor benefits, like FPO.

[redfordxx]

Target Prescott or Core2
1) How?
2) I have AthlonXP...doesn't matter?

[redfordxx]

Now there are usually 3 scalar pipes. There is aDoes it mean, that it is best to prepare not 2 but 3 flows of instructions?

[redfordxx]

When the code reads last pixel of the plane (srcp+pitch*height-1) using mov, movd, or movq the reading of last bytes will happen outside the allocated memory...may it crash?
Same for writing, but here I see that it probably will...

[redfordxx]

Thank you all for providing me the helping info...so I thought, maybe I should tell you what I am working on so that you know where is your effort going.

Some might know that I want to succeed to make my SmoothDeblock filter...but that's a distant target.

Now I am warming up with upgrading TBarry's DCTFilter...because it will be the key for the Smoothdeblock anyway.

Changes so far (working and hope bug free):
+any dimension of DCT (well, too big takes really time) --- if you like 1x1;-), 20x20 or 100x1, no problemo
+any dimension of clip, independent on DCT size --- no error messages, the borders just will not be processed
+possibility to shift the DCT blocks
+minor other features
+backward compatible with original DCTFilter (parameters format)
-I didn't bother with YUY2
-as it is general-size and not very optimized, it is about 4x slower than original DCTFilter at 8x8 at the moment --- however, at 8x8 it swithces to the original routine unless specified else

ToDo features:
+load quant matrix from file
+add weighted DCT mode (based on input mask clip)
+add variable quant DCT mode (based on input mask clip)

ToDo optimizations:
+improve core algo, then optimize
+optimize the transfer of data to work area and back

It's working now, and sooner or later I plan to publish it...
Should I start thread in Avs usage or Avs dev forum?

[redfordxx]

Back to bug you with questions...;-) (sorry)

* I'd like to add the quantization based on matrix. Probably somewhere is already existing GPL code to load the matrix from a file. Can you recommend me where can I get it?

* Is it possible in asm do something like switch?
What I mean: I have a number 0-10 in register eax and the code would be something like
mov ebx, -1
jump to address [EIP+2+3*EAX] ;if 2 would be the lenght of the jump instruction and 3 lenght of the add instruction for example
add ebx,1
add ebx,1
add ebx,1
add ebx,1
add ebx,1
add ebx,1
add ebx,1
add ebx,1
add ebx,1
add ebx,1
add ebx,1
; here the value of EBX would be same as the EAX
This code makes no sense but I hope you know what I mean.

[redfordxx]

And you can use all the registers in your code, just put them back at the end.Mhm, after some tough moments I realized that using ESP and especially EBP is road to hell.
Any other restrictions?

[Dark Shikari]

Mhm, after some tough moments I realized that using ESP and especially EBP is road to hell.
Any other restrictions?You should have no problem using ebp if you use --fomit-frame-pointer when compiling.

[Fizick]

--fomit-frame-pointer is flag for GCC, but for VC it is /Oy
It is defuult with full optimization /Ox


Too many questions. Are most of them obsolete now? :) Anyway, they are useful for future beginner asm developers (like me). May be add to the thread title ("16x16 code to use with assembler optimisation")

'any dimension of DCT' is interesting, but big slowdown is not.
For really fast DCT you must use FAST DCT algo with butterfly and other more complex tricks for power of 2 sizes (4,8,16, 32,) and probably 3,9,27.

[redfordxx]

--fomit-frame-pointer is flag for GCC, but for VC it is /Oy
It is defuult with full optimization /Ox
Does not help...:-(
Too many questions. Are most of them obsolete now? :) No...

'any dimension of DCT' is interesting, but big slowdown is not.
For really fast DCT you must use FAST DCT algo with butterfly and other more complex tricks for power of 2 sizes (4,8,16, 32,) and probably 3,9,27.well, the thing is, that I was not focusing much on the algo and more on the learning coding.
Instead of the three calculations: DCT-Quantization-IDCT I made it one step together. I precalculated coeficients C_u*C_u*C_v*C_v*Q_uv*COS_iu*COS_xu*COS_jv*COS_yv. However I think, incorporating Q_uv (quant matrix coef) removed the posibility so separe calculation...I didn't do research for other algo options yet.
The rough performance on 720x480 (there can be some influences on my PCSize My algo, FFTW, Int8x8
8x8 65 150 250
16x16 14 14
FFTW is not implemented...I calculate it as 2xtime for the DCT in your DCTFFTW class

[sh0dan]

Does it mean, that it is best to prepare not 2 but 3 flows of instructions?

For non mmx (scalar) instructions, yes. Scalar optimizations are however IMHO mostly a waste of time, since it mostly doesn't bring much over nicely written C-code.

[Fizick]

Does not help...:-(

?

__asm
{
mov esi, param1; got params
push ebp ; store ebp

...; any change ebp

pop ebp ; restore ebp and stack
}

[foxyshadis]

1) How?
2) I have AthlonXP...doesn't matter?

I forgot, that's only with ICL (Intel compiler), sorry. VS only gives you SSE and SSE2. And yeah, you can't target SSE2 and up if you have an XP. :(

A generic switch is like this (http://www.eventhelix.com/RealtimeMantra/Basics/CToAssemblyTranslation3.htm), but a dirt simple switch should be calculable like:

mov eax, -1
mov ebx, 6 ; this being your jump-in value
add ebx, jumper ; inc is single-opcode, no multiply?
jmp ebx
jumper:
inc eax
inc eax
inc eax
inc eax
inc eax
inc eax
inc eax
inc eax

by my assembly is so rusty that might not be legal at all. Of course counting hex bytes can get old quick, it might be much saner to use a lookup table.

[Leak]

by my assembly is so rusty that might not be legal at all. Of course counting hex bytes can get old quick, it might be much saner to use a lookup table.
That, or use a label at the start of the first and second unrolled loop part and subtract their addresses - if it's a bit more complicated than you'll have to mul by that value anyway...

[redfordxx]

I did
__asm
{
pushad ; store everything

...; change ebp
;3 instruction after it crushed...still in asm area


popad; restore all
}

[redfordxx]

use a lookup table.but this would be slow, wouldn't it?
IIRC, in the AMD appendix there is written latency 1 for most of short jumps...but I assume it is only the evalulation of the condition and then the jump takes some time...

...same as memory reads... they announce latency 2 but they take much longer as sh0dan mentioned

[IanB]

int foo(int abc) {
int def;
__asm {
mov eax, abc ;; abc is probably [ebp+8]
mov def, eax ;; def is probably [ebp-20]
Have you worked out how to get ASM listings from the compiler yet?

Always look at the ASM listing from the compiler, your __asm code must fit in with the code from the compiler. i.e. the whole code must be consistant.


And the magic word you need to reference a code label is offsetadd ebx, offset jumper

To find these magic words look in the ASM listing, write some C that will use the concept you need and see how the compiler does it.

[gioowe]

but this would be slow, wouldn't it?
IIRC, in the AMD appendix there is written latency 1 for most of short jumps...but I assume it is only the evalulation of the condition and then the jump takes some time...

...same as memory reads... they announce latency 2 but they take much longer as sh0dan mentioned

The condition is calculated before. A jump only checks flags.

A correctly predicted jump or an unconditional jump has a latency of 2, assuming that the next instruction is in the L1 code cache. If it was mispredicted then the CPU has to flush all decoded instructions and start again. This takes about 42 cycles. The AMD processor (I don't care about Intel) has a branch prediction as follows: A conditional branch is assumed as non-taken the first time. The second time (address) it is assumed as the same as last time. All further times (address) it is assumed as the second time.

[foxyshadis]

And the magic word you need to reference a code label is offsetadd ebx, offset jumper

To find these magic words look in the ASM listing, write some C that will use the concept you need and see how the compiler does it.

Thanks, I was scratching my head over that when I was trying to test and get the code actually working yesterday. :p

[redfordxx]

Have you worked out how to get ASM listings from the compiler yet?Yeah, almost reading like a book;-)
Of course I am learning from that.

I read also one funny thing:the compiler translated my jnz to some other kind of conditional jump;-)

Always look at the ASM listing from the compiler, your __asm code must fit in with the code from the compiler. i.e. the whole code must be consistant....having consistent code with the code from the compiler...this topic I probably leave to the horse for now...he has bigger head than me;-)

[Leak]

I read also one funny thing:the compiler translated my jnz to some other kind of conditional jump;-)
Well, jne (not equal) and jnz (not zero) are the same instruction, since for both you just check whether the zero bit in the flags register is set - maybe that's what happened?

np: Yello - Daily Disco (1980-1985: The New Mix In One Go)

[redfordxx]

@Fizick

I changed the title...d'you like it better?

First I borrowed your Bytes2Float routine and changed it into Bytes2Words...Then I completely replaced it with scalar asm and it was significant speedup...I will add MMX and then I post it...maybe it would be useful for you if it is possible change it back to float...

[Fizick]

i have also SSE optimized bytes to float routine in Vaguedenoiser ;)
(code written by Kurosu though) :)
But it take very small percent of time.

When (if) you make fast MMX dct 16x16 (16x8, 8x16), I will try add it to MVTools. :)

[redfordxx]

Hello,

here is new area to explore for me:

Packed integer division on mmx registers... afaik it is not in MMX set, is there any common instruction set with divisions? Or it is only AMD specific when I have AthlonXP? Where should I focus my learning efforts?

[sh0dan]

redfordxx: What is the C-equivalent of what you want to do?

MMX cannot do division, but you can use inverse multiply to achieve a division if your division is constant.

For example:

y = x / 5;
==
y = x * (256 / 5) / 256
==
y = (x * 51) >> 8

Increase 256 to any power of two to get better precision.

[redfordxx]

OK, I try it short and fast, coz this hotel internet in Brussels is constantly disconnecting me.
The mul-division is nice, I heard of it but didn't know what is it exactly...will use later...tnx

[redfordxx]

My case:
a=IDCT(Quantize(DCT(x))
b=IDCT(Quantize(DCT(y))
c=a/b

I have
x=[0,65535]
y=[0,255]
a,b scaled to signed DW
c=[0,255] unsigned saturated

x,y are values from video...so definitely not constant...

So I see two options:
1)do it scalar
2)use other instruction set? There is no common packed integer division?

[IanB]

unsigned short Reciprocal[65536]; // 65536/i

c=(a*Reciprocal[b])>>16;

Look for the extract word/insert word instructions pinsw/pextw (sp?) and pmulhw

[redfordxx]

So, iiuc I should prepare some lookuptable for all numbers [0,65535]...

[IanB]

In the general case, Yes, a 65K table. But if you know your data you can pull some tricks to increase accuracy or reduce the table size.

[redfordxx]

It seems, that maybe all this insert/extract gymnastics takes so much time, that it is better to do in in normal scalar asm...

Or maybe I will do this part is scalar version for compatibility and then I'll do 3DNowPro version with normal division... however, I am not sure yet, whether 3DNowPro can on xmm do something so nice as PMADDWD:(

[Sulik]

The most efficient way to achieve this is probably to temporarily convert the data to floating point and use single-precision floating-point SSE to perform the final division on 4 values at a time.

[IanB]

Look at how many cycles all the division instructions take on all of the processors. In this many cycles you could almost rebuild the pyramids.

Do not do division unless there is no other way around the problem.

Post your existing code for this portion and I will see what can be done.

[Sulik]

Not true. You should be able to issue a DIVPS instruction operating on 4 values with only ~20 cycle latency on a Core2 duo.
This should end up faster than 4 scalar lookup and avoids trashing L1.

[IanB]

The code I am thinking about would be 4 streams of 2 fast instructions plus a pmulhuw all up maybe 12 to 16 cycles on a Core2 and will do almost as well on most other CPU's

You also have to include the to and from float conversion as well to use the DIVPS.

[redfordxx]

OK, back to switch code and jumps:
jmp ecx is already working...
jg ecx does not...
is there any trick?