Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Two AVL benchmarks fail with errors #47

Closed
treeowl opened this issue Aug 30, 2016 · 5 comments
Closed

Two AVL benchmarks fail with errors #47

treeowl opened this issue Aug 30, 2016 · 5 comments

Comments

@treeowl
Copy link
Contributor

treeowl commented Aug 30, 2016

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
Copy link
Contributor Author

treeowl commented Aug 30, 2016

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

@treeowl
Copy link
Contributor Author

treeowl commented Aug 30, 2016

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

@ivan-m
Copy link
Contributor

ivan-m commented Oct 5, 2016

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
Copy link
Contributor

ivan-m commented Oct 5, 2016

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
Copy link
Contributor

ivan-m commented Oct 5, 2016

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

@ivan-m ivan-m closed this as completed Oct 5, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants