[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.