Speed up equality; remove expensive invariant

[treeowl]

We used to define == to test equality in priority order. This was expensive in and of itself, since it takes logarithmic time to produce each entry. But the situation was worse than that: since priorities are not unique, we introduced an extra invariant to make sure that keys with the same priority are extracted in key order. This requires additional comparisons in various performance-critical functions.

• Remove the extra invariant.
• Remove the extra code to preserve it.
• Change (==) to work in key order instead of priority order. Keys are unique, so this is very natural.
• Remove a bunch of now-redundant constraints.

[treeowl]

@jaspervdj, do you want to go this way? If not, I guess I can open a PR that just changes the Eq instance. While the benefits won't be as great, there seems to be no possible reason not to at least do that.

[jaspervdj]

Thanks for looking into this @treeowl! I am definitely fine changing the Eq instance.

I'm a bit more worried about changing the minView behaviour. However, I read through the documentation and it seems like we never documented the order of extraction in case priorities are equal, so probably it's fine? We probably need to bump the package to 0.3.0.0 just to make sure, which is a bit annoying for consumers.

Do you have any benchmark data laying around? What sort of speedups are we talking about?

[treeowl]

No, I don't have data, but I can try to get some.