mhostetter / galois

A performant NumPy extension for Galois fields and their applications
https://mhostetter.github.io/galois/
MIT License
321 stars 29 forks source link

Memoize expensive polynomial tests #470

Closed mhostetter closed 1 year ago

mhostetter commented 1 year ago

The memoization overhead doesn't hurt for small polynomials, but really helps for large polynomials.

Before

In [1]: import galois

In [2]: %time polys = list(galois.primitive_polys(7, 35, terms=3))
CPU times: user 9.03 s, sys: 0 ns, total: 9.03 s
Wall time: 8.89 s

# Paying the computation cost again
In [3]: %time polys[0].is_irreducible()
CPU times: user 12.1 ms, sys: 0 ns, total: 12.1 ms
Wall time: 10.7 ms
Out[3]: True

# Paying the computation cost again
In [4]: %time polys[0].is_primitive()
CPU times: user 21 ms, sys: 0 ns, total: 21 ms
Wall time: 20 ms
Out[4]: True

After

In [1]: import galois

In [2]: %time polys = list(galois.primitive_polys(7, 35, terms=3))
CPU times: user 8.93 s, sys: 0 ns, total: 8.93 s
Wall time: 8.78 s

# LRU cache lookup
In [3]: %time polys[0].is_irreducible()
CPU times: user 117 µs, sys: 0 ns, total: 117 µs
Wall time: 75.1 µs
Out[3]: True

# LRU cache lookup
In [4]: %time polys[0].is_primitive()
CPU times: user 107 µs, sys: 0 ns, total: 107 µs
Wall time: 82.5 µs
Out[4]: True
codecov[bot] commented 1 year ago

Codecov Report

Base: 96.40% // Head: 96.48% // Increases project coverage by +0.07% :tada:

Coverage data is based on head (b436e61) compared to base (0fa9721). Patch coverage: 98.61% of modified lines in pull request are covered.

:exclamation: Current head b436e61 differs from pull request most recent head 84f2a73. Consider uploading reports for the commit 84f2a73 to get more accurate results

Additional details and impacted files ```diff @@ Coverage Diff @@ ## release/0.3.x #470 +/- ## ================================================= + Coverage 96.40% 96.48% +0.07% ================================================= Files 43 48 +5 Lines 5708 5775 +67 ================================================= + Hits 5503 5572 +69 + Misses 205 203 -2 ``` | [Impacted Files](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter) | Coverage Δ | | |---|---|---| | [src/galois/\_polys/\_dense.py](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-c3JjL2dhbG9pcy9fcG9seXMvX2RlbnNlLnB5) | `96.45% <ø> (-0.36%)` | :arrow_down: | | [src/galois/\_polys/\_primitive.py](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-c3JjL2dhbG9pcy9fcG9seXMvX3ByaW1pdGl2ZS5weQ==) | `99.04% <96.77%> (-0.96%)` | :arrow_down: | | [src/galois/\_polys/\_search.py](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-c3JjL2dhbG9pcy9fcG9seXMvX3NlYXJjaC5weQ==) | `97.36% <97.36%> (ø)` | | | [src/galois/\_polys/\_factor.py](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-c3JjL2dhbG9pcy9fcG9seXMvX2ZhY3Rvci5weQ==) | `98.23% <98.23%> (ø)` | | | [src/galois/\_polys/\_\_init\_\_.py](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-c3JjL2dhbG9pcy9fcG9seXMvX19pbml0X18ucHk=) | `100.00% <100.00%> (ø)` | | | [src/galois/\_polys/\_constructors.py](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-c3JjL2dhbG9pcy9fcG9seXMvX2NvbnN0cnVjdG9ycy5weQ==) | `100.00% <100.00%> (ø)` | | | [src/galois/\_polys/\_conway.py](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-c3JjL2dhbG9pcy9fcG9seXMvX2NvbndheS5weQ==) | `100.00% <100.00%> (ø)` | | | [src/galois/\_polys/\_functions.py](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-c3JjL2dhbG9pcy9fcG9seXMvX2Z1bmN0aW9ucy5weQ==) | `100.00% <100.00%> (ø)` | | | [src/galois/\_polys/\_irreducible.py](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-c3JjL2dhbG9pcy9fcG9seXMvX2lycmVkdWNpYmxlLnB5) | `100.00% <100.00%> (ø)` | | | [src/galois/\_polys/\_lagrange.py](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-c3JjL2dhbG9pcy9fcG9seXMvX2xhZ3JhbmdlLnB5) | `100.00% <100.00%> (ø)` | | | ... and [2 more](https://codecov.io/gh/mhostetter/galois/pull/470?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter) | | Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter)

:umbrella: View full report at Codecov.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.

mhostetter commented 1 year ago

@iyanmv just tagging you here in case you wanted to review this. I'm thinking of merging this onto release/0.3.x. I believe it should not conflict with your branch when rebasing.

If you have any thoughts or concerns, we can address them before I merge.

iyanmv commented 1 year ago

Oh, wow! Nice! I now understand all those @functools.lru_cache(maxsize=8192) in the code 😄 . I will not have time to review this properly, unfortunately, so don't wait for me to merge.