search

haskell / fgl

A Functional Graph Library for Haskell
http://hackage.haskell.org/package/fgl
Other
185 stars 54 forks source link

Two AVL benchmarks fail with errors #47

Closed treeowl closed 8 years ago

treeowl commented 8 years ago 
microbench "insEdge into AVL tree" insEdgeAVL
microbench "emap on AVL tree" emapAVL

We get

    * insEdge into AVL tree: .fgl-benchmark: insEdge: cannot add edge from non-existent vertex 1

and

    * emap on AVL tree: .fgl-benchmark: insEdge: cannot add edge from non-existent vertex 1
treeowl commented 8 years ago

I've commented those benchmarks out in #46 (adding Cabal benchmark integration), but they obviously need to be fixed.

treeowl commented 8 years ago

A brief glance suggests that the problem is in the implementation, rather than the benchmarks themselves. Uh-oh.

ivan-m commented 8 years ago

This may have been caused by changes required for #14

(Though I can't see how as it would have failed before then as well, just with a different error.)

ivan-m commented 8 years ago

Actually, I think I may have an idea about where the issues arise:

Originally, newNodes started creating new nodes from max_node_number + 1, and max_node_number defaulted to 0. As such, 1 would have been the first node created here.

But now, if a graph is empty the initial node created is 0 (which is admittedly a regression I hadn't spotted). So I think this can be resolved by changing the 1 in insEdges' to 0 (though this may affect other implicit assumptions, as I believe it assumed that insEdgeAVL 1 would create a singleton loop).

So the question is to whether to fix this regression (that no-one has complained about, and indeed I couldn't find anyone actually using nodeRange manually when I attempted to fix the behaviour of how it was defined) or have insEdges' do insEdge (0, n-1, ()) g instead of insEdge (1, n, ()) g (which is my preference).

ivan-m commented 8 years ago

Yup, that fixed it. I'll give the changes to make in #46.