Introducing the Fast-Ref-Search (version 0.2)

[Dark Shikari]

http://i18.tinypic.com/7w53807.jpg

Download latest binary (SVN 682--Fast-Ref-Search 0.2) (http://www.mediafire.com/?bturl0wwwuy)
Download old binary (SVN 682--Fast-Ref-Search 0.1) (http://www.mediafire.com/?8dk3cudinxg)
(Note: SVN builds, so no AQ/whatever for now; you'll get that when my new patches get merged into SVN)

How to use Fast-Ref-Search:

1. Its on by default, on normal mode (1). This, with a very minimal bitrate/quality loss (0.1-0.5%, usually) will considerably increase the speed of using multiple refs, especially 2-3 or more. Think speed increases of 20%, 30%, or even 50% with ESA.

2. It only applies to UMH and ESA, otherwise its disabled. Beneift for UMH can go up to 20-30%, benefit for ESA can approach double that.

3. To disable it, use --fast-ref-search 0.

4. To enable Aggressive mode, use --fast-ref-search 2. This will increase the quality/bitrate loss (to 0.5-2%) but will increase speed further, especially when using fewer refs. Its not useful with very large numbers of refs, as in those cases its more efficient to just lower the number of refs. I have not tried Aggressive mode on ESA, so I can't guarantee it being at all useful.

5. This build includes a few other optimizations of mine, mostly code optimizations, along with the addition of first-order predictors ("accelerators"). These are very minor changes by comparison though.

6. It is sometimes more useful to lower the number of refs to increase speed than to use the fast-ref-search, especially for ref values nearing 16. Don't use this option as an excuse to use absurd number of refs; you're just going to be wasting your time. I cannot guarantee this will be useful in all cases; in fact, I can guarantee there are cases in which it will not be useful. I will do some analysis later to figure out exactly where it is and is not useful.

Have fun ;)

[burfadel]

Hmmm, well I guess using ESA instead of UMH will counteract that 0.1%-0.5% quality loss yet still provide a nice speed boost?...

[Dark Shikari]

Hmmm, well I guess using ESA instead of UMH will counteract that 0.1%-0.5% quality loss yet still provide a nice speed boost?...I don't think this makes ESA faster than UMH just yet... it closes the gap though.

Also from my preliminary analysis so far, the results show that Aggressive mode is most useful between ref1 and ref5, and Normal mode is useful between ref3 and ref8, for UMH at least. Also note this is on Elephant's Dream, not a sequence that benefits hugely from 8-16 reference frames, like anime. In fact the benefit from the extra refs past 6 or 7 is hardly measurable, which could contribute to the fast-ref-search being useless beyond this point also.

[kumi]

Thanks. I have a lowly Sempron and I'm searching for ways to speed things up. This is how my x264.exe is called by MeGUI:
"C:\Program Files\megui\tools\x264\x264.exe" --pass 1 --bitrate 2200 --stats "C:\xtemp\VTS_01_1.stats" --bframes 3 --b-pyramid --direct auto --filter -2,-1 --subme 1 --analyse none --vbv-maxrate 25000 --me dia --threads auto --thread-input --sar 1:1 --progress --no-psnr --no-ssim --output NUL "C:\xtemp\VTS_01_1.avs"
"C:\Program Files\megui\tools\x264\x264.exe" --pass 2 --bitrate 2200 --stats "C:\xtemp\VTS_01_1.stats" --ref 5 --mixed-refs --bframes 3 --b-pyramid --b-rdo --bime --weightb --direct auto --filter -2,-1 --subme 6 --trellis 1 --analyse p8x8,b8x8,i4x4,i8x8 --8x8dct --vbv-maxrate 25000 --me umh --threads auto --thread-input --sar 1:1 --progress --no-psnr --no-ssim --output "C:\xtemp\VTS_01_1.264" "C:\xtemp\VTS_01_1.avs"

That's the "HQ-Slower" profile, btw. Now, you mentioned that your new search is on by default in "mode 1", but I'm not sure what that "mode" is. I do see multiple refs and umh in my 2nd pass... so will replacing my x264.exe with your Fast-Ref-Search version result in a speed boost?

[/newb]

[Dark Shikari]

Graph of data points for UMH on Elephant's Dream (non-anime source). FPS vs Adjusted Bitrate (adjusted for SSIM differences). Blue = No Fastref, Red = Normal, Yellow = Aggressive.

http://i8.tinypic.com/81plnr8.png

The area under the blue curve is where an algorithm is better than it; under the curve means faster and lower bitrate.

Notice how Aggressive is pretty superior at refs ~1-5, and Normal is especially good between ~refs 3-8.

[Dark Shikari]

Thanks. I have a lowly Sempron and I'm searching for ways to speed things up. This is how my x264.exe is called by MeGUI:
"C:\Program Files\megui\tools\x264\x264.exe" --pass 1 --bitrate 2200 --stats "C:\xtemp\VTS_01_1.stats" --bframes 3 --b-pyramid --direct auto --filter -2,-1 --subme 1 --analyse none --vbv-maxrate 25000 --me dia --threads auto --thread-input --sar 1:1 --progress --no-psnr --no-ssim --output NUL "C:\xtemp\VTS_01_1.avs"
"C:\Program Files\megui\tools\x264\x264.exe" --pass 2 --bitrate 2200 --stats "C:\xtemp\VTS_01_1.stats" --ref 5 --mixed-refs --bframes 3 --b-pyramid --b-rdo --bime --weightb --direct auto --filter -2,-1 --subme 6 --trellis 1 --analyse p8x8,b8x8,i4x4,i8x8 --8x8dct --vbv-maxrate 25000 --me umh --threads auto --thread-input --sar 1:1 --progress --no-psnr --no-ssim --output "C:\xtemp\VTS_01_1.264" "C:\xtemp\VTS_01_1.avs"

That's the "HQ-Slower" profile, btw. Now, you mentioned that your new search is on by default in "mode 1", but I'm not sure what that "mode" is. I do see multiple refs and umh in my 2nd pass... so will replacing my x264.exe with your Fast-Ref-Search version result in a speed boost?

[/newb]
You use --fast-ref-search 0, 1, or 2 as the extra commandline. See the graph above to get an idea of the speed and bitrate change. Each point on the graph is one more ref, with points on the left = most refs and point all the way on the right = 1 ref.

[Adub]

I saw this thread on the RSS feed and I knew it had to be one of your crazy ideas.

Thank you very very much!

[Zanejin]

Since we're on the topic, is there any other disadvantage to using a greater --ref value (as there is to using a greater --b-frame value) than a reduction in encoding speed?

[Dark Shikari]

Since we're on the topic, is there any other disadvantage to using a greater --ref value (as there is to using a greater --b-frame value) than a reduction in encoding speed?Many profiles and levels limit the number of refs. As such, for hardware compatibility, higher --ref values are worse.

In terms of decoding, there is likely an absolutely minimal effect on encoding speed due to having to fetch the motion compensation pixels from RAM instead of cache for farther-back frames (probably not even measurable). The memory usage is also slightly higher due to having to store the previously decoded frames (width * height * 12 bits * number of refs).

Overall, unless you're looking for specific hardware compatibility, there is no reason other than encoding time to avoid large numbers of refs.

[Dark Shikari]

Same graph for ESA:

http://i1.tinypic.com/8fci6fa.png

Another note is that I highly suspect that higher MEranges will significantly increase the speed gap between Fast-Ref and Normal, both in UMH and ESA.

Since I found with the earlier graph that the fast-ref-search became pretty useless at high ref values, I may modify the higher-ref versions of the fast-ref-search to be a bit more intensive to avoid them being worse than the regular method.

[akupenguin]

Put ESA and UMH on the same graph.

[Dark Shikari]

Put ESA and UMH on the same graph.http://i13.tinypic.com/8anyqa9.png

I boxed the areas where the fast-ref-search is useful.

The other thing I need to check is how effective this is with and without various partitions.

[Sagekilla]

What does x and y represent on the graphs? I'm confused as to what you're showing on your graphs.

[Zanejin]

The x-axis represents "FPS", and the y-axis represents "Adjusted Bitrate (adjusted for SSIM differences)" (from post #5).

[kumi]

Tested with Sharktooth's HQ-Slower profile on some clean interlaced handheld DV footage, Sempron 2600+ CPU...

--fast-ref-search 0
2.82 fps (baseline):
--pass 2 --bitrate 1656 --stats ".stats" --ref 5 --mixed-refs --bframes 3 --b-pyramid --b-rdo --bime --weightb --direct auto --filter -2,-1 --subme 6 --trellis 1 --analyse p8x8,b8x8,i4x4,i8x8 --8x8dct --vbv-maxrate 25000 --me umh --threads auto --thread-input --progress --no-psnr --no-ssim --output "output" "input" --fast-ref-search 0

--fast-ref-search 1
3.13 fps (+11%):
--pass 2 --bitrate 1656 --stats ".stats" --ref 5 --mixed-refs --bframes 3 --b-pyramid --b-rdo --bime --weightb --direct auto --filter -2,-1 --subme 6 --trellis 1 --analyse p8x8,b8x8,i4x4,i8x8 --8x8dct --vbv-maxrate 25000 --me umh --threads auto --thread-input --progress --no-psnr --no-ssim --output "output" "input" --fast-ref-search 1

--fast-ref-search 2
3.24 fps (+15%):
--pass 2 --bitrate 1656 --stats ".stats" --ref 5 --mixed-refs --bframes 3 --b-pyramid --b-rdo --bime --weightb --direct auto --filter -2,-1 --subme 6 --trellis 1 --analyse p8x8,b8x8,i4x4,i8x8 --8x8dct --vbv-maxrate 25000 --me umh --threads auto --thread-input --progress --no-psnr --no-ssim --output "output" "input" --fast-ref-search 2

[Unearthly]

Wow, this feature works really well! I ran some tests on an 11 minute anime clip (low motion) using the following options:

--crf 18 --ref XX --mixed-refs --no-fast-pskip --bframes 16 --b-pyramid --b-rdo --bime --weightb --direct auto --subme 7 --trellis 2 --analyse all --8x8dct --me umh --merange 32 --threads 100 --thread-input --progress

Summary of using --fast-ref-search 1:
8 refs: +10.25% FPS, +0.14% Bitrate
16 refs: +29.75% FPS, +0.10% Bitrate

I can post the full logs if anyone is curious.

Dark Shikari: Since you are working straight off the SVN, could we get a patch, pretty please? :) I'd like to see how it works with the other patches that I'm building with.

[Dark Shikari]

Dark Shikari: Since you are working straight off the SVN, could we get a patch, pretty please? :) I'd like to see how it works with the other patches that I'm building with.I'll upload a patch later tonight, but note it contains some various other changes:

1. Slight DIA optimization (Pengvado is disputing this one, so I'll probably toss it unless I can get clear proof that it works)
2. Code cleanup + slight optimization in x264_macroblock_encode.
3. Adding accelerators (first-order predictors) in macroblock.c.
4. Removal of one set of IDIVs in macroblock.c using a lookup table generated once per frame, and removing another IDIV in me.c using three IMULs instead.
5. Probably a few other very minor things I don't remember.

Its very interesting how much of an improvement you got on the anime source; I suspected that in cases where lots of refs would be used, such as anime, this might not be as good; instead, its actually more effective with less bitrate gain, going by your test.

[Unearthly]

Its very interesting how much of an improvement you got on the anime source; I suspected that in cases where lots of refs would be used, such as anime, this might not be as good; instead, its actually more effective with less bitrate gain, going by your test.

Indeed, and comparing 8 refs fast vs 16 refs fast, I get -3.1% bitrate for only a decrease of 16.7% FPS. I think that is worth it.

I also tried aggressive mode with 16 refs (for fun ;) ) and it didn't really change much (though only for the worse). -0.11 fps and +.16% bitrate compared to the standard mode. So I guess that reinforces that it is only for the lower ref counts.

[Dark Shikari]

Indeed, and comparing 8 refs fast vs 16 refs fast, I get -3.1% bitrate for only a decrease of 16.7% FPS. I think that is worth it.

I also tried aggressive mode with 16 refs (for fun ;) ) and it didn't really change much (though only for the worse). -0.11 fps and +.16% bitrate compared to the standard mode. So I guess that reinforces that it is only for the lower ref counts.Yeah, basically here's the difference between them:

Normal mode, UMH:
P16x16 partitions: UMH for first and second ref, HEX for the rest.
B16x16 partitions: UMH for first ref, HEX for the rest.
P8x8 partitions with mixed-refs: UMH for first and second ref, HEX for the rest.
All other partitions: UMH

Aggressive mode, UMH:
P16x16 partitions: UMH for first ref, HEX for the rest.
B16x16 partitions: HEX for all refs.
P8x8 partitions with mixed-refs: UMH for first ref, HEX for the rest.
B8x8 partitions and P8x8 without mixed-refs: UMH
All other partitions: HEX

Normal mode gives very little benefit for low ref values for clear reasons, so aggressive mode exists to really push the envelope on optimization, at the cost of having more of a quality drop. While its useful in general, its specifically useful when you're restricted on the number of refs; I originally came up with the idea because of a suggestion by DaKaz, since his company was restricted to 3 refs for encoding with x264.

[Dark Shikari]

P8x8 partitions with mixed-refs: UMH for first and second ref, HEX for the rest.
And this appears to be the primary source of lost quality overall... perhaps with some tweaks this can be avoided without decreasing speed too much :)

I will likely post a new build that will have reduced speed for the regular fast-ref mode. Aggressive mode will likely be unchanged.

[Unearthly]

Well I tried one more test, same options as before but this time with ESA + 16 refs.

Reults:
+116.95% FPS, +0.050% Bitrate

Huge speed increase! I was amazed how fast it went. ESA with --fast-ref-search 1 was only 22% slower than UMH without. Of course, the bitrate only decreased by 0.12% so it's still not worth it for this clip.

[Yong]

file removed?
this is what i get when i try to download the binary:
The quickkey you provided for file download was invalid. This is usually caused because the file is no longer stored on Mediafire. This occurs when the file is removed by the originating user or Mediafire.
:(

[Dark Shikari]

file removed?
this is what i get when i try to download the binary:
The quickkey you provided for file download was invalid. This is usually caused because the file is no longer stored on Mediafire. This occurs when the file is removed by the originating user or Mediafire.
:(It still works fine here...

[Yong]

downloaded the binary, mediafire might be overloaded at tht moment :p
thx alot! cant wait to get the patches :D

[Dark Shikari]

downloaded the binary, mediafire might be overloaded at tht moment :p
thx alot! cant wait to get the patches :DYeah, I found out that apparently the majority of the gain from the patch was due to the over-optimization of the p8x8-mixed-refs function; so I've come up with a more efficient but slightly slower optimization that should work basically just as well. Doing some final testing on it now.

[Dark Shikari]

New version is ready... and this time, it didn't get worse than without --fast-ref-search for any number of refs I tested; the line never crossed ;)

http://i17.tinypic.com/87ls0nd.png

Link to the new build is in the original post.

The last data point for Fast-Ref-Search 1 is very slightly below due to the SSIM difference being larger than the bitrate difference; its mostly a fluke.

[audyovydeo]

All quiet on the --fast-ref-search front ?
Any provisional date when it will hit svn ? Will it ever ?
This looks like the most promising improvement, beating --me-prepass and --imh.

How come none of them have hit svn yet ?


cheers
audyovydeo

[Dark Shikari]

All quiet on the --fast-ref-search front ?
Any provisional date when it will hit svn ? Will it ever ?
This looks like the most promising improvement, beating --me-prepass and --imh.

How come none of them have hit svn yet ?


cheers
audyovydeoIMH is useless now that threaded ESA is in. Me-prepass will probably come soon.

Akupenguin tends to be rightfully skeptical of anything I come up with, so adding to SVN is slow ;)

[Unearthly]

Akupenguin tends to be rightfully skeptical of anything I come up with, so adding to SVN is slow

Which is why a patch would be great. ;)

[jethro]

This doesn't affect decoding speed? Say, 8 "normal" reference frames and 8 "fast" ref frames decode at the same speed?

[Dark Shikari]

This doesn't affect decoding speed? Say, 8 "normal" reference frames and 8 "fast" ref frames decode at the same speed?No, its solely for encoding decision. Unrelated to decoding.

[Dark Shikari]

Here's a patch... note its very dev-ish and has loads of other changes like my code revamp, where I'm converting loads of long if/elses to switches, and so forth. It also probably has a few left-over temp variables and such, maybe some debugging code. Amazingly, this 120kb diff does compile.

Pastebin link (http://pastebin.com/f6037e958).

[J_Darnley]

Are you still looking for some encoding statistics? I have got the results of many encodes of a 5000 frame sample from a cartoon source. I ran the command line below with the settings: umh and esa; refs 2-16 (evens); and search 0-2. Interestingly I found that it was most effective with higher refs which is probably due to the ref search being so quick compared with the rest. I also found that it never increased the bitrare by more than 0.3%.

Should I be testing it with other quicker options: lower subme; fewer partitions? If you have any suggestions or options you want to see altered/run please say. Also say if you want a fancy-lookin' graph.

x264_fast-0.2 --crf 21 --bframes 16 --b-pyramid --ref %%B --deblock 1,1
--qpmin 5 --partitions "all" --direct auto --weightb --me umh --subme 7
--b-rdo --mixed-refs --bime --8x8dct --trellis 2 --no-fast-pskip
--fast-ref-search %%A --no-dct-decimate --progress --no-psnr --no-ssim
--threads auto --thread-input --sar 16:15 --output "NUL"
"x264_fast-test.avs"
AviSynth script loads the FFV1 compressed sample.
CSV file containing stats: fast-ref-search-0.2_american-dad.csv (http://users.telenet.be/darnley/fast-ref-search-0.2_american-dad.csv)

[Unearthly]

Here's a patch... note its very dev-ish and has loads of other changes like my code revamp, where I'm converting loads of long if/elses to switches, and so forth. It also probably has a few left-over temp variables and such, maybe some debugging code. Amazingly, this 120kb diff does compile.

Pastebin link (http://pastebin.com/f6037e958).

Thanks for the patch. Only one odd thing, your range information lines were missing their leading @@. Luckily it was easy to remedy. It built fine alone, though it interacted badly with my already patched build. I'll have to work on it.

[Dark Shikari]

Thanks for the patch. Only one odd thing, your range information lines were missing their leading @@. Luckily it was easy to remedy. It built fine alone, though it interacted badly with my already patched build. I'll have to work on it.Its an SVN DIFF patch, so it'll work directly off SVN 682.

[Pomyk]

Maybe it would be useful to make search method based not only on reference number but also on motion complexity.

[Dark Shikari]

Maybe it would be useful to make search method based not only on reference number but also on motion complexity.This is difficult to make compatible with threads, because one doesn't have all the motion information from the previous frame yet, which would be needed to say "this scene is high motion" or "this scene isn't high motion."

There already is adaptive MERange and early termination for low-motion segments.

[Pomyk]

I was thinking about using stats from the previous pass for this :)

[Dark Shikari]

I was thinking about using stats from the previous pass for this :)This would be very useful, I would think; I have found that the average MV length from the previous pass would be a very useful heuristic for motion searching. Or perhaps the average distance of the resulting MV from the predictor.

[burfadel]

Just wondering whehther you are going to update the builds of x264 found here:
http://mirror05.x264.nl/Dark/

Wwith the latest AQ patch and fast ref search? or is it that differences between 697 and (the current) 705 not warranting a recompile?

On two tests I did, your fast ref search patch is still faster than 705, and surprisingly the file size was fractionally smaller... I didn't go in to depths with the quality ratings, visually they were identical... It was kind of rushed, but the speed difference was several fps in both cases (at the least, 15 percent!!).

[Dark Shikari]

Just wondering whehther you are going to update the builds of x264 found here:
http://mirror05.x264.nl/Dark/

Wwith the latest AQ patch and fast ref search? or is it that differences between 697 and (the current) 705 not warranting a recompile?

On two tests I did, your fast ref search patch is still faster than 705, and surprisingly the file size was fractionally smaller... I didn't go in to depths with the quality ratings, visually they were identical... It was kind of rushed, but the speed difference was several fps in both cases (at the least, 15 percent!!).705 includes some of the changes made in fast-ref, but not the fast-ref search itself. I'm waiting for Akupenguin to add the rest of the non-major changes into SVN.

[Splashdriver]

Hi,

Excuse me for maybe asking a quite stupid question, but there's something I would really like to ask:

I thought I saw somewhere in another topic, a link to a Fast-Ref-Search build with AQ support. Unfortunately, I cannot find it anymore. Maybe I'm mixing things up, so can somebody confirm that this build does exist allready, and if possible, provide me with a link to it?

Thanks in advance.

[Dark Shikari]

Link (http://mirror05.x264.nl/Dark/force.php?file=./x264.697.fast-ref-search.01.aq-brdo.exe) to the build.

[Splashdriver]

Thank you very much, all your work is still improving and I know it's getting better, thanks again.

Why is Brdo-option mentioned in the filename, anything special with that?

[Dark Shikari]

Thank you very much, all your work is still improving and I know it's getting better, thanks again.

Why is Brdo-option mentioned in the filename, anything special with that?There was a bug a while ago with AQ and B-RDO, which was fixed. AQ_BRDO is the name of the latest AQ patch, representing the fact that the BRDO bug was fixed.

[Splashdriver]

@Dark Shikari

I see, well, I'm encoding Resident Evil (part 1) at the moment with the AQ_BRDO patch you provided me. I'm very curious to see the encoding results (I've found out that KMplayer can play the allready encoded video parts in advance, while the rest of the video is still constructed by the process of encoding, quite handy if ya ask me :))

The source is a bit too grainy, since I like the HIGH Detail CQM (M4G-HighDetail-V3.1) of MP4Guy, I think I'm going to disable B-RDO anyway along with setting B-frame mode to "none".

Undeen filter seems to make the video output a bit too smooth, and I mostly like it crisp, sharp and detailed :p (grain presence doesn't bother much too much).

I find the Fast-Ref-Search very handy to use since I can now safely up the ref frames like something to 8-0 for real-life content and still notice'a quite welcome speed increasement. Too bad the AQ-brdo patch you provided hasn't moved up to version 0.2, cause that would mean further speed improvement, right?

I'm on an P4 3.4Ghz HT, 1GB DDR SDRAM laptop and do really experience a speed improvement with the introduction of this FRS version without very noticable quality degradation.

PS. English is not my native language, so excuse me for any kind of weird sentence construction.

[Dark Shikari]

@Dark Shikari

I see, well, I'm encoding Resident Evil (part 1) at the moment with the AQ_BRDO patch you provided me. I'm very curious to see the encoding results (I've found out that KMplayer can play the allready encoded video parts in advance, while the rest of the video is still constructed by the process of encoding, quite handy if ya ask me :))

The source is a bit too grainy, since I like the HIGH Detail CQM (M4G-HighDetail-V3.1) of MP4Guy, I think I'm going to disable B-RDO anyway along with setting B-frame mode to "none".

Undeen filter seems to make the video output a bit too smooth, and I mostly like it crisp, sharp and detailed :p (grain presence doesn't bother much too much).

I find the Fast-Ref-Search very handy to use since I can now safely up the ref frames like something to 8-0 for real-life content and still notice'a quite welcome speed increasement. Too bad the AQ-brdo patch you provided hasn't moved up to version 0.2, cause that would mean further speed improvement, right?I'm pretty sure the 0.1 is referring to the version of the AQ-BRDO patch... I think.

Fast-ref is on hold for a bit now; I've been fooling with other ways to do a fast-ref search, and some could potentially be better. One idea I've thrown around is doing HEX on every reference frame, picking the best few, and running UMH on those.

[Shinigami-Sama]

I'm pretty sure the 0.1 is referring to the version of the AQ-BRDO patch... I think.

Fast-ref is on hold for a bit now; I've been fooling with other ways to do a fast-ref search, and some could potentially be better. One idea I've thrown around is doing HEX on every reference frame, picking the best few, and running UMH on those.

ohh a hybrid method?
good luck dark, its always nice to see new developments

[Splashdriver]

Fast-ref is on hold for a bit now; I've been fooling with other ways to do a fast-ref search, and some could potentially be better. One idea I've thrown around is doing HEX on every reference frame, picking the best few, and running UMH on those.

Some sort of adaptive ME search, which behaves a bit like the idea behind BRDO, you mean?

[Dark Shikari]

Some sort of adaptive ME search, which behaves a bit like the idea behind BRDO, you mean?Nothing like BRDO. All B-RDO does is run RDO on every single B-block type, and pick the best. Its basically brute-force.