Skip to content

Eager size tracking of PathCopyingPersistentTreeMap #64

Description

@PhilippWendler

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:

  1. 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.
  2. 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.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions