Try to make fromList a little better

[treeowl]

Try to make fromList a little better

[treeowl]

While I'm on the topic, we may want to add fusion rules for enumerations, so that fromList [1,3..n], say, gets rewritten to a fromFunction form automatically. If we decide to leave fromList alone, that means adding rules to (try to) fuse with build forms involving eftIntFB, efdtIntFB, and maybe a couple others, which will only actually fire on GHC >= 7.9. If we decide to change fromList as I suggest above, we'd instead fuse with eftInt, efdtInt, etc., which would likely be easier.

[RossPaterson]

This would avoid the shuffling:

fromList' :: [a] -> Seq a
fromList' xs = Seq $ mkTree $ map Elem xs

mkTree :: (Sized a) => [a] -> FingerTree a
mkTree [] = Empty
mkTree [x1] = Single x1
mkTree [x1, x2] = deep (One x1) Empty (One x2)
mkTree [x1, x2, x3] = deep (One x1) Empty (Two x2 x3)
mkTree (x1:x2:x3:xs) = deep (Three x1 x2 x3) (mkTree ns) sf
  where (ns, sf) = getNodes xs

getNodes :: (Sized a) => [a] -> ([Node a], Digit a)
getNodes [x1] = ([], One x1)
getNodes [x1, x2] = ([], Two x1 x2)
getNodes [x1, x2, x3] = ([], Three x1 x2 x3)
getNodes (x1:x2:x3:xs) = (node3 x1 x2 x3:ns, d)
  where (ns, d) = getNodes xs

A further refinement would be to calculate the sizes of the nodes top-down, since they're all powers of 3.

[treeowl]

@RossPaterson Nice. I'll try to refine it as you suggest, and we'll see what the benchmarks say.

[RossPaterson]

With computed sizes:

fromList' :: [a] -> Seq a
fromList' xs = Seq $ mkTree 1 $ map Elem xs

mkTree :: (Sized a) => Int -> [a] -> FingerTree a
mkTree s [] = Empty
mkTree s [x1] = Single x1
mkTree s [x1, x2] = Deep (2*s) (One x1) Empty (One x2)
mkTree s [x1, x2, x3] = Deep (3*s) (One x1) Empty (Two x2 x3)
mkTree s (x1:x2:x3:xs) = deep (Three x1 x2 x3) (mkTree s' ns) sf
  where
    s' = 3*s
    (ns, sf) = getNodes s' xs

getNodes :: Int -> [a] -> ([Node a], Digit a)
getNodes s [x1] = ([], One x1)
getNodes s [x1, x2] = ([], Two x1 x2)
getNodes s [x1, x2, x3] = ([], Three x1 x2 x3)
getNodes s (x1:x2:x3:xs) = (Node3 s x1 x2 x3:ns, d)
  where (ns, d) = getNodes s xs

[treeowl]

Nicer! We may or may not be able to do even slightly better by returning the size along with ns and ds from getNodes, so we won't need those deep smart constructors hitting the now-out-of-cache left-side digits and nodes on the way back up the recursion.

[treeowl]

Oh, that probably makes no difference. I tend to forget just how short these spines are.

[treeowl]

Argh. I'm struggling to make this perform well. After some strictification, it reduces allocation marginally compared to the current version when the current version fuses with a list producer, and reduces allocation a little more when the current version does not fuse. But for some reason it seems the garbage collector ends up doing more work, and the total times don't look so great. Maybe someone else can give it a go, or I'll try some other possible modifications (e.g., see what happens if this right-fold-like arrangement is changed to a strict-left-fold-like one), or maybe this is just one of those ideas that look good but don't actually work out.

[treeowl]

I think the tricky thing is that we have to (in some fashion) pile up a stack of known prefixes (and perhaps their known lengths) while waiting for the middle lengths and the suffixes to become available. The exact manner in which we do this probably matters a lot from a performance standpoint, and I'm sure I don't know the right way.

[treeowl]

All right. I did a little more work on this and brought allocation down quite a bit more, with a 31% allocation reduction compared to the original without list fusion and 15% reduction compared to the original with list fusion. Unfortunately, it's still coming out slower, so I guess I have more work to do.

[treeowl]

OK, sorry for the noise. I think I fixed most of it. At one point I made one thing too strict. I got a version that allocates way less now. It's still making the garbage collector work harder for some reason, but the mutator time drops to compensate. I'll put together a pull request and see if anyone else can improve it further.

[treeowl]

I have a new idea that should allocate things in a more typical way, and
therefore might make the RTS happier. Instead of building a FingerTree
directly, build a FingerTreeLS, just like a FingerTree but with a lazier
spine (lazy in the sizes and the digits). Once that's built, converting it
to a FingerTree is just O(log n) time and space.

I also had an idea for reducing allocation further, that may or may not
work. At the top level (at least) try to do things in chunks of 9 instead
of 3. This avoids allocating a list of nodes a third the length of the
original list. Whether we do this or not, we probably want to special-case
the top level, because the map Elem only comes free in GHC >= 7.9—in
earlier versions it would cost O(n) unless it fused with its argument.

[foxik]

Merged the pull request.