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.

[manofstick]

Riding home this afternoon I have thought of a Plan. It will require a few hours to implement so hopefully I'll get a chance over the weekend.

[manofstick]

I'm a fixer! (Well hopefully better than that!) But problem solved!.

OK; So this was the thought process to solving this;

Problem:

1. I'd splattered eliminate_tail_call_xxx quite liberally over the place;
2. Can't use constrained generics, as can't tail call them (although that does sound like a JIT problem to me... But I got no leverage with them...)

Solution:

1. Don't
2. Hmmm... I can still create types based on what is required, but just use casting where required (which, when I think about it, must be going on under the hood anyway, as generics share implementation? Mr Original Implementer, can tell me if I'm wrong!)

Anyway, here is a gist which stack-overflowed here. This should probably be added in some form to regression tests. The pull request that fixes the problem is here at #961.

This PR might fail regression tests due to me pushing the removal of eliminate_tail_call_xxx in some situations; but I'd prefer someone else to eyeball any IL generation changes.

Not sure. Anyway. Friday night. Few beers down. Time to watch some brain rotting TV.

[dsyme]

@manofstick @KevinRansom @otawfik-ms Looking through the prim-types.fs code that came from #513 I realize now that we simply didn't code review that code properly, see this comment. To be honest I actually have very little idea what that code is doing.

I really think we must revert that PR until it is properly reviewed. It is just wrong to have so much complexity inserted into such a critical part of FSharp.Core without proper review and without many people understanding what is going on. We are just asking for trouble if we take that approach.

I don't feel able to review changes/fixes to that code until we've properly reviewed and adjusted the #513 PR.

@manofstick - do you think you could you prepare a PR to revert the change and resubmit it? I'm really sorry but it's in the best interests of F# to do that.

[dsyme]

@manofstick Can I confirm that this is the relevant change to prim-types.fs? Thanks

[dsyme]

Here's a link to the file diff (thanks @enricosada) https://github.com/Microsoft/visualfsharp/commit/0735d37c2a5ca5fcfdde6405f6a4a94700404c3d.diff

[manofstick]

@dsyme

I shouldn't of scared you with reminders of Christopher Pyne! :-)

Anyway, no worries I'll make the PR to restore original prim_types.fs over the weekend.

Then I'm thinking that we close #513, #961 & #930, and then can just make one new PR that is the combination of them all, as there is no real point in dealing with them in isolation.

...and really if it makes it back into master or not is ultimately neither here nor there. To me the more important thing is to know why it makes it or not. I obviously have a quite silly style of commentary in my correspondence, but I do take it code very seriously, and understand the responsibility of ensuring stability of the code base (if not my comments!) My light heartedness is just an attempt to engage with people (and I'm surrounded by 2 little monsters under 4 years old, so that also probably affects my communication style!)

That said I do think the implementation I have written is a bridge between the two worlds that you have created - i.e. generics and f#. I think it does use some tricks that are on the edge of rules, but still fully within the rules. I think the composition of the constrained types into tuples comparison is an elegance that appears because of the underlying simplicity of this use. I am saddened that I didn't test recursive types with generic arguments, as I had just written off recursive types being resolved by the inlining within the compiler - I should have done better.

Anyway, let's reset, and start again.

[manofstick]

#966 removes #513. This issue should be closed. The phoenix will rise again, but I'm not sure when.

[dsyme]

#966 removes #513. This issue should be closed. The phoenix will rise again, but I'm not sure when.