Proposal: plug the space leak in transpose
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? * https://gitlab.haskell.org/ghc/ghc/-/merge_requests/3882
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.
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 < lemming@henning-thielemann.de> 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.
participants (2)
-
David Feuer -
Henning Thielemann