Topic/inductive implicits 2.13.x #6481

milessabin · 2018-03-29T14:36:55Z

(continuation of #5649, moved to 2.13.x and rebased on to #6050).

Some additional work is needed to integrate the induction heuristics with byname implicits

This PR provides much faster (35 x in the provided benchmark case) compilation of the kind of inductive implicit resolution that is found in shapeless and its uses for type class derivation in libraries such as Circe, Doobie and Scodec.

The method is to spot patterns in the set of eligible implicit definitions for an implicit argument of the form F[A, B, C ...] corresponding to a singly recursive, convergent (to either success or failure) induction. When these hold the induction is solved for directly by unfolding the recursive steps until one of the base cases is reached. The patterns are a little conservative (in the sense that some inductions might be missed), but they cover many important cases, in particular most of the interesting inductions in shapeless are handled.

The strategy is enabled by the -Yinduction-heuristics scalac flag. If it isn't enabled then normal implicit resolution is always performed. If it is enabled, then the inductive strategy is applied where possible. If it cannot be applied implicit resolution falls back to the normal mechanism. In all cases it is intended that the semantics are identical to normal implicit resolution: the only effect of enabling this option should be a reduction in compile times for applicable implicit resolutions.

An @inductive annotation for types is provided with a similar intent to @tailrec. It asserts that implicit instances of types with the annotation are expected to be solved for by the new induction mechanism. It is an error if they are not and they are instead solved by the normal mechanism. Note that the annotation does not change semantics in the success case (it does change semantics in the failure case because an error is reported). Nor does it affect which algorithm is used to resolve implicits: it is simply a post hoc check that the expected solver was used successfully, in the same way that @tailrec is a post hoc check that an expected tail call optimization was performed.

The use of @inductive allows more informative error messages to be generated for inductions which fail due to missing implicit instances of types which are auxiliary to the main induction. For example, in the case of shapeless's Mapper type class (which recurses through an HList applying an auxiliary type class instance specific to the type of each element as it goes), with normal implicit search if any instance of the auxiliary type class is missing the error reported will be just that the overall Mapper instance can't be resolved. With this algorithm, and in the presence of the @inductive annotation, the compiler knows that an induction is being performed and is able to report that an induction has failed due to the absence of the specific auxiliary type class instance. This is a much requested feature by the authors and users of libraries based on shapeless type class derivation. See test/files/neg/inductive-implicts.{scala,flags,check} for an example.

All (par)tests pass with this option forcibly enabled. In addition shapeless, Circe, Doobie and Scodec, which make extensive use of these forms of induction, all compile and test successfully. A benchmark is provided in test/files/induction which validates my performance claims.

This is an implementation of byname implicit parameters with recursive dictionaries, intended as a language-level replacement for shapeless's Lazy type. As of this commit, implicit arguments can be marked as byname and at call sites will be eligible as parameters in recursively nested positions within their own implicit expansions. Consider the following example, trait Foo { def next: Foo } object Foo { implicit def foo(implicit rec: => Foo): Foo = new Foo { def next = rec } } val foo = implicitly[Foo] assert(foo eq foo.next) In current Scala this would diverge due to the recursive implicit argument rec of method foo. Under the scheme implemented in this commit recursive occurrences of this sort are extracted out as lazy val members of a local synthetic object as follows, val foo: Foo = scala.Predef.implicitly[Foo]( { object LazyDefns$1 { lazy val rec$1: Foo = Foo.foo(rec$1) // recursive knot tied here } LazyDefns$1.rec$1 } ) assert(foo eq foo.next) and the example compiles with the assertion successful. This general pattern is essential to the derivation of type class instances for recursive data types, one of shapeless's most common applications. Byname implicits have a number of benefits over the macro implementation of Lazy in shapeless, + the implementation of Lazy in shapeless is extremely delicate, relying on non-portable compiler internals. By contrast there is already an initial implementation of byname implicits in Dotty: scala/scala3#1998. + the shapeless implementation is unable to modify divergence checking, so to solve recursive instances it effectively disables divergence checking altogether ... this means that incautious use of Lazy can cause the typechecker to loop indefinitely. The byname implicits implementation is able to both solve recursive occurrences and check for divergence. + the implementation of Lazy interferes with the heuristics for solving inductive implicits in scala#5649 because the latter depends on being able to verify that induction steps strictly reduce the size of the types being solved for; the additional Lazy type constructors make the type appear be non-decreasing in size. Whilst this could be special-cased, doing so would require some knowledge of shapeless to be incorporated into the compiler. Being a language-level feature, byname implicits can be accommodated directly in the induction heuristics. + in common cases more implicit arguments would have to be marked as Lazy than would have to be marked as byname under this PR due to restrictions on what the Lazy macro is able to do. Given that there is a runtime cost associated with capturing the thunks required for both Lazy and byname arguments, any reduction in the number is beneficial.

This is an implementation of byname implicit parameters with recursive dictionaries, intended as a language-level replacement for shapeless's Lazy type. As of this commit, implicit arguments can be marked as byname and at call sites recursive uses of implicit values are permitted if they occur in an implicit byname argument. Consider the following example, trait Foo { def next: Foo } object Foo { implicit def foo(implicit rec: Foo): Foo = new Foo { def next = rec } } val foo = implicitly[Foo] assert(foo eq foo.next) In current Scala this would diverge due to the recursive implicit argument rec of method foo. Under the scheme implemented in this commit we can mark the recursive implicit parameter as byname, trait Foo { def next: Foo } object Foo { implicit def foo(implicit rec: => Foo): Foo = new Foo { def next = rec } } val foo = implicitly[Foo] assert(foo eq foo.next) and recursive occurrences of this sort are extracted out as val members of a local synthetic object as follows, val foo: Foo = scala.Predef.implicitly[Foo]( { object LazyDefns$1 { val rec$1: Foo = Foo.foo(rec$1) // ^^^^^ // recursive knot tied here } LazyDefns$1.rec$1 } ) assert(foo eq foo.next) and the example compiles with the assertion successful. Note that the recursive use of rec$1 occurs within the byname argument of foo and is consequently deferred. The desugaring matches what a programmer would do to construct such a recursive value explicitly. This general pattern is essential to the derivation of type class instances for recursive data types, one of shapeless's most common applications. Byname implicits have a number of benefits over the macro implementation of Lazy in shapeless, + the implementation of Lazy in shapeless is extremely delicate, relying on non-portable compiler internals. By contrast there is already an initial implementation of byname implicits in Dotty: scala/scala3#1998. + the shapeless implementation is unable to modify divergence checking, so to solve recursive instances it effectively disables divergence checking altogether ... this means that incautious use of Lazy can cause the typechecker to loop indefinitely. The byname implicits implementation is able to both solve recursive occurrences and check for divergence. + the implementation of Lazy interferes with the heuristics for solving inductive implicits in scala#6481 because the latter depends on being able to verify that induction steps strictly reduce the size of the types being solved for; the additional Lazy type constructors make the type appear be non-decreasing in size. Whilst this could be special-cased, doing so would require some knowledge of shapeless to be incorporated into the compiler. Being a language-level feature, byname implicits can be accommodated directly in the induction heuristics. + in common cases more implicit arguments would have to be marked as Lazy than would have to be marked as byname under this PR due to restrictions on what the Lazy macro is able to do. Given that there is a runtime cost associated with capturing the thunks required for both Lazy and byname arguments, any reduction in the number is beneficial.

In rankImplicits, before we attempt to fully typecheck the pending candidate implicit, we first attempt to partially instantiate type variables in both the candidate and the target type and check for compatibility. If the compatibility check fails we can immediately prune the the candidate without having to fully typecheck it. In the kinds of implicit searches typical of the inductive style found in shapeless and related libraries this can result in a drastic reduction in the search space and a corresponding reduction in compile times. This commit is much simpler, more generally applicable, and less invasive than my earlier work on inductive implicits in, scala#6481 which was doing similar pruning almost by accident. It turns out that almost all of the speedups in that earlier PR were due to the pruning rather than to any special casing of inductive patterns. The compilation benchmark (a shapeless-style "select element by type from a large HList") from that PR is carried over here (in test/induction) and shows the same performance improvements, (1) (2) HList Size 50 4 3 100 7 3 150 15 4 200 28 4 250 48 5 300 81 6 350 126 8 400 189 11 450 322 13 500 405 16 As an added bonus users of shapeless and shapeless based libraries which use shapeless's Lazy type will see benefits immediately without needing to wait for and port to byname implicit arguments. Compile time in seconds

In rankImplicits, before we attempt to fully typecheck the pending candidate implicit, we first attempt to partially instantiate type variables in both the candidate and the target type and check for compatibility. If the compatibility check fails we can immediately prune the the candidate without having to fully typecheck it. In the kinds of implicit searches typical of the inductive style found in shapeless and related libraries this can result in a drastic reduction in the search space and a corresponding reduction in compile times. This commit is much simpler, more generally applicable, and less invasive than my earlier work on inductive implicits in, scala#6481 which was doing similar pruning almost by accident. It turns out that almost all of the speedups in that earlier PR were due to the pruning rather than to any special casing of inductive patterns. The compilation benchmark (a shapeless-style "select element by type from a large HList") from that PR is carried over here (in test/induction) and shows the same performance improvements, (1) (2) HList Size 50 4 3 100 7 3 150 15 4 200 28 4 250 48 5 300 81 6 350 126 8 400 189 11 450 322 13 500 405 16 Compile time in seconds As an added bonus users of shapeless and shapeless based libraries which use shapeless's Lazy type will see benefits immediately without needing to wait for and port to byname implicit arguments.

milessabin · 2018-04-30T18:38:05Z

Closing in favour of #6580.

This is a backport to 2.12.x of, scala#6580 In rankImplicits, before we attempt to fully typecheck the pending candidate implicit, we first attempt to partially instantiate type variables in both the candidate and the target type and check for compatibility. If the compatibility check fails we can immediately prune the the candidate without having to fully typecheck it. In the kinds of implicit searches typical of the inductive style found in shapeless and related libraries this can result in a drastic reduction in the search space and a corresponding reduction in compile times. This commit is much simpler, more generally applicable, and less invasive than my earlier work on inductive implicits in, scala#6481 which was doing similar pruning almost by accident. It turns out that almost all of the speedups in that earlier PR were due to the pruning rather than to any special casing of inductive patterns. The compilation benchmark (a shapeless-style "select element by type from a large HList") from that PR is carried over here (in test/induction) and shows the same performance improvements, 1) baseline - scalac 2.12.5 2) scalac 2.12.5 with matchesPtInst (1) (2) HList Size 50 4 3 100 7 4 150 14 4 200 25 5 250 46 5 300 74 6 350 118 8 400 183 10 450 298 12 500 421 15 Compile time in seconds As an added bonus users of shapeless and shapeless based libraries which use shapeless's Lazy type will see benefits immediately without needing to wait for and port to byname implicit arguments.

In rankImplicits, before we attempt to fully typecheck the pending candidate implicit, we first attempt to partially instantiate type variables in both the candidate and the target type and check for compatibility. If the compatibility check fails we can immediately prune the the candidate without having to fully typecheck it. In the kinds of implicit searches typical of the inductive style found in shapeless and related libraries this can result in a drastic reduction in the search space and a corresponding reduction in compile times. This commit is much simpler, more generally applicable, and less invasive than my earlier work on inductive implicits in, scala#6481 which was doing similar pruning almost by accident. It turns out that almost all of the speedups in that earlier PR were due to the pruning rather than to any special casing of inductive patterns. The compilation benchmark (a shapeless-style "select element by type from a large HList") from that PR is carried over here (in test/induction) and shows the same performance improvements, (1) (2) HList Size 50 4 3 100 7 3 150 15 4 200 28 4 250 48 5 300 81 6 350 126 8 400 189 11 450 322 13 500 405 16 Compile time in seconds As an added bonus users of shapeless and shapeless based libraries which use shapeless's Lazy type will see benefits immediately without needing to wait for and port to byname implicit arguments.

This is an implementation of byname implicit parameters with recursive dictionaries, intended as a language-level replacement for shapeless's Lazy type. As of this commit, implicit arguments can be marked as byname and at call sites recursive uses of implicit values are permitted if they occur in an implicit byname argument. Consider the following example, trait Foo { def next: Foo } object Foo { implicit def foo(implicit rec: Foo): Foo = new Foo { def next = rec } } val foo = implicitly[Foo] assert(foo eq foo.next) In current Scala this would diverge due to the recursive implicit argument rec of method foo. Under the scheme implemented in this commit we can mark the recursive implicit parameter as byname, trait Foo { def next: Foo } object Foo { implicit def foo(implicit rec: => Foo): Foo = new Foo { def next = rec } } val foo = implicitly[Foo] assert(foo eq foo.next) and recursive occurrences of this sort are extracted out as val members of a local synthetic object as follows, val foo: Foo = scala.Predef.implicitly[Foo]( { object LazyDefns$1 { val rec$1: Foo = Foo.foo(rec$1) // ^^^^^ // recursive knot tied here } LazyDefns$1.rec$1 } ) assert(foo eq foo.next) and the example compiles with the assertion successful. Note that the recursive use of rec$1 occurs within the byname argument of foo and is consequently deferred. The desugaring matches what a programmer would do to construct such a recursive value explicitly. This general pattern is essential to the derivation of type class instances for recursive data types, one of shapeless's most common applications. Byname implicits have a number of benefits over the macro implementation of Lazy in shapeless, + the implementation of Lazy in shapeless is extremely delicate, relying on non-portable compiler internals. By contrast there is already an initial implementation of byname implicits in Dotty: scala/scala3#1998. + the shapeless implementation is unable to modify divergence checking, so to solve recursive instances it effectively disables divergence checking altogether ... this means that incautious use of Lazy can cause the typechecker to loop indefinitely. The byname implicits implementation is able to both solve recursive occurrences and check for divergence. + the implementation of Lazy interferes with the heuristics for solving inductive implicits in scala#6481 because the latter depends on being able to verify that induction steps strictly reduce the size of the types being solved for; the additional Lazy type constructors make the type appear be non-decreasing in size. Whilst this could be special-cased, doing so would require some knowledge of shapeless to be incorporated into the compiler. Being a language-level feature, byname implicits can be accommodated directly in the induction heuristics. + in common cases more implicit arguments would have to be marked as Lazy than would have to be marked as byname under this PR due to restrictions on what the Lazy macro is able to do. Given that there is a runtime cost associated with capturing the thunks required for both Lazy and byname arguments, any reduction in the number is beneficial.

In rankImplicits, before we attempt to fully typecheck the pending candidate implicit, we first attempt to partially instantiate type variables in both the candidate and the target type and check for compatibility. If the compatibility check fails we can immediately prune the the candidate without having to fully typecheck it. In the kinds of implicit searches typical of the inductive style found in shapeless and related libraries this can result in a drastic reduction in the search space and a corresponding reduction in compile times. This commit is much simpler, more generally applicable, and less invasive than my earlier work on inductive implicits in, scala#6481 which was doing similar pruning almost by accident. It turns out that almost all of the speedups in that earlier PR were due to the pruning rather than to any special casing of inductive patterns. The compilation benchmark (a shapeless-style "select element by type from a large HList") from that PR is carried over here (in test/induction) and shows the same performance improvements, (1) (2) HList Size 50 4 3 100 7 3 150 15 4 200 28 4 250 48 5 300 81 6 350 126 8 400 189 11 450 322 13 500 405 16 Compile time in seconds As an added bonus users of shapeless and shapeless based libraries which use shapeless's Lazy type will see benefits immediately without needing to wait for and port to byname implicit arguments.

This is an implementation of byname implicit parameters with recursive dictionaries, intended as a language-level replacement for shapeless's Lazy type. As of this commit, implicit arguments can be marked as byname and at call sites recursive uses of implicit values are permitted if they occur in an implicit byname argument. Consider the following example, trait Foo { def next: Foo } object Foo { implicit def foo(implicit rec: Foo): Foo = new Foo { def next = rec } } val foo = implicitly[Foo] assert(foo eq foo.next) In current Scala this would diverge due to the recursive implicit argument rec of method foo. Under the scheme implemented in this commit we can mark the recursive implicit parameter as byname, trait Foo { def next: Foo } object Foo { implicit def foo(implicit rec: => Foo): Foo = new Foo { def next = rec } } val foo = implicitly[Foo] assert(foo eq foo.next) and recursive occurrences of this sort are extracted out as val members of a local synthetic object as follows, val foo: Foo = scala.Predef.implicitly[Foo]( { object LazyDefns$1 { val rec$1: Foo = Foo.foo(rec$1) // ^^^^^ // recursive knot tied here } LazyDefns$1.rec$1 } ) assert(foo eq foo.next) and the example compiles with the assertion successful. Note that the recursive use of rec$1 occurs within the byname argument of foo and is consequently deferred. The desugaring matches what a programmer would do to construct such a recursive value explicitly. This general pattern is essential to the derivation of type class instances for recursive data types, one of shapeless's most common applications. Byname implicits have a number of benefits over the macro implementation of Lazy in shapeless, + the implementation of Lazy in shapeless is extremely delicate, relying on non-portable compiler internals. By contrast there is already an initial implementation of byname implicits in Dotty: scala/scala3#1998. + the shapeless implementation is unable to modify divergence checking, so to solve recursive instances it effectively disables divergence checking altogether ... this means that incautious use of Lazy can cause the typechecker to loop indefinitely. The byname implicits implementation is able to both solve recursive occurrences and check for divergence. + the implementation of Lazy interferes with the heuristics for solving inductive implicits in scala#6481 because the latter depends on being able to verify that induction steps strictly reduce the size of the types being solved for; the additional Lazy type constructors make the type appear be non-decreasing in size. Whilst this could be special-cased, doing so would require some knowledge of shapeless to be incorporated into the compiler. Being a language-level feature, byname implicits can be accommodated directly in the induction heuristics. + in common cases more implicit arguments would have to be marked as Lazy than would have to be marked as byname under this PR due to restrictions on what the Lazy macro is able to do. Given that there is a runtime cost associated with capturing the thunks required for both Lazy and byname arguments, any reduction in the number is beneficial.

milessabin added 3 commits March 29, 2018 14:59

Simplified algorithm; added tests.

4febe74

Faster resolution of inductive implicits.

dd82516

scala-jenkins added this to the 2.13.0-M4 milestone Mar 29, 2018

milessabin added the performance the need for speed. usually compiler performance, sometimes runtime performance. label Mar 29, 2018

milessabin mentioned this pull request Mar 29, 2018

Faster compilation of inductive implicits. #5649

Closed

milessabin mentioned this pull request Apr 19, 2018

Support by-name implicits with recursive dictionaries #6050

Merged

milessabin mentioned this pull request Apr 30, 2018

Prune polymorphic implicits more aggressively #6580

Merged

milessabin closed this Apr 30, 2018

milessabin mentioned this pull request Apr 30, 2018

Prune polymorphic implicits more aggressively (2.12.x backport) #6582

Closed

SethTisue removed this from the 2.13.0-M4 milestone May 4, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Topic/inductive implicits 2.13.x #6481

Topic/inductive implicits 2.13.x #6481

Uh oh!

milessabin commented Mar 29, 2018 •

edited

Loading

Uh oh!

milessabin commented Apr 30, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Topic/inductive implicits 2.13.x #6481

Topic/inductive implicits 2.13.x #6481

Uh oh!

Conversation

milessabin commented Mar 29, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

milessabin commented Apr 30, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

milessabin commented Mar 29, 2018 •

edited

Loading