[New motion search algorithm] Simulated annealing

[Dark Shikari]

Update: Diff is ready! The algorithm itself uses --me umh followed by the new algorithm (instead of being followed by hex). Its somewhat slower than UMH but gives better, more consistent results and is also of course much faster than ESA. The graph below speaks for itself.

After some heavy optimization (converting the entire function to integer math except for variable initialization), the speed is now merely 11% lower than UMH at --merange 16. There are plenty of optimizations possible and I'm doing some more research on the algorithm theory behind it, so it can definitely get better. I've finished the patch, which is available for download below.

Source: 1000 frames of Elephant's Dream at 1280x720.
--bframe 16 --b-pyramid --subme 7 --ref 3 --mixed-refs --bime --weightb --partitions all --direct auto --8x8dct --no-fast-pskip --crf 25
http://i4.tinypic.com/669q5vs.png

Get the patch now! (http://tjhsst.edu/~jgarrett/SA.diff)

[DeathTheSheep]

Ah, so here's the new thread after all! So the 5x5 esa didn't have an effect on UMH after it calls hex, even though it effects plain hex considerably? But despite this annealing itself benefits both similarly?

That is quite interesting...!

Slightly off-topic, I've found that increasing merange with satd/hadamard yields different results than with standard sad; whereas with sad the results of a higher merange were relatively unpredictable and led to erratic benefits, with satd they almost always lead to decreased filesize and/or increased SSIM. Maybe the same holds with increasing the "distance" which the [annealing] algorithm "prefers" to travel without affecting its other properties.

So not only a new transform, but now a new search algorithm... When used in tandem, I wonder what results they will bring? They would produce drastically different results than the x264 people are accustomed to, perhaps?

Even more interesting! What's your current progress? I look forward to your results!

[Dark Shikari]

Ah, so here's the new thread after all! So the 5x5 esa didn't have an effect on UMH after it calls hex, even though it effects plain hex considerably? But despite this annealing itself benefits both similarly?

That is quite interesting...!

Slightly off-topic, I've found that increasing merange with satd/hadamard yields different results than with standard sad; whereas with sad the results of a higher merange were relatively unpredictable and led to erratic benefits, with satd they almost always lead to decreased filesize and/or increased SSIM. Maybe the same holds with increasing the

So not only a new transform, but now a new search algorithm... When used in tandem, I wonder what results they will bring? They would produce drastically different results than the x264 people are accustomed to, perhaps?

Even more interesting! What's your current progress? I look forward to your results!
Well note that, by definition, simulated annealing cannot be better than an exhaustive search; the goal is to create an algorithm that is as close to ESA as possible without being as slow.

For example, --me esa is about 1.7% better than --me umh in my test. However, its only 0.83% better than --me umh with the simulated annealing.

The --hadamard patch is nearly ready to be finalized, but this will have a lot of development needed before I'll even post the patch file. Basically I'm looking to do two things:

a) Performance optimizations, such as storing all previous SAD scores in a hash table. This hash table would have to be extremely fast with absolutely minimal overhead.
b) Improvements to the algorithm overall. Apparently there's a professor at my college who knows quite a bit about stochastic optimization (of which simulated annealing is a common type), so hopefully she'll be able to enlighten me more on how to better implement this motion search.

[DeathTheSheep]

Of course, by definition, nothing can be better than an exhaustive search, because you can't possibly search more than everything...

But I'm very impressed by these results. Is that (slow) code ready to stick in? Or do you have a more recent version underway?

[Dark Shikari]

Of course, by definition, nothing can be better than an exhaustive search, because you can't possibly search more than everything...

But I'm very impressed by these results. Is that (slow) code ready to stick in? Or do you have a more recent version underway?
Updated with the latest non-testing version (I'm testing various modifications to it, most of which turn out to suck :p ).

The "memory" feature as you may notice is an array-based memory system, which means lookups are order O(n), a horrible solution. That's why its only size 3; any larger and its slowness outweighs its usefulness.

Note that with --hadamard, since COST_MV takes so much longer, a larger memory is worthwhile.

[Sharktooth]

why arrays?!?

[Dark Shikari]

why arrays?!?Yes, shoot me. It was something I hacked together in a few seconds.

I would think the best solution would be something like a hash table, but is there a built-in C library for that? And is its hidden constant small enough to make it worthwhile?

[DeathTheSheep]

What the heck is "COST_MV_SA(neighbor1,neighbor2)"? Not SAD, not SATD?

And where do you get probability(arg,arg2) from? Is it some function in some library needed to include?

[Dark Shikari]

What the heck is "COST_MV_SA"? Not SAD, not SATD?

And where do you get probability(arg,arg2) from? Is it some function in some library needed to include?

Oops, forgot to paste that part. Updated.

The modified COST_MV is simply so that it uses an existing "cost" variable instead of declaring a new one. SA just stands for simulated annealing, explaining where it is used rather than what it does.

Also: WOW. A simple modification has the boost over --me hex up to 2.21%... and rising as I improve the code. In a bit I'll re-run UMH and see how much that is being helped.

[DeathTheSheep]

Hmm, this really looks decent (even though I was never one to understand the difference between a "hacky" method and an "ingenious" one--arrays, hash tables or otherwise).

I'll give this a shot, alright? :)

[Dark Shikari]

Hmm, this really looks decent (even though I was never one to understand the difference between a "hacky" method and an "ingenious" one--arrays, hash tables or otherwise).

I'll give this a shot, alright? :)
The array is the hacky bit, and is pretty useless at the moment except with --hadamard. I might as well remove it.

The method itself is somewhat hackily written but overall its a tried-and-true algorithm.

[DeathTheSheep]

Ah, thanks. I learned a new phrase: "hackily written." :p

Utterly OT, but would you mind if I asked you what your area study is (or major, field, etc)?

[Dark Shikari]

Utterly OT, but would you mind if I asked you what your area study is (or major, field, etc)?Not at all. I'm planning to double-major physics and computer science, because I'm somewhat nuts. I'm not far enough along in college just yet to make the final decision, though by the time I do I'll likely have plenty of prerequisites under my belt.

I'm currently studying at Harvey Mudd College (http://www.hmc.edu/).

Also, here's an interesting update with the algorithm: ME UMH and then my algorithm is slightly faster than running my algorithm alone, and gives better quality. I'm guessing this is because my algorithm takes longer to get near the best result, and combining it with UMH lowers the time it takes for that to occur.

[Sharktooth]

Yes, shoot me. It was something I hacked together in a few seconds.

I would think the best solution would be something like a hash table, but is there a built-in C library for that? And is its hidden constant small enough to make it worthwhile?
maybe this (http://www.burtleburtle.net/bob/hash/doobs.html) could be what you need

[Dark Shikari]

maybe this (http://www.burtleburtle.net/bob/hash/doobs.html) can be what you need
Seems too complicated, and the hash function is overkill for this purpose (and will probably eat up too many clock cycles).

I need something that sacrifices hash quality (i.e. it has collisions often) for hash speed.

Edit: Nevermind, seems that page includes some! I guess I can try that, though it is a bit complicated.

[Sharktooth]

you can also try a hash table with a bloom filter... however im not an expert in hash tables and never analyzed the complexity and memory usage of the common hashing functions, but i know array lookups are a pain in the...

[DeathTheSheep]

ME UMH and then my algorithm is slightly faster than running my algorithm alone, and gives better quality.
Confirmed.

When merange is increased (in the current incarnation), no significant increase in SSIM is observed. This is as predicted, since your algorithm seems largely independent of merange, correct?

the boost over --me hex up to 2.21%... and rising
Now that's what I like to hear. :D

[Dark Shikari]

Confirmed.

When merange is increased (in the current incarnation), no significant increase in SSIM is observed. This is as predicted, since your algorithm seems largely independent of merange, correct?Yes, it is entirely independent of merange. Merange should only affect UMH at this point.

[Kopernikus]

Hi,

you could try to use a different pseudo random number generator. From my experience the stdlib rand ist rather slow, and as we have a lot of rand() calls that may have a significant impact on speed.

A usually very good and fastt prng is the shift register generator. Start with a seed k_0 and:

tmp = k_n ^ (k_n >> 15);
k_(n+1) = tmp ^ (tmp << 17);

The 15 and 17 are magic values that work good for 32 bit integers.

And here are some useful informations and very fast prngs:

http://agner.org/random/

[Dark Shikari]

Hi,

you could try to use a different pseudo random number generator. From my experience the stdlib rand ist rather slow, and as we have a lot of rand() calls that may have a significant impact on speed.

A usually very good and fastt prng is the shift register generator. Start with a seed k_0 and:

tmp = k_n ^ (k_n >> 15);
k_(n+1) = tmp ^ (tmp << 17);

The 15 and 17 are magic values that work good for 32 bit integers.

And here are some useful informations and very fast prngs:

http://agner.org/random/I'll try that; the rands don't actually have to be very random, only decently probabilistic, so that should work fine.

[Dark Shikari]

OK, this is bad. I don't know what I'm doing wrong but something here is really, really screwed up.

Code section:

float tempFactor = 1.05;
unsigned int curRand=rand();
curRand = shiftRand(curRand);
for(temperature = threshold;temperature >= 1.0;temperature /= 1.05)
{
gives much better quality than
float tempFactor = 1.05;
unsigned int curRand=rand();
curRand = shiftRand(curRand);
for(temperature = threshold;temperature >= 1.0;temperature /= tempFactor)
{

What the fuck? :confused: This is completely nonsensical, and turning off optimization changes nothing.

[Sharktooth]

?!?
place a watch on tempfactor and see if it's = 1.05 at runtime...

[Dark Shikari]

?!?
place a watch on tempfactor and see if it's 1.05 at runtime...
It is: I ran a printf to print out temperature throughout the entire runthrough and its exactly equivalent! :confused:

This has stumped me for a few hours now and regardless of the changes I make it keeps coming up. In particular, its stopping me from making the temperature rate of change variable, which is required for implementing me_range as a parameter to my function.

[Sharktooth]

well... that's a nonsense then... or maybe you found a compiler bug :p
is tempfactor going to be modified? if not try defining it as a constant...

[Dark Shikari]

well... that's a nonsense then... or maybe you found a compiler bug :p
Of course it is possible that my printf debug statements somehow are changing the behavior of the code... or it could have something to do with the fact that I'm using floats (though I am liberally using x264_emms()!)
is tempfactor going to be modified? if not try defining it as a constant...See above, it needs to be modified for higher merange values. The idea is that the "merange" in the SA algorithm represents its length of runtime.

Also, the new random function gave roughly a 6% speed boost.

[Sharktooth]

there are 3 possible causes:
1 - compiler bug
2 - the memory space where the variable is allocated gets overwritten after you display it with the printf (and that's the worst case scenario)
3 - system unstabilities

[Dark Shikari]

there are 3 possible causes:
1 - compiler bug
2 - the memory space where the variable is allocated gets overwritten after you display it with the printf (and that's the worst case scenario)
3 - system unstabilities
It is possible there is some sort of memory overflow somewhere that is farking with things. Its happened to me before.

I'm running some tests to try to find the problem.

[Dark Shikari]

Issue solved, it appears to be two separate issues.

1. For some reason, the problem I posted occurred. It has now disappeared.

2. In addition, i_me_range, which I was trying to base tempFactor off of, is not constant.

Its quite possible that lowering tempFactor is bad for quality, too.

I may end up having the SA algorithm's method be constant, while having merange only affect the initial UMH.

[akupenguin]

Don't divide. Multiplication is faster.
probability() doesn't need to check against 0 or 1. 0 can't ever happen due to the exp, and the rest of the code should work fine with probabilities >1.
The choice of which neighbor to try could be a table rather than a series of ifs (I don't know which is faster).
memoryContains() could be a single table lookup, though that might be offset by the cost of emptying the table to begin with. See x264_me_refine_qpel_rd().

[Manao]

Are you doing a emms after every satd calls ? That could explain random behaviors when floats are concerned.

[akupenguin]

No, he does a emms before every float call. Which is the appropriate way in a program that uses lots of mmx and little float.

[Dark Shikari]

Don't divide. Multiplication is faster.
probability() doesn't need to check against 0 or 1. 0 can't ever happen due to the exp, and the rest of the code should work fine with probabilities >1.
The choice of which neighbor to try could be a table rather than a series of ifs (I don't know which is faster).
memoryContains() could be a single table lookup, though that might be offset by the cost of emptying the table to begin with. See x264_me_refine_qpel_rd().
I've removed memory altogether; a number of implementations simply failed to do well. I can probably later optimize it by using a very very fast hash table.

You're right about the probability; I've removed that.

You're right about the multiplication/division, though I assume its less intensive for floats than for integers. I'll post the modified version soon. I'm implementing a lookup table instead of the if/else crap, one should always avoid branches when possible.

[akupenguin]

branch-free neighbor decision (possibly tweak mask and shift if some bits of the prng are more random than others):
int neighbor = (rand() & 0x7fff) * 3 >> 14;
int neighborX = curX + hex2[neighbor][0];
int neighborY = curY + hex2[neighbor][1];

[Dark Shikari]

branch-free neighbor decision (possibly tweak mask and shift if some bits of the prng are more random than others):
int neighbor = (rand() & 0x7fff) * 3 >> 14;
int neighborX = curX + hex2[neighbor][0];
int neighborY = curY + hex2[neighbor][1];
Hmm that's a good idea; I was assuming the compiler would optimize out the IDIV I was using into a series of bitshifts, but doing it manually is probably more reliable.

I had to shift down the random value by 17 since my current rand algorithm is 32-bit unsigned int, but thats just one op.

Edit: Nevermind, apparently the IDIV is actually slightly faster than your ops. I am guessing this is because it can be parallelized--the IDIV is run, and because of the lack of data-dependency, shiftRand() can be run afterwards while the IDIV is being calculated.

[Dark Shikari]

Okay, here's the current results. Its about 15-25% slower than UMH depending on the merange used.

http://i7.tinypic.com/5zc5o5g.png

Notice the quality seems a lot more stable than UMH, which is somewhat finicky (SSIM dropped a whole bunch for little gain at certain meranges).

The % numbers are the improvement over plain --me hex --merange 16.

(Blue = SA, Purple = UMH)

[DeathTheSheep]

What's blue and what's purple? :p

[edit] I think the purple is UMH, now that I read more carefully.

Also note that the erratic improvements to UMH might be due to the originally erratic behavior of UMH with varying merange. UMH merange 64 is worse than UMH merange 16 sometimes, which is worse than UMH at merange 128, etc.

Funny stuff.

[Dark Shikari]

What's blue and what's purple? :p

[edit] I think the purple is UMH, now that I read more carefully.

Also note that the erratic improvements to UMH might be due to the originally erratic behavior of UMH with varying merange. UMH merange 64 is worse than UMH merange 16 sometimes, which is worse than UMH at merange 128, etc.

Funny stuff.Whatever the problem with UMH is, simulated annealing (blue) seems to solve it and gives a very smooth curve. :cool:

I'll make a patch to add this as --me SAU (Simulated Annealing w/UMH). It'll serve the job as an algorithm better than UMH but worse then ESA.

[DeathTheSheep]

Sounds good! I look forward to the patch. Do you think you'll have it done in the next hour? Or month?

...but then what's the purple curve?!

[Dark Shikari]

Sounds good! I look forward to the patch. Do you think you'll have it done in the next hour? Or month?

...but then what's the purple curve?!
Purple curve is ordinary UMH (which calls Hex once its done). Blue curve is UMH, except it calls SA once its done.

I'm not sure whether to make a separate patch for this or simply lump it in with the --hadamard patch. It'll probably be a day or two because I have to clean up the code a good bit.

[Sagekilla]

Erm, how exactly will this fit in with your hadamard patch? Will it be compatible with it too?

[Dark Shikari]

Erm, how exactly will this fit in with your hadamard patch? Will it be compatible with it too?
Yes, it is related in that both affect the motion search, but in terms of code they are entirely separate and are fully compatible.

Basically any motion search calls a metric function, COST_MV, a whole lot. My motion search still calls COST_MV a lot. --hadamard modifies what COST_MV does, independent of what calls it and where.

[Sharktooth]

i would do separate patches.

[Dark Shikari]

i would do separate patches.That's fine then, it shouldn't be a problem.

[Sagekilla]

Mmm, well, I'll be patiently waiting for you to release an SA patched x264 build. Looking at that simple graph, it looks like I'll benefit more from SA then the hadamard patch. I already did a little informal testing of my own and the quality boost per speed loss was too much for me to use it on huge encodes. I think I had a 50% speed loss w/ 50 KB smaller video size. (13872 KB vs 13839 KB)

Keep up the good work with all these patches though, I see tons of potential in my insanely-long-15-plus-hour-encodes if you get these fully optimized. :)

[DeathTheSheep]

@Sagekilla: So you're not really a "recovering x264aholic" after all! :p

[Sagekilla]

@Sagekilla: So you're not really a "recovering x264aholic" after all! :p

Shh! They don't know that :p But, let's not get off topic here!

Like I said, I'd really love to see a patched (667b) version so I can give it a go and see how much of a difference I can squeeze out.

[Sergey A. Sablin]

Edit: Nevermind, apparently the IDIV is actually slightly faster than your ops. I am guessing this is because it can be parallelized--the IDIV is run, and because of the lack of data-dependency, shiftRand() can be run afterwards while the IDIV is being calculated.

just wondering - how did you manage to measure such a small ops within such a huge module as H.264 encoder? (anyway such a difference in speed between AND + SHIFT and IDIV I ever could imagine maybe only related to either precision of measurement or due to random nature of algorithm)

[Dark Shikari]

just wondering - how did you manage to measure such a small ops within such a huge module as H.264 encoder? (anyway such a difference in speed between AND + SHIFT and IDIV I ever could imagine maybe only related to either precision of measurement or due to random nature of algorithm)
x264 is huge, but the motion search algorithm makes up a huge percentage of the time spent. This means that a very small change in the motion search algorithm, especially an op run on every single step of a for loop, will affect runtime enough that it can be measured.

To be exact, the change was about -1% speed. Not a lot, but on the other hand enough to show that getting rid of the IDIV was pointless.

[Sergey A. Sablin]

x264 is huge, but the motion search algorithm makes up a huge percentage of the time spent. This means that a very small change in the motion search algorithm, especially an op run on every single step of a for loop, will affect runtime enough that it can be measured.

To be exact, the change was about -1% speed. Not a lot, but on the other hand enough to show that getting rid of the IDIV was pointless.

I see, I see... if it is 1%, than I think you can measure the time spent "exactly" on these instructions in seconds per instruction - just for fun.

[Dark Shikari]

I see, I see... if it is 1%, than I think you can measure the time spent "exactly" on these instructions in seconds per instruction - just for fun.Certainly not exactly, but if there's a speed drop due to optimization X without an associated increase in quality or decrease in bitrate, X is obviously not worth doing.

My explanation of why the speed drop occurred was just an educated guess. It doesn't really matter anyways.

[Dark Shikari]

Diff is ready and is available in the original post. :cool: A nice, much more detailed graph is available also.

[foxyshadis]

Mind posting to the x264 list for the benefit of those who don't regularly check the forum? (As an aside, Gabriel Bouvigne has recently posted some very interesting b-frame patches there that might interest you.)

[akupenguin]

just wondering - how did you manage to measure such a small ops within such a huge module as H.264 encoder? (anyway such a difference in speed between AND + SHIFT and IDIV I ever could imagine maybe only related to either precision of measurement or due to random nature of algorithm)
If there were an actual IDIV then the difference would be huge. IDIV takes 42 cycles on core2 or k8, which is more than a whole 16x16 SAD. The compiler can optimize away the division, though it's not quite as good as hand optimization when I know that I'm dealing with random numbers and thus can make optimizations that just have the same effect rather than the same equation.

uint32_t div(uint32_t x)
{ return x / 715827883; }

uint32_t mul(uint32_t x)
{ return (uint64_t)x * 6 >> 32; }

uint32_t mask(uint32_t x)
{ return (x & 0xffffff) * 3 >> 23; }


<div>:
mov eax, 0xbfffffff
mul edi
shr edx, 0x1d
mov eax, edx
ret

<mul>:
mov eax, 0x6
mul edi
mov eax, edx
ret

<mask>:
and edi, 0xffffff
lea rax, [rdi+rdi*2]
shr eax, 0x17
ret


On a core2, running 100 inlined copies, feeding output to input so as to measure latency, and recording rdtsc, I get:
div() takes 5 cycles
mul() takes 4 cycles
mask() takes 3 cycles

[Sharktooth]

is this going to get its place in x264 svn or is it just experimental?

[Dark Shikari]

If there were an actual IDIV then the difference would be huge. IDIV takes 42 cycles on core2 or k8Are you sure? this (http://www.behardware.com/articles/623-5/intel-core-2-duo-test.html) says it takes 17 cycles on a Core2.

But yeah, I assumed the compiler optimized it away somehow.

[Dark Shikari]

Optimization progress:

1. Slowest parts of the function identified. EMMS is 6 clock cycles, and FMUL is 5 clock cycles. EXP is much worse; it uses F2XM1, which uses more clock cycles alone than an entire SAD! I'm doing an approximation assembly optimization of it at the moment.

2. EXP optimized somewhat using the following GFDL/CC code from here (http://t-a-w.blogspot.com/2006/06/docking-assembly.html):

inline float fast_exp2_t2(float x)
{
float res;
asm (
"fld %%st(0) \n\t" // x x 0.5
"frndint \n\t" // r(x) x 0.5
"fsubr %%st, %%st(1) \n\t" // r(x) f(x)=y 0.5
"fxch %%st(1) \n\t" // y r(x) 0.5
"fldln2 \n\t" // ln2 y r(y) 0.5
"fmulp \n\t" // ln2*y r(y) 0.5
"fld %%st(0) \n\t" // ln2*y ln2*y r(y) 0.5
"fmul %%st(3) \n\t" // ln2*y/2 ln2*y r(y) 0.5
"fld1 \n\t" // 1 ln2*y/2 ln2*y r(y) 0.5
"faddp \n\t" // (1+ln2*y/2) ln2*y r(y) 0.5
"fmulp \n\t" // (1+ln2*y/2)*ln2*y r(y) 0.5
"fld1 \n\t"
"faddp \n\t"
"fscale \n\t"
"fstp %%st(1)\n\t"
:"=t"(res)
:"0"(x), "u"(0.5)
);
return res;
}

Speed boost: About 6% overall. Quality did change since the assembly isn't 100% accurate, but within the margin of error (quality actually rose a tiny bit).

3. Next step: optimize out the division in the probability section by dealing with the inverse of temperature, not the temperature (so nothing other than FMULs are ever needed). Result: 1-2% speed boost with very minimal effect on quality (due to different rounding).

[akupenguin]

Are you sure? this (http://www.behardware.com/articles/623-5/intel-core-2-duo-test.html) says it takes 17 cycles on a Core2.
Agner (http://agner.org/optimize/) says between 18 and 42 cycles on a core2, depending on the magnitude of the numbers involved. My experiment concurs.
AMD (http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF) says exactly 42 cycles on a k8.

EXP is much worse; it uses F2XM1, which uses more clock cycles alone than an entire SAD!
glibc expf() = 39 cycles in 64bit mode, or 177 cycles in 32bit mode
glibc exp() = 100 cycles in 64bit mode, or 171 cycles in 32bit mode
fast_exp2_t2() = 85 cycles.
(still core2)

[DeathTheSheep]

Is there a reason you used b-pyramid twice in the same commandline, or that you specifically called --deblock 0:0 (it's on by default)? I don't want to be too picky, but I also don't want to let anything slip by unexplained. ;)

if(h->param.analyse.i_me_method==X264_ME_SAU) h->mb.i_me_method = X264_ME_SAU_ONLY;
When will the codec lapse into sau_only mode?

[akupenguin]

inline float fast_exp2_sse2(float x)
{
static const float ss_bias = 12582912.0; // 3<<22
static const float ss_ln2 = 0.693147180559945;
static const float ss_1 = 1.0;
static const float ss_0_5 = 0.5;
float t, u;
asm volatile (
"movaps %0, %1 \n\t"
"addss %3, %0 \n\t"
"movaps %0, %2 \n\t"
"subss %3, %0 \n\t" // round(x)
"pslld $23, %2 \n\t" // round(x) in the exponent
"subss %0, %1 \n\t" // frac(x)
"mulss %4, %1 \n\t" // frac(x)*ln2 = y
"movaps %1, %0 \n\t"
"mulss %1, %1 \n\t" // y*y
"addss %5, %0 \n\t" // 1+y
"mulss %6, %1 \n\t" // y*y*.5
"addss %1, %0 \n\t" // 1+y+y*y*.5
"paddd %2, %0 \n\t" // (1+y+y*y*.5)<<round(x)
:"+x"(x), "=x"(t), "=x"(u)
: "m"(ss_bias), "m"(ss_ln2), "m"(ss_1), "m"(ss_0_5)
);
return x;
}
10 cycles, same precision as fast_exp2_t2()

[Dark Shikari]

Is there a reason you used b-pyramid twice in the same commandline, or that you specifically called --deblock 0:0 (it's on by default)? I don't want to be too picky, but I also don't want to let anything slip by unexplained. ;)
Me being absent-minded, probably.

if(h->param.analyse.i_me_method==X264_ME_SAU) h->mb.i_me_method = X264_ME_SAU_ONLY;
When will the codec lapse into sau_only mode?
The purpose of this is, in my testing, using HEX in slicetype.c for the frame decision gives substandard results when SAU is enabled. So I added an extra bit to swap to SAU instead of HEX for the frametype decision if SAU is enabled.
inline float fast_exp2_sse2(float x)
{
static const float ss_ln2 = 0.693147180559945;
static const float ss_bias = 12582912.0; // 3<<22
static const float ss_1 = 1.0;
static const float ss_0_5 = 0.5;
float t, u;
asm volatile (
"movaps %0, %1 \n\t"
"addss %4, %0 \n\t"
"movaps %0, %2 \n\t"
"subss %4, %0 \n\t" // round(x)
"pslld $23, %2 \n\t" // round(x) in the exponent
"subss %0, %1 \n\t" // frac(x)
"mulss %3, %1 \n\t" // frac(x)*ln2 = y
"movaps %1, %0 \n\t"
"mulss %1, %1 \n\t" // y*y
"addss %5, %0 \n\t" // 1+y
"mulss %6, %1 \n\t" // y*y*.5
"addss %1, %0 \n\t" // 1+y+y*y*.5
"paddd %2, %0 \n\t" // (1+y+y*y*.5)<<round(x)
:"+x"(x), "=x"(t), "=x"(u)
:"m"(ss_ln2), "m"(ss_bias), "m"(ss_1), "m"(ss_0_5)
);
return x;
}
10 cycles, same precision as fast_exp2_t2()
Nice, I like it, though it requires SSE2.

What would you think of doing the following:
1. Removing all floating point operations, replace with integer ops.
2. Using a lookup table with a few hundred entries for exp, to avoid the otherwise obligatory float.
?

Edit: Your code gives me an "error: impossible constraint in 'asm'".

[DeathTheSheep]

Well, if this SSE2 monster makes it into today's patch, I sense some blazing fast hadamard annealment coming up for me!

[Sharktooth]

What would you think of doing the following:
1. Removing all floating point operations, replace with integer ops.
go for it! :D

[Dark Shikari]

go for it! :D
/hardcodes 600-length lookup table into me.h :p

[akupenguin]

/hardcodes 600-length lookup table into me.h :p
Surely you mean a power of 2. Otherwise you can't quickly mask off the fractional part from the shift.
And you can get 1% precision with 32 entries. (Though unlike TAW's algo it's 1% off everywhere, not just worst case).

Your code gives me an "error: impossible constraint in 'asm'".
Compile with -mfpmath=sse -msse. Otherwise gcc doesn't know how to store floats in xmm regs. (Or use x86_64 where sse is on by default, or use nasm.)

The purpose of this is, in my testing, using HEX in slicetype.c for the frame decision gives substandard results when SAU is enabled. So I added an extra bit to swap to SAU instead of HEX for the frametype decision if SAU is enabled.
Strange. Using HEX in slicetype.c should make identical slicetype and ratecontrol decisions regardless of what ME method is used for the real encode. Certainly a better ME method is better, but I don't see how SAU_only can be a good speed-quality tradeoff in slicetype but a bad tradeoff in real encoding.

[Dark Shikari]

Surely you mean a power of 2. Otherwise you can't quickly mask off the fractional part from the shift.
And you can get 1% precision with 32 entries. (Though unlike TAW's algo it's 1% off everywhere, not just worst case).
32 entries won't get 1% off... it may get 1% off the input, but not the output.

My exponent function is as follows:
-inf -> -6: 0
-6 -> 0: entry every 0.01 in the table, for 600 total entries. All entries are scaled by appropriate integer amounts as to make bitshifting possible instead of division. I chose the number of entries so as to make each entry about 1% higher than the previous one, for a max error of 1%. They're scaled so that 1 probability is 2^31.
0 -> inf: 2^31


Strange. Using HEX in slicetype.c should make identical slicetype and ratecontrol decisions regardless of what ME method is used for the real encode. Certainly a better ME method is better, but I don't see how SAU_only can be a good speed-quality tradeoff in slicetype but a bad tradeoff in real encoding.
Its good in real encoding also--its just that its not as good as UMH + SA.

What I noticed was that when I was modifying the HEX algorithm to create the SA algorithm, I was using it in place of Hex. Then, when I placed it into the main code as a separate method, the quality wasn't nearly as high; soon I noticed the problem was that Hex was still being called by slicetype.c. Changing that brought the quality back up.

I assume HEX gives different results from SAU in terms of frame decision for the same reason the quality graphs in the original post are so different; they're related different algorithms and so give different results, as compared to UMH and ESA, for example, which seem highly correlated.

[akupenguin]

32 entries won't get 1% off... it may get 1% off the input, but not the output.
Store only exp2(-1) .. exp2(0) in the table. Get the rest by shifting.

[Dark Shikari]

Store only exp2(-1) .. exp2(0) in the table. Get the rest by shifting.Ah, that's definitely a good idea. Uses one more op but saves coding space and memory, so not a big deal.

Anyways, I've given up on pure integer ops because there is at least one case in which going pure-integer requires an integer division with a dynamic denominator, which means the compiler can't optimize it out.

So I'll use integers when possible but otherwise use floats. I'll also make sure to avoid float -> int conversions and the like.

Edit: Wait a minute, we're dealing with E here as our exponent... wouldn't that mean you can't do the shift trick? Of course I could switch to exp2 and see how it affects the performance.

[akupenguin]

Anyways, I've given up on pure integer ops because there is at least one case in which going pure-integer requires an integer division with a dynamic denominator, which means the compiler can't optimize it out.
That's the division by temperature, right? Instead of starting temperature at threshold and decreasing it until 1.0, start 1/temperature at 1/threshold and increase until 1.0, and multiply in the probability equation.

Wait a minute, we're dealing with E here as our exponent... wouldn't that mean you can't do the shift trick? Of course I could switch to exp2 and see how it affects the performance.
2^(x*log2(e)) = e^x
So start at log2(e)/threshold and increase until log2(e). But then, your starting temperature contains an arbitrary factor anyway, so just change the factor. And afaict there's nothing special about 1.0 as an end condition either.

[Dark Shikari]

That's the division by temperature, right? Instead of starting temperature at threshold and decreasing it until 1.0, start 1/temperature at 1/threshold and increase until 1.0, and multiply in the probability equation.
Already did that earlier. The problem here is simple: temperature decreases by X% each time (or the inverse temperature increases by X%). This can be done very easily with floats but requires an integer division.

[akupenguin]

multiply by 1+epsilon instead of by 1-epsilon.
i.e. tempFactor = fixed_point(1+0.05*convergenceSpeed);

[Dark Shikari]

Apparently switching to EXP2 increases quality slightly anyways, so no need for the extra multiply op.

[Dark Shikari]

multiply by 1+epsilon instead of by 1-epsilon.
i.e. tempFactor = fixed_point(1+0.05*convergenceSpeed);
Doing that already, but how does that avoid the division?

Either you're doing temperature = temperature * 1.05 (floating point) or temperature = temperature + temperature / 20 (integer divide).

[akupenguin]

Haven't you ever heard of fixed-point?
temperature = (temperature * tempFactor) >> 16;
if you want a factor of 1.05, then tempFactor = round(1.05*(1<<16)) = 68813.

[Dark Shikari]

Haven't you ever heard of fixed-point?
temperature = (temperature * tempFactor) >> 16;
if you want a factor of 1.05, then tempFactor = round(1.05*(1<<16)) = 68813.
But doesn't that require knowing the multiplier ahead of time, which doesn't work since me-range is determined by the user?

Or do you mean to use round in the program itself? I already did try it integer-wise (with the divides) and the loss of precision seemed to harm quality.

The issue is that InverseTemperature cannot get larger than MAX_INT / (MAX DIFFERENCE BETWEEN TWO SADs). This means the difference between InverseTemperatures in runs of the for loop get very truncated at low values of InverseTemperature.

I'll try again though.

[akupenguin]

If 16bit fixed-point isn't enough, use more bits. The intermediate values in a multiplication can go up to uint64 without adding a significant computation cost, as long as you rightshift the result and store it back in a int32 or uint32 variable.

[Dark Shikari]

If 16bit fixed-point isn't enough, use more bits. The intermediate values in a multiplication can go up to uint64 without adding a significant computation cost, as long as you rightshift the result and store it back in a int32 or uint32 variable.
Really? Now that is nice... :cool:

Didn't know the compiler took advantage of those extra 32 bits in the result.

[Dark Shikari]

Well, it would be nice, but your idea isn't working. I set the value to >> 24 and used a simple printf and I'm getting a nice wraparound. Its definitely not working in the code either. I managed to get >> 15 using an unsigned int, but any higher won't work.

Anyways, doing a final test and then moving to implement the new lookup table.

[akupenguin]

Post the code that wraps.

[Dark Shikari]

float convergenceSpeed = ((float)16.0 / i_me_range);
unsigned int tempFactor = round((1+0.05*convergenceSpeed)*(1<<14));
int terminationFactor = (int)(15.0 / convergenceSpeed);
unsigned int curRand=rand(); //Initialize fast random number generator.
static const int hexTable[6][2] =
{
{ -2, 0 },
{ -1, 2 },
{ 1, 2 },
{ 2, 0 },
{ 1, -2 },
{ -1, -2 },
};
shiftRand(curRand);
for(inverseTemperature = threshold;inverseTemperature <= 65536;inverseTemperature = (inverseTemperature*tempFactor)>>14)

If I set 14 to, say, 20, it wraps.

[akupenguin]

You can't just multiply two int32 values and expect to keep the extra bits. C defines the result of int32*int32 to be int32, and thus throws away the extra bits even though the IMUL instruction can compute them. You have to cast one or more of the values to int64 before the multiplication. Then the other value will be implicitly upgraded, and the operation is technically an int64*int64 -> int64. x86 can't do int64*int64 efficiently in general, but the compiler is smart enough to know that these int64 values were cast from int32 and thus fit in 32bit registers.
inverseTemperature = ((uint64_t)inverseTemperature*tempFactor)>>20

[Dark Shikari]

You can't just multiply two int32 values and expect to keep the extra bits. C defines the result of int32*int32 to be int32, and thus throws away the extra bits even though the IMUL instruction computed them. You have to cast one or more of the values to int64 before the multiplication. Then the other value will be implicitly upgraded, and the operation is technically an int64*int64 -> int64. x86 can't do int64*int64 efficiently in general, but the compiler is smart enough to know that these int64 values were cast from int32 and thus fit in 32bit registers.
inverseTemperature = ((uint64_t)inverseTemperature*tempFactor)>>20Ahhhhh... that makes sense.

Anyways, the lookup table code is finished, I'll add your uint_64 fix after I make sure this is working.

[Dark Shikari]

Table lookup is done and working, current speed is only 11% lower than UMH. :cool:

And, oops, I forgot to remove x264_emms(), since I got rid of all the floats; so it should get a little bit faster.

[Dark Shikari]

And the new patch is up. It doesn't include the uint_64 fix; I'll try that now and see if it makes any difference.

Update: Now that its complete, I've run it on some other source samples... and its unfortunately not as good as it was on Elephant's Dream.... even other samples of Elephant's Dream than the 1000 frames I chose for my test sample.

I'm probably going to have to tune the parameters more to make it generally useful. :(

[DeathTheSheep]

Uh, might sound like a stupid question relating to variable scope and the like, but in cost_mv(), do you want to take away the "int" designator? Very different results occur with and without it, just to let you know...

It just updates an older 'cost' declared before, but I was wondering if this is what you wanted.

[Dark Shikari]

Uh, might sound like a stupid question relating to variable scope and the like, but in cost_mv(), do you want to take away the "int" designator? Very different results occur with and without it, just to let you know...

It just updates an older 'cost' declared before, but I was wondering if this is what you wanted.
I took it out because without the int designator, you can access the cost variable after COST_MV is called, but with it, due to the brackets, cost becomes entirely an internal variable.

This does not affect any other function, but SAU requires the cost to be accessible after the call.

Also, after some testing, it appears my disappointment was a bit premature--SAU does decently well on some sources and not as well on others... much like most of the other ME algorithms.

[DeathTheSheep]

Does it behave in a similar pattern regardless of whether or not satd is used?

[Dark Shikari]

Does it behave in a similar pattern regardless of whether or not satd is used?Actually, I have not tried that, and --hadamard may affect it also because it likely will change the manner in which the motion estimation function varies.

I'll run some tests on that tonight.

[DeathTheSheep]

It looks like SAD SEA isn't all too much slower than SATD SAU (just sau with hadamard, no changes). Just to note. :)

But I speculate that if tweaked enough, SATD SAU at higher meranges would come pretty close to SATD ESA at range 16, but faster. Sound like a new goal? ;)

[Dark Shikari]

It looks like SAD SEA isn't all too much slower than SATD SAU (just sau with hadamard, no changes). Just to note. :)

But I speculate that if tweaked enough, SATD SAU at higher meranges would come pretty close to SATD ESA at range 16, but faster. Sound like a new goal? ;)
SAU has huge optimization potential.

One idea is to do to it what has been done to ME-HEX; disallow moves that send the function back on itself. This would save a whole boatload of clock cycles.

[Dark Shikari]

Oh god, bug found :p

if(numIterationsSinceBest >= terminationFactor){curX=bmx;curY=bmy;prevCost=bcost;numResets++}

to

if(numIterationsSinceBest >= terminationFactor){curX=bmx;curY=bmy;prevCost=bcost;numResets++;numIterationsSinceBest=0;}

Yeah, when doing some internal diagnostics I noticed it would reset three times in a row and then quit... I wondered why :rolleyes:

[Dark Shikari]

Another massive bug... the search wasn't updating correctly and was resetting to the wrong point in the search, causing it to get way away from where it should be :rolleyes:

Hopefully after all this the algorithm will be much, much better.

[Sharktooth]

Dark Shikari is on fire... :)

[Dark Shikari]

Dark Shikari is on fire... :)I'm using a simple but effective bugfinding method:

For random motion searches:
1. Print out a full ESA of the ME space.
2. Run the algorithm, print out where the algorithm is at each step of it.
3. If its doing whacko stuff, ask yourself why.

[DeathTheSheep]

Dark Shikari is on fire... :)

You said it, Sharktooth. :eek:

[akupenguin]

The graph in the first post would be more readable if merange were labeled in multiples of 4 like it was sampled.

[DeathTheSheep]

Yeah, but I don't think that graph is valid anymore, given that the results were wrong due to (big) bugs in the algorithm.

But yes, I was wondering how 17.5 got on there. :rolleyes:

[Dark Shikari]

Yeah, but I don't think that graph is valid anymore, given that the results were wrong due to (big) bugs in the algorithm.

But yes, I was wondering how 17.5 got on there. :rolleyes:
Yeah, it was just what OpenOffice labelled by default.

When I make the new graph I'll fix that, but there's a lot of tuning to do. The new graph will have SATD on it also.

[TheRyuu]

If anyone cares, I built this with the patch (along with others).

This build has hadamard patch, simulated annealing patch, thread pool (version 4a) patch, and the brdo AQ patch (the new AQ patch).

If I'm missing any patches that should be in, tell me (I like patched builds :))
Finally got all the patches to actually...well...patch! :p

The patch versions used are the newest ones that were in the OP in both threads at the time this was posted.

Never tried it and I hope that it works. I did receive a few errors when patching (no idea why...) but it built just fine so here it is:
x264 had/SA/AQ/TP x86 generic (http://www.sendspace.com/file/2ouu9q) (you need mmx support to run this)
*Please don't download this. It's bad.*

Enjoy (if it works)

If it works, you can put it in the stick for both this thread and the hadamard thread I guess if people want to try it.
But like I said, see if it works first :p

[Dark Shikari]

If anyone cares, I built this with the patch (along with others).

This build has hadamard patch, simulated annealing patch, thread pool (version 4a) patch, and the brdo AQ patch (the new AQ patch).

If I'm missing any patches that should be in, tell me (I like patched builds :))
Finally got all the patches to actually...well...patch! :p

The patch versions used are the newest ones that were in the OP in both threads at the time this was posted.

Never tried it and I hope that it works. I did receive a few errors when patching (no idea why...) but it built just fine so here it is:
x264 had/SA/AQ/TP x86 generic (http://www.sendspace.com/file/2ouu9q) (you need mmx support to run this)

Enjoy (if it works)

If it works, you can put it in the stick for both this thread and the hadamard thread I guess if people want to try it.
But like I said, see if it works first :p
If you got errors while patching it usually means that something didn't patch... which is bad.

And yes, the patches are currently incompatible for technical reasons (some of them affect the same lines of code in extremely minor ways).

Don't bother with the currently posted SAU algorithm--its crap. I already have it way, way beaten :p

[TheRyuu]

If you got errors while patching it usually means that something didn't patch... which is bad.

And yes, the patches are currently incompatible for technical reasons (some of them affect the same lines of code).

Don't bother with the currently posted SAU algorithm--its crap. I already have it way, way beaten :p

Ok. I'll keep the link for the hell of it but I put a notice to please not download it.

Someone should create like an all it one patch that combines all the "good" x264 patches there are into one big compatible one or something.

[Raere]

Once you tidy up everything, will the patches be merged onto the main x264 tree? I can't wait to use the new stuff all compiled and stuff for us newbs.

[Terranigma]

What's the command for simulated annealing?

[Dark Shikari]

What's the command for simulated annealing?
It'll be --me sau when its done (standing for Simulated Annealing w/ UMH).

[Terranigma]

It'll be --me sau when its done (standing for Simulated Annealing w/ UMH).

OK, thanks. So will it work with this (http://forum.doom9.org/showpost.php?p=1042408&postcount=98) build? He said it's patched with SAU, but i'm unsure it'd even work now because you just said "It'll be --me sau when its done" :p

[Dark Shikari]

OK, thanks. So will it work with this (http://forum.doom9.org/showpost.php?p=1042408&postcount=98) build? He said it's patched with SAU, but i'm unsure it'd even work now because you just said "It'll be --me sau when its done" :pNote what I said about that build:

a) He said there were errors when patching even though it compiled successfully. This probably means its broken.

b) The algorithm, though working, was quite bugged at that point.

I've changed the algorithm so that instead of a single, long SA function, 6 different annealing functions are called in a hexagon formation between 8 and 12 spaces away from the center. The best result from these is then taken, and a 5x5 ESA is run on that location.

Its slow, but to speed it up I've done some very heavy optimization (elimination of branches, etc) along with some early termination code.

[Bulletproof]

Can this be combined with the hadamard transformations?

[Sharktooth]

yes, it can but there's no hurry.

[Dark Shikari]

Can this be combined with the hadamard transformations?
Yes, easily.

[DeathTheSheep]

"6 different annealing functions are called in a hexagon formation between 8 and 12 spaces away from the center."

What if the actual motion is closer to the center than those 8-12 spaces? Will it be ignored?! Or do you mean "in addition to searching near the center" these hexagons will poke around their 12 spaces away and illuminate the big picture?

"I've done some very heavy optimization (elimination of branches, etc) along with some early termination code."
Done? As in past tense? That's pretty interesting...

[Dark Shikari]

"6 different annealing functions are called in a hexagon formation between 8 and 12 spaces away from the center."

What if the actual motion is closer to the center than those 8-12 spaces? Will it be ignored?! Or do you mean "in addition to searching near the center" these hexagons will poke around their 12 spaces away and illuminate the big picture?
First of all, one can expect that at least one of these branches will head towards the center, in all probability. Depending on whether it improves the results, I may run a 7th in the center. I could also run a couple iterations of HEX in the middle.

"I've done some very heavy optimization (elimination of branches, etc) along with some early termination code."
Done? As in past tense? That's pretty interesting...
These are just on my code, nothing else.

[Dark Shikari]

Slight difficulty so far. The problem is that SAU simply isn't good enough with its current algorithm to be useful. Its definitely better and slightly slower than UMH, but look at these graphs and you'll understand the problem:

http://i15.tinypic.com/4uah8hj.png

SAU-SAD is worse and slower than UMH-SATD!

And SAU-SATD is worse than ESA-SAD. :mad:

(I'll find a way to fix this ;) )

[akupenguin]

better graph
http://akuvian.org/images/x264_sau_speed_v_quality_0.png

[Sharktooth]

SATD UMH seems the best compromise between speed and quality. it also scales well.
SAD ESA is also interesting but still slower and "fluctuating".

[*.mp4 guy]

Satd ESA is the most interesting to me, it has a rather impresive total quality increase, it outperforms Sad ESA by an impressive margin aswell. It's too bad that its unusable slow. Satd UMH is probably the most usable option.

[Dark Shikari]

Satd ESA is the most interesting to me, it has a rather impresive total quality increase, it outperforms Sad ESA by an impressive margin aswell. It's too bad that its unusable slow. Satd UMH is probably the most usable option.
The graph uses the old SATD ESA algorithm; the new one is about 2-2.5x faster, so slightly usable.

By the way, I totally trashed the Simulated Annealing algorithm in favor of another one (since I couldn't get SA to work well enough). The new algorithm basically takes advantage of the fact that the HEX ME algorithm is so well optimized, and, well... has fun with that :p

Its relatively near ESA in terms of quality, at least for SAD. Hopefully it'll turn out well for SATD too. Graphs will be up later.

Not sure what to call it: maybe HHH for Hexagon Hexagon Hexagon (Hungry Hungry Hexagons?) Or TMH for Too Many Hexagons? Or MHS for Multi Hexagon Search?

Also note the new algorithm scales somewhat differently; the new portion of the algorithm only scales every 8 --merange, so the only difference between --merange 16 and --merange 23 is the increased size of the UMH search. Technically it does have slight improvements there, as UMH has an adaptive search range that will increase the merange when it thinks its necessary, so a few times it'll go over --merange 24 and activate the next level of the algorithm.

[Dark Shikari]

Updated graph with the new algorithm:

http://i15.tinypic.com/4tjd8i9.png

I need to find a way to make that thing faster :mad:. It isn't bad for SAD, but SATD UMH barely eclipses it. And with SATD, its just too slow, though still vastly faster than ESA.

[check]

is there any reason why some of these functions seem to produce such variable output? It seems to be all the ones based on SAD, but is it some problem that persists across test samples, or just random luck?

[Dark Shikari]

is there any reason why some of these functions seem to produce such variable output? It seems to be all the ones based on SAD, but is it some problem that persists across test samples, or just random luck?Its both. A test sample may have situations in which SAD finds a pretty good match very close-by, and if the motion search is extended far enough, finds another good match that is slightly better quality-wise but much farther away, resulting in the block requiring more bits to encode.

It all boils down to SAD being a mediocre metric.

The source footage I'm using is the scene with all the wires (the running scene) in Elephant's Dream, which might be particularly susceptible to this problem, given the very complex background.

[Sagekilla]

Wow, that kind of explains why SATD ESA has such a higher quality over everything else.. Literally a perfect example of where using a brute force method -can- be worth it.

[Dark Shikari]

Apparently the numbers for SATD UMH were totally wrong; I have no idea why. Here's the graph with corrected numbers, along with my new and improved algorithm.

http://i10.tinypic.com/66bsdox.png

[Sagittaire]

Mind posting to the x264 list for the benefit of those who don't regularly check the forum? (As an aside, Gabriel Bouvigne has recently posted some very interesting b-frame patches there that might interest you.)

Where I can find these patch ?

[foxyshadis]

Original message (http://mailman.videolan.org/pipermail/x264-devel/2007-August/003559.html)
bchanges.diff (http://mailman.videolan.org/pipermail/x264-devel/attachments/20070828/5d798238/attachment.txt)

[Dark Shikari]

Updated graph with some slight improvements to MHS.

http://i6.tinypic.com/5z5107o.png

Note that SAD ESA cannot be multithreaded at the moment; all the others can. The graph is singlethreaded performance.

[foxyshadis]

Odd, the last two graphs appear to have exactly the same datapoints.

[Dark Shikari]

Odd, the last two graphs appear to have exactly the same datapoints.
The change was small, but yeah, I think I forgot to copy/paste the datapoints into the new graph. Fixed.

I have some other possible improvements to MHS upcoming as I change some of the hexagonal searches a slight bit.

If I can do enough elimination I may be able to raise the entire curve up a bit and possibly regain the --merange 32 spike in the older MHS.

[Dark Shikari]

I'm going to shut down this thread for now (maybe it can be locked?) and make a new thread, since I totally redid the algorithm described in the original post and it doesn't even have the same name.

[DeathTheSheep]

I don't think locking is such a good idea (the algorithm still exists and is still linked to!) but splitting into a new thread is the way to go. :cool: