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

2015-10-22 Thread Michael Niedermayer
On Thu, Oct 22, 2015 at 08:53:07AM -0400, Ganesh Ajjanagadde wrote: > On Thu, Oct 22, 2015 at 8:42 AM, Ganesh Ajjanagadde wrote: > > On Thu, Oct 22, 2015 at 8:33 AM, Michael Niedermayer > > wrote: > >> On Thu, Oct 22, 2015 at 07:04:41AM -0400, Ganesh Ajjanagadde wrote: > >>> On Thu, Oct 22, 2015

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

2015-10-22 Thread Ganesh Ajjanagadde
On Thu, Oct 22, 2015 at 8:42 AM, Ganesh Ajjanagadde wrote: > On Thu, Oct 22, 2015 at 8:33 AM, Michael Niedermayer > wrote: >> On Thu, Oct 22, 2015 at 07:04:41AM -0400, Ganesh Ajjanagadde wrote: >>> On Thu, Oct 22, 2015 at 5:49 AM, Carl Eugen Hoyos wrote: >>> > Ganesh Ajjanagadde gmail.com> writ

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

2015-10-22 Thread Ganesh Ajjanagadde
On Thu, Oct 22, 2015 at 8:33 AM, Michael Niedermayer wrote: > On Thu, Oct 22, 2015 at 07:04:41AM -0400, Ganesh Ajjanagadde wrote: >> On Thu, Oct 22, 2015 at 5:49 AM, Carl Eugen Hoyos wrote: >> > Ganesh Ajjanagadde gmail.com> writes: >> > >> >> > This broke fate with -ftrapv >> > >> >> > The prob

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

2015-10-22 Thread Michael Niedermayer
On Thu, Oct 22, 2015 at 07:04:41AM -0400, Ganesh Ajjanagadde wrote: > On Thu, Oct 22, 2015 at 5:49 AM, Carl Eugen Hoyos wrote: > > Ganesh Ajjanagadde gmail.com> writes: > > > >> > This broke fate with -ftrapv > > > >> > The problem seems to be in av_gcd() and not the De-Bruijn version of > >> > f

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

2015-10-22 Thread Ganesh Ajjanagadde
On Thu, Oct 22, 2015 at 5:49 AM, Carl Eugen Hoyos wrote: > Ganesh Ajjanagadde gmail.com> writes: > >> > This broke fate with -ftrapv > >> > The problem seems to be in av_gcd() and not the De-Bruijn version of >> > ff_ctzll since the gcc builtin is being used. >> >> Don't have the time to investig

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

2015-10-22 Thread Carl Eugen Hoyos
Ganesh Ajjanagadde gmail.com> writes: > > This broke fate with -ftrapv > > The problem seems to be in av_gcd() and not the De-Bruijn version of > > ff_ctzll since the gcc builtin is being used. > > Don't have the time to investigate right now - revert for now unless > someone can fix it quickly

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

2015-10-20 Thread Ganesh Ajjanagadde
On Tue, Oct 20, 2015 at 12:52 AM, James Almer wrote: > On 10/11/2015 12:45 AM, Michael Niedermayer wrote: >> On Sat, Oct 10, 2015 at 09:58:47PM -0400, Ganesh Ajjanagadde wrote: >>> This uses Stein's binary GCD algorithm: >>> https://en.wikipedia.org/wiki/Binary_GCD_algorithm >>> to get a roughly 4

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

2015-10-20 Thread Ganesh Ajjanagadde
On Tue, Oct 20, 2015 at 12:52 AM, James Almer wrote: > On 10/11/2015 12:45 AM, Michael Niedermayer wrote: >> On Sat, Oct 10, 2015 at 09:58:47PM -0400, Ganesh Ajjanagadde wrote: >>> This uses Stein's binary GCD algorithm: >>> https://en.wikipedia.org/wiki/Binary_GCD_algorithm >>> to get a roughly 4

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

2015-10-19 Thread James Almer
On 10/11/2015 12:45 AM, Michael Niedermayer wrote: > On Sat, Oct 10, 2015 at 09:58:47PM -0400, Ganesh Ajjanagadde wrote: >> This uses Stein's binary GCD algorithm: >> https://en.wikipedia.org/wiki/Binary_GCD_algorithm >> to get a roughly 4x speedup over Euclidean GCD on standard architectures >> wi

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

2015-10-11 Thread Ganesh Ajjanagadde
On Sun, Oct 11, 2015 at 12:33 PM, wm4 wrote: > On Sun, 11 Oct 2015 09:59:39 -0400 > Ganesh Ajjanagadde wrote: > >> On Sun, Oct 11, 2015 at 9:34 AM, wm4 wrote: >> > On Sat, 10 Oct 2015 21:58:47 -0400 >> > Ganesh Ajjanagadde wrote: >> > >> >> This uses Stein's binary GCD algorithm: >> >> https://

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

2015-10-11 Thread wm4
On Sun, 11 Oct 2015 09:59:39 -0400 Ganesh Ajjanagadde wrote: > On Sun, Oct 11, 2015 at 9:34 AM, wm4 wrote: > > On Sat, 10 Oct 2015 21:58:47 -0400 > > Ganesh Ajjanagadde wrote: > > > >> This uses Stein's binary GCD algorithm: > >> https://en.wikipedia.org/wiki/Binary_GCD_algorithm > >> to get a

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

2015-10-11 Thread Ganesh Ajjanagadde
On Sun, Oct 11, 2015 at 9:34 AM, wm4 wrote: > On Sat, 10 Oct 2015 21:58:47 -0400 > Ganesh Ajjanagadde wrote: > >> This uses Stein's binary GCD algorithm: >> https://en.wikipedia.org/wiki/Binary_GCD_algorithm >> to get a roughly 4x speedup over Euclidean GCD on standard architectures >> with a com

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

2015-10-11 Thread wm4
On Sat, 10 Oct 2015 21:58:47 -0400 Ganesh Ajjanagadde wrote: > This uses Stein's binary GCD algorithm: > https://en.wikipedia.org/wiki/Binary_GCD_algorithm > to get a roughly 4x speedup over Euclidean GCD on standard architectures > with a compiler intrinsic for ctzll, and a roughly 2x speedup ot

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

2015-10-10 Thread Michael Niedermayer
On Sat, Oct 10, 2015 at 09:58:47PM -0400, Ganesh Ajjanagadde wrote: > This uses Stein's binary GCD algorithm: > https://en.wikipedia.org/wiki/Binary_GCD_algorithm > to get a roughly 4x speedup over Euclidean GCD on standard architectures > with a compiler intrinsic for ctzll, and a roughly 2x speed

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

2015-10-10 Thread Ganesh Ajjanagadde
This uses Stein's binary GCD algorithm: https://en.wikipedia.org/wiki/Binary_GCD_algorithm to get a roughly 4x speedup over Euclidean GCD on standard architectures with a compiler intrinsic for ctzll, and a roughly 2x speedup otherwise. At the moment, the compiler intrinsic is used on GCC and Clang