Skip to content

[pdata/pprofile] Dictionary merge in switchDictionary is O(N·L²) from linear-scan dedup #15544

Closed

Description

@lazureykis

Profiles.MergeTo → switchDictionary deduplicates every source dictionary entry (strings, functions, mappings, locations, stacks, attributes, links) against the destination table by linear-scanning it and comparing with Equal. Each lookup is O(table size), so merging M source entries into an N-entry table is O(N·M) — quadratic as dictionaries grow, and locations/stacks compound it further via their nested index lists.

For workloads that merge many profiles into a shared dictionary (e.g. batching before export), this dedup dominates merge time.

Proposal: keep Equal as the dedup arbiter but front it with a per-merge hash index (hash buckets keyed on the entry's contents) so the common "already present" and "brand new" cases are O(1) instead of O(N). Benchmarks in the PR.

Addressed by #15472.

Activity

  1. github-actions commented on Jul 6, 2026

    @github-actions
    Contributor

    Pinging code owners:

    See Adding Labels via Comments if you do not have permissions to add labels yourself.

  2. added a commit that references this issue on Sep 17, 2026
    e460a7f
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    Priority

    None yet

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions