Uncurryfication seems to be slow

[nobrakal]

As discovered working on #103

Using:

edges :: [(a, a)] -> Graph a
edges = overlays . map edge'

edge' :: (a,a) -> Graph a
edge' (x,y) = connect (vertex x) (vertex y)

(so uncurryfying "by-hand"),

lead to better performances:

Using [("Mesh",4),("Clique",4)] as graphs

## edges

### Mesh
#### 1000

+---------++----------+-------+
|         ||     Time |    R² |
+=========++==========+=======+
|    Alga || 75.10 μs | 1.000 |
| AlgaOld || 105.4 μs | 0.998 |
+---------++----------+-------+

### Clique
#### 1000

+---------++----------+-------+
|         ||     Time |    R² |
+=========++==========+=======+
|    Alga || 20.04 ms | 0.998 |
| AlgaOld || 26.76 ms | 0.995 |
+---------++----------+-------+


ABSTRACT:
(Based on an average of the ratio between largest benchmarks)

 * Alga was 1.37 times faster than AlgaOld

[snowleopard]

I'm surprised GHC doesn't turn uncurry edge into your edge' automatically. You could perhaps add a rewrite rule so that the user code also benefits from this optimisation (uncurry edge might be common).

What about edges = overlays . map (\(x, y) -> edge x y)? This doesn't require an extra function.

By the way, here is how uncurry is implemented:

uncurry :: (a -> b -> c) -> ((a, b) -> c)
uncurry f p = f (fst p) (snd p)

[snowleopard]

Perhaps, the problem is that the call to uncurry is partially applied and GHC does not want to inline it.

This may be a relevant SO thread:

https://stackoverflow.com/questions/11690146/why-does-ghc-consider-the-lhs-syntactically-when-inlining

[snowleopard]

@nobrakal I just realised that your new implementation is not equivalent to the original one: the strictness properties are different:

> g = edges [undefined]
> isEmpty g
False

> g = newEdges [undefined]
> isEmpty g
*** Exception: Prelude.undefined

The reason is that you pattern match on the tuple constructor (x, y) in edge', but uncurry doesn't.

I wonder if it is possible to both keep the full laziness and increase the performance.

[nobrakal]

@snowleopard Ah I didn't thought about strictness.

Looking a the code produced by GHC, with the current lazy implementation:

Rec {
-- RHS size: {terms: 21, types: 33, coercions: 0, joins: 0/0}
Algebra.Graph.edges1 [Occ=LoopBreaker]
  :: forall a. [(a, a)] -> Graph a
[GblId, Arity=1, Caf=NoCafRefs, Str=<S,1*U>]
Algebra.Graph.edges1
  = \ (@ a_a8YM) (ds_icea :: [(a_a8YM, a_a8YM)]) ->
      case ds_icea of {
        [] -> Algebra.Graph.Empty @ a_a8YM;
        : y_icef ys_iceg ->
          Algebra.Graph.Overlay
            @ a_a8YM
            (Algebra.Graph.Connect
               @ a_a8YM
               (Algebra.Graph.Vertex
                  @ a_a8YM (case y_icef of { (a1_aclW, b1_aclX) -> a1_aclW }))
               (Algebra.Graph.Vertex
                  @ a_a8YM (case y_icef of { (a1_acm1, b1_acm2) -> b1_acm2 })))
            (Algebra.Graph.edges1 @ a_a8YM ys_iceg)
      }
end Rec }

[...]

edges
  = \ (@ a_a8YM) (x_ic4h :: [(a_a8YM, a_a8YM)]) ->
      Algebra.Graph.edges1 @ a_a8YM x_ic4h

Using edge':

Rec {
-- RHS size: {terms: 18, types: 28, coercions: 0, joins: 0/0}
Algebra.Graph.edges1 [Occ=LoopBreaker]
  :: forall a. [(a, a)] -> Graph a
[GblId, Arity=1, Caf=NoCafRefs, Str=<S,1*U>]
Algebra.Graph.edges1
  = \ (@ a_a8Wo) (ds_icbK :: [(a_a8Wo, a_a8Wo)]) ->
      case ds_icbK of {
        [] -> Algebra.Graph.Empty @ a_a8Wo;
        : y_icbP ys_icbQ ->
          Algebra.Graph.Overlay
            @ a_a8Wo
            (case y_icbP of { (x_a798, y1_a799) ->
             Algebra.Graph.Connect
               @ a_a8Wo
               (Algebra.Graph.Vertex @ a_a8Wo x_a798)
               (Algebra.Graph.Vertex @ a_a8Wo y1_a799)
             })
            (Algebra.Graph.edges1 @ a_a8Wo ys_icbQ)
      }
end Rec }

So yes, all of this is a strictness issue !
Not sure what is the good way to go because I don't see a solution:
Either you pattern match for tuple before Connect either you use fst and snd after Connect

[snowleopard]

@nobrakal I think I'd prefer to keep edges maximally lazy.

My understanding is that edgesOrd will have to be strict, since it will be comparing actual values in the list of edges, so let's keep edges as a maximally lazy alternative.

[snowleopard]

I guess we can close thig now, since it doesn't seem possible to make uncurrying faster while staying lazy.