Make fromList fuse

[treeowl]

OK, so this one is a little weird, but bear with me! If the argument of fromList is a good producer, then it is not an actual list in memory. So what? So if we take its length, that forces its realization as a list. If we don't take its length, then we have all sorts of other options, all of which are (typically) better. For example, we can build a list of SmallArrays holding chunks of, say, 32 elements each, and then concatenate them all in the end. That's inefficient, but less inefficient than what we do now.

For SmallArray, an option I thought about long ago is to use classic array doubling, and then shrink the final result. This will work just fine even if there is an actual list in memory.

[andrewthad]

Agreed. I totally buy this argument. Array doubling is the only way to be a good consumer for fusion.

[treeowl]

How should array doubling work? Unfortunately, doubling the array is somewhat more expensive than usual: it has to be filled totally with garbage, then the first half copied over. Hopefully there will be a new primop to fix that soon. It would probably be worth experimenting also with various sorts of lists of arrays. There are lots of options there. One that seems particularly promising to me is to use classic array doubling up to a certain size, then freezes that chunk and builds a new one. In the end, there's a list of arrays and a known size; we can then concatenate all the arrays. The idea is that the linked-list overhead becomes insignificant compared to the overhead of recopying that portion. Lots of tuning to do, of course.