search

fslaborg / flips

Fsharp LInear Programming System
https://flipslibrary.com/#/
MIT License
253 stars 32 forks source link

LinearExpression.GetHashCode giving stack overflow exception #132

Closed smoothdeveloper closed 3 years ago

smoothdeveloper commented 3 years ago

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()

this originates from: https://github.com/matthewcrews/flips/blob/e6c9141a1cc1f9cee715cf20a2378b4be818c66c/Flips/Types.fs#L261-L262

there are few other implementation that looks the same.

current work around is to change the implementation to the rather crude hash (sprintf "%A" this) but this will be problematic.

matthewcrews commented 3 years ago

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 commented 3 years ago

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

TysonMN commented 3 years ago

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 https://github.com/fslaborg/flips/issues/138#issuecomment-752101711).

I think a good fix would be to replace https://github.com/fslaborg/flips/blob/73e4065bd422b69ddf0a10bd55b1e2b897f7fe06/Flips/Types.fs#L261-L262

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 commented 3 years ago

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 commented 3 years ago

Quoting https://github.com/fslaborg/flips/issues/141#issuecomment-752183805

[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 https://github.com/fslaborg/flips/issues/141#issuecomment-752194963. Then this issue would be fixed by not overriding GetHashCode.

matthewcrews commented 3 years ago

@smoothdeveloper Were you using GetHashCode for anything?

smoothdeveloper commented 3 years ago

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 commented 3 years ago

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 https://github.com/fslaborg/flips/issues/141#issuecomment-752183805 as I quoted in https://github.com/fslaborg/flips/issues/132#issuecomment-752227358), 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 commented 3 years ago

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:

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 commented 3 years ago

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.