Skip to content

perf: don't reuse the same incompatibility repeatedly#88

Merged
Eh2406 merged 2 commits intodevfrom
dont-reuse-incompatibilities
May 22, 2021
Merged

perf: don't reuse the same incompatibility repeatedly#88
Eh2406 merged 2 commits intodevfrom
dont-reuse-incompatibilities

Conversation

@Eh2406
Copy link
Copy Markdown
Member

@Eh2406 Eh2406 commented May 4, 2021

This includes #87, the only new part is the last commit. It is intended to be merged after it.

Most of the time relation for an incompatibility (like A depends on B) is called at least twice, once when A gets added and when B gets added. After the first call we get AlmostSatisfied and change the partial_solution so that it will be contradicted the next time. This adds a HashSet to keep track of all the IncompIds we know will stay contradicted until the next backtrack. IncompId are just a small integer so hash very quickly.

It is possible to figure out witch IncompIds are still used after a backtrack, but so far nothing that is pulls its weight.

Warning: Unable to complete 100 samples in 20.0s. You may wish to increase target time to 23.6s, or reduce sample count to 80.
large_cases/elm_str_SemanticVersion.ron
                        time:   [244.05 ms 244.40 ms 244.79 ms]
                        change: [-9.0431% -8.8780% -8.7172%] (p = 0.00 < 0.05)
                        Performance has improved.
large_cases/large_case_u16_NumberVersion.ron
                        time:   [9.3124 ms 9.3213 ms 9.3302 ms]
                        change: [-13.284% -13.164% -13.049%] (p = 0.00 < 0.05)
                        Performance has improved.
Benchmarking large_cases/zuse_str_SemanticVersion.ron: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 20.0s. You may wish to increase target time to 35.2s, or reduce sample count to 50.
large_cases/zuse_str_SemanticVersion.ron
                        time:   [351.46 ms 351.77 ms 352.08 ms]
                        change: [-12.531% -12.418% -12.310%] (p = 0.00 < 0.05)
                        Performance has improved.

@Eh2406
Copy link
Copy Markdown
Member Author

Eh2406 commented May 6, 2021

There are more complicated structures that can support backtracking or filter out items faster than a HashSet.contains, but this was a simple change with a significant perf improvement. Love to play with a bigger PR, but only after the Range Trait.

@Eh2406 Eh2406 force-pushed the dont-reuse-incompatibilities branch 2 times, most recently from 2cccf26 to 285aba7 Compare May 11, 2021 18:37
@Eh2406
Copy link
Copy Markdown
Member Author

Eh2406 commented May 12, 2021

@mpizenberg Yes, No, or after 0.2.1? Thoughts?

@mpizenberg
Copy link
Copy Markdown
Member

mpizenberg commented May 12, 2021

@Eh2406 sorry haven't had time to check this out. Seems like a good idea but I'll have to wait until the weekend I think to review

@Eh2406
Copy link
Copy Markdown
Member Author

Eh2406 commented May 12, 2021

No rush! Thank you for the thorough reviews. Just wanted to make shore it was still on your radar.

@Eh2406 Eh2406 force-pushed the dont-reuse-incompatibilities branch from 285aba7 to 0eef073 Compare May 15, 2021 23:27
@Eh2406
Copy link
Copy Markdown
Member Author

Eh2406 commented May 21, 2021

I am feeling the urge to try some of the more complicated options. Will you have time to take a look at this before I succumb?

@mpizenberg
Copy link
Copy Markdown
Member

mpizenberg commented May 21, 2021 via email

@mpizenberg mpizenberg force-pushed the dont-reuse-incompatibilities branch 2 times, most recently from 1aa9ee2 to 27f272e Compare May 21, 2021 15:27
@mpizenberg mpizenberg force-pushed the dont-reuse-incompatibilities branch from 27f272e to e6a0fa5 Compare May 21, 2021 15:28
mpizenberg
mpizenberg approved these changes May 21, 2021
View reviewed changes
Copy link
Copy Markdown
Member

@mpizenberg mpizenberg left a comment

Choose a reason for hiding this comment

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

I renamed used_incompatibilities into contradicted_incompatibilities and added a few comments here and there. Let me know if that's ok.
Otherwise, all seems good to me!

@Eh2406
Copy link
Copy Markdown
Member Author

Eh2406 commented May 22, 2021

That is fabulous, thank you!
Do you think the rename should trigger a new 10 day open time or can we merge now?

@mpizenberg
Copy link
Copy Markdown
Member

mpizenberg commented May 22, 2021 via email

@Eh2406 Eh2406 merged commit 3f2c1b9 into dev May 22, 2021
@Eh2406 Eh2406 deleted the dont-reuse-incompatibilities branch May 22, 2021 14:33
@mpizenberg mpizenberg mentioned this pull request May 24, 2021
Closed
@dimbleby dimbleby mentioned this pull request Mar 20, 2022
Merged
@Eh2406 Eh2406 mentioned this pull request Dec 18, 2023
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@mpizenberg mpizenberg mpizenberg approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@Eh2406 @mpizenberg