New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Struct representation for active patterns [ RFC FS-1039 ] #612

Open
gsomix opened this Issue Sep 27, 2017 · 15 comments

Comments

Projects
None yet
6 participants
@gsomix

gsomix commented Sep 27, 2017

Struct representation for active patterns

To make active patterns near-zero-cost abstraction I propose to add struct versions of FSharpOption and FSharpChoice to FSharp.Core and use it as active patterns backend.

The existing way of approaching this problem in F# is using plain functions with custom struct option/choice types instead of active patterns.

Pros and Cons

The advantages of making this adjustment to F# is reducing memory traffic for code with heavily use of active patterns.

The disadvantages of making this adjustment to F# is additional data structures should be added to the FSharp.Core.

Extra information

Estimated cost (XS, S, M, L, XL, XXL): M

Affidavit

Please tick this by placing a cross in the box:

  • This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
  • I have searched both open and closed suggestions on this site and believe this is not a duplicate
  • This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

  • This is not a breaking change to the F# language design
  • I or my company would be willing to help implement and/or test this
@dsyme

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Sep 27, 2017

Collaborator

Yes, we should do this. I'll mark it as approved as I mentally had always intended that we would do this at some point. That makes this the fastest approved suggestion from the community ever I think :)

Collaborator

dsyme commented Sep 27, 2017

Yes, we should do this. I'll mark it as approved as I mentally had always intended that we would do this at some point. That makes this the fastest approved suggestion from the community ever I think :)

@gsomix

This comment has been minimized.

Show comment
Hide comment
@gsomix

gsomix Sep 28, 2017

@dsyme Wow, that's fast. Should I write a RFC?

gsomix commented Sep 28, 2017

@dsyme Wow, that's fast. Should I write a RFC?

@dsyme

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Sep 28, 2017

Collaborator

@gsomix Yes, please

Collaborator

dsyme commented Sep 28, 2017

@gsomix Yes, please

@gsomix

This comment has been minimized.

Show comment
Hide comment
@gsomix

gsomix commented Oct 23, 2017

@gerardtoconnor

This comment has been minimized.

Show comment
Hide comment
@gerardtoconnor

gerardtoconnor Nov 20, 2017

Further to the request, in relation to the extra "trick" for users (expanded api), is there any reason we would not always want AP to be structs except for backwards compatibility? In cases where we know the created value is immediately deconstructed in next return/call, there is just no need to allocate and therefore perhaps, instead of requiring annotation, we could look to make struct default with overload/constraint resolver in match syntax accept both struct/obj AP so that there is no noticeable difference to user but backwards compatibility being maintained?

As an aside, I don't see why Option should not always be a struct too as the copy time of bool * ref is negligible vs just ref, and in the majority of cases, option is a temp structure in an evaluation pipeline to safely deliver a result, it is less frequently used as a persisted data structure. On this basis, it would be great if we could think of a way to make Option struct by default, and have match syntax and Option module overload/constrain for both (but the differing/defaulting namespace usage may be tricky).

gerardtoconnor commented Nov 20, 2017

Further to the request, in relation to the extra "trick" for users (expanded api), is there any reason we would not always want AP to be structs except for backwards compatibility? In cases where we know the created value is immediately deconstructed in next return/call, there is just no need to allocate and therefore perhaps, instead of requiring annotation, we could look to make struct default with overload/constraint resolver in match syntax accept both struct/obj AP so that there is no noticeable difference to user but backwards compatibility being maintained?

As an aside, I don't see why Option should not always be a struct too as the copy time of bool * ref is negligible vs just ref, and in the majority of cases, option is a temp structure in an evaluation pipeline to safely deliver a result, it is less frequently used as a persisted data structure. On this basis, it would be great if we could think of a way to make Option struct by default, and have match syntax and Option module overload/constrain for both (but the differing/defaulting namespace usage may be tricky).

@vasily-kirichenko

This comment has been minimized.

Show comment
Hide comment
@vasily-kirichenko

vasily-kirichenko Nov 20, 2017

@gerardtoconnor Someone should make an experiment: make Option a struct, then compile the compiler with it (it uses options a lot), then compile VFT solution with the new compiler and compare times.

vasily-kirichenko commented Nov 20, 2017

@gerardtoconnor Someone should make an experiment: make Option a struct, then compile the compiler with it (it uses options a lot), then compile VFT solution with the new compiler and compare times.

@realvictorprm

This comment has been minimized.

Show comment
Hide comment
@realvictorprm

realvictorprm Nov 20, 2017

Member
Member

realvictorprm commented Nov 20, 2017

@vasily-kirichenko

This comment has been minimized.

Show comment
Hide comment
@vasily-kirichenko

vasily-kirichenko Nov 20, 2017

It's not crazy. We must not change anything so that the compiler becomes slower that it is.

vasily-kirichenko commented Nov 20, 2017

It's not crazy. We must not change anything so that the compiler becomes slower that it is.

@gerardtoconnor

This comment has been minimized.

Show comment
Hide comment
@gerardtoconnor

gerardtoconnor Nov 20, 2017

@vasily-kirichenko don't worry, I would never suggest we change something so integral without heavy testing first, for both compatibility and performance. As we've briefly discussed before, structs are not silver bullets and often slow JIT down but there are cases where it is highly likely (but not certain) that it will perform better, namely, temp pipelines with TCO (that stay on stack without boxing).

Updating the compiler with things like this (as you know) will often blow up with errors and require a lot of tidying/fixing to get all working again so before we start down that road, It is helpful if experts like you and Don share any obvious feedback I'm overlooking as I have nowhere near the familiarity of the internals you guys have.

gerardtoconnor commented Nov 20, 2017

@vasily-kirichenko don't worry, I would never suggest we change something so integral without heavy testing first, for both compatibility and performance. As we've briefly discussed before, structs are not silver bullets and often slow JIT down but there are cases where it is highly likely (but not certain) that it will perform better, namely, temp pipelines with TCO (that stay on stack without boxing).

Updating the compiler with things like this (as you know) will often blow up with errors and require a lot of tidying/fixing to get all working again so before we start down that road, It is helpful if experts like you and Don share any obvious feedback I'm overlooking as I have nowhere near the familiarity of the internals you guys have.

@vasily-kirichenko

This comment has been minimized.

Show comment
Hide comment
@vasily-kirichenko

vasily-kirichenko Nov 20, 2017

I'm not an expert :) But I've already tried to make Option a struct several months ago and it broke compilation heavily, so a gave up fixing it.

vasily-kirichenko commented Nov 20, 2017

I'm not an expert :) But I've already tried to make Option a struct several months ago and it broke compilation heavily, so a gave up fixing it.

@gerardtoconnor

This comment has been minimized.

Show comment
Hide comment
@gerardtoconnor

gerardtoconnor Nov 20, 2017

I've tried to integrate my new map into compiler but due to heavy direct use of Map module on aliased map types, it blew up with hundreds of errors (despite the aliased map type module functions all being fine.) so I have a healthy respect for what your saying, appreciate these things are not simple.

gerardtoconnor commented Nov 20, 2017

I've tried to integrate my new map into compiler but due to heavy direct use of Map module on aliased map types, it blew up with hundreds of errors (despite the aliased map type module functions all being fine.) so I have a healthy respect for what your saying, appreciate these things are not simple.

@gerardtoconnor

This comment has been minimized.

Show comment
Hide comment
@gerardtoconnor

gerardtoconnor Nov 20, 2017

On a side note, It would be pretty amazing (and extremely difficult) if optimizer could change data types (DU & Records) automatically between obj or struct based on the execution path, ie, if temp value never leaves stack with TCO, change to struct, otherwise, if boxing/copying/persisted, use obj ... as most users should not have to care about struct/obj or stack/heap as it's irrelevant to their app logic.

If types had instance methods, would need to convert to static methods with additional instance argument but that's the easy part, reliably defining the obj/struct rules as well as passing loose types through type checker would be difficult but could take the approach of everything is a type (obj) and it can be optimized to a struct in latter part of compilation once execution paths known.

gerardtoconnor commented Nov 20, 2017

On a side note, It would be pretty amazing (and extremely difficult) if optimizer could change data types (DU & Records) automatically between obj or struct based on the execution path, ie, if temp value never leaves stack with TCO, change to struct, otherwise, if boxing/copying/persisted, use obj ... as most users should not have to care about struct/obj or stack/heap as it's irrelevant to their app logic.

If types had instance methods, would need to convert to static methods with additional instance argument but that's the easy part, reliably defining the obj/struct rules as well as passing loose types through type checker would be difficult but could take the approach of everything is a type (obj) and it can be optimized to a struct in latter part of compilation once execution paths known.

@dsyme dsyme added the needs rfc label Dec 1, 2017

@dsyme dsyme removed the needs rfc label Dec 1, 2017

@dsyme dsyme changed the title from Struct representation for active patterns to Struct representation for active patterns [ RFC FS-1039 ] Dec 1, 2017

@wanton7

This comment has been minimized.

Show comment
Hide comment
@wanton7

wanton7 Jan 23, 2018

I just started using this language little while back and was amazed that Option is not a struct already. When struct Option is available be it ValueOption or StructOption i wish you can set some setting in F# project file to default to struct option. Maybe you could then use something like heapoption or classoption keyword to use class version, if you really need it to be a class.

Edit.. Noticed that Option has [<CompilationRepresentation(CompilationRepresentationFlags.UseNullAsTrueValue)>] attribute. If i understood it correctly None will be null and Some will heap allocate a class that host the value. If it's so then current situation is much better than thought because None doesn't allocate anything.

Edit 2. Just understood that struct Option DU can't be named None and Some. So this might be a bigger problem to solve. Compiler would have to map None and Some to struct versions as well.

wanton7 commented Jan 23, 2018

I just started using this language little while back and was amazed that Option is not a struct already. When struct Option is available be it ValueOption or StructOption i wish you can set some setting in F# project file to default to struct option. Maybe you could then use something like heapoption or classoption keyword to use class version, if you really need it to be a class.

Edit.. Noticed that Option has [<CompilationRepresentation(CompilationRepresentationFlags.UseNullAsTrueValue)>] attribute. If i understood it correctly None will be null and Some will heap allocate a class that host the value. If it's so then current situation is much better than thought because None doesn't allocate anything.

Edit 2. Just understood that struct Option DU can't be named None and Some. So this might be a bigger problem to solve. Compiler would have to map None and Some to struct versions as well.

@wanton7

This comment has been minimized.

Show comment
Hide comment
@wanton7

wanton7 Jan 28, 2018

I wish struct option won't be named StructOption, StructSome and StructNone. To make this more usable, how about using option = maybe, Option = Maybe, None = Nothing and Some = Just for struct version naming similar to Haskell? I would hate to write StructSome and StructNone all the time.

wanton7 commented Jan 28, 2018

I wish struct option won't be named StructOption, StructSome and StructNone. To make this more usable, how about using option = maybe, Option = Maybe, None = Nothing and Some = Just for struct version naming similar to Haskell? I would hate to write StructSome and StructNone all the time.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment