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

Michael Niedermayer michael at niedermayer.cc
Sun Oct 11 01:14:27 CEST 2015

On Sat, Oct 10, 2015 at 11:32:06PM +0200, Henrik Gramner 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).

without __builtin_ctzll() the old code seems faster in a simple test
make -j12 && ./ffmpeg -i matrixbench_mpeg2.mpg test.mov

also it seems a simple
    while (u != v) {
        if (u > v)
            FFSWAP(int64_t, v, u);
        v -= u;
        do {
            v >>= 1;
        } while(!(v & 1));
is faster than the non builtin ctzll in its place but still not as
fast as the current code

Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

What does censorship reveal? It reveals fear. -- Julian Assange
-------------- 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/20151011/518f2f1f/attachment.sig>

More information about the ffmpeg-devel mailing list