Use HashHelpers prime sizing and FastMod for LINQ bucketing - #130315
#130315Use HashHelpers prime sizing and FastMod for LINQ bucketing#130315tannergooding merged 1 commit intodotnet:maindotnet/runtime:mainfrom tannergooding:tannergooding-linq-lookup-hashhelpers-growthtannergooding/runtime:tannergooding-linq-lookup-hashhelpers-growthCopy head branch name to clipboard
Conversation
The LINQ Lookup/Grouping bucketing used a count * 2 + 1 growth scheme (7, 15, 31, 63, ...), effectively picking pow2-1 sizes, combined with a plain hashCode % length bucket index. This yields poor bucket distribution compared to Dictionary<TKey, TValue>. Switch the LINQ hash structures to the same resizing and growth used by Dictionary via the shared System.Collections.HashHelpers: grow with ExpandPrime (prime sizes) and index with FastMod (using a precomputed multiplier, gated on 64-bit with a plain modulo fallback on 32-bit). This applies the same fixup to all three sibling LINQ hash structures: - System.Linq Lookup/Grouping (ToLookup, GroupBy, joins) - System.Linq.Parallel HashLookup (PLINQ GroupBy, Join, GroupJoin) - System.Linq.AsyncEnumerable AsyncLookup (ToLookupAsync, GroupBy, joins) Co-authored-by: Copilot App <223556219+Copilot@users.noreply.github.com>
|
Tagging subscribers to this area: @dotnet/area-system-linq |
|
CC. @jeffhandley, @jkotas, @GrabYourPitchforks as an FYI |
There was a problem hiding this comment.
Pull request overview
This PR updates the internal hash-table bucketing/resizing logic used by LINQ lookup-style structures to match the sizing and bucket-indexing strategy used by Dictionary<TKey, TValue> (prime sizing via HashHelpers.ExpandPrime and 64-bit HashHelpers.FastMod with a precomputed multiplier).
Changes:
- Replace
count * 2 + 1growth withHashHelpers.ExpandPrime(...)in the LINQLookup, PLINQHashLookup<,>, and asyncAsyncLookup<,>implementations. - Use a shared
GetBucketIndex(...)helper that usesHashHelpers.FastModon 64-bit (with a cached multiplier) and%on 32-bit. - Link
System.Collections.HashHelpers.csinto each project and add theArg_HTCapacityOverflowSR string required byHashHelpers.
Show a summary per file
| File | Description |
|---|---|
| src/libraries/System.Linq/src/System/Linq/Lookup.cs | Switches Lookup/Grouping bucketing and resizing to HashHelpers + adds fast-mod multiplier caching. |
| src/libraries/System.Linq/src/System.Linq.csproj | Links HashHelpers.cs into System.Linq. |
| src/libraries/System.Linq/src/Resources/Strings.resx | Adds Arg_HTCapacityOverflow SR string needed by linked HashHelpers. |
| src/libraries/System.Linq.Parallel/src/System/Linq/Parallel/Utils/HashLookup.cs | Updates PLINQ HashLookup<,> to use ExpandPrime + FastMod bucketing (and actually uses the multiplier). |
| src/libraries/System.Linq.Parallel/src/System.Linq.Parallel.csproj | Links HashHelpers.cs into System.Linq.Parallel. |
| src/libraries/System.Linq.Parallel/src/Resources/Strings.resx | Adds Arg_HTCapacityOverflow SR string needed by linked HashHelpers. |
| src/libraries/System.Linq.AsyncEnumerable/src/System/Linq/ToLookupAsync.cs | Updates async lookup bucketing/resizing to ExpandPrime + FastMod with cached multiplier. |
| src/libraries/System.Linq.AsyncEnumerable/src/System.Linq.AsyncEnumerable.csproj | Links HashHelpers.cs into System.Linq.AsyncEnumerable. |
| src/libraries/System.Linq.AsyncEnumerable/src/Resources/Strings.resx | Adds Arg_HTCapacityOverflow SR string needed by linked HashHelpers. |
Copilot's findings
- Files reviewed: 9/9 changed files
- Comments generated: 0
|
Thanks. Curious if you had any lookup benchmark improvements to share with this change. |
I hadn't done any explicit ones outside validating that the original issue in #128583 no longer repros. The main point of this wasn't strictly perf related, but to get off a known bad bucketing strategy where entries would incorrectly weight against odd buckets. We should get more concrete perf numbers in the weekly triage on Thursday and/or this next Tuesday. Namely the point was that the previous bucketing logic started at
Where we rarely see primes for larger buckets and the prime factors weight heavily towards every 3rd bucket (and other odd buckets a bit less frequently), leading to more accidental collisions. This also meant that not only could we end up with poor distribution for a given size, but on the next growth its likely that we would persist that poor distribution or even make it worse. It is a known issue with using non-primes for buckets, even if the hashing algorithm is "robust". This is very distinct from -- That is, the |
## Summary The LINQ `Lookup`/`Grouping` bucketing grew its bucket array using a `count * 2 + 1` scheme, effectively only ever picking `pow2 - 1` sizes (7, 15, 31, 63, ...), combined with a plain `hashCode % length` bucket index. This gives poor bucket distribution compared to `Dictionary<TKey, TValue>`. This switches the LINQ hash structures to reuse the same resizing/growth and bucketing that `Dictionary` uses, via the shared `System.Collections.HashHelpers`: - Grow with `HashHelpers.ExpandPrime` (prime sizes) instead of `count * 2 + 1`. - Index buckets with `HashHelpers.FastMod` using a precomputed multiplier, gated on 64-bit (`IntPtr.Size == 8`), with a plain modulo fallback on 32-bit — matching the pattern already used by `Dictionary` and `OrderedDictionary`. The default initial size of 7 is already prime and is retained, so small lookups keep the same starting footprint; only the growth curve changes (e.g. 7 → 17 instead of 7 → 15). This is an alternative approach to #128583, per follow-up discussion: rather than changing the hashing implementation, we align the bucketing/growth with `Dictionary`. ## Scope The same fixup is applied to all three sibling LINQ hash structures that shared the identical anti-pattern: | Structure | Assembly | Backs | |---|---|---| | `Lookup`/`Grouping` | System.Linq | `ToLookup`, `GroupBy`, joins | | `HashLookup<,>` | System.Linq.Parallel | PLINQ `GroupBy`, `Join`, `GroupJoin` | | `AsyncLookup<,>` | System.Linq.AsyncEnumerable | `ToLookupAsync`, `GroupBy`, joins | Each project now links the shared `HashHelpers.cs` and gains the `Arg_HTCapacityOverflow` resource string it references. Note: PLINQ's `HashLookup` previously computed a `fastModMultiplier` but never used it; it is now used. ## Structures reviewed but intentionally left unchanged Several other internal hash structures grow with `mask * 2 + 1` but index with `hashCode & mask` over **power-of-2** tables — a valid, standard strategy, not the `%`-with-`2n+1` anti-pattern this PR targets: `Microsoft.CSharp` `NameTable`, `System.Xml` `NameTable`/`DomNameTable`/`MTNameTable`, and `System.Xml.Linq` `XHashtable`. Changing these would be an out-of-scope behavioral change with no clear benefit. `ComWrappers.RcwCache` (in `System.Private.CoreLib`) does share the true anti-pattern (`% (len*2+1)`), but it is COM-interop-specific, lives in CoreLib, and is keyed on already-distributed `GCHandle` hash codes; it is left for a separate, independently-justified change. ## Testing All existing tests pass with zero failures: - System.Linq.Tests: 52,260 passed - System.Linq.Parallel.Tests: 28,932 passed - System.Linq.AsyncEnumerable.Tests: 547 passed Builds clean across all target frameworks (including `netstandard2.0`/`net462` for System.Linq.AsyncEnumerable). > [!NOTE] > This PR was created by GitHub Copilot. Co-authored-by: Copilot App <223556219+Copilot@users.noreply.github.com>
Summary
The LINQ
Lookup/Groupingbucketing grew its bucket array using acount * 2 + 1scheme, effectively only ever pickingpow2 - 1sizes (7, 15, 31, 63, ...), combined with a plainhashCode % lengthbucket index. This gives poor bucket distribution compared toDictionary<TKey, TValue>.This switches the LINQ hash structures to reuse the same resizing/growth and bucketing that
Dictionaryuses, via the sharedSystem.Collections.HashHelpers:HashHelpers.ExpandPrime(prime sizes) instead ofcount * 2 + 1.HashHelpers.FastModusing a precomputed multiplier, gated on 64-bit (IntPtr.Size == 8), with a plain modulo fallback on 32-bit — matching the pattern already used byDictionaryandOrderedDictionary.The default initial size of 7 is already prime and is retained, so small lookups keep the same starting footprint; only the growth curve changes (e.g. 7 → 17 instead of 7 → 15).
This is an alternative approach to #128583, per follow-up discussion: rather than changing the hashing implementation, we align the bucketing/growth with
Dictionary.Scope
The same fixup is applied to all three sibling LINQ hash structures that shared the identical anti-pattern:
Lookup/GroupingToLookup,GroupBy, joinsHashLookup<,>GroupBy,Join,GroupJoinAsyncLookup<,>ToLookupAsync,GroupBy, joinsEach project now links the shared
HashHelpers.csand gains theArg_HTCapacityOverflowresource string it references.Note: PLINQ's
HashLookuppreviously computed afastModMultiplierbut never used it; it is now used.Structures reviewed but intentionally left unchanged
Several other internal hash structures grow with
mask * 2 + 1but index withhashCode & maskover power-of-2 tables — a valid, standard strategy, not the%-with-2n+1anti-pattern this PR targets:Microsoft.CSharpNameTable,System.XmlNameTable/DomNameTable/MTNameTable, andSystem.Xml.LinqXHashtable. Changing these would be an out-of-scope behavioral change with no clear benefit.ComWrappers.RcwCache(inSystem.Private.CoreLib) does share the true anti-pattern (% (len*2+1)), but it is COM-interop-specific, lives in CoreLib, and is keyed on already-distributedGCHandlehash codes; it is left for a separate, independently-justified change.Testing
All existing tests pass with zero failures:
Builds clean across all target frameworks (including
netstandard2.0/net462for System.Linq.AsyncEnumerable).Note
This PR was created by GitHub Copilot.