search

fsharp / fsharp.github.io

F# Core Engineering Group
http://fsharp.github.io
45 stars 53 forks source link

Parallel Typechecking #67

Closed cloudRoutine closed 8 years ago

cloudRoutine commented 8 years ago

I stumbled upon this paper and was curious if some of the techniques it describes could be applied to improve the speed of the F# typechecker.

Abstract Given the sophistication of recent type systems, unification-based type-checking and inference can be a time-consuming phase of compilation—especially when union types are combined with subtyping. It is natural to consider improving performance through parallelism, but these algorithms are challenging to parallelize due to complicated control structure and difficulties representing data in a way that is both efficient and supports concurrency. We provide a solution to these problems based on the LVish approach to deterministic-by-default parallel programming. We extend LVish with a novel class of concurrent data structures: Saturating LVars, which are the first LVars to safely release memory during the object’s lifetime. Our new design allows us to achieve a parallel speedup on worst-case (exponential) inputs of traditional HindleyMilner inference, and on the Typed-Racket type-checking algorithm, which yields up an 8.46× parallel speedup on type-checking examples drawn from the Racket repository.

http://www.ccs.neu.edu/home/samth/parallel-typecheck-draft.pdf

dsyme commented 8 years ago

Hi @cloudRoutine - Thanks for the info!

I'll close this since it's suggestive information and there's a fair leap to an actual adjustment for the F# compiler.