VagueDenoise optimization

[sh0dan]

afaik, YV12 width*height should be MOD4, but I guess there are trickier things to consider).
Careful! While this is true for the Y-plane, it is not always for the UV-planes! You could however still make it a filter requirement, without many people being bothered by it.

Operating on "larger pitch" images could also be a problem, as garbage in the right border probably will infuence the result.

[Kurosu]

Originally posted by sh0dan
Careful! While this is true for the Y-plane, it is not always for the UV-planes! You could however still make it a filter requirement, without many people being bothered by it.
Indeed, (vi.height>>1)*(vi.width>>1) should be MOD4. Why I said that: on some loops, only one pixel is processed at a time, because registers are fully used. But with SSE, 10 input coefficients per output coeff don't match well 4 coefficients per register. I haven't got further than that, and it might not be possible (for instance, JPEG-2000 transform reads data interleaved, so it's not as straightforward).

Operating on "larger pitch" images could also be a problem, as garbage in the right border probably will infuence the result.
Well, the problem really occurs because some processing is done in place. That's why I thought I should enforce restrictions so that all ranges processed (ie the shortest, because others are probably a power of 2 bigger than that shortest). And actually, that's what I meant by 'trickier things' (mirroring?) :)

[Kurosu]

(I could have updated above post...)

I'm testing various alignement optimizations, but I can't seem to get it working... I declare with __declspec(align(8)) the float[10] analysis/synthesis arrays, code compiles fine, but dll doesn't load. Does anyone know what are the requirements to use it (I failed to find it using google and MSDN)?

[EDIT]
(yeah, I like editing and editing again my posts). I managed to do the equivalent by dynamically allocating (_aligned_malloc) those arrays, and manually ( :mad: ) entering the values. Small improvement: with Vaguedenoiser(threshold=2.5,nsteps=6,chroma=true), from 21.3ms to 20.9ms. The 3DNow! code also has a bug: 3DNow doesn't behave like expected, and I must do something like realtoChar, ie adding 0.5 to the float value before converting back to integer. This was much needed on black surface, where bands and patterns were very noticeable.

[sh0dan]

Just recently found out that "__declspec(align(8))" requires you to maintain ebx in your assembler part, otherwise you will get strange behaviour - I guess this is the reason for the very unpredictable behaviour.

But _aligned_malloc is better to use. You should try aligning it to a 64-byte boundary, so it can be retained in a single cache line.

[Kurosu]

Thanks for the info, I won't bother anymore... You loose a register and you can achieve the same (if not better) with an aligned malloc? Sure there must be some kind of advantage, but I can live without it. I myself align to 64 (Athlon, K6 should probably be 32? but that can't hurt them), though I thought P4 had a 128 alignement (!).

Regarding asm code, I've managed to convert 3 parts (out of... 7?)to SSE so far. Bad thing is that the heavier loops are far slower with SSE! Those loops using SSE are very close to the 3DNow! code, but it really feels like a waste: I'll probably need to rework the way the data is processed... I guess a first working version should be ready by next week, but seeing how bad SSE performed, I expect a 50% slower version compared to 3DNow! (yet 20% faster than plain C - but P4 owners might have different results).

[trbarry]

Just recently found out that "__declspec(align(8))" requires you to maintain ebx in your assembler part, otherwise you will get strange behaviour - I guess this is the reason for the very unpredictable behaviour.

Sh0dan -

That is very scary and I'm probably violating it regularly. Where did you hear that? And is it just that you have to restore ebx before going back into C code?

- Tom

[sh0dan]

IA32 Intel Optimization Guide, Appendix D, page 10.

For some reason I cannot copy paste, but to quote some of it.

When using aligned frames, the ebx register generally should not be modified in inlined assembly blocks, since ebx is used to keep track of the argument block. Programmers may modify ebx only if they do not need to access the arguments and provided they save and restore it before the end of the function (since esp is restored relative to ebx in the functions epilog).


They say this is true for the Intel C++ compiler, but all the problems we have had with __declspec(align) might very well relate to the fact that it is also true for MSVC. I'm not sure if MSVC actually is doing "dynamic stack alignment", which is where the problem arise.

[Kurosu]

Then it's just a matter of pushing ebx onto the stack before processing and popping it back at the end... It's a simplier trade-off than what I had expected. In the past, I always had such problems, so I guess I'll start using it more often now.

[Kurosu]

Ok, finished the float-SSE code. I'm rather disappointed by its performance on my Athlon system (640x480 YV12 source):
- 3DNow: 19.6ms
- SSE: 24.8ms
- plain C: 34.2ms
I'd like everybody interested in that filter to check how it performs - no check is done regarding CPUs, 0.25 wasn't used (that's not my purpose) - so that I see if it's just AMD that aren't that good at SSE, or if there's a real flaw in my code.

Regarding developpers, I do believe there are prefetching possibilities available (thresholding benefits from this, and could directly help data conversion). To compile for a particular processor, set DEF_CPU to:
- 0 for plain C
- 1 for 3DNow!
- 2 for SSE
Overall, I think Wavelet::transform_step performs particularly bad, followed by Wavelet::invert_step. The first should be completely rewritten to get rid of some shuffps, and the 2nd one could be unrolled a bit. In addition, it might be usefull to check for alignement in both case and process separately the inner part of the loop that works on aligned data (like IScripEnvironment:BitBlt does).

parameters were:
Vaguedenoiser(threshold=50.0,nsteps=6,chroma=true)
The threshold is much exaggerated in order to see stronger results.

Get the 3 DLLs (C, 3DNow!, SSE) in that package (http://kurosu.inforezo.org/avs/VagueDenoiser.zip) and please do post your results...

[Lefungus]

Hi Kurosu, here is my feedback:

VagueDenoiserIntel crash at the beginning with an illegal instruction at 0x013914c0.

VagueDenoiserC run at 16 ms, versus 11 ms for my last binary (0.25)

I've tried to compile again your version but with both Intel ot vc7 compiler there are a few errors:

__asm 'movups' Bad memvx128 qualifier
__asm 'movaps' Bad memvx128 qualifier
__asm unknown opcode 'FEMMS'

My lack of knowledge concerning asm prevents me to help you any more than this :/

[Kurosu]

Originally posted by Lefungus
Hi Kurosu, here is my feedback:

VagueDenoiserIntel crash at the beginning with an illegal instruction at 0x013914c0.
True, that's the femms you pointed later in your post.

VagueDenoiserC run at 16 ms, versus 11 ms for my last binary (0.25)
I guess so, the dll was compiled with MSVC++ 6, with an AMD as target. Besides, I really don't mind for the C version, I'm not working on it. It's just there to see how the different optimizations behave comparatively.


I've tried to compile again your version but with both Intel ot vc7 compiler there are a few errors:

__asm 'movups' Bad memvx128 qualifier
__asm 'movaps' Bad memvx128 qualifier
__asm unknown opcode 'FEMMS'

I'm quite surprised femms isn't well handled by VC7. I wouldn't be surprised if ICL7 only supported intel works (lame, but that's how it is). And I have the feeling you pasted me the ICL7 log, which isn't really helpfull without lines where to find errors.
Regarding movaps/movups, they are perfectly valid simd/SSE instructions. And I would be very surprised if they caused such an error... Maybe the error occurs when the compiler parse the #define MOVPS movups and #define movaps ?
If not, I really don't see why even VC7 fails to compile.

Anyway, regarding the compile, I've updated the linked package.

Last but not least, have you ever checked what the adaptive thresholding as performed by Donoho and Johnstone? I have none to point to, but Bach had once posted this:
http://www.quantlet.com/mdstat/scripts/wav/html/wavhtmlframe81.html
The principle is to separate coefficients into bands/windows (of 2048 coefficients for instance) and do a local analysis yielding average/standard deviation of the coefficients, and deducing the threshold to apply locally (could produce a factor for the input threshold in your case). Nothing spectacular, though.

[Lefungus]

OK about your previous version, i made an error. It compiles well under vc7 (but still crash).
Under icl, there are some errors but i wouldn't worry much about it.

Here they are:


wavelet.cpp(92): (col. 40)warning #998: reference to EBX in a function requiring stack alignment
wavelet.cpp(147): (col. 37)warning #998: reference to EBX in a function requiring stack alignment
wavelet.cpp(147): error: __asm unknown opcode 'PREFETCHW'
wavelet.cpp(147): error: __asm unknown opcode 'PREFETCHW'
wavelet.cpp(158): error: __asm unknown opcode 'PREFETCHW'
wavelet.cpp(158): error: __asm unknown opcode 'PREFETCHW'
VagueDenoiser.cpp(343): error: __asm 'movaps' Bad memvx128 qualifier
VagueDenoiser.cpp(428): error: __asm 'movups' Bad memvx128 qualifier
VagueDenoiser.cpp(430): error: __asm 'movaps' Bad memvx128 qualifier
VagueDenoiser.cpp(431): error: __asm 'movaps' Bad memvx128 qualifier
VagueDenoiser.cpp(459): error: __asm unknown opcode 'FEMMS'


About adaptive thresholding :)
Well, i have already some code done like Qian thresholding or an adaptive subband based thresholding.
Qian works very well, it's supposed to keep more details than soft thresholding.
Adaptive thresholding works less well. It's not really noise adaptive. I may have an error in my algorithm, but i've checked it many times. I still need to work on it..
And with this, it's even more SLOW. To compute noise variance for each subband is expensive, and i'm not really impressed by the results yet :/

[Edited]
With the new package, i get an exception at 0x01362856

[Kurosu]

Originally posted by Lefungus
OK about your previous version, i made an error. It compiles well under vc7 (but still crash).
Then there's somewhere, an unknown 3DNow instruction left... It works perfectly for me, so it's harder to spot...


wavelet.cpp(92): (col. 40)warning #998: reference to EBX in a function requiring stack alignment
wavelet.cpp(147): (col. 37)warning #998: reference to EBX in a function requiring stack alignment

Should not be a problem, but I did my best to solve this.
The message may still appear however


wavelet.cpp(147): error: __asm unknown opcode 'PREFETCHW'
wavelet.cpp(147): error: __asm unknown opcode 'PREFETCHW'
wavelet.cpp(158): error: __asm unknown opcode 'PREFETCHW'
wavelet.cpp(158): error: __asm unknown opcode 'PREFETCHW'

That's the error imo: I've left 3DNow code inside the SSE parts...


VagueDenoiser.cpp(343): error: __asm 'movaps' Bad memvx128 qualifier
VagueDenoiser.cpp(428): error: __asm 'movups' Bad memvx128 qualifier
VagueDenoiser.cpp(430): error: __asm 'movaps' Bad memvx128 qualifier
VagueDenoiser.cpp(431): error: __asm 'movaps' Bad memvx128 qualifier

That still worries me as those instructions are really available. That it gives an error on these places (and not in wavelet.cpp) is even stranger... Maybe ICL7 name them differently? I'll try to look that up.


VagueDenoiser.cpp(459): error: __asm unknown opcode 'FEMMS'

Ok, that's from the old code... I may have uploaded a bad file... Soon to be corrected!

And with this, it's even more SLOW. To compute noise variance for each subband is expensive, and i'm not really impressed by the results yet :/
yeah, that's not the smartest way to do this (my suggestion, yours should be more effective), but I guess nothing can be achieved with too simplistic estimators.

With the new package, i get an exception at 0x01362856
Unfortunately I'm not good enough to track an instruction from a memory location where the code is stored... That's the bad part about avisynth, it doesn't have a mini-disassembler (like Vdub) to report what kind of instruction caused the error.

New package (dlls+zip) uploaded...

[Lefungus]

Ok, your dll still crash on me.
But i've compiled myself an SSE version of your code with VC7, and it works now

I have 13.3ms average, so 4.5ms gained from a standard C version compiled with vc7. Good work Kurosu :)

About the adaptive thresholding, i've implemented this (http://www.ee.iitb.ernet.in/~icvgip/PAPERS/202.pdf) paper.

[Kurosu]

Originally posted by Lefungus
Ok, your dll still crash on me.
But i've compiled myself an SSE version of your code with VC7, and it works now
Fine... But I still can't understand why it can't compile well. I never had reports about 3DNow!, so it feels strange.

I have 13.3ms average, so 4.5ms gained from a standard C version compiled with vc7. Good work Kurosu :)
I don't find this result that impressive :/
But I guess the SSE code is really crappy. As I said, it's quite a shame the SSE code performs worse on my Athlon than the 3DNow! part. Ah well, unless someone points out some obvious optimizations, I don't think I can improve something: that's a naive implementation and the best I can do.

Btw, only hard thresholding is optimized, so it might reduce the performance difference (compared to my own measures).

About the adaptive thresholding, i've implemented this (http://www.ee.iitb.ernet.in/~icvgip/PAPERS/202.pdf) paper.
Ahah, it's so much more readable that all I've read searching for smarter algorithms... google search or http://citeseer.nj.nec.com/cs ?

[Lefungus]

With hard-thresholding (i used soft thresholding before), it's 11.8 ms, just 0.5 ms more than icl version. Imo that's not so bad.

For the paper, i guess i've collected an impressive collection of links now :) Both by google or citeseer. But i don't remember which for this one.

{Edited]
Qian thresholding (http://www.owlnet.rice.edu/~joejqian/elec532.pdf)

i'll try to clean it, and give source/binary next week.

[Kurosu]

Out of boredom, I decided to disassemble the ICL7 compile by LeFungus with Nasm 0.98.35 (ndisasm -u -i -p amd/intel vaguedenoiser.dll > vd-?????.txt)...

And... Not that surprising but quite more explanatory!

ICL7 compile, even compiled from C code, does use float SSE code. ICL7 compiler therefore automatically detects vectorizable parts and optimize them. Less than a handwritten asm, that's the satisfying part :D

I've checked all compiles:
- my C code: no MMX, SSE or 3DNow code (at least no such registers)
- my 3DNow: usual MMX/3DNow, as expected
- my SSE: expected MMX/SSE registers used
- LFG's ICL7: SSE code in the conversion parts, it seems, and maybe elsewhere. No MMX registers used in other places than the above conversions.
- LFG's VC6: nasm reports 4 MMX instructions, but I didn't find any emms, which may be possible, but is doubtful.

The later result looks suspicious. But I believe the other evidences are sufficient to see that ICL7 does a good job, and that further optimizations may not yield much better results...

For the ones interested, check this 400K rar3 file (http://kurosu.inforezo.org/avs/disassembly.rar) with the 5 disassembly results (no fancy details, just plain old asm against binary data)

[Kurosu]

Could someone point me at some free (as in beer, not speech) tools to evaluate performance (like AMD tool which name I don't recall)? For instance, cache miss, cpu cycles count... (I should have posted this in the development but people here should give me better help regarding the case of VagueDenoiser).

For my recent playing with prefetch, I have the feeling that "few CPU cyles + aligned reads = big win by prefetch". This is of course obvious for seasoned ASM coders, but not for me.

Prefetch could improve things more for thresholding, float<->int conversion (where there are few calculus done) than for the rest. That improvement is as far as my abilities can go, so I'll most probably stop optimizations after.

[sh0dan]

There is a CodeAnalyst 2.1 beta that can be downloaded from AMD's homepage - I do however prefer the slightly older AMD CodeAnalyst 1.2.8 (http://cultact-server.novi.dk/kpo/avisynth/AMDCodeAnalyst.exe).

It provides detailed pipeline analysis of assembler sections.

I'm not sure there is much to be gained from prefetching - at least not in my experience. Aligned data is much more important, as it will give a fixed cycle penalty per unaligned instruction.

[Kurosu]

1) I do think some gain can be achieved with proper prefetching. By only adding prefetchnta looking up at 512 or even 1Kb distance (ok, the loop was just averaging and distance should be shorter for slower systems), I got a 100% speed-up on another plugin (interpolation as done in TPRIVTC). But it won't be that visible considering those parts are not the most important (good speed-up locally but globally like 1%).

2) Unfortunately, the FIR filter can't read aligned data, as it's its very own property to read by offsets of 2 relatively to the input data... I tried some unrolling and reorganization of the unrolled loop but without success.

[trbarry]

Unfortunately, the FIR filter can't read aligned data, as it's its very own property to read by offsets of 2 relatively to the input data...

I'm not sure but suspect the main performance hit of unaligned data is that it sometimes causes 2 cache lines to be fetched. However in something like a FIR filter that is reading the data multiple times it is probably a lot less important since it is usually in the highest level cache anyway.

My own various filters that load mmx regs from *+1, *+2, *-2, etc. don't really seem to pay any significant penalty for it. Once you are already reading bytes from the same cache line it seems you can do pretty much what you want.

- Tom

[Kurosu]

No optimizations this time, but I prefer to only make it available inside the developement forum - for a purpose. I dubbed it 0.26 as this builds has several new features:
- debug=true will attempt to visualize the wavelet coefficients
- mode=2 should apply no thresholding - only usefull when using with debug=true, then
- pure C (no vectorization a la ICL), 3DNow! and SSE all inside a single DLL. OO adepts will surely appreciate old C dinosaurs like me doing an attempt at cleaner (?) code thanks to polymorphism :)

Ah, btw, the package (dll+source) is here (http://kurosu.inforezo.org/avs/VagueDenoiser0.26.zip)

I didn't manage to achieve any conclusive speed increase (ven by mirroring some calculus), so I'll leave the code as is.

[sh0dan]

Just profiled the latest version (AMD Tbird 1200):

30% overall are spent in void Wavelet::invert2d(float *, int, int, int)
of these 30%, 99%(!!) are spent in the four copy(....) routines.

29% overall are spent in void void Wavelet::invert2d(float *, int, int, int)
Again, of these 29%, 99% is spent in the four copy operations.

Pipeline analysis shows nothing interesting.

I found a few percent (115,4ms average execution time, vs. 120,7ms execution time), by using bitblit for the simple copy:
_inline void Wavelet::copy(float register*p1, float register*p2, int length)
{
DLLEnv->BitBlt((BYTE*)p2,0,(const BYTE*)p1,0,length*sizeof(float),1);
// for(int i=0;i<length;i++)
// p2[i]=p1[i];
}
It requires a few other additions. modified files (http://cultact-server.novi.dk/kpo/avisynth/Vague_opt_test.zip). Not much - I don't know if it has any impact on SSE code (right now I only modified the C/3DNOW).

[Kurosu]

Gain here is a lot less, but it still exists. Around 0.4ms out of 20.4, 24.5 and 30.8ms: maybe P4 machines will have a greater or far lower boost, maybe BltBit (read: prefetch distance) is especially optimized for your kind of processor, while newer hardly beneficiate from this.

Too bad the others can't be optimized that way. However I did read articles where they tried to do the processing in place, but that requires more study and time than available. I hadn't notice the copy were the most costly part of the algorithm, so I guess the optimization isn't in how the calculus are done - Haar wavelet would be almost as costly as Brislawn's.

I don't think I'll take time to do it, but maybe the debug mode (levels accessible) could lead to some nicer thresholding.

[Bidoche]

Did you try a regular memcpy ?
Since it don't have to bother about pitchs and height, it may be faster in this case (it is supposedly well optimised)


By the way, I noticed a potential memory leak in Wavelet code:
the constructor init dynamically some static arrays.
it will leak if it is called a 2nd time (and don't worry there will be users to use it twice or more).


@Kurosu

I noticed you used some polymorphism this time :)

[Kurosu]

@Bidoche
1) It means that anybody using it in some scripts using scriptclip (like FMF or QMF) will have a lot of problem... I thought that several calls would instanciate several objects. Do you see any way to fix this as I don't even know why it would leak?
2) About polymorphism, I'm still disappointed to have to write several constructors/destructors just to get sure the proper classes are used for compilation (most often, I would otherwise have "conversion from class Wavelet_SSE * to class Wavelet exists but isn't accessible" or something like this - my C++ abilities are too limited to solve this).

[Bidoche]

To fix the leak, replace in wavelet.cpp
float *analysisLow, *synthesisHigh, *synthesisLow, *analysisHigh;byfloat analysisLow[10] = { ... //values
//same for other arrays
Wavelet constructor and destructor become trivial (inlined in the .h)

If you do need the 128 alignement, there is directive for that whose I never remember about it.
I saw sh0dan use it in his code, he should know.


About polymorphism, I'm still disappointed to have to write several constructors/destructors just to get sure the proper classes are used for compilationI don't catch your problem here, such constructors are generally so trivial you just inline them.. (in the .h, not an _inlien directive)
You certainly don't inline enough.

most often, I would otherwise have "conversion from class Wavelet_SSE * to class Wavelet exists but isn't accessible
You can't convert a pointer to a class, or is it just a typo !?
I noticed you used a second Wavelet pointer for 3DNow and SSE subclass.
Why is that, it defeats the purpose of inheritance... letting the superclass destructor handling deletion and such...


By the way, there is a C++ thing which is easy and could help the readibility of your code :
Don't declare the vars at block scope, but only when needed.

It was required in C, but not in C++ and in fact faster (slightly if u only use basic classes)
When u write for(int x = ... ) at least x is self commenting.


Another thing, about the invert2d bottleneck, this function dynamically allocates and deallocates memory at each call.
I believe it may consume a significant part of processing time.
You should better allocate buffers of appropriate size once in constructor and always reuse them, either statically if needed size can be maxed or dynamically if not.

(If blocks are too big to reasonably have one per instance, then you can share them, but then you must consider synchronisation issues)

At least, replace int *hLowSize = new int[nsteps];
int *hHighSize = new int[nsteps];
int *vLowSize = new int[nsteps];
int *vHighSize = new int[nsteps];byint *hLowSize = new int[4 * nsteps];
int *hHighSize = hLowSize + nsteps * sizeof(int);
int *vLowSize = hHighSize + nsteps * sizeof(int);
int *vHighSize = vLowSize + nsteps * sizeof(int);

[Kurosu]

My post is horribly formatted... Sorry for that in advance.

Originally posted by Bidoche
To fix the leak, replace in wavelet.cpp
float *analysisLow, *synthesisHigh, *synthesisLow, *analysisHigh;byfloat analysisLow[10] = { ... //values
//same for other arrays
Wavelet constructor and destructor become trivial (inlined in the .h)

If you do need the 128 alignement, there is directive for that whose I never remember about it.
I saw sh0dan use it in his code, he should know.
__declspec(align(x))
And yes, now I can use it, as Sh0dan pointed out why asm code would crash with such declarations. Change applied.

I don't catch your problem here, such constructors are generally so trivial you just inline them.. (in the .h, not an _inlien directive)
You certainly don't inline enough.
Most probably, but as I tend to experiment too many things at a time, I probably got side-tracked by a compile error, which I attributed to some C++ mystery...


most often, I would otherwise have "conversion from class Wavelet_SSE * to class Wavelet exists but isn't accessible[/code]
You can't convert a pointer to a class, or is it just a typo !?

Please... It _is_ a typo :p (writing by memory the error message and not a copy'n'paste)
But when I reread this, I can only think I read class Wavelet * while it actually was class Wavelet. And not a typo :)


I noticed you used a second Wavelet pointer for 3DNow and SSE subclass.
Why is that, it defeats the purpose of inheritance... letting the superclass destructor handling deletion and such...
Once again it comes from the "I don't understand why - let's hack" method. I had the previous compilation error certainly due to something else, and found this hack to work at this time. It is now solved.


By the way, there is a C++ thing which is easy and could help the readibility of your code :
Don't declare the vars at block scope, but only when needed.

Yes, I know, but I often prefer to have them declared first, for readability purpose in fact. It just depends how you read the code :)
In our context, I don't know if it has any importance.


It was required in C, but not in C++ and in fact faster (slightly if u only use basic classes)
When u write for(int x = ... ) at least x is self commenting.

I guess so, memory allocation are made when needed, ie not immediately or never.


Another thing, about the invert2d bottleneck, this function dynamically allocates and deallocates memory at each call.
I believe it may consume a significant part of processing time.
You should better allocate buffers of appropriate size once in constructor and always reuse them, either statically if needed size can be maxed or dynamically if not.
I was looking into this for a long time. Actually, I had proposed this in this thread or the other, but I think I deleted this idea, because of the following results: bad. I thing the areas need to be zero'ed prior to use. An single allocation in the constructor for the whole processing was producing only gibberish, and wasn't giving any noticeable speed gain. But I haven't looked any further since then.


At least, replace int *hLowSize = new int[nsteps];
int *hHighSize = new int[nsteps];
int *vLowSize = new int[nsteps];
int *vHighSize = new int[nsteps];byint *hLowSize = new int[4 * nsteps];
int *hHighSize = hLowSize + nsteps * sizeof(int);
int *vLowSize = hHighSize + nsteps * sizeof(int);
int *vHighSize = vLowSize + nsteps * sizeof(int);
That's a nice idea, but considering nsteps is generally low (like 6 or 8) and a pointer is 32bits wide, I'm not sure the gain is that noticeable. However this may be better in means of memory fragmentation.

I forgot to reply to the memcpy part. Considering the 2 other functions only read or write 4 bytes per position, I guess it won't be enough for any optimization from memcpy to improve anything.

Maybe rewriting the loops of Bitblt (one isn't needed, useless tests regarding loop end and alignment could be saved) would improve a bit things, but that's a bad coding time/performance gain trade-off.

[Kurosu]

What's new in 0.26.1 (http://kurosu.inforezo.org/avs/VagueDenoiser0.261.zip):
- merge from Sh0dan on copy
- cleaner and safer management from Bidoche
- fixed a crash that may have affected P4 users (Athlons with SSE support weren't affected as 3DNow! code, being the fatest, is always selected).

If someone still has the older versions handy, could he verify if using a particular wavelet had any consequencies on speed? Maybe a simpler wavelet could still do a nice job but be a lot faster (like VHQ modes in XviD)

@Sh0dan
I still find astonishing 99% of the time is spent in copies. That would mean almost nothing can be significantly improved in the math parts. But when one looks at the difference between SSE and 3DNow! code, difference in processing time is obvious. Either the 3DNow! code is lightning fast, or the SSE code suffers a lot from some problem yet to identify. If copies are really that important (even up to 80%), then it's not worth continuing any optimizations in the calculus parts. The algorithm would be better be modified strongly to avoid as many copies as possible (in-place transform ?).

[Lefungus]

I have almost all versions :). Here is the last with all filters:
VagueDenoiser 0.221 (http://perso.wanadoo.fr/reservoir/dl/VagueDenoiserSrc-0.221.rar)

I think it'll be interesting to add it again to the current version with the debug mode. As my time is limited now, i won't do it myself soon. If i remember well, Haar was still much faster than Brislawn, but results were less satisfying too. One way to test it is to use a high threshold and look at artifacts created.

[sh0dan]

Originally posted by Kurosu
@Sh0dan
I still find astonishing 99% of the time is spent in copies. That would mean almost nothing can be significantly improved in the math parts.

It may have been written a bit cryptic, but on my system (3DNOW!), approximately 60% _overall_ is spent on copying. The rest is math processing. I don't know if it means anything significant, but I profiled using plain "VagueDenoise()" without any additional parameters.

I'll do a profile on the new version - both 3DNOW and SSE any specific paramters you would have tested?

[Kurosu]

Originally posted by sh0dan
It may have been written a bit cryptic, but on my system (3DNOW!), approximately 60% _overall_ is spent on copying. The rest is math processing. I don't know if it means anything significant, but I profiled using plain "VagueDenoise()" without any additional parameters.
Ok, that sounds more reasonable. But that still means that 3DNow is 50% faster than SSE on calculus (0.4*19.8 vs 24.3-0.6*19.8)

I'll do a profile on the new version - both 3DNOW and SSE any specific paramters you would have tested?
Regarding the above trhe result, I would consider commenting the first line of Create_VagueDenoiser so that SSE code is always used, and profile that. There's something fishy in there: latency of SSE instructions is obviously greater, but I wouldn't have think to that extent. But you and me don't need SSE anyway, so don't waste too much time on it *pokes P4 users* :D

CodeAnalyst is a powerfull tool, but is a bit cryptic and eats a lot of data (some temp files were 1GB big...).

I have almost all versions . Here is the last with all filters:
VagueDenoiser 0.221
Thanks, I had looked back at the original author's source, and found that it was going to need more decyphering so as to retrieve the FIR coefficients.


I think it'll be interesting to add it again to the current version with the debug mode. As my time is limited now, i won't do it myself soon. If i remember well, Haar was still much faster than Brislawn, but results were less satisfying too. One way to test it is to use a high threshold and look at artifacts created.
Well, I don't plan to really use for any debug, but rather to gain speed where it's easily done (calculus - the copies can only be optimized at that point by changing the whole structure), and create new possibilities. The source isn't particularly modular, but my current version is now able to use differents wavelets seamlessly.

Regarding the "modularity", I was thinking of this post:
http://neuron2.net/ipw-web/bulletin/bb/viewtopic.php?t=137
I think this new wavelet (already pointed out by MfA) would need a big rewrite, but may have some advantages.

[sh0dan]

New profile:

VagueDenoiser(threshold=0.8,method=1,nsteps=6,chroma= true)

All percentages are percent of TOTAL execution time. (So no percentages of percentages in this one)

3DNOW:
"Wavelet_3DNow::invert_step", 19.69%
This piece of code is the slowest line, taking up 1.65% of total execution time:for (i =0;i<lowSize;i++)
{
idx++;
temp[idx]=input[idx];
}
This line takes up 1.47%:
pfadd mm3,[edi+ebx+8] //mm3=out[idx+2]+sl2*t0 | out[idx+3]+sl3*t0

"Wavelet::invert2d", 13.52%
The two (non-bitblit) copies are clearly the two slowest parts. The env->bitblt parts are NOT included in the 13,52%

"Wavelet::transform2d", 12.54%
Same as above.

"Wavelet_3DNow::transform_step", 9,86%
psrlq mm2,32Takes up 1.04% of the execution time. To avoid this dependency stall, try pshufw(mmX,mm2,11101110b) and store mmX instead of mm2 to completely hide the latency of this instruction.

"VagueDenoiser3DNow::filter", 6.52%
movq mm2,mm0 //mm2 = srcTakes up about 3% of total execution time. It's probably memory latency - and it waits for mm0 to be filled. Nothing much to do about it - maybe a bit of prefetching would help??

"VagueDenoiser3DNow::filterBlockYV12", 5.23%
movq dword ptr[edi+ebx+8],mm4 Takes up about 2% of execution time. Again memory latency, while waiting for mm3 and mm4 to be filled.

(I'll edit in SSE results in a moment)

[sh0dan]

SSE:

The percentages should not be directly compared to the numbers above, since overall speed may be different - use them also relatively.

"Wavelet_SSE::invert_step", 22.25%
This loop is again the slowest part: for (i =0;i<lowSize;i++)
{
idx++;
temp[idx]=input[idx];
} About 2.5% of overall processing time is spent here.
for(i= 0;i<idx;i++)
output[i] = 0.0;This takes up aout 0.8%.

mulps is also relatively slow.

"Wavelet_SSE::transform_step", 15.22%
movss [ebx+esi],xmm0 and the movss above takes up about 2.8% os total execution time. A memory store shouldn't be that slow. At least shuffle to another register and store that instead to avoid depency stall.

"Wavelet::invert2d", 10.59%
"Wavelet::transform2d", 9.88%
See 3DNOW notes.

"VagueDenoiserSSE::filter", 5.28%
movaps xmm2,xmm0Takes up 2.59% Probably the same issue as above.

"VagueDenoiserSSE::filterBlockYV12", 4.39%
Same as above. 4.39% is spent waiting for data.

Test system: Athlon XP Barton 2700+. (512KB L2 cache). Dual channel DDR memory. FSB 166Mhz.

[Kurosu]

For 3DNOW.

Originally posted by sh0dan
VagueDenoiser(threshold=0.8,method=1,nsteps=6,chroma= true)

"Wavelet_3DNow::invert_step", 19.69%
This piece of code is the slowest line, taking up 1.65% of total execution time:for (i =0;i<lowSize;i++)
{
idx++;
temp[idx]=input[idx];
}
Then let's use BltBit in that one. Would it be worth adding a bzero-like optimized version to core along env->BitBlt? Or is the available bzero/memset fast enough. Maybe a BitBltLine (self-explaining I hope) too ? :)

That makes me also think the symetric extension has a fair amount of
copies.

This line takes up 1.47%:
pfadd mm3,[edi+ebx+8] //mm3=out[idx+2]+sl2*t0 | out[idx+3]+sl3*t0
Maybe prefteching, but I only saw performance decrease with it on those parts.

"Wavelet_3DNow::transform_step", 9,86%
psrlq mm2,32Takes up 1.04% of the execution time. To avoid this dependency stall, try pshufw(mmX,mm2,11101110b) and store mmX instead of mm2 to completely hide the latency of this instruction.
Will try. But at this level, I guess only Code Analyst can really show up the improvements.

"VagueDenoiser3DNow::filter", 6.52%
movq mm2,mm0 //mm2 = srcTakes up about 3% of total execution time. It's probably memory latency - and it waits for mm0 to be filled. Nothing much to do about it - maybe a bit of prefetching would help??
Yes, I had not unrolled it and used prefetch on it, seeing how little it helped (could be seen as unefficient).

[sh0dan]

Would it be worth adding a bzero-like optimized version to core along env->BitBlt?
Couldn't hurt. A direct copy of AMD's memcopy (from the Optimization Guide) should be useable. I'll try if I can implement it before the upcoming 2.5.3! It could be implemented as a simple if (height==1) in the existing BitBlt - that way it would be transparent.

Added! It now does this: if (height == 1 || (src_pitch == dst_pitch == row_size)) {
memcpy_amd(dstp, srcp, row_size*height);
} else {
asm_BitBlt_ISSE(dstp,dst_pitch,srcp,src_pitch,row_size,height);
}
It will be in the next binary.

[ARDA]

@sh0dan
@Kurosu
I've just taken a fast look ; so few contributions.But I've seen a posible trick for one situation.
//Optionnal chroma filtering
if(chroma)
{
//Filter U Plane
srcp = (unsigned char*) src->GetReadPtr(PLANAR_U);
dstp = dst->GetWritePtr(PLANAR_U);
filterBlockYV12(heightU,widthU,srcp,dstp,src_pitchU,dst_pitchU,size_UV);

//Filter V Plane
srcp = (unsigned char*) src->GetReadPtr(PLANAR_V);
dstp = dst->GetWritePtr(PLANAR_V);
filterBlockYV12(heightU,widthU,srcp,dstp,src_pitchU,dst_pitchU,size_UV);

}
else
{
//Copy U Plane to Destination no needed anymore
/* env->BitBlt(dst->GetWritePtr(PLANAR_U),
dst_pitchU,
src->GetReadPtr(PLANAR_U),
src_pitchU,
widthU,
heightU);*/

//Copy V Plane to Destination no needed anymore
/* env->BitBlt(dst->GetWritePtr(PLANAR_V),
dst_pitchU,
src->GetReadPtr(PLANAR_V),
src_pitchU,
widthU,
heightU);*/


env->BitBlt(srcp,
src_pitch,
dstp,
dst_pitch,
width,
height);

return src;
}
}
else
filterBlockYUY2(height,width,srcp,dstp,src_pitch,dst_pitch);

return dst;
}
.
In that case we save a BitBlt; by now if there is no way working over src.
At least when the filter just works in luma ,you 'll have a little gain.
Really nice work I'll be following its development and maybe any other stupid
idea appears in my old and tired brain.I hope you find it usefull.
Arda
PD:I've not tested too much apologizes in advance if it's wrong

[Kurosu]

@ARDA
Integrated anyway - I don't have even tested if it really improves anything, as makewritable copies the frame in fact.

@Anybody reading
[Refer to just released (22 Sep 03) 0.27.0 code.]

As expected, unrolls and prefetching helped a bit, but it is far from making the improvement I could expect. The magic of sfence, movntq and prefetch(/w/nta/t0/t1/t2) is totally mysterious to me, so if you have anything to offer please do. An pseudo-optimized memcpy and float2byte and byte2float are really needing it.

0.27.0 is around 7% (3DNow) faster than 0.261 on my comp. There is room left for very tiny improvements (maybe 0.2ms out of 17.2) with unrolling all possible (some thresholding) loops and modifying code (C code shows how the loop should look like). Here are the current imrovements:[list=1] Previously unused registers are now used to store FIR filter coefficients
As many as possible memory allocations are done in the constructor
[/list=1]
One last point: I found a copy of Intel Compiler at work. I quickly hacked the code to merge my 3DNow code (blatantly unsupported by ICL and left to "other compiler") into the ICL compilation. It did improve things (now 17.0ms on my comp). I'm now wondering if dropping support for old Athlon/K6-III CPUs to build an hybrid 3DNow/SSE path for Athlon XPs would be worth it, considering I don't work in the optimization field, and the improvements are now likely to be ridiculous. They are 2 steps needed:[list=1] comparisons of SSE vs 3DNow code execution times
possibly have ICL compile (I can't do that so easily, so I may only build a project compatable with ICL to build all 3 pathes [C,3DNow,SSE]) some parts, and compare them to the others
merge the best of them[/list=1]

[acrespo]

I can't the VagueDenoise 0.261. The link is broken:

http://kurosu.inforezo.org/avs/VagueDenoiser0.261.zip

Can anybody send to me?

Andre Crespo
acrespo@was.ddns.info

[superdump]

Here you go :) (http://kurosu.inforezo.org/avs/VagueDenoiser/VagueDenoiser0.27.0.zip)

[MfA]

A suggestion for optimization, as maven pointed out ... getting rid of the memory access overhead for a single pass is quite trivial (that still leaves a lot of redundant access, but the rest is harder to remove).

If anyone one of you is feeling up to it Id suggest coding the transform with interleaved vertical/horizontal transform.

What this means is that if you first do the horizontal transform, you perform the vertical transform for a single line of coefficients after every line done with the horizontal transform ... or if you are doing the vertical transform first you first do the vertical transform for an entire line of coefficients before doing the horizontal transform for that line. You need some pro/epilogue obviously, and the edges need to be dealt with appropriately.

This way there is a significant gain to be had by doing the char to real conversion on the fly for the first level of the forward transform, and the real to char conversion for the final level of the reverse transform.

BTW does the present code do vector processing on groups of 2/4 columns (3DNow/SSE) simultaneously for the vertical transform yet?

[ARDA]

@Kurosu

quote
---------------------------------------------------------------------------------
@ARDA
Integrated anyway - I don't have even tested if it really improves anything,
as makewritable copies the frame in fact.
---------------------------------------------------------------------------------

In fact you've made better you've avoided all BitBlit.But one question
if you can do when just Y plane with both pointers over src;why do you
work over dst when doing the three planes in YV12? Why not always on place?

quote:
---------------------------------------------------------------------------------
The magic of sfence, movntq and prefetch(/w/nta/t0/t1/t2) is totally mysterious to me,
so if you have anything to offer please do. An pseudo-optimized memcpy and float2byte
and byte2float are really needing it.
---------------------------------------------------------------------------------
I've looked a little more, and if I'm not wrong all loops are forward,I mean
in a regular increasing (address) secuence.
I believe that modern cpu will do a prediction and make hardware prefetch
(always the better one for its architecture).
So if I'm not wrong (at least for pentium4) you'd better not include any prefetch.
It needs two iteractions( is that the right word?) to be able to make the prediction.
Any no temporal hint instruccion will have penalties is data is already in cache.The only
way you can use them in regular forward loops in deceiving the cpu; by storing
data irregularly; ex:load from src,src+8,src+16,src,24,src+32..write dst+32,dst+16,dst+8,dst.
I think you should write back or in a totally irregular secuence.
You could find an example in memcpy_amd that sHodan has included recently in avisynth.
But that it's true and improve things for large blocks.
For small blocks (if both are <= than 1/2 cache size; that's true in avisynth environment)
it's better always a forward loop, cause both blocks will be in cache.
For example I've tested that in my pentium 4 (512k cache) the limit is 131072 bytes
(1/4 cache for each buffer)if I want to copy a block.
Size of cache is very important to decide the best way of moving data;
that's why sHodan has been working (not completely included yet) on it (cpu_info.cpp).

quote:
-----------------------------------------------------------------------------------
sHodan wrote:
This is ONLY true when doing straight copies. If you process the data, do NOT use
the write combiner, as it makes delayed (cached) writes impossible.
-----------------------------------------------------------------------------------

All above would be important if we are only moving data in the limits of bandwith;
but I guess that's not the case.

By now for improving (I think this was sHodan'idea) with memcpy you could do the following:

-----------------------------------------------------------
This is memcpy syntax: memcpy(dest, src, n)
-----------------------------------------------------------

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

This is nowadays bitblit status:
if (GetCPUFlags() & CPUF_INTEGER_SSE) {
if (height == 1 || (src_pitch == dst_pitch == row_size)) {
memcpy_amd(dstp, srcp, row_size*height);

} else {
asm_BitBlt_ISSE(dstp,dst_pitch,srcp,src_pitch,row_size,height);
return;}
}
-----------------------------------------------------------

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

This is the way to call BitBlt from a plugin
env-> BitBlt (dstp,dst_pitch,srcp,src_pitch,row_size,height);
----------------------------------------------------------------
use:
env-> BitBlt (dest,n,src,n,n,1);
instead of memcpy(dest, src, n)

By this way BitBlt will call memcpy_amd which is faster than compiler library.
This is not the best solution ; but if you do not include in your plugin
a complete substitute of memcpy library ;this is a patch by now.

As always thanks for the great work.

ARDA

[Kurosu]

Originally posted by MfA
What this means is that if you first do the horizontal transform, you perform the vertical transform for a single line of coefficients after every line done with the horizontal transform ... or if you are doing the vertical transform first you first do the vertical transform for an entire line of coefficients before doing the horizontal transform for that line. You need some pro/epilogue obviously, and the edges need to be dealt with appropriately

I had already thought of this and wasn't really motivated to even design the whole stuff, not even code it. The tricky part is indeed the edge management: for each decomposition level you'd need to have a rather complex buffer management, to leave room for the symmetric extension done prior to the FIR filtering.

Memory bandwidth is indeed wasted in the current implementation: copy from line j, level n to buffer, filter buffer (with symmetric extension), copy to same place, but now as low + high parts + level n-1. Apply the same to columns. Locally, one would consider this a waste to re-read coefficients, but the same would apply to FIR filter coefficients. As of now they are as best as possible directly loaded into registers to avoid this memory movement. Keeping wavelet coefficients instead of FIRF ones could lead to better performance, but I bet the hardware would cope a little worse with it. In the end, it looks like more work than result, but that maybe the only possibility to speed things up.

This way there is a significant gain to be had by doing the char to real conversion on the fly for the first level of the forward transform, and the real to char conversion for the final level of the reverse transform.
As of now, the float2uchar and uchar2float conversions are already vectorized. I guess more speed could be obtained by better prefetch management (see ARDA's post below).

While the algorithm right now is pretty straightforward, what you suggest is at quite another scale of, for a starter, debugging. Sure, truly in-place transform sounds neat, but that's just like the links at the start of this thread: several PhDs with years on their hands. I am alone, and not motivated to spend entire days on this without an immediate result. This is obvious, as you stated.

Last, the algorithm would be quite much tied to the size of the registers used, so I bet you wouldn't be able to produce a C-version that can be quite easily translated into vectorized code. Or if it is possible (read: to be available), and it shows significant speed improvements over the old code, then I'll consider spending time to finetuning it and vectorizing it.

BTW does the present code do vector processing on groups of 2/4 columns (3DNow/SSE) simultaneously for the vertical transform yet?
Yes and no:
1) yes because it uses vectorization to do the convolution
2) no because it's a convolution that is done, not... lifting?
That's quite troublesome for SSE1 which doesn't have an equivalent of the pfacc (2-floats accumulator from the same register).

[Kurosu]

Originally posted by ARDA
In fact you've made better you've avoided all BitBlit.
Well, not really, but I'll explain why later on.

But one question if you can do when just Y plane with both pointers over src;why do you
work over dst when doing the three planes in YV12? Why not always on place?
Because I think that the makewritetable now copies the planes of the original frame requested to a copy. I'll need the exact facts from any core developper about this to be sure one way is better than the other.


I've looked a little more, and if I'm not wrong all loops are forward,I mean in a regular increasing (address) secuence.
Indeed.

I believe that modern cpu will do a prediction and make hardware prefetch (always the better one for its architecture).
So if I'm not wrong (at least for pentium4) you'd better not include any prefetch.
One can #define USE_PREFETCH3D / USE_PREFETCHSSE as 0 to deactivate it and see for oneself how it performs. I noticed it improved things a bit. On the other hand, I've written for one of my other filters (TPRIVTC) an function that averages odd/even lines to fill even/odd lines. While the addressing is completely forward, adding prefetches did boost my filters by around 50% on my Duron 700. But:
- as stated before by MfA, old Duron probably had a simplistic prefetch mechanism
- the computationnal part is very low, so one could expect such a need for prefetch)

I think you should write back or in a totally irregular secuence.
You could find an example in memcpy_amd that sHodan has included recently in avisynth.
Indeed, I had left that idea inexploited (see comments on page 3 of this thread).

it's better always a forward loop, cause both blocks will be in cache. For example I've tested that in my pentium 4 (512k cache) the limit is 131072 bytes
Then it's valid to use backward reads for conversions.

Size of cache is very important to decide the best way of moving data;
that's why sHodan has been working (not completely included yet) on it (cpu_info.cpp).
Well, the longer data read once in the wavelet transformation is vi.width*4 bytes, so quite less than 128KB. I guess then that blitblt is very suboptimal in that case... but it might depend on the processor, again.

On the other hand, wavelet.h holds a MMX-optimized memset. Contrary to the original source, I've removed movntq/prefetch because it was slowing things done.

One has to consider that the data accessed can be as low as (with)^(1/(2*nsteps)) (ie possibly 4 pixels for instance).


Originally posted by Sh0dan
This is ONLY true when doing straight copies. If you process the data, do NOT use the write combiner, as it makes delayed (cached) writes impossible.
All above would be important if we are only moving data in the limits of bandwith; but I guess that's not the case.
I don't really know: I guess it's always better not to waste the memory bandwidth.


By now for improving (I think this was sHodan'idea) with memcpy you could do the following:
env-> BitBlt (dest,n,src,n,n,1);
instead of memcpy(dest, src, n)
It's already used as such, but from what you said, data copied is not enough for it. It is however a good inspiration for rewriting the float2byte/byte2float conversion... Anybody motivated ? :)

This is not the best solution ; but if you do not include in your plugin a complete substitute of memcpy library ;this is a patch by now.
This is done by giving the env pointer to the wavelet class.

As always thanks for the great work.
Ah well, if people that actually know that well vectorization / optimization think it's great, then I guess I haven't been at least too straightforward in the implementation :)

Thanks again for your pointers.

[MfA]

Originally posted by Kurosu
I had already thought of this and wasn't really motivated to even design the whole stuff, not even code it. The tricky part is indeed the edge management: for each decomposition level you'd need to have a rather complex buffer management, to leave room for the symmetric extension done prior to the FIR filtering.

The whole buffer thing has to go, you need special case code to deal with the edges ... not a huge deal.

I bet the hardware would cope a little worse with it.

At that level not much changes about how you can optimize, you can still keep taps in registers if you want. Although usually on AMD using memory references is pretty damn fast if the values are in the LSU anyway.

While the algorithm right now is pretty straightforward, what you suggest is at quite another scale of, for a starter, debugging. Sure, truly in-place transform sounds neat, but that's just like the links at the start of this thread: several PhDs with years on their hands. I am alone, and not motivated to spend entire days on this without an immediate result. This is obvious, as you stated.

Doing it in semi inplace is an option, not a mandate.

EDIT : hell it is not even an option really, the only way to do the transform inplace is to store the high/low-pass results in an interleaved manner.

One day you are going to accumulate enough time spend on premature optimization to have been able to do it right in the first place :)

Last, the algorithm would be quite much tied to the size of the registers used, so I bet you wouldn't be able to produce a C-version that can be quite easily translated into vectorized code.

Shrug well I wont speculate about you in return, but I know I could and I know myself better ... Im not going to prove it though.

The pre-existing C code is almost impossible to vectorize well, even for the column wise operations which are always the easiest operations to vectorize. So it would be hard to do worse.

BTW does the present code do vector processing on groups of 2/4 columns (3DNow/SSE) simultaneously for the vertical transform yet?

Yes and no:
1) yes because it uses vectorization to do the convolution
2) no because it's a convolution that is done, not... lifting?
That's quite troublesome for SSE1 which doesn't have an equivalent of the pfacc (2-floats accumulator from the same register).

Vector processing is a little different from vectorization, vector processing in this context means that you convolve the filter with 2/4 sets of coefficients from neighbouring columns. Instead of working your way serially along a single column you work your way along 2/4 columns.

It makes optimization so much easier, and cache access much nicer (column wise float by float access by a copy operator is not a nice way to treat your cache). If you are already in column wise format it is almost always the most efficient way to vectorize code, hell sometimes it is worth transposing rows simply to be able to do it that way.

Marco

[Lefungus]

In one of my experiments, the transform was applied horizontally for each line, for one pixel, then this vertical line was processed. Edges was taken into account without copying buffers everywhere. Speed was equal or worst than current C version. So i'm not sure this is truly the right solution to improve it.

[Kurosu]

Originally posted by MfA
The whole buffer thing has to go, you need special case code to deal with the edges ... not a huge deal.
The best thing I can see is including space for mirrored coefficients at each level, hence a video of W*H would need a buffer of (W+nsteps*10)*H, at least to avoid the horizontal copies. It's still not what you have in mind, and indeed, the vertical copies are the most costly.

At that level not much changes about how you can optimize, you can still keep taps in registers if you want. Although usually on AMD using memory references is pretty damn fast if the values are in the LSU anyway.
The accesses are rather localized, so the memory bandwidth economy might not be the best by keeping the coefficients in the registers, but that was the most obvious, and succesfull approach.


Doing it in semi inplace is an option, not a mandate.

EDIT : hell it is not even an option really, the only way to do the transform inplace is to store the high/low-pass results in an interleaved manner.
How much interleaved (indeed, those results are stored sequentially atm).

One day you are going to accumulate enough time spend on premature optimization to have been able to do it right in the first place :)
Were it a job I'm paid for, and with people behind my back to urge me for the best efficieny, then indeed that would have been a waste. But I only work on VagueDenoiser because I enjoy it - I prefer little and quickly obtained improvements over one huge yet uncertain improvement.

Shrug well I wont speculate about you in return, but I know I could and I know myself better ... Im not going to prove it though.
Well, it seems possible, but the feasibility, to me, isn't that motivating. Lefungus code, although probably different from what you described, would be a better place where to start.

The pre-existing C code is almost impossible to vectorize well, even for the column wise operations which are always the easiest operations to vectorize. So it would be hard to do worse.
Ah well, now, am I misreading you, or did you give me a proof it isn't worth spending time for me on it? :D

Vector processing is a little different from vectorization, vector processing in this context means that you convolve the filter with 2/4 sets of coefficients from neighbouring columns. Instead of working your way serially along a single column you work your way along 2/4 columns.
I'm afraid I'd be short on registers.

It makes optimization so much easier, and cache access much nicer (column wise float by float access by a copy operator is not a nice way to treat your cache). If you are already in column wise format it is almost always the most efficient way to vectorize code,
This is interesting locally, as a 4x4 transpose function could be written for the need of it. At least this could be done and should be tried.


hell sometimes it is worth transposing rows simply to be able to do it that way.
Columns, you meant?

Right now, I have another problem, which will delay anything in that direction.

[Kurosu]

OK, I've more or less released 0.28.0, but there are things I'd like to tackle first:
- some kinds of resize before vaguedenoiser randomly crash it on the clip->GetFrame(), while clips which are of that size (but without resize) don't crash
- I noticed a major slowdown for MOD64 widthes - could Sh0dan have a look at what is responsible of such a slowdown? My bet would be the float2byte/byte2float transformations, yet...
- when width=pitch*, one can process the whole array as a continuous 1D-array; it's not yet published, but using the above method doesn't improve the problem stated above
- btw, the workspace is now ICL-able :) (though it doesn't sound worth it, only 1% improvement)

*as used already by blitblt/amd_copy in Avisynth from CVS
There are some additions:
- UV planes are now properly processed, resulting in a small speed increase
- YV12 supports interlaced video through the interlaced=true option
- all of these hasn't been extensively tested: size and colorspaces, size and interlaced mode,... I suspect there are quite some crash points left: if anybody finds one, please report

[MfA]

Originally posted by Kurosu
The best thing I can see is including space for mirrored coefficients at each level, hence a video of W*H would need a buffer of (W+nsteps*10)*H, at least to avoid the horizontal copies. It's still not what you have in mind, and indeed, the vertical copies are the most costly.

It is the easiest approach, but since I was assuming the first pass being done directly from the frame buffer you would need to create the special case code to deal with the edges anyway.

Of course a char to char copy is still relatively cheap, you just loose a little of the advantage (unless you have enough L2 to store the edge extended copy of the frame buffer, then you might be able to use it as a prefetch ... using NT load/stores during the transform as to not pollute L2).

How much interleaved (indeed, those results are stored sequentially atm).

Well if you work with a temp row you can have non interleaved results for the horizontal transform with an inplace transform. But for the vertical results you are screwed.

If you want to stay in cache and have non-interleaved high/low-pass then you cant do inplace.

Marco

BTW, I wonder how well a lapped DCT would work for thresholding.

You would just do a blocked DCT transform of the frame 2 times, the second time with the locations of the blocks shifted by (4,4). You threshold the coefficients, do the inverse transforms and weight the pixels for each block by something like :

[0 1 1 2 2 1 1 0]
[1 1 2 3 3 2 1 1]
[1 2 3 3 3 3 2 1]
[2 3 3 4 4 3 3 2]
[2 3 3 4 4 3 3 2]
[1 2 3 3 3 3 2 1]
[1 1 2 3 3 2 1 1]
[0 1 1 2 2 1 1 0] /4

Then you combine the 2 frames.

I might try that, sliding DCT+thresholding can do very high quality denoising and repeated DCT+quantization with shifted blocks is one of the best documented methods to denoise JPEG ... so this seems like something which might work, never as good as those methods of course but a lot faster. It isnt translation invariant, but then neither are the wavelets being thresholded at the moment.

The redundancy should help combat translation variance and artifacting from hard-thresholding, and with hard thresholding you could use p-domain methods to find the inflection point on the R-D curve to determine the optimal threshold (just talking to myself here for future reference ... this last bit isnt meant to be understood, if you do good for you :).

[acrespo]

Was vaguedenoiser 0.28 already release? Where?