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
{{ message }}
Repository navigation
[pdata/pprofile] Dictionary merge in switchDictionary is O(N·L²) from linear-scan dedup #15544
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.
Activity
github-actions commentedon Jul 6, 2026
Pinging code owners:
See Adding Labels via Comments if you do not have permissions to add labels yourself.
[pdata/pprofile] Point the changelog entry at the tracking issue
[pdata/pprofile] Point the changelog entry at the tracking issue
[pdata/pprofile] Speed up dictionary merging with an indexed dedup (o…