Replace PathCopyingPersistentTreeMap hash and size calculation

[Druidos]

Replace PathCopyingPersistentTreeMap hash and size calculation from lazy linear algorithm to pre-calculations, which is efficient for public copying methods

[PhilippWendler]

Thanks!

While this certainly increases the performance for some users, it causes higher memory usage for all users of this data structure due to the new fields in the node class. So I would like to understand the effects a little bit better before merging this.

Do you have any numbers on how much improves this performance or how much it increases memory usage in practice? What is your use case that benefits from this? In CPAchecker, for example, we apply hash-code caching for these maps outside of them in those cases where we feel it is relevant, is this possible for you as well?

[Druidos]

If memory consumption is critical, then I will move hash and size calculation from Node into PathCopyingPersistentTreeMap on put/remove-AndCopy. Main idea is to optimize equals(). The hashcode calculation is obtained as a side result of the size calculation. For example, following code twice iterates by whole pMap to identify size change:

boolean compare(PathCopyingPersistentTreeMap<Integer, Integer> pMap) {
    PathCopyingPersistentTreeMap<Integer, Integer> comp = pMap.putAndCopy(1,1);
    return comp.equals(pMap);
}

Exact numbers about performance I can provide later.