Optimize Chain.traverseVoid #4695
Conversation
|
The optimization looks great, thank you! However, I have to say that it seems that which apparently is not very comprehensive. There's also abstract Therefore, perhaps the simplest way to address that could be inheriting |
| case Append(l, r) => | ||
| go(l, if (rhs.isEmpty) r else Append(r, rhs), acc) | ||
| case Wrap(as) => | ||
| val va = Traverse[Vector].traverseVoid(as.toVector)(f) |
There was a problem hiding this comment.
It'd be nice to see the difference in memory consumption though
|
about:
There are two ways the stack can overflow: due to some recursion on the chain as we are traversing, or via the effect that we are combining with. foldRight + Eval can prevent a stack overflow from recursion on the chain, but inside it is still using map2Eval which has a default implementation of just calling So, I don't see how stack unsafety of repeated product applications can be improved with the current main version. Additionally, Chain isn't a linear chain necessarily. It can have some treelike structure, so it can only have G.product depth <= the original depth, never more. |
|
okay, I followed the existing convention for List/Vector etc... and just added a new class to the TraverseSuite file. How does that look? |
we can directly iterate through traverseVoid (which is really a kind of monoidal aggregation), so we don't need to use the expensive foldRight to do this.