「数字6桁パスワードのMD5ハッシュ値の総当たり」Scalaは1.70秒だった

[パスワード問合せシステムを作る (clojureのreducers)](http://qiita.com/kawasima/items/ef75f317605ce800a839) に端を発してにわかに盛り上がっている **数字6桁パスワードのMD5ハッシュ値の総当たり** ですが、PHPやPerlでは1秒を切る実装が紹介されているようです。（他の言語もあるかもしれません）
[数字6桁パスワードのハッシュ値の総当たり、PHPなら約0.25秒で終わるよ](http://z.tokumaru.org/2014/02/6php025.html)
[数字6桁パスワードのハッシュ値の総当たり、Perlでも約0.25秒で終わるよ](http://shimx.hateblo.jp/entry/2014/02/10/190132)

[kawasima氏](http://qiita.com/kawasima)は追加の記事（[String.formatが遅い理由](http://qiita.com/kawasima/items/d671d9e57ac03f24fbaa)）で「String.formatが遅い原因」と書かれてますが、JVM上の言語で実際にどの程度なものなのか試してみました。。。Scalaで！

## 環境
Winodws7 Pro SP1 64bit/Corei7-3770K/JDK 1.7.0_25/Scala 2.10.3

## フォーマッタ利用、並列化無し

まずはClojureと同様の処理をScalaで書いてみます。

```scala:FindPassword_Single.scala
import java.security.{MessageDigest => MD}
 
object MD5FindPassword_Single_WithFormatter {
  def findPassword(salt:String, pw:String):Option[Int]  = {
    def hexdigest(s:String):String = {
      val digester = MD.getInstance("MD5")
      digester.update(s.getBytes)
      digester.digest.toList.map(_&0xff).map("%02x".format(_)).mkString
    }
    (0 to 1000000)
      .find(i => hexdigest("%s$%06d".format(salt, i)) == pw)
 
  }
  def main(args: Array[String]) {
    findPassword(args(0), args(1)) match {
      case Some(f) => printf("match [%06d]%n", f)
      case None    => printf("not match%n")
    }
  }
}
```

11.88秒でした。遅いですね。

## フォーマッタ利用、並列化有り

Scalaの場合、parメソッドを呼び出すだけでCollectionを容易に並列Collection化できます。

```scala:MD5FindPassword_Parallel_WithFormatter.scala
import java.security.{MessageDigest => MD}
 
object MD5FindPassword_Parallel_WithFormatter {
  def findPassword(salt:String, pw:String):Option[Int]  = {
    def hexdigest(s:String):String = {
      val digester = MD.getInstance("MD5")
      digester.update(s.getBytes)
      digester.digest.toList.map(_&0xff).map("%02x".format(_)).mkString
    }
    (0 to 1000000)
      .par // 変更点はココだけ
      .find(i => hexdigest("%s$%06d".format(salt, i)) == pw)
 
  }
  def main(args: Array[String]) {
    findPassword(args(0), args(1)) match {
      case Some(f) => printf("match [%06d]%n", f)
      case None    => printf("not match%n")
    }
  }
}
```

4.52秒になりました。8コアありますが、さすがに単純に1/8にはなりませんね。

## フォーマッタ無し、並列化無し

では、フォーマッタを使わないとどうなるか。

```scala:MD5FindPassword_Single_NoFormatter.scala
import java.security.{MessageDigest => MD}
 
object MD5FindPassword_Single_NoFormatter {
  def findPassword(salt:String, pw:String):Option[Int]  = {
    def hexformatter(x:Int):String = {
      val h = Integer.toHexString(x)
      "0"*(2 - h.length) + h.toString
    }
    def mkOrigin(x:Int):String = {
      val xs = x.toString
      salt + "$" + "0"*(6 - xs.length) + xs
    }
    def hexdigest(s:String):String = {
      val digester = MD.getInstance("MD5")
      digester.update(s.getBytes)
      digester.digest.toList.map(_&0xff).map(hexformatter(_)).mkString
    }
    (0 to 1000000)
      .find(i => hexdigest(mkOrigin(i)) == pw)
 
  }
  def main(args: Array[String]) {
    findPassword(args(0), args(1)) match {
      case Some(f) => printf("match [%06d]%n", f)
      case None    => printf("not match%n")
    }
  }
}
```

3.10秒でした。Formatterを使った場合に比べて1/4になっています。確かにFormatterはかなり遅いですね。

## フォーマッタ無し、並列化有り

最後に、フォーマッタ無しで並列化有りの場合

```scala:MD5FindPassword_Parallel_NoFormatter.scala
import java.security.{MessageDigest => MD}
 
object MD5FindPassword_Parallel_NoFormatter {
  def findPassword(salt:String, pw:String):Option[Int]  = {
    def hexformatter(x:Int):String = {
      val h = Integer.toHexString(x)
      "0"*(2 - h.length) + h.toString
    }
    def mkOrigin(x:Int):String = {
      val xs = x.toString
      salt + "$" + "0"*(6 - xs.length) + xs
    }
    def hexdigest(s:String):String = {
      val digester = MD.getInstance("MD5")
      digester.update(s.getBytes)
      digester.digest.toList.map(_&0xff).map(hexformatter(_)).mkString
    }
    (0 to 1000000)
      .par // 変更点はココだけ
      .find(i => hexdigest(mkOrigin(i)) == pw)
 
  }
  def main(args: Array[String]) {
    findPassword(args(0), args(1)) match {
      case Some(f) => printf("match [%06d]%n", f)
      case None    => printf("not match%n")
    }
  }
}
```

1.70秒まで縮みました

## まとめ

| パターン                     |    秒 |
|:-----------------------------|------:|
| フォーマッタ利用＋並列化無し | 11.88 |
| フォーマッタ利用＋並列化有り |  4.52 |
| フォーマッタ無し＋並列化無し |  3.10 |
| フォーマッタ無し＋並列化有り |  1.70 |

JVM上の言語でも、2秒は切れるようですが、1秒を切ることはできませんでした。
なんだかとても悔しいので、次はCで書いてみます。