Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Improve foldl and foldr for IntSet #667

Open
wants to merge 2 commits into
base: master
Choose a base branch
from
Open

Improve foldl and foldr for IntSet #667

wants to merge 2 commits into from

Conversation

treeowl
Copy link
Contributor

@treeowl treeowl commented Jul 18, 2019

foldrBits was previously defined just like foldr'Bits, and
foldlBits was defined just like foldl'Bits. That is, each of them
built up an accumulator, lazily, across a whole leaf before producing
anything. Swap that around so the folds can process values promptly.

Fixes #666

@treeowl
Improve foldl and foldr for IntSet
7278be6 
`foldrBits` was previously defined just like `foldr'Bits`, and
`foldlBits` was defined just like `foldl'Bits`. That is, each of them
built up an accumulator, lazily, across a whole leaf before producing
anything. Swap that around so the folds can process values promptly.

Fixes haskell#666
@treeowl
Add benchmarks
4863d85
@treeowl
Copy link
Contributor Author

treeowl commented Jul 18, 2019

I've done a bit of benchmarking. My results aren't very stable, but it seems, generally, that foldr is pretty similar (perhaps because of the cost of reversing the bits) while foldl is improved. Perhaps someone better at benchmarking and/or micro-optimization should take a look at it.

@treeowl
Copy link
Contributor Author

treeowl commented Jul 18, 2019

Er.... no, that's not it. The reversing happens with foldl.... I have no explanation.

@treeowl
Copy link
Contributor Author

treeowl commented Jul 22, 2019

@oisdk, this looks like the sort of thing you might know how to think about and test properly. Any ideas?

@meooow25
Copy link
Contributor

@treeowl do you want to continue with this PR? The changes to foldrBits and foldlBits seem ok to me.
Once rebased we could add some benchmarks similar to what we recently added for Data.Tree's foldr and measure if there's an improvement.

@treeowl
Copy link
Contributor Author

treeowl commented Jul 29, 2023

I'm currently recovering from COVID, so can't really do much this week.

@meooow25
Copy link
Contributor

Hope you get well soon! I didn't mean to imply any sort of urgency, this can surely wait.

@treeowl
Copy link
Contributor Author

treeowl commented Jul 29, 2023

I feel bad for making you wait so long on multiple things.

@meooow25
Copy link
Contributor

I have had some free time, don't worry about it 😅

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
IntSet performance
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

IntSet foldl and foldr smell funny
3 participants
@treeowl @meooow25 @sjakobi