Skip to content

[#859] Optimize SizedList Monad instance

Nikolay Yakimov requested to merge lierdakil/#859-optimize-sizedlist-monad into master

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

    • I checked whether I should update the docs and did so if necessary:
    • I updated changelog files of all affected packages released to Hackage if my changes are externally visible.

Stylistic guide (mandatory)

Merge request reports