Consider removing overhead of NodeUtil#ensureNoDuplicateEdges()

[knutwannheden]

For my particular tree I have run some performance measurements indicating that around 15% of the time constructing a tree is spent in NodeUtil#ensureNoDuplicateEdges(). I think that is a rather steep price to be paying.

AFAICT it shouldn't be possible to violate this constraint in the first place (the ConcurrentRadixTree implementation looks correct). So if this is to help people implementing their own implementation, maybe there could be some debug flag to guard this? Alternatives would be: Speed it up (e.g. for edge cases like size() <= 2) or move it into the node constructor, where once the children are sorted it would only be a matter of looping over all children and finding any two adjacent identical ones. Should be cheaper.

Thoughts?

[npgall]

Yes, this is a good point.

This is an example of defensive programming to ensure the algorithms didn't violate the constraints! But indeed I think the algorithms are well proven now, and they don't violate the constraints. So it makes sense to allow this checking to be relaxed.

It would be quite easy to add a constructor to the node factories which would allow this checking to be disabled. So I'll accept this suggestion, and try to add it for the next release! Thanks!

[knutwannheden]

Excellent!

[VHarisop]

@npgall I took the liberty of adding the constructor as you suggested and made the relevant check conditional in the createNode() method, as of e383145. Do you think that I should add some extra test?

I would be happy to contribute this as a PR if that's ok with you.

[npgall]

@VHarisop Yes that looks good.
Could you add a unit test(s), to test the new constructor, and to exercise the new branch? We just need to maintain 100% test coverage for the change.

Also one minor point - could you add brackets {} in the if statement - just for consistency with code style?

If you create a PR from with these changes, I'd be happy to merge it. Thanks!

[VHarisop]

Cool, I'll look into writing the tests.