【Scala】n%127やn%129よりもn%128のほうが速い。もっと言うとn&127のほうが速い。

結論は、タイトルの通りです。

ついでに、n % 128の代わりにn & 127と書くと速くなるのか（正数の場合のみ等価ですが）も検証した結果、
今回の検証環境では若干速くなった。

本記事では、これをどう検証したのかを書きます。

検証方法

↓以下手順でsbt-jmhを導入する
JMHを使ってScalaのパフォーマンスを計測する - Qiita

ベンチマークのコードを書く

import java.security.SecureRandom
import org.openjdk.jmh.annotations.{Benchmark, Scope, Setup, State}

@State(Scope.Thread)//スレッド毎にフィールドの状態を持つようにする
class Mod {
  private val r = new SecureRandom
  private var number = 0

  //ベンチマークの実行前に実行してくれるらしい
  @Setup def getNumber() = number = r.nextInt(Integer.MAX_VALUE)

  @Benchmark def mod128 = number % 128

  @Benchmark def mod129 = number % 129

  @Benchmark def mod127 = number % 127

  @Benchmark def bitMask127 = number & 127
}

sbt shellで以下コマンドを打つ

jmh:clean
jmh:compile
jmh:run com.github.momosetkn.mod.Mod

jmh:runだけだとjarに入ってたorg.openjdk.jmh.benchmarks.BlackholeBenchとかもベンチマークしようとして１０時間以上もかかることがあるのでクラス名を指定しました。

ベンチマークの結果

環境

OS: Ubuntu 18.04LTS
CPU: i7-4770K
JMH version: 1.21
VM version: JDK 11.0.2, OpenJDK 64-Bit Server VM, 11.0.2+9

[info] Benchmark        Mode  Cnt          Score          Error  Units
[info] Mod.bitMask127  thrpt   25  404978709.111 ± 11379559.349  ops/s
[info] Mod.mod127      thrpt   25  215737442.945 ± 10010415.077  ops/s
[info] Mod.mod128      thrpt   25  369377857.751 ± 14498431.564  ops/s
[info] Mod.mod129      thrpt   25  294198802.757 ± 15613693.254  ops/s

Scoreがスループットの値となります。
今回の結果はn&127でビットマスクしたほうがn%128の剰余演算より9%速くなっている。
n % 127はビットマスクの半分ぐらいのスループットしか出ていない。
こんなに違いが出るとは思いもしなかった。
Error(誤差)も大きくなってますね。詳しいことは、他の記事に任せますが、計算に必要な時間が分子の数によって変わってくるのでしょう。

Bytecodeを見てみた

IntelliJ IDEAなどのJetBrainsのIDEを使っている人は、
メニューバーのBuild=>Build Projectしてから、View=>Show Bytecodeでバイトコードが見れます。

  // access flags 0x1
  public mod128()I
  @Lorg/openjdk/jmh/annotations/Benchmark;()
   L0
    LINENUMBER 16 L0
    ALOAD 0
    INVOKESPECIAL com/github/momosetkn/mod/Mod.number ()I
    SIPUSH 128
    IREM
    IRETURN
   L1
    LOCALVARIABLE this Lcom/github/momosetkn/mod/Mod; L0 L1 0
    MAXSTACK = 2
    MAXLOCALS = 1

  // access flags 0x1
  public bitMask127()I
  @Lorg/openjdk/jmh/annotations/Benchmark;()
   L0
    LINENUMBER 22 L0
    ALOAD 0
    INVOKESPECIAL com/github/momosetkn/mod/Mod.number ()I
    BIPUSH 127
    IAND
    IRETURN
   L1
    LOCALVARIABLE this Lcom/github/momosetkn/mod/Mod; L0 L1 0
    MAXSTACK = 2
    MAXLOCALS = 1

bitMask127メソッドのほうはIANDというビットごとの論理積の命令だが、
mod128メソッドのほうはIREMという余りを求める命令。
もし、JavaやScalaの言語仕様に符号なし整数(unsigned int)という型があったのであれば、この辺は最適化してくれていたかもしれません。

↓参考
Java仮想マシン - Wikipedia

⚠負数の場合は等価にならない

-1 % 128 //-1
-1 & 127 //127

オマケ

C++コンパイラでunsigned intの場合にはn % 128と書いてもn & 127と書いても同じコンパイル結果になるか（最適化がされるか）の調査結果

↓調査に使ったもの
Compiler Explorer

|C++コンパイラ |最適化されるか|
|:--|:--|:--|
|x86-64 gcc 8.3 | O|
|x86-64 clang 8.0 | O|
|x86-64 icc 19.0.1 |O|
|x64 msvc v19.20 | X|
|x64 msvc v19.20(最適化オプション-O1) | O|