tailRecEff space leak

[matthewleon]

https://github.com/purescript/purescript-tailrec/blob/master/src/Control/Monad/Rec/Class.purs#L126

The reference to a will be unnecessarily held while the loop is run.

[matthewleon]

I suspect there is no way to fix this without resorting to JS or some unsafe* calls. Within PureScript, the only way I know of to rewrite such references is to create a tail call... Which is of course what this code is meant to simulate in the first place.

[natefaubion]

I don't think this is the case. It's no different than writing something like:

function go(k, a) {
  var step = k(a);
  while (step.next) {
    step = k(step.next);
  }
  return step.done;
}

And I don't think anyone would claim this "leaks" anything.

[matthewleon]

Yes, I guess "leak" isn't really the right word here. Correct me if I'm wrong, though, but if the var step line were replaced with a = k(a), wouldn't this signal to the GC that the old a reference could now be cleaned, as long as there are no other references to it lingering around? It seems to be that in certain cases, this could be quite advantageous.

[natefaubion]

There's nothing holding on to a reference of a, so I don't think it would matter for the GC if it decided to run in the middle of the loop.

[matthewleon]

I recall particularly that what prompted this was a case where a was the only reference to the head of a linked list, and by overwriting it, I was able to get the GC to progressively clean the list, rather than waiting until the end of the loop. It's been a while though, so I might not be remembering correctly. Does this make sense to you?

[matthewleon]

It's quite similar to this, I think: https://github.com/purescript/purescript/issues/2822

[natefaubion]

Thanks for the reference. Personally, I think we should just write the implementation in the FFI, as we aren't going to be able to use ST anyway, and I would be wary of incurring the performance penalty of Ref.

[matthewleon]

as we aren't going to be able to use ST anyway

I guess this issue has come up because this part of the library has to be adapted to Effect? And ST needs to be rewritten?

In any case, this issue is a hitch to be aware of. I wish I had some sample code that demonstrated this particularly in the case of tailRecEff.

[natefaubion]

ST is going to be a newtype, which means you can't interleave arbitrary Effects, so we can't use it as a basis for this part of the code. We can use normal Refs, but it won't trigger any optimizations and would likely be significantly slower.

[safareli]

It feels this implementation can avoid storing any references to the a0 and fix the issue?:

tailRecM f = f >>> tailRec case _ of
  Nothing -> Done Nothing
  Just (Loop a) -> Loop (f a)
  Just (Done b) -> Done (Just b)

(Tho I might be miss understanding the issue)