You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
PathCopyingPersistentTreeMap tracks sizes lazily, i.e., on first access to size() the whole tree is iterated and the result is cached for future accesses. We could improve this, with one of the following ways:
Track the subtree size in each node of the tree, similar to what is implemented in Extend persistent path copying map with size tracking #51. This is guaranteed O(1), but increases the memory consumption of every node. This may or may not be relevant in practice, and it might also be that due to object sizes and alignment requirements there is actually no size increase, but we don't know.
Track the size only for each map instance, and when changing a map compute the new size without counting all nodes, similar to what is implemented in Replace PathCopyingPersistentTreeMap hash and size calculation #36. This has the same memory usage as today and negligible overhead.
We should also consider PartialSortedMap, which we use for views like subMap(). There it is more difficult and we might only be able to optimize partially because a PartialSortedMap need to match a subtree of nodes exactly.
PathCopyingPersistentTreeMaptracks sizes lazily, i.e., on first access tosize()the whole tree is iterated and the result is cached for future accesses. We could improve this, with one of the following ways:We should also consider
PartialSortedMap, which we use for views likesubMap(). There it is more difficult and we might only be able to optimize partially because aPartialSortedMapneed to match a subtree of nodes exactly.