LinearExpression.GetHashCode giving stack overflow exception about flips

[matthewcrews]

Once I'm done with the interface work, I will come back and deal with this. I don't think the base types in Flips are going to change, but I'd rather be sure of that before doing the work to update the hashing logic.

[smoothdeveloper]

Update: it only does that in debug builds, I'm not sure how/if you want to address it.

[TysonMN]

this one does a stack overflow:

#r @"C:\dev\src\github.com\matthewcrews\flips\bin\netstandard2.0\Flips.dll"
(Flips.Types.LinearExpression.OfFloat 1.0).GetHashCode()

I think a simpler reproduction is

LinearExpression.Empty.GetHashCode()

However, the devops keeps getting in my way. Sometimes I can't build main either (just like I can't build dev as I said in #138 (comment)).

I think a good fix would be to replace

flips/Flips/Types.fs

Lines 261 to 262 in 73e4065

	override this.GetHashCode () =
	hash this

with

override this.GetHashCode () =
    match this with
    | Empty -> 0
    | AddFloat (f, le) -> hash (f, le)
    | AddDecision (f, d) -> hash (f, d)
    | Multiply (f, le) -> hash (f, le)
    | AddLinearExpression (le1, le2) -> hash (le1, le2)

However, the above devops issue as well as another devops issue have blocked me from confirming this.

it only does that in debug builds

That is interesting. I don't know how to explain this. I am currently unable to confirm this because of the devops issues.

I tried to reproduce this in a minimal working example. In debug, the stack overflows and in release, the behavior seemed to be an infinite loop (presumably because of tail call optimization).

IIRC, Option.None is represented at runtime as null. Maybe Empty is represented in a certain way a runtime in release mode that prevents the infinite recursion.

[matthewcrews]

I tried to reproduce this in a minimal working example. In debug, the stack overflows and in release, the behavior seemed to be an infinite loop (presumably because of tail call optimization).

Yes, that is a challenge with the difference when compiling in Debug vs Release

The GetHashCode will likely need to perform a reduction of the LinearExpression before computing the hash so that you don't get a stack overflow error. This is why the ReducedLinearExpression type exists. The LinearExpression type was intended for just creating a the tree which models the mathematical expression. Writing a reducer of the tree which did not stack overflow took some work.

[TysonMN]

Quoting #141 (comment)

[Approximate equality is] for testing.

Based on that, I think GetHashCode is not being used within the library. It is not intended for public use either even though it is publically exposed.

I think the proper fix for this issue is to implement the approach to infinite precision testing that I suggested in #141 (comment). Then this issue would be fixed by not overriding GetHashCode.

[matthewcrews]

@smoothdeveloper Were you using GetHashCode for anything?

[smoothdeveloper]

That is interesting. I don't know how to explain this. I am currently unable to confirm this because of the devops issues.
I tried to reproduce this in a minimal working example. In debug, the stack overflows and in release, the behavior seemed to be an infinite loop (presumably because of tail call optimization).

@TysonMN I think this is related to how recursion is optimized or not by default by F# compiler, instead of compiling a while loop, it makes actual method calls.

Your proposed code looks better than my work around 🙂, I think this bug is important enough that we should have a fix in main.

@smoothdeveloper Were you using GetHashCode for anything?

Storing in a hashset or as a key in a dictionary would hit this code IIRC.

[TysonMN]

Your proposed code looks better than my work around 🙂, I think this bug is important enough that we should have a fix in main.

I just created PR #142 that contributes that fix. Hopefully it works.

Storing in a hashset or as a key in a dictionary would hit this code IIRC.

You are correct. So, are these being stored in a hashset or dictionary?

Based on the comments by @matthewcrews in #141 (especially #141 (comment) as I quoted in #132 (comment)), I expect that they are not being stored in a hashset or dictionary. Instead, my guess is that only Equals is being used.

This is another disadvantage of using overloads of Equals and GetHashCode. If instead new members MyEquals and MyGetHashCode were created and combined in a custom instance of IEqualityComparer<>, then it would be a trivial symbolic search in Visual Studio to find all uses of these two methods.

[smoothdeveloper]

You are correct. So, are these being stored in a hashset or dictionary?

Not in the implementation of the library AFAIK, but the client code I was writing (toying around with my current implementation for Cplex solver).

I think we can expect that people will keep Decision, LinearExpression and Objective values in their own structures in code consuming Flips:

• they can't access the representation of Model which hold those
• even if they could, it wouldn't fit the needs to map the model and the solution with their own domain in convenient fashion, they could likely rely on hashsets and dictionaries

the usage of such solution for the mapping in client code could be simplified if Flips can work with "representation agnostic" IDecision and the like, and the client code deal with embedding the "ties" that would otherwise be achieved with dictionaries / hashsets.

[TysonMN]

Not in the implementation of the library AFAIK, but the client code I was writing (toying around with my current implementation for Cplex solver).

Can you elaborate on this? PR #142 fixes the stack overflow, but the contract for Equals and GetHashCode are still being violated (c.f. #141). It is important to see how you want to use hashsets and dictionaries in order to select the correct fix.