Currently, we build various thunks when extracting. Some of these are definitely unnecessary (suspending the work of incrementing a forest that starts with Skip). Can we always force the increments to WHNF without risking a somewhat expensive cascade? I haven't done a proper analysis. Is such a cascade even bad enough to be worth avoiding? That should probably be checked with benchmarks.
Additionally: we use a (boxed) sum type as an intermediate result. Can we switch that to an unboxed one without performance trouble? Or might it be better to make two passes: one to locate the minimum and one to remove it?
I was pretty conservative when I made everything just strict enough to avoid thunk chains and their associated bad worst-case performance, but it's worth seeing if we can tighten things up further.
treeowl
commented
1 year ago
Currently, we build various thunks when extracting. Some of these are definitely unnecessary (suspending the work of incrementing a forest that starts with
Skip). Can we always force the increments to WHNF without risking a somewhat expensive cascade? I haven't done a proper analysis. Is such a cascade even bad enough to be worth avoiding? That should probably be checked with benchmarks.Additionally: we use a (boxed) sum type as an intermediate result. Can we switch that to an unboxed one without performance trouble? Or might it be better to make two passes: one to locate the minimum and one to remove it?
I was pretty conservative when I made everything just strict enough to avoid thunk chains and their associated bad worst-case performance, but it's worth seeing if we can tighten things up further.