Proposed new feature or change:
Description
In NumPy 2.x, a hash-based unique algorithm (_unique_hash using C++ std::unordered_set) was introduced (PR #26018) to find unique values. However, for numeric arrays (e.g. int64, int32), this has introduced a massive performance regression at medium-to-large scales compared to sorting. Hashing a 1M element int64 array takes over 712 ms, whereas sorting-based unique (which is SIMD-accelerated via x86-simd-sort in NumPy 2.x) takes only 15.2 ms (a 46x difference!).
Why this happens
- Node Allocations:
std::unordered_set is a node-based container. Inserting 1,000,000 unique values incurs 1,000,000 heap memory allocations.
- Cache Locality: Linked lists in the bucket array lead to significant CPU cache misses.
- No Vectorization: Hashing/lookup cannot be vectorized, whereas sorting uses AVX-512/AVX2 registers to process multiple elements in parallel.
Even when there are heavy duplicates (e.g., 10 unique elements repeated 100,000 times each), sorting is still 3x faster than hashing (15.8 ms vs 45.7 ms). Hashing only beats sorting at micro scales (e.g., < 50 elements) where Python-level sorting setup overhead dominates.
Proposed Solution
Introduce adaptive thresholding: for numeric and fixed-width dtypes, route to the hash-based pathway only if the size is small (e.g., < 100 elements). For larger sizes, bypass _unique_hash and use the sorting pathway. For variable-width string types (StringDType), we keep the hashing pathway at all sizes, as hashing remains faster than string comparisons.
Proposed new feature or change:
Description
In NumPy 2.x, a hash-based unique algorithm (
_unique_hashusing C++std::unordered_set) was introduced (PR #26018) to find unique values. However, for numeric arrays (e.g.int64,int32), this has introduced a massive performance regression at medium-to-large scales compared to sorting. Hashing a 1M elementint64array takes over 712 ms, whereas sorting-based unique (which is SIMD-accelerated viax86-simd-sortin NumPy 2.x) takes only 15.2 ms (a 46x difference!).Why this happens
std::unordered_setis a node-based container. Inserting 1,000,000 unique values incurs 1,000,000 heap memory allocations.Even when there are heavy duplicates (e.g., 10 unique elements repeated 100,000 times each), sorting is still 3x faster than hashing (15.8 ms vs 45.7 ms). Hashing only beats sorting at micro scales (e.g.,
< 50elements) where Python-level sorting setup overhead dominates.Proposed Solution
Introduce adaptive thresholding: for numeric and fixed-width dtypes, route to the hash-based pathway only if the size is small (e.g.,
< 100elements). For larger sizes, bypass_unique_hashand use the sorting pathway. For variable-width string types (StringDType), we keep the hashing pathway at all sizes, as hashing remains faster than string comparisons.