Implement Applicative based API #522
Draft
Conversation
This file contains 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
generateA is used as primitive and all other functions are expressed in it terms. First version goes through intermediate list. This is simplest implementation possible and would serve as baseline for further optimizations
We establish implementation which goes through list as baseline and the we can try to optimize it. Note definition of foldlOf'. It's different from definition in lens<=5.3.3 but it's absolutely necessary to get good perfomance in folds
Does wonders for traversals using Identity
konsumlamm
reviewed
Jan 28, 2025
| go !i | i >= n = pure $ STA unsafeFreeze | ||
| | otherwise = (\a (STA m) -> STA $ \mv -> M.unsafeWrite mv i a >> m mv) | ||
| <$> f i | ||
| <*> go (i + 1) |
There was a problem hiding this comment.
It's probably better to use liftA2 here.
There was a problem hiding this comment.
Probably. But I'm not sure that STA will survive maybe some New-like variant will perform better
Co-authored-by: konsumlamm <44230978+konsumlamm@users.noreply.github.com>
Good point! I forgot about them. But they're simpler since in this case one isn't in business of constructing vector so it simply reduces to fold. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.
Implementation follows plan described in #477 with
generateA :: Applicative f => Int -> (Int -> f a) -> f (v a)as primitive. It is not subject to stream fusion.Writing
generateAis not difficult. Problem is doing it efficiently. Current benchmarks are (suggestions for more are very welcome):First and naive implementation uses list as intermediate data structure. Sum benchmark performs well in this case. Using
STAinstead brings map benchmark on par with explicit loop and produces slight (5-10%) improvements in state and IO benchmark)Currently sum and map perform on par with explicit loop. State gives 7x slowdown and 8x allocations, IO benchmark 4x slowdown and 8x allocations. We obviously can add rewrite rules for
IO/STbut maybe there're more general optimizations.Fixes #477, #69, #132, #144