(no subject)
Random thought: I'm sure people who actually know about this stuff will be able to tell me why it won't work, or, alternatively, cases where it's already been done.
Recall the problem with the naive Haskell mean program
mean xs = sum xs / length xs
which when asked to calculate the mean of [1 .. 1e9] allocates 8GB of RAM and brings the computer to a grinding halt. The problem there isn't really to do with naiveté: a similarly naive Ruby version works fine and runs in constant space, albeit slowly. The problem is garbage collection, or rather the lack of it. The Haskell runtime calculates the list [1.. 1e9] bit-by-bit so it can be summed, and normally would be able to throw every element away when it was done with it; but because the elements of the list will later need to be counted, there's still a (very long) pointer chain from the top-level to any given element of the list. So none of it can be garbage-collected.
In this case, this is a bad strategy: the effects of swapping out that much memory totally eliminate any benefit from caching the list. It would be quicker to throw the list away and calculate it again from scratch. Since Haskell's a purely functional language, we could in principle do this without worrying about any side-effects of the calculation. We could set up our garbage collector to become more aggressive as memory got shorter: when it starts to use swap, we could throw away any pure data that's more than N indirections from the toplevel, where N is varied dynamically to maximise performance. But what if our program is, say mean $ take 1000000000 mersennePrimes? Then it will take much longer to re-calculate the values than it would to swap them in and out of core. You'd need to keep track of how long each function call takes, and how long each bit of data took to calculate, and estimate re-calculation times when throwing data away.
But this is exactly the kind of profiling data that you need to track for the smart optimizing VMs that Steve Yegge talks about here. So, it seems that there's a synergy here. Does anyone know of a Sufficiently Smart VM that does this kind of aggressive garbage collection? Has it been tried before? Is there some obvious problem with the idea that I'm not seeing?
Recall the problem with the naive Haskell mean program
mean xs = sum xs / length xs
which when asked to calculate the mean of [1 .. 1e9] allocates 8GB of RAM and brings the computer to a grinding halt. The problem there isn't really to do with naiveté: a similarly naive Ruby version works fine and runs in constant space, albeit slowly. The problem is garbage collection, or rather the lack of it. The Haskell runtime calculates the list [1.. 1e9] bit-by-bit so it can be summed, and normally would be able to throw every element away when it was done with it; but because the elements of the list will later need to be counted, there's still a (very long) pointer chain from the top-level to any given element of the list. So none of it can be garbage-collected.
In this case, this is a bad strategy: the effects of swapping out that much memory totally eliminate any benefit from caching the list. It would be quicker to throw the list away and calculate it again from scratch. Since Haskell's a purely functional language, we could in principle do this without worrying about any side-effects of the calculation. We could set up our garbage collector to become more aggressive as memory got shorter: when it starts to use swap, we could throw away any pure data that's more than N indirections from the toplevel, where N is varied dynamically to maximise performance. But what if our program is, say mean $ take 1000000000 mersennePrimes? Then it will take much longer to re-calculate the values than it would to swap them in and out of core. You'd need to keep track of how long each function call takes, and how long each bit of data took to calculate, and estimate re-calculation times when throwing data away.
But this is exactly the kind of profiling data that you need to track for the smart optimizing VMs that Steve Yegge talks about here. So, it seems that there's a synergy here. Does anyone know of a Sufficiently Smart VM that does this kind of aggressive garbage collection? Has it been tried before? Is there some obvious problem with the idea that I'm not seeing?