Skip to content

Specialize CombinationsWithReplacement::nth#923

Merged
Philippe-Cholet merged 4 commits intorust-itertools:masterfrom
Philippe-Cholet:nth-combination-with-repl
Apr 26, 2024
Merged

Specialize CombinationsWithReplacement::nth#923
Philippe-Cholet merged 4 commits intorust-itertools:masterfrom
Philippe-Cholet:nth-combination-with-repl

Conversation

@Philippe-Cholet
Copy link
Copy Markdown
Member

@Philippe-Cholet Philippe-Cholet commented Apr 25, 2024 •
edited
Loading

Similarly to #914, I reorder CombinationsWithReplacement::next then specialize CombinationsWithReplacement::nth.

Benchmarks similar to #916 (comment)

cargo bench --bench specializations "combinations_with_replacement./(next|nth)"

Same allocations for:
1/next  [276.51 µs 277.04 µs 277.59 µs] [242.27 µs 242.93 µs 243.57 µs] [-13.937% -11.156% -8.0886%]
2/next  [278.45 µs 281.24 µs 284.58 µs] [251.73 µs 252.30 µs 252.90 µs] [-10.006% -9.0960% -8.1830%]
3/next  [275.74 µs 276.22 µs 276.80 µs] [227.55 µs 227.96 µs 228.36 µs] [-17.592% -16.847% -15.849%]
4/next  [265.08 µs 265.89 µs 266.76 µs] [241.05 µs 241.74 µs 242.47 µs] [-8.2684% -6.9087% -4.9878%]

Same allocations for:
1/nth/0 [2.7809 ms 2.7854 ms 2.7899 ms] [2.7524 ms 2.7612 ms 2.7709 ms] [-1.1968% -0.8696% -0.4725%]
2/nth/0 [2.7375 ms 2.7441 ms 2.7511 ms] [2.7761 ms 2.7871 ms 2.8002 ms] [+1.0923% +1.5657% +2.1318%]
3/nth/0 [2.8067 ms 2.8120 ms 2.8186 ms] [2.8385 ms 2.8534 ms 2.8709 ms] [+0.8478% +1.4726% +2.0929%]
4/nth/0 [2.5950 ms 2.5989 ms 2.6031 ms] [2.7731 ms 2.7777 ms 2.7830 ms] [+6.6335% +6.8806% +7.1368%]

-50% allocations for:
1/nth/1 [2.6836 ms 2.6882 ms 2.6929 ms] [1.4259 ms 1.4310 ms 1.4370 ms] [-46.934% -46.723% -46.471%]
2/nth/1 [2.7765 ms 2.7813 ms 2.7863 ms] [1.4193 ms 1.4270 ms 1.4355 ms] [-48.727% -48.488% -48.212%]
3/nth/1 [2.7947 ms 2.7994 ms 2.8045 ms] [1.4820 ms 1.4890 ms 1.4975 ms] [-46.859% -46.415% -45.916%]
4/nth/1 [2.6290 ms 2.6396 ms 2.6512 ms] [1.4378 ms 1.4436 ms 1.4532 ms] [-45.435% -45.103% -44.747%]

-67% allocations for:
1/nth/2 [2.7839 ms 2.7921 ms 2.8035 ms] [994.40 µs 999.99 µs 1.0072 ms] [-64.439% -64.203% -63.992%]
2/nth/2 [2.8508 ms 2.8547 ms 2.8589 ms] [986.24 µs 989.15 µs 992.24 µs] [-65.565% -65.432% -65.269%]
3/nth/2 [2.8938 ms 2.8980 ms 2.9023 ms] [1.0342 ms 1.0422 ms 1.0514 ms] [-64.243% -64.039% -63.847%]
4/nth/2 [2.7616 ms 2.7652 ms 2.7687 ms] [1.0504 ms 1.0536 ms 1.0568 ms] [-61.853% -61.580% -61.243%]

-80% allocations for:
1/nth/4 [2.7153 ms 2.7193 ms 2.7249 ms] [648.35 µs 650.19 µs 652.55 µs] [-75.952% -75.820% -75.684%]
2/nth/4 [2.7615 ms 2.7676 ms 2.7744 ms] [633.59 µs 634.88 µs 636.35 µs] [-76.885% -76.651% -76.382%]
3/nth/4 [2.8553 ms 2.8602 ms 2.8651 ms] [649.37 µs 652.42 µs 656.35 µs] [-77.134% -76.873% -76.551%]
4/nth/4 [2.7362 ms 2.7388 ms 2.7415 ms] [686.40 µs 688.99 µs 691.59 µs] [-74.836% -74.587% -74.255%]

-89% allocations for:
1/nth/8 [2.7403 ms 2.7499 ms 2.7600 ms] [431.48 µs 432.98 µs 434.67 µs] [-84.242% -84.024% -83.746%]
2/nth/8 [2.7270 ms 2.7574 ms 2.7969 ms] [398.89 µs 400.00 µs 401.43 µs] [-85.675% -85.462% -85.276%]
3/nth/8 [2.8713 ms 2.8850 ms 2.9016 ms] [417.89 µs 419.27 µs 420.81 µs] [-85.646% -85.553% -85.470%]
4/nth/8 [2.6630 ms 2.6712 ms 2.6812 ms] [460.50 µs 461.09 µs 461.68 µs] [-82.851% -82.770% -82.700%]

I did not expect next to be a bit faster but I'm not complaining.
.nth(0) is a little bit slower but other .nth(..)s are faster, closely following allocations changes.

@Philippe-Cholet
CombinationsWithReplacement::increment_indices
8459f93 
Steal how `next` increment indices, a bit improved.
It will soon be used in `nth` (and more later).
@Philippe-Cholet
Update CombinationsWithReplacement::next (1)
271b55f 
Use the new `increment_indices`. This is done in a different commit because the git difference was difficult to read.
@Philippe-Cholet
Update CombinationsWithReplacement::next (2)
a04e0bc 
Use `pool.get_at` once! That way, `next` and `nth` will ressemble each other.
@Philippe-Cholet
Specialize CombinationsWithReplacement::nth
a250651 
Similar to `next` except we increment indices n times before generating the vector item.
@Philippe-Cholet Philippe-Cholet added this to the next milestone Apr 25, 2024
@codecov
Copy link
Copy Markdown

codecov Bot commented Apr 25, 2024 •
edited
Loading

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 94.51%. Comparing base (6814180) to head (a250651).
Report is 59 commits behind head on master.

Additional details and impacted files 
@@            Coverage Diff             @@
##           master     #923      +/-   ##
==========================================
+ Coverage   94.38%   94.51%   +0.12%     
==========================================
  Files          48       48              
  Lines        6665     6890     +225     
==========================================
+ Hits         6291     6512     +221     
- Misses        374      378       +4

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

phimuemue
phimuemue reviewed Apr 26, 2024
View reviewed changes
Copy link
Copy Markdown
Member

@phimuemue phimuemue left a comment •
edited
Loading

Choose a reason for hiding this comment

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

Thanks @Philippe-Cholet. I think it's technically correct, although I'd rewrite some parts. If you like your proposal better, fine with me.

Should we extract the "initialization" part into an own function?

Comment thread src/combinations_with_replacement.rs Outdated
Comment thread src/combinations_with_replacement.rs
phimuemue
phimuemue reviewed Apr 26, 2024
View reviewed changes
Comment thread src/combinations_with_replacement.rs Outdated
@Philippe-Cholet Philippe-Cholet force-pushed the nth-combination-with-repl branch from 210e6e4 to a250651 Compare April 26, 2024 10:21
Philippe-Cholet
Philippe-Cholet commented Apr 26, 2024
View reviewed changes
Comment thread src/combinations_with_replacement.rs
@Philippe-Cholet Philippe-Cholet added this pull request to the merge queue Apr 26, 2024
Merged via the queue into rust-itertools:master with commit dd6a569 Apr 26, 2024
@Philippe-Cholet Philippe-Cholet deleted the nth-combination-with-repl branch April 26, 2024 12:21
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@phimuemue phimuemue phimuemue approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

0.13.0

Development

Successfully merging this pull request may close these issues.

2 participants

@Philippe-Cholet @phimuemue