静的ダックタイピングのパフォーマンスとその仕組み

ここでの静的ダックタイピングはScalaの構造的部分型(Structural Typing)を用いて実現されるものを指しています。
構造的部分型については以下が参考になるかと思います。

• 構造的部分型について - Qiita
• Scala School - Advanced types
• Structural typing - Effective Scala

tl;dr

構造的部分型はリフレクション結果をキャッシュしてるから速い。

構造的部分型とはどういったものか

下のスニペット中にあるHasSizeのように、特定のメソッドシグネチャを持つ型を指定してそのメソッドを呼ぶことが出来る仕組みのこと。

DuckTyping.scala

object DuckTyping extends App {
  sealed abstract class AwesomeData(id: Int)
  case class Nice(id: Int) extends AwesomeData(id) {
    def size: Int = id * 100
  }
  case class Great(id: Int) extends AwesomeData(id) {
    def size: Int = id * 200
  }

  type HasSize = { def size: Int }
  def callSizeDuck[A <: HasSize](hasSize: A) = {
    hasSize.size
  }
  callSizeDuck(Nice(1)) // 100
  callSizeDuck(Great(2)) // 200
}

引数にsizeメソッドが無い型のインスタンスを与えるとコンパイルエラーとなるため、型安全性は失われないはず。
Javaであればリフレクションで凌ぐところが、Scalaだと安全なダックタイピングが出来てしまう。

パフォーマンスについて

内部的にはリフレクションによって実現されているらしいのでパフォーマンスが気になる
そこでktoso/sbt-jmhを使って計測してみた。

// 共通するクラス定義と変数群
object Param {
  sealed abstract class AwesomeData(id: Int)

  case class Nice(id: Int) extends AwesomeData(id) {
    def size: Int = id * 100
    def calc(n: Int): Int = n * id
  }

  case class Great(id: Int) extends AwesomeData(id) {
    def size: Int = id * 200
    def calc(n: Int): Int = 2 * n * id
  }
  val nice = Nice(1)
  val great = Great(2)
  val seq = Seq(1, 2, 3)

  val num = 10000
  val x = 999
}

// 引数なしバージョン
class DuckTypingJustCall {
  import Param._
  
  // リフレクション
  def callSizeReflection[A](a: A) = {
    val method = a.getClass.getMethod("size")
    val size = method.invoke(a)

    size.asInstanceOf[Int]
  }

  // 構造的部分型
  type HasSize = { def size: Int }
  def callSizeDuck[A <: HasSize](hasSize: A) = {
    hasSize.size
  }

  @Benchmark  // リフレクション
  def benchSizeReflection(): Unit = {
    (0 to num) foreach (_ => callSizeReflection(nice))
  }

  @Benchmark  // 構造的部分型
  def benchSizeDuck(): Unit = {
    (0 to num) foreach (_ => callSizeDuck(nice))
  }
}

// 引数ありバージョン
class DuckTypingWithArg {
  import Param._

  // リフレクション
  def callCalcReflection[A](a: A) = {
    val method = a.getClass.getMethod("calc", classOf[Int])
    val calc = method.invoke(a, x.asInstanceOf[AnyRef])

    calc.asInstanceOf[Int]
  }

  // 構造的部分型
  type HasCalc = { def calc(n: Int): Int }
  def callCalcDuck[A <: HasCalc](hasCalc: A) = {
    hasCalc.calc(x)
  }

  @Benchmark  // リフレクション
  def benchCalcReflection(): Unit = {
    (0 to num) foreach (_ => callCalcReflection(nice))
  }

  @Benchmark  // 構造的部分型
  def benchCalcDuck(): Unit = {
    (0 to num) foreach (_ => callCalcDuck(nice))
  }
}

• 明示的なリフレクション
  • callSizeReflection
  • callCalcReflection
• 構造的部分型
  • callSizeDuck
  • callCalcDuck

$ sbt 'jmh:run -i 10 -wi 10 -f1 -t 1' 

[info] Benchmark                                Mode  Cnt      Score     Error  Units
[info] DuckTypingJustCall.benchSizeDuck        thrpt   10  14463.751 ± 650.516  ops/s
[info] DuckTypingJustCall.benchSizeReflection  thrpt   10    227.449 ±   3.296  ops/s
[info] DuckTypingWithArg.benchCalcDuck         thrpt   10   8887.349 ± 914.437  ops/s
[info] DuckTypingWithArg.benchCalcReflection   thrpt   10    224.279 ±   6.274  ops/s

構造的部分型を用いた方が、引数なしの呼び出しだと64倍、引数ありだと40倍ほどスループットが大きくなった。
Errorが高いため構造的部分型の方が速度にムラがあったらしい。

構造的部分型の方が速い理由

雰囲気をつかむために以下のコマンドを実行。

scalac -version
Scala compiler version 2.11.7 -- Copyright 2002-2013, LAMP/EPFL

scalac /path/to/DuckTyping.scala -Xprint:jvm

該当箇所を抜き出して整形すると以下のようになっている。
引数に関わらず、構造的部分型を用いたメソッドの方はクラスのフィールドにリフレクションで取得したメソッドをキャッシュしてあって、2回目以降に呼び出される時はそのキャッシュを用いるようになっている。

それに対して明示的にリフレクションを使ったものではそういった最適化(?)はなされておらず、毎回メソッド取得処理が走るようになっている。

class DuckTypingJustCall extends Object {
    
    <static> def <init>: Unit = {
      DuckTypingJustCall.this.reflParams$Cache1 = Array[Class]{};
      DuckTypingJustCall.this.reflPoly$Cache1 = new ref.SoftReference(new runtime.EmptyMethodCache());
      ()
    };
    
    final <synthetic> <static> private var reflParams$Cache1: Array[Class] = Array[Class]{};
    
    @volatile <synthetic> <static> private var reflPoly$Cache1: ref.SoftReference = new ref.SoftReference(new runtime.EmptyMethodCache());
    
    <synthetic> <static> def reflMethod$Method1(x$1: Class): reflect.Method = {
      var methodCache1: runtime.MethodCache = DuckTypingJustCall.this.reflPoly$Cache1.get().$asInstanceOf[runtime.MethodCache]();
      if (methodCache1.eq(null)) {
        methodCache1 = new runtime.EmptyMethodCache();
        DuckTypingJustCall.this.reflPoly$Cache1 = new ref.SoftReference(methodCache1)
      };
      var method1: reflect.Method = methodCache1.find(x$1);
      if (method1.ne(null))
        return method1
      else {
        method1 = scala.runtime.ScalaRunTime.ensureAccessible(x$1.getMethod("size", DuckTypingJustCall.this.reflParams$Cache1));
        DuckTypingJustCall.this.reflPoly$Cache1 = new ref.SoftReference(methodCache1.add(x$1, method1));
        return method1
      }
    };
    
    def callSizeReflection(a: Object): Int = {
      val method: java.lang.reflect.Method = a.getClass().getMethod("size", Array[Class]{});
      val size: Object = method.invoke(a, Array[Object]{});
      scala.Int.unbox(size)
    };
    
    def callSizeDuck(hasSize: Object): Int = scala.Int.unbox({
      val qual1: Object = hasSize;
      try {
        DuckTypingJustCall.this.reflMethod$Method1(qual1.getClass()).invoke(qual1, Array[Object]{})
      } catch {
        case (1 @ (_: reflect.InvocationTargetException)) => throw 1.getCause()
      }.$asInstanceOf[Integer]()
    });
    
    def <init>(): net.petitviolet.sandbox.DuckTypingJustCall = {
      DuckTypingJustCall.super.<init>();
      ()
    }
};

class DuckTypingWithArg extends Object {
    
    <static> def <init>: Unit = {
      DuckTypingWithArg.this.reflParams$Cache2 = Array[Class]{java.lang.Integer.TYPE};
      DuckTypingWithArg.this.reflPoly$Cache2 = new ref.SoftReference(new runtime.EmptyMethodCache());
      ()
    };
    
    final <synthetic> <static> private var reflParams$Cache2: Array[Class] = Array[Class]{java.lang.Integer.TYPE};
    
    @volatile <synthetic> <static> private var reflPoly$Cache2: ref.SoftReference = new ref.SoftReference(new runtime.EmptyMethodCache());
    
    <synthetic> <static> def reflMethod$Method2(x$1: Class): reflect.Method = {
      var methodCache2: runtime.MethodCache = DuckTypingWithArg.this.reflPoly$Cache2.get().$asInstanceOf[runtime.MethodCache]();
      if (methodCache2.eq(null)) {
        methodCache2 = new runtime.EmptyMethodCache();
        DuckTypingWithArg.this.reflPoly$Cache2 = new ref.SoftReference(methodCache2)
      };
      var method2: reflect.Method = methodCache2.find(x$1);
      if (method2.ne(null))
        return method2
      else {
        method2 = scala.runtime.ScalaRunTime.ensureAccessible(x$1.getMethod("calc", DuckTypingWithArg.this.reflParams$Cache2));
        DuckTypingWithArg.this.reflPoly$Cache2 = new ref.SoftReference(methodCache2.add(x$1, method2));
        return method2
      }
    };
    
    def callCalcReflection(a: Object): Int = {
      val method: java.lang.reflect.Method = a.getClass().getMethod("calc", Array[Class]{java.lang.Integer.TYPE});
      val calc: Object = method.invoke(a, Array[Object]{scala.Int.box(Param.x())});
      scala.Int.unbox(calc)
    };
    
    def callCalcDuck(hasCalc: Object): Int = scala.Int.unbox({
      val qual2: Object = hasCalc;
      try {
        DuckTypingWithArg.this.reflMethod$Method2(qual2.getClass()).invoke(qual2, Array[Object]{scala.Int.box(Param.x())})
      } catch {
        case (2 @ (_: reflect.InvocationTargetException)) => throw 2.getCause()
      }.$asInstanceOf[Integer]()
    });
    
    def <init>(): net.petitviolet.sandbox.DuckTypingWithArg = {
      DuckTypingWithArg.super.<init>();
      ()
    }
};

パフォーマンス結果を見ると引数ありの方が、引数なしに比べてスループットが小さくなっていたが、メソッドの引数として渡すIntをボクシングしているからのように見える。

まとめ

LL的なダックタイピングが型で守られつつ実行できて、少なくともリフレクションに比べるとパフォーマンスもそこまで悪くないため、必要なシーンがあれば使っても良さそう。

Do not use structural types in normal use.
Effective Scalaより

普通に実装していればjavaより柔軟にtraitでmix-in出来るので、活躍する機会はそんなに無いはずだが、知っていれば何かの役に立つかと。