[issue35588] Speed up mod/divmod/floordiv for Fraction type

Serhiy Storchaka added the comment: Thank you for your contribution Stefan! I am sorry for an awful commit message. I edited it, but due to some bug on GitHub the edited commit message was ignored after pressing the "Try merge" button. I heart this is not the first time of ignoring the

[issue35588] Speed up mod/divmod/floordiv for Fraction type

Serhiy Storchaka added the comment: New changeset 3a374e0c5abe805667b71ffaaa7614781101ff4c by Serhiy Storchaka (Stefan Behnel) in branch 'master': bpo-35588: Speed up mod, divmod and floordiv operations for Fraction type (#11322)

[issue35588] Speed up mod/divmod/floordiv for Fraction type

Mark Dickinson added the comment: > since the code with divmod() is simpler, I think it is worth to use it. +1 from me, and +1 on the PR in general. -- ___ Python tracker

[issue35588] Speed up mod/divmod/floordiv for Fraction type

Serhiy Storchaka added the comment: Using divmod() makes the case of small integers 2-3% slower, but makes the case of large integers more significantly faster. And since the code with divmod() is simpler, I think it is worth to use it. The Fraction class also serves educational goals. The

[issue35588] Speed up mod/divmod/floordiv for Fraction type

Josh Rosenberg added the comment: divmod imposes higher fixed overhead in exchange for operating more efficiently on larger values. Given the differences are small either way, and using divmod reduces scalability concerns for larger values (which are more likely to occur in code that

[issue35588] Speed up mod/divmod/floordiv for Fraction type

Stefan Behnel added the comment: Thanks for your review and ideas, Serhiy. I added a couple of test cases, but failed to find any case where the new implementation is not much faster. I also tried "divmod(n_div, d_div)" for implementing __divmod__(), and the results are mixed, e.g.

[issue35588] Speed up mod/divmod/floordiv for Fraction type

Serhiy Storchaka added the comment: I want to check whether removing the normalization step has a negative performance effect larger than the time spent on normalization. -- ___ Python tracker

[issue35588] Speed up mod/divmod/floordiv for Fraction type

Stefan Behnel added the comment: Sure, I can add tests, but I wonder what kind of regression you expect. The algorithm is still the same as before, it's just implemented more efficiently. It does trade a bit of memory for the speed, though, since there is no longer an intermediate

[issue35588] Speed up mod/divmod/floordiv for Fraction type

Serhiy Storchaka added the comment: Please make several additional tests, and ensure that there is no regression. 1. Test with fractions with the same large denominator (for example 2**50, 2**100, 10**30, 3**50, factorial(30), or a large pseudo-primary number) and small and large

[issue35588] Speed up mod/divmod/floordiv for Fraction type

Stefan Behnel added the comment: Motivation for the latter: $ ./python -m timeit -s 'from fractions import Fraction as F; a = F(-7, 3); b = F(3, 2)' 'a // b' 10 loops, best of 5: 3.7 usec per loop $ ./python -m timeit -s 'from fractions import Fraction as F; a = F(-7, 3); b = F(3, 2)'