Added more efficient unionWith, eliminate transformation Map to List in Foldable{WithIndex} instances.#60
Merged
JordanMartinez merged 6 commits intopurescript:masterfrom Apr 22, 2022
Conversation
…List` in `Foldable{WithIndex}` instances
JordanMartinez
suggested changes
Apr 21, 2022
Contributor
JordanMartinez
left a comment
There was a problem hiding this comment.
Could you check what the benchmarks are if the Foldable instances are updated?
Contributor
|
With the |
JordanMartinez
approved these changes
Apr 21, 2022
Contributor
JordanMartinez
left a comment
There was a problem hiding this comment.
Thanks @xgrommx.
Would you mind pushing a changelog entry stating that the speed was improved?
Contributor
natefaubion
reviewed
Apr 21, 2022
natefaubion
reviewed
Apr 21, 2022
| instance foldableMap :: Foldable (Map k) where | ||
| foldl f z m = foldl f z (values m) | ||
| foldr f z m = foldr f z (values m) | ||
| foldMap f m = foldMap f (values m) |
Contributor
There was a problem hiding this comment.
Should we implement values in terms of foldr? Seems like values being accidentally quadratic is a huge problem.
Contributor
There was a problem hiding this comment.
He means the values function. Since it produces a List, and each list part is concatenated via <>, which traverses over the list on the left side again (e.g. 1 : 2 : 3 : Nil <> 4 : Nil), then there's room for optimization here.
Contributor
There was a problem hiding this comment.
In other words, rather than building multiple lists that get appended together, which requires iterating through list parts a second time, we could just build the final list in one go, no traversals needed:
values :: forall k v. Map k v -> List v
values Leaf = Nil
-values (Two left _ v right) = values left <> pure v <> values right
+values (Two left _ v right) = foldr Cons (Cons v (foldr Cons Nil right)) left
-values (Three left _ v1 mid _ v2 right) =
- values left <> pure v1 <> values mid <> pure v2 <> values right
+values (Three left _ v1 mid _ v2 right) =
+ foldr Cons (Cons v1 (foldr Cons (Cons v2 (foldr Cons Nil right) mid))) left
Contributor
There was a problem hiding this comment.
Ha! I'm dumb. Actually, values is just foldr Cons Nil.
values :: forall k v. Map k v -> List v
values = foldr Cons Nil
Contributor
There was a problem hiding this comment.
How do you like them apples?
Map
===
values
---------------
Map2a0bff.values: big map (1000000)
mean = 2.89 s
stddev = 302.43 ms
min = 2.52 s
max = 3.43 s
M.values: big map (1000000)
mean = 278.44 ms
stddev = 4.57 ms
min = 271.75 ms
max = 287.72 ms
Contributor
|
This is really great work! Thanks! |
JordanMartinez
approved these changes
Apr 22, 2022
thomashoneyman
approved these changes
Apr 22, 2022
Member
thomashoneyman
left a comment
There was a problem hiding this comment.
Fantastic work! Thank you!
4 tasks
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
4 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Here benchmark results