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

[Ganesh Ajjanagadde]

On Sat, Oct 10, 2015 at 6:10 PM, James Darnley <james.darnley at gmail.com> wrote:
> On 2015-10-10 23:06, Ganesh Ajjanagadde wrote:
>> ...
>
> Is the greatest common denominator (yes, I had to look that up) actually
> used anywhere that is slow and needs to be fast?
>
> All the uses of 'av_gcd' found by grep appear be dealing with timing.  I
> see framerate, timebase, scale.  I do see uses in rational.c which
> implies uses through AVRational, how many codecs are using rational
> numbers in their processing?
>
> I think this is a case of premature optimization.

The new algorithm is essentially as readable as the old one, is well
established and is widely used. FFmpeg accepts commits even for a 10%
improvement in an init function (commit
1bc873acd6e15eaca8c2aebfd7dc6472b0429c50) that is rarely called.
av_gcd is actually more widely used than the resampler init, so this
should be at least as useful.

Also, av_gcd is used in the rescale functions, which are very widely
used. Maybe in avcodec they are mostly for timestamps, but avfilter
uses rescaling heavily.

>
> On the other hand if people want to replace the current algorithm then
> who am I to stop them.

I don't care either way. If FFmpeg does not want simple speed
improvements like this, then I will return to fixing bugs, security
issues, etc.

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