Proposal: plug the space leak in transpose

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Proposal: plug the space leak in transpose

David Feuer
Data.List.transpose, unfortunately, can potentially leak space. The problem is that it walks a list of lists twice: once to get the heads and once to get the tails. Depending on the way the result is consumed, it's possible that heads or tails that are never used will be retained by the garbage collector. I have a fix[*] that probably makes the function slower in typical cases, but that plugs the leak. What do y'all say?


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: plug the space leak in transpose

Henning Thielemann

On Sun, 23 Aug 2020, David Feuer wrote:

> Data.List.transpose, unfortunately, can potentially leak space. The
> problem is that it walks a list of lists twice: once to get the heads
> and once to get the tails. Depending on the way the result is consumed,
> it's possible that heads or tails that are never used will be retained
> by the garbage collector. I have a fix[*] that probably makes the
> function slower in typical cases, but that plugs the leak. What do y'all
> say?

Your way sounds more correct than using 'head' and 'tail'. I have no
numbers, though.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: plug the space leak in transpose

David Feuer
There's no use of head or tail functions. Two list comprehensions equivalent to two applications of mapMaybe, rather than one of mapMaybe and a second of unzip. The whole situation is rather sad; a generalization of the selector thunk trick could in principle plug the leak without hurting performance, but that will require various GHC changes.

On Mon, Aug 24, 2020, 1:25 AM Henning Thielemann <[hidden email]> wrote:

On Sun, 23 Aug 2020, David Feuer wrote:

> Data.List.transpose, unfortunately, can potentially leak space. The
> problem is that it walks a list of lists twice: once to get the heads
> and once to get the tails. Depending on the way the result is consumed,
> it's possible that heads or tails that are never used will be retained
> by the garbage collector. I have a fix[*] that probably makes the
> function slower in typical cases, but that plugs the leak. What do y'all
> say?

Your way sounds more correct than using 'head' and 'tail'. I have no
numbers, though.

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries