[#859] Optimize SizedList Monad instance
Disclaimer: actual change to the Monad
instance is a very marginal improvement
However, making SizedList
lazy improves the situation by about 50% allocations-wise and about 30% timing-wise in my (limited) testing.
Description
Problem: the instance is somewhat inefficient in that it indexes into the bind argument multiple times. Could stand to be a bit more efficient.
Solution: Walk the argument explicitly, apply function to each element and immediately index.
An alternative without explicit indexing was considered, but in testing turns out it's more expensive:
f >>= k = go $ fmap k f
where
go :: SizedList' m (SizedList' m b) -> SizedList' m b
go Nil = Nil
go ((el :< _) :< rest) = el :< go (fmap tail rest)
The curious thing about this implementation is it doesn't require SingI
.
Problem: Currently SizedList is strict in both head and tail, which can
lead to doing more work than necessary (case in point: its Monad
instance).
Solution: Make it lazy. Considering how we use SizedList
(i.e. in most
cases we use values almost immediately), this shouldn't create
noticeable space leaks. Besides, we're still using regular lists, and
those are lazy.
Related issue(s)
Resolves #859 (closed)
✅ Checklist for your Merge Request
Related changes (conditional)
-
Tests (see short guidelines)
-
If I added new functionality, I added tests covering it. -
If I fixed a bug, I added a regression test to prevent the bug from silently reappearing again.
-
-
Documentation
Stylistic guide (mandatory)
-
My commits comply with the following policy. -
My code complies with the style guide.