[FFmpeg-devel] [PATCH] avfilter/vf_deshake: replace qsort with AV_QSORT

[Michael Niedermayer]

On Sat, Oct 31, 2015 at 11:19:04AM +0100, Nicolas George wrote:
> Le nonidi 9 brumaire, an CCXXIV, Ganesh Ajjanagadde a écrit :
> > Sample benchmark (x86-64, Haswell, GNU/Linux):
> > File: original from https://trac.ffmpeg.org/ticket/1430
> > command: ffmpeg -stream_loop 8 -i file.webm -vf deshake=rx=64:ry=64 -f null -
> > 
> > Timer truncated at 1024 runs.
> > new:
> > 39676 decicycles in qsort,    1024 runs,      0 skips
> > 
> > old:
> >   86783 decicycles in qsort,    1024 runs,      0 skips
> 
> What was inside the start/stop_timer block? I see that the qsort call is
> after a very expensive loop, I suspect those few thousand cycles may be
> completely negligible in front of the loop itself.

that loop before IIRC is a exhaustive search motion estimator
there are much faster ways to estimate motion like what is implemented
in libavcodec/motion_est* or what x264 does
then again all the encoder motion estimation is tuned toward finding
good matches _for_encoding_blocks_ while for deshake and other filters
the goal is to find the actual real world motion. These 2 problems
are similar but not identical so the best algorithms may differ


[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Complexity theory is the science of finding the exact solution to an
approximation. Benchmarking OTOH is finding an approximation of the exact
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20151031/15aad461/attachment.sig>