1821362 - Write a fast GCD algorithm

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Paul Adenot (:padenot)]

I'm going to reduce a bunch of fractions in another patch, and the gcd algorithm we have is very naive, lets get something faster.

Comment 1

[Paul Adenot (:padenot)]

Attachment: bench-gcd.cpp

Compile with:

clang++ -O3 bench-gcd.cpp -std=c++17

sample run on x86_64:

~::$ ./a.out
reducing 1000000 fractions
binary -- took: 99391810ns (99.3918ns per fraction) 307709210 cycles, 307.709 per fractions
euclid -- took: 1003870058ns (1003.87ns per fraction) 3107962156 cycles, 3107.96 per fractions

That's about a 10x speedup.

On the g++ I have locally, the speedup is less pronounced: the new version is slower than clang (~170ns per fraction), the old version is faster than clang (~656ns per fraction). Weird but also not that problematic.

Comment 2

[André Bargull [:anba]]

Could we actually just switch to std::gcd https://en.cppreference.com/w/cpp/numeric/gcd?

Comment 3

[Paul Adenot (:padenot)]

It's ~10% slower than my code on the clang we use at the optimization level we use.

Comment 4

[[:sergesanspaille]]

The implementation available in https://en.algorithmica.org/hpc/algorithms/gcd/ avoids a few branching and is, in my setup, more than two times faster than the version linked to this patch. It's worth giving it a try :-)

Comment 5

[Mayank Bansal]

Attachment: GCD_ChatGPT.txt

I asked ChatGPT for some answers, and it gave these 4 versions.

Comment 6

[Paul Adenot (:padenot)]

Attachment: Bug 1821362 - Add a generic CountTrailingZeroes function that lowers to the right intrinsic based the type its called with. r?#media-playback-reviewers

Depends on D173313

Comment 7

[Paul Adenot (:padenot)]

Attachment: Bug 1821362 - Replace EuclidGCD by a binary gcd algorithm using intrinsics. r?#media-playback-reviewers

Perf notes:
https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Depends on D173314

Comment 8

[André Bargull [:anba]]

(In reply to Paul Adenot (:padenot) from comment #3)

It's ~10% slower than my code on the clang we use at the optimization level we use.

Looking at the generated assembly code, your version has a tighter loop code when compared to std::gcd. Only after switching to -march=x86-64-v3 both versions generate (essentially) the same code.

Comment 9

[Paul Adenot (:padenot)]

(In reply to André Bargull [:anba] from comment #8)

(In reply to Paul Adenot (:padenot) from comment #3)

It's ~10% slower than my code on the clang we use at the optimization level we use.

Looking at the generated assembly code, your version has a tighter loop code when compared to std::gcd. Only after switching to -march=x86-64-v3 both versions generate (essentially) the same code.

The current code has a version that's 30% faster than the previous one I had, so even faster.

Comment 10

[André Bargull [:anba]]

I think the current version has a bug, because it doesn't handle overflows in T diff = aA - aB;. For example GCD<uint32_t>(3, 7) returns 3, whereas std::gcd<uint32_t>(3, 7) returns the correct result 1.

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/6dd80575e551
Add a generic CountTrailingZeroes function that lowers to the right intrinsic based the type its called with. r=sergesanspaille
https://hg.mozilla.org/integration/autoland/rev/04c60cd83c5f
Replace EuclidGCD by a binary gcd algorithm using intrinsics. r=media-playback-reviewers,alwu

Comment 12

[Cristina Horotan [:chorotan]]

https://hg.mozilla.org/mozilla-central/rev/6dd80575e551
https://hg.mozilla.org/mozilla-central/rev/04c60cd83c5f

Comment 13

[Cosmin Sabou [:CosminS]]

Backed out 80 changesets (bug 1821362, bug 1703812, bug 1817997) for causing media crashes as in Bug 1833890.

Backout link: https://hg.mozilla.org/mozilla-central/rev/225c5ab0d999e743db5298d125893ae0702884af

Comment 14

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/159e2eee7549
Add a generic CountTrailingZeroes function that lowers to the right intrinsic based the type its called with. r=sergesanspaille
https://hg.mozilla.org/integration/autoland/rev/dc506e3ad29d
Replace EuclidGCD by a binary gcd algorithm using intrinsics. r=media-playback-reviewers,alwu

Comment 15

[Narcis Beleuzu [:NarcisB]]

https://hg.mozilla.org/mozilla-central/rev/159e2eee7549
https://hg.mozilla.org/mozilla-central/rev/dc506e3ad29d