Consider tailcalls and 513 (generic specializations for eq/hash/compare)

[dsyme]

#513 has removed some tailcalls, see the discussion starting here: #944 (comment)

@manofstick is looking into the cases where this has caused a change in behaviour and whether we should consider reverting #513 pending resolution of theses issues.

My concern is that we just keep things exactly as they were before (no regressions) for the cases we care about, which are outlined in the thread above. If necessary we can pin down exactly the cases where we expect the automatically generated eq/hash/compare to work on arbitrarily size data inputs.

[manofstick]

OMG, I have looked deeper into the rabbit hole than my poor myoptic eyes are capable !

Anyways...

Let's recap from where we left off. In this comment I made an assertion that I believed that the code gen of f# is potentially not adding the tail call instruction in on constrained type calls (and I was unsure if this was for technical reasons). I think I'm now I'm pretty confident that it is a valid construct, and a fix to the F# compiler would assist in making #513 work (heck, if I can pass the buck...)

OK, so lets start with the simply case of tail instruction:

type JumpBImpl () =
    member __.JumpB (x:JumpAImpl, y:JumpAImpl) : bool =
        if (System.Random ()).NextDouble () < 0.0 then failwith "this is just to stop inlining, and should not occur"
        x.JumpA y

and [<AllowNullLiteral>] JumpAImpl(parent:JumpAImpl) =
    member __.Next = parent
    member this.JumpA (other:JumpAImpl) =
        let e = JumpBImpl ()
        System.Console.Write '.'
        e.JumpB (this.Next, other.Next)

let rec createList n l  = 
    if n = 0 then l
    else createList (n-1) (JumpAImpl l)

let a0 = createList 100000 (JumpAImpl null)
let e = a0
let value = e.JumpA a0

This code does what I would expect it to - outputs a lot of dots and then crash with a null reference exception! (not pretty, but just asserts that it manages to get to the tail of the list).

If this is then modified to this version

type JumpBImpl<'a when 'a : null and 'a :> System.IEquatable<'a>>() =
    member __.JumpB (x:'a, y:'a) =
        x.Equals y

[<AllowNullLiteral>]
type JumpAImpl(parent:JumpAImpl) =
    member __.Next = parent
    interface System.IEquatable<JumpAImpl> with
        member this.Equals other =
            let e = JumpBImpl<JumpAImpl> ()
            System.Console.Write '.'
            e.JumpB (this.Next, other.Next)

let rec createList n l  = 
    if n = 0 then l
    else createList (n-1) (JumpAImpl l)

let a0 = createList 100000 (JumpAImpl null)
let e = a0 :> System.IEquatable<JumpAImpl>
let value = e.Equals a0

Then this no longer "works", it now crashes with a stack overflow, rather than a null reference exception. What we see is that the calls to JumpA and JumpB now no longer have the IL tail instruction added, as they are used in a generic context (presumably).

So to see if this was an actual limitation, or just a potential compiler issue, I dumped the IL and added the tail instruction before the call, and compiled it up with ilasm and low and behold it works!

The gist of that is here.

But I know not how deeply this is within the F# il generation code and would be really grateful if someone could take the lead on that one?

[manofstick]

There does appear to be some performance implications here, although I'm hoping for non-trivial code (i.e. something that actually does something!) then it will hopefully be unnoticeable (well at least for ref types and value types <= 64 bits).

Anyway, if I modify the code so that I return instead of crashing when I reach the root, and shrink the list so that I no longer have a stackoverflow, adding some timing around that shows that with the introduction of the tail instruction the 64-bit JIT takes about half the time, and the 32-bit JIT takes about twice as long! The lord giveth and he taketh away...

[dsyme]

It seems that neither of these pass peverify.

tail.
constrained. !a
callvirt   instance bool class [mscorlib]System.IEquatable`1<!a>::Equals(!0)

or

constrained. !a
tail.
callvirt   instance bool class [mscorlib]System.IEquatable`1<!a>::Equals(!0)

I believe this is because in the case of a value type instantiation a byref to a local value (potentially on the stack) is being passed as the first argument to the constrained call.

[dsyme]

BTW my debugging technique was

devenv /debugexe Debug\net40\bin\fsc.exe tmp.fs

then breakpoint in IlxGen.fs on all the places where I_callconstrained is generated

[manofstick]

Ug. I was under the deluded impression that if it compiled with ilasm (and executed properly!) then it was good! (i.e. what I had produced in the gist above...) Damn peverify! Could it be that peverify is wrong?!?!

Anyway, well I'll have a little think about other things... Possibly I could detect recursive types and fall back to the default back to the original comparison method... Hmmm...

[dsyme]

@manofstick For clarity, could you list a couple of recursive type definitions where behaviour has definitely changed? Thanks.

[manofstick]

Using this "test harness" (well...)

let rec createList n l  = 
    if n = 0 then l
    else createList (n-1) (createItem n l)

let lots = 1000000
let a0 = createList lots Nil
let a1 = createList lots Nil

System.Console.WriteLine ("{0}", (a0 = a1))

The following type blows up (based on your idea)

type Pair<'T,'U> = Pair of 'T * 'U
type List<'T> = Nil | Cons of Pair<'T, List<'T>>
let createItem n l = (Cons (Pair(n, l)))

Under the existing compiler this blows up under Debug, but runs under Release, but with #513 this also blows up under Release.

[manofstick]

Actually maybe this isn't too bad after all. I it seems that the particular form listed above is possibly the only case that currently works and after #513 doesn't.

The whole point of this is for auto generated operators, so I see this as for structs, tuples, records, union types. I have tried the various combinations on the above failing example.

If the "Cons" recursive type:

• is not right most in any of the structures it currently fails
• is in a struct it currently fails
• is in a tuple or an explicitly defined recursive type record or union type then it works.
• is only recursive via a generic argument that makes it recursive (in a record or union), then it current works, but now doesn't.

I would be willing to accept that limitation (he says, with his fingers crossed behind his back).

[manofstick]

Maybe something like:

let recursiveViaGenericArgument (rootType:System.Type) =
    let processed = System.Collections.Generic.HashSet ()

    let rec takesRootAsGenericArgument depth isGenericArgument (typeToCheck:System.Type) =
        if depth > 0 && rootType.Equals typeToCheck then
            isGenericArgument
        elif processed.Add typeToCheck |> not then 
            false
        else
            let genericArgumentIsRoot =
                typeToCheck.IsGenericType
                && typeToCheck.GetGenericArguments ()
                    |> Array.exists (takesRootAsGenericArgument (depth+1) true)

            if genericArgumentIsRoot then
                true
            elif FSharp.Reflection.FSharpType.IsUnion typeToCheck then
                FSharp.Reflection.FSharpType.GetUnionCases typeToCheck
                |> Array.exists (fun case -> 
                    case.GetFields ()
                    |> Array.exists (fun field -> takesRootAsGenericArgument (depth+1) false field.PropertyType))
            elif FSharp.Reflection.FSharpType.IsRecord typeToCheck then
                FSharp.Reflection.FSharpType.GetRecordFields typeToCheck
                |> Array.exists (fun field -> takesRootAsGenericArgument (depth+1) false field.PropertyType)
            else
                false
    takesRootAsGenericArgument 0 false rootType

[manofstick]

Hmmm... There is a non-trivial amount of code to support the FSharp.Reflection functionality. What are your thoughts on maybe ripping all the comparison code out of prim_types and putting it in a separate module that comes after reflect? It might mean exposing some currently module private prim_types items; I'm not sure.

There would need to be some sort of hook back into prim_types. I'm imagining some sort of mutable function that represents a factory which creates the comparers. When the new comparers module is initialized it would set this function. Not pretty, but should work? The initial factory could be null if we wanted to ensure it was always initialized correctly (i.e. just crash if it isn't!), or could be a default factory object that creates the original style comparers - might be safer given initialization ordering; maybe.

I think it would be nice from a cognitive perspective to rip out all that code to a separate file.

[dsyme]

Actually maybe this isn't too bad after all. I it seems that the particular form listed above is possibly the only case that currently works and after #513 doesn't.

.. .If a generic argument is instantiated to a record or union in a way that makes the type recursive, then it current works, but now doesn't..... I would be willing to accept that limitation (he says, with his fingers crossed behind his back)......

I am also willing to accept this limitation. I think the best thing is to submit testing that pins down this behaviour in positive cases systematically. If we do that I think we can be done with this?

Thanks!
Don

[manofstick]

I keep going from high to lows with this... My new low is can't do recursive record types like:

type XList<'T> = { N : 'T; L : option<XList<'T>> }

As that falls into the camp of "true" to my recursiveViaGenericArgument function above.