inline algebra typeclass methods

[erikerlandson]

fix #1309

[erikerlandson]

Note, I cannot inline fromInt or fromDouble because in Fractional and Numeric they inherit multiply from both Field and ConvertibleFromDouble, and so they must be overridden there. inline defs are always final, so these cannot be inlined at DoubleIsField.

Just leaving fromInt and fromDouble as-is seems reasonable, since fixing this little knot would likely require larger interface changes.

[erikerlandson]

Thanks for the PR! In the PR description/comments would you mind sharing a small program whose bytecode would be optimized because of these changes?

Yes, I can provide an example that invokes at least one method from each instance (Field, NRoot, Trig, etc). I can exercise all the inlined methods if you want.

[armanbilge]

I can exercise all the inlined methods if you want.

Thanks, just one is sufficient! Essentially a manual test just to demonstrate that this PR actually works, and to demonstrate how to take advantage of it. Since typeclasses are often used in dynamic dispatch situations, I don't think the inlining can work in those cases. Probably it can only work when the typeclass instance itself is inlined.

[erikerlandson]

Probably it can only work when the typeclass instance itself is inlined.

That is what my experiments show - if the calling code itself is not inline, it will default to the standard non-inlined typeclass calls.

Here is a code example that demonstrates in-lining of methods from "all" the Double typeclasses. If you compile this in scala-3, you should see that any references to actual typeclass methods have been elided by inlining:

object inlineTest {
    import spire.implicits.*

    type DoubleTypeClasses = Field[Double]
        & NRoot[Double]
        & Trig[Double]
        & Order[Double]
        & Signed[Double]
        & IsRational[Double]
        & TruncatedDivisionCRing[Double]

    inline def inlinedCalls(x: Double, y: Double)(using alg: DoubleTypeClasses): Double =
        val t1 = alg.plus(x, y)
        val t2 = alg.sqrt(x)
        val t3 = alg.exp(y)
        val t4 = alg.compare(x, y)
        val t5 = alg.abs(x)
        val t6 = alg.tmod(x, y)
        val t7 = alg.floor(y)

        t1 + t2 + t3 + t4 + t5 + t6 + t7

    val x = 1.0
    val y = 2.0

    // with scala-3 inlined typeclasses, the resulting bytecode should
    // show no reference to actual typeclass methods, only raw double
    // operations or calls to 'Math.xxx' methods or other java methods.
    val z = inlinedCalls(x, y)
}

[erikerlandson]

@armanbilge as you can see, this change breaks MIMA. Before we proceed, is this going to be a problem?

I can limit the ABI damage to scala-3 only, since this doesn't really apply to scala-2 anyway

[erikerlandson]

@armanbilge that seems to work :tada:

The methods are all inlined. It seems to be inserting a call to implicit function, although its result is unused in the subsequent bytecode:

      20: getstatic     #33                 // Field spire/implicits$.MODULE$:Lspire/implicits$;
      23: invokevirtual #37                 // Method spire/implicits$.ImplicitDoubleAlgebra:()Lspire/std/DoubleAlgebra;

Maybe it gets removed in linking? https://docs.scala-lang.org/scala3/reference/contextual/givens.html# "The inlining of given instances will not inline/duplicate the implementation of the given, it will just inline the instantiation of that instance. This is used to help dead code elimination of the given instances that are not used after inlining."

I'm a bit puzzled by it, because in my experiments described on #1309, the implicit object never appeared in the byte code at all, but that was an actual object, not an implicit function.

[armanbilge]

Maybe it gets removed in linking?

If by "linking" you mean the JVM optimizes it away at runtime, then maybe? Scala.js and Scala Native have an explicit linking step, but Scala JVM does not.

The reason that static call may be there is to force the companion object to initialize. Not sure.

[erikerlandson]

@armanbilge The four native types are complete. I think that is where I wanted to get for this. One minor dangling mystery is that mima check failed for log on NRoot[Int] and NRoot[Long], I'm guessing because it's exposed somewhere else besides IntAlgebra. I removed the inline for that and fpow just to see if it passed (it did).

[armanbilge]

It should be okay to leave inline for fpow.

The reason it failed for log is because log is actually not part of the NRoot parent interface. I'm not sure why that method is there. Anyway, when you add inline, it takes away the usual method declaration. This hasn't been a problem in the other cases because the method declaration is always inherited from the parent interface.

[erikerlandson]

@armanbilge the only question I have left is whether there is a way to get rid of the call to implicit function in the byte-code. I doubt I will have a second chance to mess with the signatures without failing MIMA.

[armanbilge]

the only question I have left is whether there is a way to get rid of the call to implicit function

I suspect that might be required for semantics, but I'm not sure. Might be a question for the compiler team (I wouldn't be surprised if there was an existing issue on this topic).

[erikerlandson]

@armanbilge I think I have worked out what is going on. Basically, scala compiles implicit def ... differently than given .... If I declare using given x: X = ..., then scala will not include any call to x() in its bytecode, but if I use the equivalent implicit def x: X = ..., then it will add the x() call.

I don't think it's currently feasible to use given ImplicitDoubleAlgebra ... and friends with spire, because it also requires the user to import xxx.{*, given}, and so doing it breaks the spire code, and presumably any client code currently calling spire.

I could try filing a compiler issue about this, but even if it is feasible to get the compiler to understand when it can elide this call, I doubt it would be a high priority for the compiler devs.

[erikerlandson]

@armanbilge given the above, I think this is the best possible solution for spire, so I'm OK to merge if you are.

I suppose it might be feasible to add some new import that uses given for scala-3 users, but that seems like a separate discussion.

[armanbilge]

I could try filing a compiler issue about this, but even if it is feasible to get the compiler to understand when it can elide this call, I doubt it would be a high priority for the compiler devs.

It looks like a bug to me, and specifically a bug with given, not with implicit def. I don't think it's an optimization issue, it's an issue of correctness / semantics, so I believe it would be high priority. Let's see what they say.

• https://github.com/lampepfl/dotty/issues/19348

[erikerlandson]

@armanbilge the behavior in your reproducer definitely seems like a bug.

[erikerlandson]

@armanbilge so we should consider @static given ?

[armanbilge]

I experimented with @static today in Cats Effect and it has two issues:

1. I do not see a way to apply it compatibly to existing APIs
2. It's completely broken on Scala.js

• https://github.com/typelevel/cats-effect/pull/3934

[erikerlandson]

I don't think any given declarations can be backward compatible with existing spire, but if we demonstrated they can compile to faster code with scala-3 I could imagine providing some new scala-3 only givens to import.

[armanbilge]

If we can get @static to work, we can just directly apply to implicit defs. No need to fuss with given for that.