Skip to content

bpo-35431: Refactor math.comb() implementation. - #13725

Merged
serhiy-storchaka merged 8 commits into
python:masterfrom
serhiy-storchaka:math-comb
Jun 1, 2019
Merged

bpo-35431: Refactor math.comb() implementation.#13725
serhiy-storchaka merged 8 commits into
python:masterfrom
serhiy-storchaka:math-comb

Conversation

@serhiy-storchaka

@serhiy-storchaka serhiy-storchaka commented Jun 1, 2019 •
edited
Loading

Copy link
Copy Markdown
Member
  • It now accepts arbitrary index-likes objects, not just int.
  • Fixed some subtle bugs which may be exposed when arguments are int subclasses with overridden __sub__, __lt__, etc.
  • MemoryError is now always raised for too large min(k, n-k). Previously MemoryError or OverflowError could be raised depending on the value.
  • Fixed leaks.
  • Improved error messages.
  • Cleaned up and optimized the code. Optimization is technical, not algorithmic.

https://bugs.python.org/issue35431

mdickinson
mdickinson reviewed Jun 1, 2019
View reviewed changes
Comment thread Modules/mathmodule.c Outdated
mdickinson
mdickinson reviewed Jun 1, 2019
View reviewed changes
Comment thread Modules/mathmodule.c Outdated
mdickinson
mdickinson reviewed Jun 1, 2019
View reviewed changes
Comment thread Lib/test/test_math.py Outdated
mdickinson
mdickinson approved these changes Jun 1, 2019
View reviewed changes

@mdickinson mdickinson left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Changes LGTM, as far as they go.

I'm not particularly happy with the current error messages: I'd expect comb(-1, 1) to complain that n is negative, instead of complaining that n should be larger than k. And the code path that leads to that error isn't obvious, either. What do you think about adding an up-front check for the sign of n, with a corresponding error message? There would be a (very) small performance cost (a Py_SIGN check should be cheap), but I think the improvement would be worth it.

Anyway, that's not a problem introduced by this PR, and fixing it doesn't have to happen in this PR either.

@mdickinson

mdickinson commented Jun 1, 2019

Copy link
Copy Markdown
Member

One more thought: should we be using OverflowError rather than MemoryError in the large cases? I think that's what factorial does. For me, neither exception class quite fits: I'd prefer that MemoryError were restricted to genuine failures of memory allocation attempts, and there isn't actually an overflow. But maybe it's worth being consistent with factorial.

@pablogsal

pablogsal commented Jun 1, 2019

Copy link
Copy Markdown
Member

I was reviewing this PR and realized the original implementation is leaking references I opened

https://bugs.python.org/issue37125

pablogsal
pablogsal reviewed Jun 1, 2019
View reviewed changes
Comment thread Modules/mathmodule.c Outdated
@pablogsal

pablogsal commented Jun 1, 2019

Copy link
Copy Markdown
Member

I checked and this PR is fixing the leak:

❯ ./python -m test test_math -R :
Run tests sequentially
0:00:00 load avg: 1.55 [1/1] test_math
beginning 9 repetitions
123456789
.........

== Tests result: SUCCESS ==

1 test OK.

Total duration: 26 sec 283 ms
Tests result: SUCCESS

pablogsal
pablogsal reviewed Jun 1, 2019
View reviewed changes
Comment thread Modules/mathmodule.c
@codecov

codecov Bot commented Jun 1, 2019 •
edited
Loading

Copy link
Copy Markdown

Codecov Report

Merging #13725 into master will increase coverage by <.01%.
The diff coverage is 90.54%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master   #13725      +/-   ##
==========================================
+ Coverage   82.76%   82.77%   +<.01%     
==========================================
  Files        1843     1843              
  Lines      559928   559938      +10     
  Branches    41403    41403              
==========================================
+ Hits       463425   463485      +60     
+ Misses      87422    87386      -36     
+ Partials     9081     9067      -14
Impacted Files Coverage Δ
Modules/clinic/mathmodule.c.h 87.28% <ø> (-0.43%) ⬇️
Lib/test/test_math.py 94% <100%> (+0.07%) ⬆️
Modules/mathmodule.c 91.81% <88.13%> (+0.32%) ⬆️
Lib/test/test_asyncio/functional.py 71.19% <0%> (-0.55%) ⬇️
Python/_warnings.c 77.1% <0%> (-0.16%) ⬇️
Objects/obmalloc.c 82.62% <0%> (-0.14%) ⬇️
Lib/test/test_bdb.py 53.64% <0%> (ø) ⬆️
Lib/test/test_importlib/util.py 87.97% <0%> (ø) ⬆️
Lib/test/test_sys_settrace.py 38.06% <0%> (ø) ⬆️
Lib/pydoc.py 63.95% <0%> (ø) ⬆️
... and 18 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 6650105...492b211. Read the comment docs.

pablogsal
pablogsal reviewed Jun 1, 2019
View reviewed changes
Comment thread Doc/library/math.rst Outdated
@serhiy-storchaka @pablogsal
Update Doc/library/math.rst
492b211 
Co-Authored-By: Pablo Galindo <[email protected]>
mdickinson
mdickinson reviewed Jun 1, 2019
View reviewed changes
Comment thread Modules/mathmodule.c Outdated
mdickinson
mdickinson reviewed Jun 1, 2019
View reviewed changes
Comment thread Modules/mathmodule.c Outdated
mdickinson
mdickinson approved these changes Jun 1, 2019
View reviewed changes

@mdickinson mdickinson left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Still LGTM

@serhiy-storchaka
serhiy-storchaka merged commit 2b843ac into python:master Jun 1, 2019
@serhiy-storchaka
serhiy-storchaka deleted the math-comb branch June 1, 2019 19:09
DinoV pushed a commit to DinoV/cpython that referenced this pull request Jan 14, 2020
@serhiy-storchaka @DinoV
bpo-35431: Refactor math.comb() implementation. (pythonGH-13725)
c427641 
* Fixed some bugs.
* Added support for index-likes objects.
* Improved error messages.
* Cleaned up and optimized the code.
* Added more tests.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@pablogsal pablogsal pablogsal approved these changes
+1 more reviewer
@mdickinson mdickinson mdickinson approved these changes
Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

skip news

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@serhiy-storchaka @mdickinson @pablogsal @the-knights-who-say-ni @bedevere-bot