Pure Java より速いぞ Groovy!

前回、ContinuedFraction クラス（連分数）を使って円周率 π の評価をしましが、Groovy だとパフォーマンス的になかなか悲しい結果になりました。　と、そう言えば最近 id:uehaj 殿が「速いぞGroovy!」って記事を書いてらしたなぁと思い出したので、ちょっと試してみようかと。

参考 URL

• 「速いぞGroovy!」
• 「Yes, Fibonacci in Groovy can be as fast as Java !」
• 「ASM Bytecode Outline for IntelliJ IDEA」

バイトコードを書く!?

正直、バイトコードの素養は全くないのでどうしたものかと思ってたのですが、実はゼロからバイトコードを書く必要はないようです。　そのカラクリは「ASM bytecode outline plugin for IntelliJ IDEA」。　これは Java のソースコードをコンパイルして生成されるバイトコードをアウトラインに表示してくれる IntelliJ Plugin。　これを使えば、普通の Java コードを書くだけで必要なバイトコードを作ることができます。　大雑把な手順はこんな感じ：

• 準備
  1. 「ASM Bytecode Outline for IntelliJ IDEA」からプラグインのアーカイブをダウンロード。
  2. IntelliJ IDEA のインストール・ディレクトリに上記のアーカイブを展開（インストール）
  3. @Bytecode アノテーションと BytecodeASTTransformation クラスを作成する（この記事の最後「インフラ・コード」を参照）
• バイトコード生成
  1. 通常の Java コードを書く
  2. 書いた Java コードのバイトコードを「ASM Bytecode Outline」で表示し、バイトコードを必要な箇所へコピペ
  3. バイトコードを修正する
     • 全て小文字にする*1
     • linenumber, localvariable の行を削除
     • goto → _goto
     • frame same1 d → frame same1, 'D'
     • など

「ASM bytecode outline plugin for IntelliJ IDEA」の使い方はダウンロードしたページにある程度載ってるのでそちらを参照のこと。　バイトコードの修正は大雑把かと。　下記のサンプルコードを見てください。

Groovy コードをバイトコードにすると言いつつ、Java コードを書いてるのがナカナカ本末転倒感たっぷりだけど、まぁ使い方次第ってことで。

パフォーマンス

さて、コードは Groovy コード内での無名クラスで実装しましょう。　ジャジャーン！

def fracBytecode = new ContinuedFraction(){
    @Override @ast.Bytecode
    protected double getA(int n, double x) {
        l0
            iload 1
            ifne l1
            ldc 3.0
            _goto l2
        l1
            frame same
            ldc 6.0
        l2
            frame same1, 'D'
            dreturn
    }

    @Override @ast.Bytecode
    protected double getB(int n, double x) {
        l0
            iconst_2
            iload 1
            imul
            iconst_1
            isub
            i2d
            dstore 4
        l1
            dload 4
            dload 4
            dmul
            dreturn
    }
}

perform(fracBytecode, 'Groovy Bytecode')

たぶん、Fibonacci 数列のサンプルより簡単ダネ（笑）　ゼロからはとても書けないけど。　で、これを実行してみると（前回の実行結果も再掲）

Pure Java : 125 ms
Groovy Closure : 2906 ms
Groovy Anonymous : 1000 ms
Groovy Bytecode : 78 ms

おぉ〜！　Pure Java よりも速ぇ〜!!　よほどの事がない限り使わない方法だろうけど、よほどの事態には使える方法かと！

インフラ・コード

最後にバイトコードを生成するために必要なアノテーションとクラスを書いておきます。　実はバイトコードよりもこっちの方が込み入ってるんですけど：

• アノテーション ast.Bytecode
• クラス ast.BytecodeASTTransformation

Bytecode アノテーションは「Yes, Fibonacci in Groovy can be as fast as Java !」で書かれているもののコピペで構いません（パッケージ注意）：

package ast

import java.lang.annotation.*
import org.codehaus.groovy.transform.GroovyASTTransformationClass

@Retention(RetentionPolicy.SOURCE)
@Target([ElementType.METHOD])
@GroovyASTTransformationClass(["ast.BytecodeASTTransformation"])
public @interface Bytecode {}

一方、BytecodeASTTransformation は上記リンク先にあるコードのコピペでは動きません。　というのは、バイトコードの命令セットが網羅されていないためです。　サンプルの Fibonacci 数列のコードが動くほぼ最低限の命令セットしか処理できねーようになってるッ！　苦心の末なんとか動くように修正できました：

package ast

import groovyjarjarasm.asm.Label
import groovyjarjarasm.asm.MethodVisitor
import groovyjarjarasm.asm.Opcodes
import org.codehaus.groovy.ast.ASTNode
import org.codehaus.groovy.ast.expr.ArgumentListExpression
import org.codehaus.groovy.ast.expr.MethodCallExpression
import org.codehaus.groovy.ast.expr.VariableExpression
import org.codehaus.groovy.ast.stmt.ExpressionStatement
import org.codehaus.groovy.classgen.BytecodeInstruction
import org.codehaus.groovy.classgen.BytecodeSequence
import org.codehaus.groovy.control.CompilePhase
import org.codehaus.groovy.control.SourceUnit
import org.codehaus.groovy.transform.ASTTransformation
import org.codehaus.groovy.transform.GroovyASTTransformation

@GroovyASTTransformation(phase = CompilePhase.SEMANTIC_ANALYSIS)
class BytecodeASTTransformation implements ASTTransformation, Opcodes {
        void visit(ASTNode[] nodes, SourceUnit source) {
                def meth = nodes[1]
                def instructions = meth.code.statements
                meth.code = new BytecodeSequence(new BytecodeInstruction() {
                        @Override
                        void visit(MethodVisitor mv) {
                                def labels = [:]
                                // perform first visit to collect labels
                                instructions.each { ExpressionStatement stmt ->
                                        def expression = stmt.expression
                                        if (expression instanceof VariableExpression) {
                                                def text = expression.text
                                                if (text ==~ /l[0-9]+/) {
                                                        labels.put(text, new Label())
                                                }
                                        }
                                }
                                instructions.each { ExpressionStatement stmt ->
                                        def expression = stmt.expression
                                        if (expression instanceof VariableExpression) {
                                                def text = expression.text
                                                if (text ==~ /l[0-9]+/) {
                                                        mv.visitLabel(labels[text])
                                                } else if (text =~ /[aild]const|[aild]sub|[aild]add|[aild]mul|[aild]return|[aild]2[aild]/) {
                                                        mv.visitInsn(Opcodes."${text.toUpperCase()}")
                                                } else {
                                                        throw new IllegalArgumentException("Bytecode operation unsupported : "+text);
                                                }
                                        } else if (expression instanceof MethodCallExpression) {
                                                if (expression.objectExpression instanceof VariableExpression 
                                                    && expression.arguments instanceof ArgumentListExpression) {
                                                        if (expression.objectExpression.text=="this") {
                                                                def opcode = expression.methodAsString.toUpperCase()
                                                                ArgumentListExpression args = expression.arguments
                                                                switch (opcode) {
                                                                        case '_GOTO':
                                                                                mv.visitJumpInsn(GOTO, labels[args.expressions[0].text])
                                                                                break;
                                                                        case 'IFNE':
                                                                                mv.visitJumpInsn(Opcodes."${opcode}",
                                                                                                        labels[args.expressions[0].text])
                                                                                break;
                                                                        case 'ILOAD':
                                                                        case 'DLOAD':
                                                                        case 'DSTORE':
                                                                                mv.visitVarInsn(Opcodes."${opcode}",
                                                                                                      args.expressions[0].text as int)
                                                                                break;
                                                                        case 'LDC':
                                                                                mv.visitLdcInsn(args.expressions[0].text as double)
                                                                                break;
                                                                        case 'FRAME':
                                                                                def frameId = args.expressions[0].text.toUpperCase()
                                                                                if ('SAME'==frameId) {
                                                                                        mv.visitFrame(Opcodes.F_SAME, 0, null, 0, null);
                                                                                        break;
                                                                                } else if ('SAME1'==frameId) {
                                                                                        if (args.expressions[1].text=='I') {
                                                                                                mv.visitFrame(Opcodes.F_SAME1,
                                                                                                                    0, null, 1,
                                                                                                                    [Opcodes.INTEGER] as Object[]);
                                                                                                break;
                                                                                        }else if (args.expressions[1].text=='D') {
                                                                                                mv.visitFrame(Opcodes.F_SAME1,
                                                                                                                    0, null, 1,
                                                                                                                    [Opcodes.DOUBLE] as Object[]);
                                                                                                break;
                                                                                        }
                                                                                }
                                                                        default:
                                                                                throw new IllegalArgumentException(
                                                                                    "Bytecode operation unsupported : "+expression);
                                                                }
                                                        } else {
                                                                throw new IllegalArgumentException(
                                                                     "Bytecode operation unsupported : "+expression);
                                                        }
                                                } else {
                                                        throw new IllegalArgumentException(
                                                            "Bytecode operation unsupported : "+expression);
                                                }
                                        } else {
                                                throw new IllegalArgumentException(
                                                    "Bytecode operation unsupported : "+expression);
                                        }
                                }
                        }
                })
        }
}

他の命令が必要になったら、もう知らん！　つーか、Groovy 1.8 になってプリミティブ型がサクサク動くようになったら、この苦労は無駄になるのかなぁ・・・　無常なり。

Java仮想マシン仕様 (The Java series)

*1:小文字にしたい箇所を選択して [メニューバー] → Edit → Toggle Case