文字列switchの性能分析

13930 ワード

私たちがたくさんの命令を持っていると仮定します。本論文で述べられるように簡単にするために、これらの命令を全部一つの種類の方法に実現します。文字列名で対応するコマンドを呼び出すことができます。メソッド呼び出しは、大文字と小文字に敏感ではない。このコマンドクラスはこう見えます。




public class ObjectWithCommands {
    public Object Command1( final Object arg ) { return arg; }
    public Object Command2( final Object arg ) { return arg; }
    ...
    public Object Command9( final Object arg ) { return arg; }
    public Object Command10( final Object arg ) { return arg; }
    ...
    public Object Command99( final Object arg ) { return arg; }
    public Object Command100( final Object arg ) { return arg; }
}

本明細書では、これらのコマンドを呼び出す異なる方法間の性能の違いを比較する。
まず、小さいテストをしましょう。これらのコマンドを以下の方法で呼び出すと、




public class EqualsIgnoreCaseCaller {
    public static Object call( final ObjectWithCommands obj, final String commandName, final Object arg )
    {
        if ( commandName.equalsIgnoreCase( "Command1" ) )
            return obj.Command1( arg );
        if ( commandName.equalsIgnoreCase( "Command2" ) )
            return obj.Command2( arg );
        ...
        if ( commandName.equalsIgnoreCase( "Command99" ) )
            return obj.Command99( arg );
        if ( commandName.equalsIgnoreCase( "Command100" ) )
            return obj.Command100( arg );
    }
}

次のどの方法でコールが一番早いですか？

EqualsIgnoreCaller.call（obj，「Command 9」，arg）；

EqualsIgnoreCaller.call（obj，「Command 99」，arg）；

EqualsIgnoreCaller.call（obj，「Commmad 100」，arg）；

私達はJMHの基準テストを書きに来ました。




@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS )
@Measurement(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS )
@Threads(1)
@State(Scope.Thread)
public class CallTest {
    private String m_commandName9 = "Command9";
    private String m_commandName99 = "Command99";
    private String m_commandName100 = "Command100";
    private ObjectWithCommands m_obj = new ObjectWithCommands();
    private Object m_arg = new Object();
 
    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase9()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName9, m_arg);
    }
    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase99()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName99, m_arg);
    }
    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase100()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName100, m_arg);
    }
 
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(".*" + CallTest.class.getSimpleName() + ".*")
                .forks(1)
                .build();
 
        new Runner(opt).run();
    }
}

以下は私のノートでの運行結果です。

Benchmark
Mode
Samples
Mean
Mean error
ユニティ
t.ClalTest.testEquals IgnoreCase 9
thrpt
10
998445.66
3518.385
ops/s
t.ClalTest.testEquals IgnoreCase 99
thrpt
10
83494.967
1237.927
ops/s
t.ClalTest.testEquals IgnoreCase 100
thrpt
10
3701991.457
21054.106
ops/s
Command 100の速度は一番速くて、次はCommand 9で、最後はCommand 99です。なぜチェーンの最後のCommund 100は前のCommand 99より44倍早いですか？彼らの性能は同じではないですか？
もちろんです。String.equalsIgnoreCaseのソースコードを見に来ました。





public boolean equalsIgnoreCase(String anotherString) {
    return (this == anotherString) ? true
            : (anotherString != null)
            && (anotherString.value.length == value.length)
            && regionMatches(true, 0, anotherString, 0, value.length);
}

ここで最も主要な最適化は文字列の長さが等しいかどうかを比較することである。この検査により、Commund 100は前の99個よりずっと速くなります。それによってスピードが一番速いものになります。この最適化はCommand 99にとっては前の9回の比較をスキップするしかないです。
Command 99はマッチを見つける前に89*9文字を比較する必要があります。次の二つの最適化があります。文字列と自分自身を比較すれば、初めての比較はそのまま通過します。この最適化はここで有用であり、すべての文字列は字面量であるため、メモリプールに存在します。この最適化はCommand 100にとってより重要です。全体の過程で文字列の内容を比較する必要はありません。
String.equalsにも同様のロジックがあります。まず唯一の検査で、長さ検査で、最後に内容の比較です。
このような命令代理の論理を実現するには、このような一連のequalsIgnoreCaseを使って呼び出すのが一番いいですか？もっといい方法がありますか？
文字列switchの大きさは敏感ではありません。
String.equalsIgnoreCaseの呼び出しチェーン
これは最も直接的な方法です。残念なことに、固定長のコマンドが一つだけあって、コマンド自体の長さが十分に短い場合にのみ、性能は計算されます。




if ( commandName.equalsIgnoreCase( "Command1" ) )
    return obj.Command1( arg );
if ( commandName.equalsIgnoreCase( "Command2" ) )
    return obj.Command2( arg );
...

Command.toLowerCaseその後String.equals
命令名を小文字に変換して小文字のコマンド名と比較することができます。この方法はコマンド数が増える時によく表現されます。




final String lcName = commandName.toLowerCase();
if ( lcName.equals( "command1" ) )
    return obj.Command1( arg );
if ( lcName.equals( "command2" ) )
    return obj.Command2( arg );

Java 7の文字列switch
Java 7からswitch文に文字列が使用されます。論理的には前のやり方と同じですが、実装上は違います。文字列switchはマッピングテーブルで実現され、文字列を対応する処理コードブロックにマッピングします。




final String lcName = commandName.toLowerCase();
switch( lcName ) {
    case "command1":
        return obj.Command1( arg );
    case "command2":
        return obj.Command2( arg );
    ...
}

文字列switchと明示的な小文字コマンド名を使用してコマンドに向けたmapを比較します。各コマンドは匿名クラスで実現されます。




interface ICommandCaller {
    public Object call( final ObjectWithCommands obj, final Object arg );
}

Java 8の前に実現されるのは、このようなものである。




private static final Map<String, ICommandCaller> CALL_MAP = new HashMap<>( 100 );
static {
    CALL_MAP.put( "command1", new ICommandCaller() {
        public Object call( final ObjectWithCommands obj, final Object arg ) {
            return obj.Command1( arg );
        }
    } );
    CALL_MAP.put( "command2", new ICommandCaller() {
        public Object call( final ObjectWithCommands obj, final Object arg ) {
            return obj.Command2( arg );
        }
    } );
    ...
}
 
public static Object call( final ObjectWithCommands obj, final String commandName, final Object arg )
{
    return CALL_MAP.get( commandName.toLowerCase() ).call( obj, arg );
}

Java 8のlamda
Java 8では匿名クラスをlambada表現に置き換えることができます。




private static final Map<String, ICommandCaller> CALL_MAP = new HashMap<>( 100 );
static {
    CALL_MAP.put( "command1", ( obj, arg ) -> obj.Command1( arg ) );
    CALL_MAP.put( "command2", ( obj, arg ) -> obj.Command2( arg ) );
    ...
}

テスト
上記のクラスはGenerator.javaによって生成されます。ソースは本文の最後にあります。命令の名前と数量を修正してテストを完成します。
極端な場合――他のコマンドとは長さが違います。
上記の例では、これらのアルゴリズムの実行効率はいかがですか？100のコマンド：Commmad 1からCommmad 100までです。Commmad 100のアクセス時間を確認します。




@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS )
@Measurement(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS )
@Threads(1)
@State(Scope.Thread)
public class CallTest {
    private String m_commandName = "Command100";
    private ObjectWithCommands m_obj = new ObjectWithCommands();
    private Object m_arg = new Object();
 
    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName, m_arg);
    }
 
    @GenerateMicroBenchmark
    public Object testEqualsLowerCase()
    {
        return EqualsCaller.call(m_obj, m_commandName, m_arg);
    }
 
    @GenerateMicroBenchmark
    public Object testSwitchCall()
    {
        return SwitchCaller.call(m_obj, m_commandName, m_arg);
    }
 
    @GenerateMicroBenchmark
    public Object testJava7Map()
    {
        return Map7Caller.call(m_obj, m_commandName, m_arg);
    }
 
    @GenerateMicroBenchmark
    public Object testJava8Map()
    {
        return Map8Caller.call(m_obj, m_commandName, m_arg);
    }
 
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(".*" + CallTest.class.getSimpleName() + ".*")
                .forks(1)
                .build();
 
        new Runner(opt).run();
    }
}

以下はテスト結果です。

Benchmark
Mode
Samples
Mean
Mean error
ユニティ
t.ClalTest.testEquals IgnoreCase
thrpt
10
372262.950
96314.315
ops/s
t.ClalTest.testEquals LowerCase
thrpt
10
139947.42
11651.113
ops/s
t.ClalTest.testJava 7 Map
thrpt
10
2640137.15
17767.132
ops/s
t.ClalTest.testJava 8 Map
thrpt
10
2673449.940
13438.176
ops/s
t.ClalTest.testSwitch Call
thrpt
10
2653356.312
22085.321
ops/s

equalsIgnoreCaseは一番速いです。equalsは一番遅いです。コードはほとんど同じです。一箇所のequals用例を除いて、それは自動的にtolowerCase方法を呼び出されます。これは違います。switchとmapのテスト結果は同じです。
100個の同じ長さのコマンド:
テストセットを修正します。100コマンドをCommmad 1001からCommmad 10100に変更します。コマンド長が同じシーンが多くテストされます。私たちがテストしたのはCommmad 10100のアクセス時間です。

Benchmark
Mode
Samples
Mean
Mean error
ユニティ
t.ClalTest.testEquals IgnoreCase
thrpt
10
62066.170
156.87
ops/s
t.ClalTest.testEquals LowerCase
thrpt
10
450102.165
1121.56
ops/s
t.ClalTest.testJava 7 Map
thrpt
10
2411420.37
11454.230
ops/s
t.ClalTest.testJava 8 Map
thrpt
10
2409035.80
54165.643
ops/s
t.ClalTest.testSwitch Call
thrpt
10
2406538.563
10945.766
ops/s

500個の同じ長さのコマンド
私たちは500個のコマンドを試してみました。Commund 1001からCommund 10100までのアクセス時間をテストしました。

Benchmark
Mode
Samples
Mean
Mean error
ユニティ
t.ClalTest.testEquals IgnoreCase
thrpt
10
12899.27
886.002
ops/s
t.ClalTest.testEquals LowerCase
thrpt
10
49137.448
976.380
ops/s
t.ClalTest.testJava 7 Map
thrpt
10
2435168.60
28192.40
ops/s
t.ClalTest.testJava 8 Map
thrpt
10
2488337.117
170484.548
ops/s
t.ClalTest.testSwitch Call
thrpt
10
948982.350
2652.893
ops/s
同じ長さのコマンド1000個
最後に1000個のコマンドを試してみました。Commund 11からCommmad 1000までです。テストはCommmad 1000のアクセス時間です。

Benchmark
Mode
Samples
Mean
Mean error
ユニティ
t.ClalTest.testEquals IgnoreCase
thrpt
10
4338.513
153.786
ops/s
t.ClalTest.testEquals LowerCase
thrpt
10
7602.722
746.926
ops/s
t.ClalTest.testJava 7 Map
thrpt
10
2147853.17
45741.062
ops/s
t.ClalTest.testJava 8 Map
thrpt
10
239853.845
10194.687
ops/s
t.ClalTest.testSwitch Call
thrpt
10
896876.772
5740.585
ops/s

これらの3つのテストでは、mapのアクセス時間はほとんどすべてのテストケースでほぼ同じであり、equals/equals IgnoreCaseはコマンド数の増加とともに大きく変化することが見られます。
文字列switchの実現
文字列switchの性能は非常に興味深いです。対数速度の低下を示しています。これはswitchが固定サイズのmapとして実現されたことを意味します。この固定されたMAPの大きさはどれぐらいかを探してみます。ここで少なくとも2つの操作の性能を計算する必要があります。command Name.toLowercase（）とcommman d 1.equals（command 2）。JMH 2）




private String m_commandName = "Command10500";
private String m_commandName2 = "Command10090";
 
@GenerateMicroBenchmark
public String testLC()
{
    return m_commandName.toLowerCase();
}
 
@GenerateMicroBenchmark
public boolean testEQ()
{
    return m_commandName.equals( m_commandName2 );
}

Benchmark
Mode
Samples
Mean
Mean error
ユニティ
t.ClalTest.testLC
thrpt
10
3262501.38
61071.448
ops/s
t.ClalTest.testEQ
thrpt
10
53070517.985
232819.742
ops/s

switchのテストには、command Name.toLowerCase（）が含まれます。後は大量のequals呼び出しがあります。そのため、次の式を通じてequalsメソッドの呼び出し回数を計算できます。
TEST TIME=LC TIME+N*EQuTIME
        N=(TESTUTIME-LCuTIME)/EQUTIME
私のテストでは、タイミングが少し違っています。最終的には100個のコマンドが5つのequals呼出に対応しています。1000個のコマンドは約50個のequals呼出があります。これはswitchのmapテーブルの中に20個のビットがあることを意味します。
結論

Java 7中の文字列switchは固定サイズのMAPを使用して実現される。これは大多数の場合、自由に使用できることを意味し、性能の問題はあまり心配しなくてもいい。見たように、比較したcase数が100未満の場合、文字列switchの性能は手動でMAPを実現するのと同じである。

もしあなたのcase文の文字列の長さが違っていて、それほど大きくないなら、String.equals/equals IgnoreCaseはswitchの性能よりいいです。これはString.equals/equalsIgnoreCaseの中で文字列の長さを先に比較してから実際の内容を比較するからです。
ソースコード
オリジナルの文章の転載は出典を明記してください。
http://it.deepinmind.com
英語のテキストリンク

Ubuntu 14.04 WPSをインストールする

Linuxは、uinputを使用して仮想inputデバイスを作成します。