[FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

[Ganesh Ajjanagadde]

On Sat, Oct 10, 2015 at 5:32 PM, Henrik Gramner <henrik at gramner.com> wrote:
> On Sat, Oct 10, 2015 at 11:06 PM, Ganesh Ajjanagadde
> <gajjanagadde at gmail.com> wrote:
>> This uses Stein's binary GCD algorithm:
>> https://en.wikipedia.org/wiki/Binary_GCD_algorithm
>> to get a reported 1.7-2.1x speedup over Euclidean GCD on standard architectures.
>> Have not benchmarked, so I can't comment
>
> Before you submit a patch that's supposed to make something faster,
> you should benchmark it to verify that it is in fact faster. Do this
> with inputs of various sizes on both 32- and 64-bit architectures and
> both with and without compilers that support __builtin_ctzll(v).

I did not do this because I don't know how to write a benchmark in C
easily: for instance, printing out can lead to I/O time loss, and on
O3, unless there is I/O, a function may not be evaluated at all due to
the "as if" optimization rules. Another problem is that the function
is small, so I can't just time a single call, there are cache issues
with arrays, etc etc. Yes, I can do it - but it will take some effort.

Also, the only compilers I have are clang and gcc, both of which have
the builtin. I figured someone with a better array of tools and more
knowledgable in writing benchmarks can trivially do this. Furthermore,
at the moment, comparisons are incomplete: I don't care about Windows
myself but one could trivially add the lines if one so desired (see my
commit message).

Lastly, I can't find any links on how to do benchmarks cleanly,
efficiently, and accurately. I hoped that FFmpeg has some clean way of
doing this, but all the methods I see are terribly ad-hoc.

> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel at ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel