[New patch] Hadamard motion estimation

[Dark Shikari]

You fail at algebra.This. ;)

[DeathTheSheep]

Oh snap

[Inventive Software]

"(average+3*min)/10" != "average-3*(average-min)/10"

Apparently, I fail at algebra. :p

If all of that's your code, essentially it's wrong. If you're trying to replace the first with the second, it's still wrong.

If you want to get rid of divisors, here's a really piss-easy way to do it: 1/the number you want to not divide. In your case 1/10, which is 0.1, which is rational and easy to compute.

So your line (and feel free to correct me on this if I'm completely skywards) should be:

"(average+3*min)*0.1"

[Dark Shikari]

If all of that's your code, essentially it's wrong. If you're trying to replace the first with the second, it's still wrong.

If you want to get rid of divisors, here's a really piss-easy way to do it: 1/the number you want to not divide. In your case 1/10, which is 0.1, which is rational and easy to compute.

So your line (and feel free to correct me on this if I'm completely skywards) should be:

"(average+3*min)*0.1"
Of course what you're actually doing on an assembly level (pseudocode) is, assuming you add the required x264_emms() to stop the program from giving you infinities:

CLEAR MMX REGISTERS FOR FLOATS (EMMS, 6 clocks)
MOVE INTEGER min TO register (1 clock)
MOVE INTEGER average TO register (1 clock)
MULTIPLY INTEGER min BY 3 AND STORE IN min (3-7 clocks) Note GCC will convert this from min*3 to (min + min << 1)
ADD min AND average AND STORE IN min (1 clock)
CONVERT min FROM INTEGER TO FLOAT (Lots of clocks)
FLOATING POINT MULTIPLY min AND 0.1 AND STORE IN min (4-7 clocks)

Considering you're doing this to avoid an integer division, you're probably worse off than before.

Rule 1 of optimizing math: Don't convert between integers and floats unless you really really have to.
Rule 2: Floats are usually slower than ints.
Rule 3: In a program covered with MMX code, floats are an even worse idea.

This is why if you need to do integer division, you should either use fixed point division or use magic numbers.

[Inventive Software]

I thought he was trying to avoid division full stop! :confused:

I've also, most of the time, gone by the rule that multiplication is better than division. This isn't the case I assume?

So what if you were just working with floats... would it make sense then?

[Dark Shikari]

So what if you were just working with floats... would it make sense then?Yes.

The issue is that the cost of converting to float and EMMS, both of which are probably going to hold up the execution of the program, are likely nearly as bad as that of integer division itself.

[akupenguin]

In the case of integer division by a constant, gcc will convert division to multiplication.
It can't make the same optimization for floating-point division, because x/10.0 is not bitwise identical to x*0.1, unless you use -ffast-math to make it ignore the difference.
(uint32_t)x/10 => ((uint64_t)x*0xcccccccd)>>35
But as long as you're picking arbitrary fractions, it's better to make the denominator a small power of 2. Then gcc might be able to avoid the multiplication too, and just use shift or lea.

[akupenguin]

Did you compare various functions of (min,average) against constant ratios of min? The latter would allow some amount of SEA during the sadarray generation.

[Dark Shikari]

Did you compare various functions of (min,average) against constant ratios of min? The latter would allow some amount of SEA during the sadarray generation.I didn't try constant ratios of min, but that might not be a bad idea at all. I'll try it in a bit and post the results here.

I was just working on trying to optimize ME DIA but unfortunately the logic required to save 1 COST_MV call per DIA cycle takes more clock cycles than the saved COST_MV call anyways. I did manage to get a 3.6% speed boost with a 0.1% quality boost (negligable) by doing a full me-range radius-2 DIA and then 2 cycles of radius-1 DIA, so that could give a bit of a first-pass speed boost for encoding.

[Dark Shikari]

OK, here's your results:

Threshold: current with 3/4: 0.4 FPS and 0.10% quality loss over ideal

Threshold: current with 1/2: 0.32 FPS and 0.03% quality loss over ideal

Threshold: min*2: 0.26 FPS and 0.05% quality loss over ideal

Threshold: 3*min/2: 0.35 FPS and 0.07% quality loss over ideal

Threshold: 4*min/3: 0.39 FPS and 0.05% quality loss over ideal

Threshold: 5*min/4: 0.4 FPS and 0.01% quality loss over ideal

In other words the quality loss is negligible and meaningless as its basically random, and a min-only based threshold works quite well; this means you could implement a SAD SEA algorithm and then my current hadamard thresholding together, right?

[DeathTheSheep]

I like the last one quite a bit. :p 0.01%? I never thought I'd see that number in a threshold-based algo...

[Dark Shikari]

I like the last one quite a bit. :p 0.01%? I never thought I'd see that number in a threshold-based algo...Seen --subme 7's algorithm?

void x264_me_refine_qpel_rd( x264_t *h, x264_me_t *m, int i_lambda2, int i8 )

That uses a SATD threshold to decide when to do RD, quite a low one too; 17/16!

[akupenguin]

SATD SEA
x264_satd_fpel.10.diff (http://akuvian.org/src/x264/x264_satd_fpel.10.diff) : simple version
x264_satd_fpel.11.diff (http://akuvian.org/src/x264/x264_satd_fpel.11.diff) : sad_x3 version, might or might not be slightly faster. (The difference is much less than before, since there's fewer SADs and x3 adds some complexity to SEA.)
I used threshold=5/4, but the speed/quality tradeoff might be different now.