Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[D145982] [libc++] Implement std::gcd using the binary version #77648

Closed
ldionne opened this issue Jan 10, 2024 · 3 comments · Fixed by #77747
Closed

[D145982] [libc++] Implement std::gcd using the binary version #77648

ldionne opened this issue Jan 10, 2024 · 3 comments · Fixed by #77747
Assignees
@serge-sans-paille @philnik777
Labels
libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi. phabricator Related to migration from Phabricator

Comments

@ldionne
Copy link
Member

ldionne commented Jan 10, 2024

This issue tracks picking up https://reviews.llvm.org/D145982 from the Phabricator archive.
@ldionne ldionne added the libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi. label Jan 10, 2024
@ldionne ldionne added awaiting-review Has pending Phabricator review phabricator Related to migration from Phabricator and removed awaiting-review Has pending Phabricator review labels Jan 10, 2024
@AdvenamTacet
Copy link
Member

I played a little with the benchmark from the Phabricator to test also bigger numbers in gcd. Performance gain is consistent.

But I think, we should add random tests to gcd test - 1000 times taking ranom numbers or numbers from a range and comparing with a naive implementation. Just because this implementation is prone to be bugged during a refactor.

@serge-sans-paille
Copy link
Collaborator

@AdvenamTacet : will do!

@serge-sans-paille serge-sans-paille mentioned this issue Jan 11, 2024
Merged
serge-sans-paille added a commit to serge-sans-paille/llvm-project that referenced this issue Jan 12, 2024
@serge-sans-paille
[libc++] Implement std::gcd using the binary version
9cc8154 
The binary version is four times faster than current implementation
in my setup, and generally considered a better implementation.

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/
which itself is inspired by https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Fix llvm#77648
@AdvenamTacet
Copy link
Member

AdvenamTacet commented Jan 18, 2024 •
edited

I looked at the algorithm closer and described a problem with it in PRs comment. I don't think we should change gcd algorithm to that one.

If I made a mistake in benchmarks, please let me know.

Example of too big performance hit:
https://quick-bench.com/q/pA3seH2pCZjP7WMeIGnUhUXJmrQ (there is a problem with that benchmark, read the discussion in the PR for details).

serge-sans-paille added a commit to serge-sans-paille/llvm-project that referenced this issue Apr 29, 2024
@serge-sans-paille
[libc++] Implement std::gcd using the binary version
baed224 
The binary version is four times faster than current implementation
in my setup, and generally considered a better implementation.

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/
which itself is inspired by https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Fix llvm#77648
serge-sans-paille added a commit to serge-sans-paille/llvm-project that referenced this issue Apr 29, 2024
@serge-sans-paille
[libc++] Implement std::gcd using the binary version
59bbb53 
The binary version is four times faster than current implementation
in my setup, and generally considered a better implementation.

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/
which itself is inspired by https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Hybrid approach and benchmarks inspired by `ylchapuy <https://github.com/ylchapuy>`.

Fix llvm#77648
serge-sans-paille added a commit to serge-sans-paille/llvm-project that referenced this issue May 2, 2024
@serge-sans-paille
[libc++] Implement std::gcd using the binary version
82b4f04 
The binary version is four times faster than current implementation
in my setup, and generally considered a better implementation.

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/
which itself is inspired by https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Hybrid approach and benchmarks inspired by `ylchapuy <https://github.com/ylchapuy>`.

Fix llvm#77648
serge-sans-paille added a commit to serge-sans-paille/llvm-project that referenced this issue May 2, 2024
@serge-sans-paille
[libc++] Implement std::gcd using the binary version
30d20ab 
The binary version is four times faster than current implementation
in my setup, and generally considered a better implementation.

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/
which itself is inspired by https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Hybrid approach and benchmarks inspired by `ylchapuy <https://github.com/ylchapuy>`.

Fix llvm#77648
serge-sans-paille added a commit to serge-sans-paille/llvm-project that referenced this issue May 3, 2024
@serge-sans-paille
[libc++] Implement std::gcd using the binary version
f453cfb 
The binary version is four times faster than current implementation
in my setup, and generally considered a better implementation.

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/
which itself is inspired by https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Hybrid approach and benchmarks inspired by `ylchapuy <https://github.com/ylchapuy>`.

Fix llvm#77648
serge-sans-paille added a commit to serge-sans-paille/llvm-project that referenced this issue May 4, 2024
@serge-sans-paille
[libc++] Implement std::gcd using the binary version
d957ef5 
The binary version is four times faster than current implementation
in my setup, and generally considered a better implementation.

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/
which itself is inspired by https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Hybrid approach and benchmarks inspired by `ylchapuy <https://github.com/ylchapuy>`.

Fix llvm#77648
serge-sans-paille added a commit to serge-sans-paille/llvm-project that referenced this issue May 4, 2024
@serge-sans-paille
[libc++] Implement std::gcd using the binary version
a8a1179 
The binary version is four times faster than current implementation
in my setup, and generally considered a better implementation.

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/
which itself is inspired by https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Hybrid approach and benchmarks inspired by `ylchapuy <https://github.com/ylchapuy>`.

Fix llvm#77648
serge-sans-paille added a commit to serge-sans-paille/llvm-project that referenced this issue May 4, 2024
@serge-sans-paille
[libc++] Implement std::gcd using the binary version
8ea797c 
The binary version is four times faster than current implementation
in my setup, and generally considered a better implementation.

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/
which itself is inspired by https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Hybrid approach and benchmarks inspired by `ylchapuy <https://github.com/ylchapuy>`.

Fix llvm#77648
serge-sans-paille added a commit that referenced this issue May 8, 2024
@serge-sans-paille
[libc++] Implement std::gcd using the binary version (#77747)
27a062e 
The binary version is four times faster than current implementation in
my setup, and generally considered a better implementation.

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/ which
itself is inspired by
https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

Fix #77648
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@serge-sans-paille serge-sans-paille

@philnik777 philnik777

Labels
libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi. phabricator Related to migration from Phabricator
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

[libc++] Implement std::gcd using the binary version serge-sans-paille/llvm-project
4 participants
@ldionne @serge-sans-paille @AdvenamTacet @philnik777