Skip to content

sorted_set: union defensively copies both trees and recounts the result size #3824

Description

@bobzhang

sorted_set/set.mbt SortedSet::union (the TODO: optimize this. Avoid counting the size of the set at ~line 175):

  1. copy_tree is called on both operands up front. The copies are required by the current mutable design (add_node/delete_node/rotations mutate nodes in place, so subtree sharing would corrupt the source sets) — but it means union is O(n+m) allocations before any merging starts.
  2. After the split/join merge, the result size is recomputed by a full each traversal because nodes store only height, not subtree size.

Possible directions:

  • Store subtree size in Node (as the immutable immut/sorted_set does) — kills the recount and gives O(1) length for subtrees; costs one word per node and bookkeeping in every rotation.
  • Count duplicates during split (a duplicate is discovered exactly when split hits comp == 0), then size = size1 + size2 - dups — no node layout change, but split needs a counting variant.
  • For the copy overhead: iterate the smaller set and add into a copy of the larger — O(n + m log n) with one copy instead of two and no recount (add maintains size). Loses the asymptotic edge of split/join union for balanced sizes.

Related: symmetric_difference had the same shape and is addressed by #3819 with a merge-walk; intersection (each + contains) may also benefit from a merge-walk.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions