Repository navigation
Stack overflow on calling GetHashCode on large list #1838
Description
I stumbled on this by chance of having a large list as part of a record and something in WPF calling GetHashCode.
Repro steps
Run this code, with or without tail calls enabled
[0..5000000].GetHashCode()Expected behavior
I would expect a result, perhaps even if only based on the first n items in the list.
Actual behavior
Execution terminates with StackOverflowException
Related information
VS 2015 Update 3
FSharp.Core 4.4.0.0
.NET Framework 4.6.1
Activity
forki commentedon Nov 25, 2016
Yes we should compute a result - but it needs all items.
forki commentedon Nov 25, 2016
@dsyme any hints to where I can find the impl?
forki commentedon Nov 25, 2016
does it fall back to IEnumerable.GetHashCode()?
PatrickMcDonald commentedon Nov 25, 2016
@forki maybe we need all the items for backwards compatibility, but without a backwards compatibility requirement there might be a case for limiting the items included in the calculation
e.g. (Seq.initInfinite id).GetHashCode() returns in a finite amount of time :)
dsyme commentedon Nov 26, 2016
@forki I think this will be hard to fix. Check the implementation of the GetHashCode override for the list type, generated by
src\fsharp\AugmentWithHashCompare.fs. It should ideally be a tail-calling loop (turned into a real loop byIlxGen.fs)forki commentedon Nov 26, 2016
tbh I can't fin the list case. I assume it uses mkUnionHashWithComparer!?
dsyme commentedon Nov 26, 2016
Yes
dsyme commentedon Nov 26, 2016
Can we confirm this is not a regression please? I'm pretty sure it isn't, indeed it is really a feature request?
forki commentedon Nov 27, 2016
It is a feature request that something doesn't blow up in stack overflow? ;-)
forki commentedon Nov 27, 2016
To be more serious: I think if we just return 0 instead of blowing up (somehow try catch the things) it would probably already solve many issues.
dsyme commentedon Nov 27, 2016
@forki The bahviour has to be backwards-compat, without changing the hash codes.
IIRC it's hard to make this tail-recursive but I can't remember the details.
abelbraaksma commentedon Dec 4, 2016
For the record, I can confirm this blows up in both debug and release builds using F# 4.0, VS2015, Win7, x86 and x64 builds (if that'd make a difference).
I don't know why this needs to be hard to be tail-recursive. In fact, I think we owe it to the users to be tail-recursive, even if it is hard. Didn't Jon Harrop once claim that every recursive function can be turned into a recursive one? I'm no expert, but if that's true..., we should, right?
The current algorithm (as I see it in Reflector on
FSharpList<T>) is first calculating hash of tail (the recursion), then combines that with head and some bit shifting. Unless the requirement is that it must behave exactly the same (except for the uncatchable SO exception, sorry @forki, you cannot catch this one and then return 0), it shouldn't be too hard to reverse the order, or add a continuation.dsyme commentedon Dec 5, 2016
One easy solution is to hand-write the GetHashCoe implementations for F# lists, rather than rely on the generated augmentation code.
The code should be written in such a way that the hash codes don't change from today
abelbraaksma commentedon Dec 5, 2016
@dsyme, Not sure I follow. You mean with "from today" that historical hash codes should be equal, that is (
hash [1;2]in vX must be integer-equal tohash [1;2]in vNext) or that BCL hash code must be integer-equal to whatever we come up with for F# lists?26 remaining items
abelbraaksma commentedon Oct 4, 2020
@krauthaufen, looking at the linked #9070, which was started to fix this, a fix lead to unexpected changes in code generation. I've had the intention to give it another look or use a different approach. I'll see what I can do.
Workarounds involve things like wrapping
Listin a new DU where you override theGetHashCodemethod, or doing so in every type that includes list types. It's unf. easy to forget and easy to get wrong.cartermp commentedon Oct 4, 2020
Yeah, unfortunately this one will be tricky without risking a source breaking or binary breaking change on one of the most-used data types in FSharp.Core: #9070 (comment)
The alternative fix is to "flatten" the structural hash function generated for lists. Since a list is defined as recursive DU, this change would also affect all other recursive DUs unless it were specialized only to list. Either way it's tricky business.
krauthaufen commentedon Oct 4, 2020
Hey, personally I think that changing HashCode values for types is not really a breaking change but if you're commited to keep the hashcodes identical I think there will not really be a way to solve this with tail-recursion/loops.
Generally speaking shouldn't all DU hashes be implemented accumulator-style s.t. cases like lists 'accidentially' are tail-recursive?
cartermp commentedon Oct 4, 2020
Note that my concerns have nothing to do with the actual hash code values. It's that the emitted API shape is different than if you explicitly implement those interfaces in List.
Happypig375 commentedon Jun 2, 2021
Even though the
hashfunction can also be used for arrays and get structural hashes, this still works but not for lists. Strange.abelbraaksma commentedon Nov 30, 2022
lists are recursive data types. The generic hash implementation uses a generic, non tail recursive approach. Hence the SO exception. Solution is to either make the code TCO, or to special case lists (or both).
abelbraaksma commentedon Jan 7, 2023
Awesome this got solved!! Gonna open the champagne now 😄. This one was a big deal :).
voronoipotato commentedon Feb 14, 2023
I missed that this was fixed! Amazing thank you so much for all your hard work.