字符串switch的性能分析

假设我们有许多命令。为了本文叙述起来简单些，我们将这些命令全都实现成一个类中的方法。通过字符串名可以调用到对应的命令。方法调用是大小写不敏感的。这个“命令类”看起来会是这样的：

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 );
    }
}

下面哪个方法调用会最快？

EqualsIgnoreCaseCaller.call( obj, "Command9", arg );

EqualsIgnoreCaseCaller.call( obj, "Command99", arg );

EqualsIgnoreCaseCaller.call( obj, "Command100", 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	Units
t.CallTest.testEqualsIgnoreCase9	thrpt	10	998445.643	3518.385	ops/s
t.CallTest.testEqualsIgnoreCase99	thrpt	10	83494.967	1237.927	ops/s
t.CallTest.testEqualsIgnoreCase100	thrpt	10	3701991.457	21054.106	ops/s

Command100的速度最快，其次是Command9，最后是Command99。那为什么在比较链最后的Command100会比前面的Command99要快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);
}

这里最主要的优化就是比较了字符串的长度是否相等。这个检查使得Command100要比前面99个要快不少，从而成为速度最快的一个。而这个优化对Command99而言只能跳过前面9次比较而已。

Command99在找到匹配之前需要比较89*9个字符。下面还有第二个优化——如果拿字符串和自身进行比较的话，第一次比较就会直接通过了。在这里这个优化是有用的，因为所有的字符串都是字面量，因此它们会被驻留到内存池里（interned)。这个优化对于Command100而言则更为重要——整个过程中它压根就不用进行字符串内容的比较（注：前面是长度不等，最后一次是引用相等）。

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的lambda

在Java 8中我们可以将匿名类替换成lambda表达式：

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个命令：从Command1到Command100。我们会去检查Command100的访问时间：

@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	Units
t.CallTest.testEqualsIgnoreCase	thrpt	10	3722062.950	96314.315	ops/s
t.CallTest.testEqualsLowerCase	thrpt	10	1399947.402	11651.113	ops/s
t.CallTest.testJava7Map	thrpt	10	2640137.150	17767.132	ops/s
t.CallTest.testJava8Map	thrpt	10	2673449.940	13438.176	ops/s
t.CallTest.testSwitchCall	thrpt	10	2653356.312	22085.341	ops/s

 



equalsIgnoreCase是最快的，而equals最慢。代码几乎是一样的，除了一个地方——equals用例中它会主动去调用toLowerCase方法，而这正是不同的地方。而switch和map的测试结果则都差不多。


100个同样长度的命令：


我们来修改下测试集合——将100命令改成Command10001到Command10100。这会测试很多命令长度都一样的场景。我们测试的是Command10100的访问时间。


   

Benchmark
Mode	Samples	Mean	Mean error	Units
t.CallTest.testEqualsIgnoreCase	thrpt	10	62066.170	157.287	ops/s
t.CallTest.testEqualsLowerCase	thrpt	10	450102.165	1121.556	ops/s
t.CallTest.testJava7Map	thrpt	10	2411420.337	11454.230	ops/s
t.CallTest.testJava8Map	thrpt	10	2400935.810	54165.643	ops/s
t.CallTest.testSwitchCall	thrpt	10	2406538.563	10945.766	ops/s

  


500个相同长度的命令

我们再试下500个命令的：Command10001 到Command10500。测试的是Command10500的访问时间。


   

Benchmark
Mode	Samples	Mean	Mean error	Units
t.CallTest.testEqualsIgnoreCase	thrpt	10	12899.127	886.002	ops/s
t.CallTest.testEqualsLowerCase	thrpt	10	49137.482	976.380	ops/s
t.CallTest.testJava7Map	thrpt	10	2435168.660	28192.640	ops/s
t.CallTest.testJava8Map	thrpt	10	2488337.117	170484.548	ops/s
t.CallTest.testSwitchCall	thrpt	10	948982.350	2652.893	ops/s

1000个相同长度的命令

最后我们再试下1000个命令的：Command10001 到Command11000。测试的是Command11000的访问时间。


   

Benchmark
Mode	Samples	Mean	Mean error	Units
t.CallTest.testEqualsIgnoreCase	thrpt	10	4338.513	153.786	ops/s
t.CallTest.testEqualsLowerCase	thrpt	10	7602.722	746.926	ops/s
t.CallTest.testJava7Map	thrpt	10	2147853.317	45741.062	ops/s
t.CallTest.testJava8Map	thrpt	10	2339853.845	10194.687	ops/s
t.CallTest.testSwitchCall	thrpt	10	896876.772	5740.585	ops/s

 


可以看到的是在这三个测试中，map的访问时间几乎在所有测试用例中都是差不多的，而equals/equalsIgnoreCase则随着命令数的增长变化很大。

字符串switch的实现

字符串switch的性能非常有意思——它呈对数速度降级，这意味着switch被实现成了一个固定大小的map。我们来试试找出这个固定的MAP的大小是多少。这里至少需要计算两个操作的性能——commandName.toLowerCase()以及command1.equals( command2 )。JMH可以帮忙做这些：

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	Units
t.CallTest.testLC	thrpt	10	3262501.308	610471.458	ops/s
t.CallTest.testEQ	thrpt	10	53070517.985	232819.742	ops/s

  


switch的测试会包括一个commandName.toLowerCase()，后面是大量的equals调用。因此我们可以通过下面的等式来计算equals方法的调用次数：


TEST_TIME = LC_TIME + N * EQ_TIME
        N = ( TEST_TIME - LC_TIME ) / EQ_TIME


在我的测试中计时略有不同。最终结果大概是100个命令对应5个equals调用，而1000个命令有大概50个equals调用。这意味着switch的map表中大概有20个槽位（很可能是一个素数，比如说19，或者23）。

结论

Java 7中的字符串switch是使用一个固定大小的MAP来实现的，这意味着在大多数情况下你可以随意使用，不用太担心它的性能问题。正如你所看到的，当比较的case数小于100的时候，字符串switch的性能和手动实现MAP相比，性能是一样的。

如果你的case语句中字符串长度不等并且也不是很大的话，String.equals/equalsIgnoreCase要比switch的性能要好不少。这是因为在String.equals/equalsIgnoreCase中它是先比较字符串长度，然后再比较实际的内容。

源代码


原创文章转载请注明出处：http://it.deepinmind.com



英文原文链接

评论

3 楼 freezingsky 2014-07-04  

deepinmind 写道

freezingsky 写道

哥们，当需要大量的string 比对时，请将其转换为long型，或者直接点hash之后，再比对！

嗯，Java 7的switch，其实就是这么做的

其实这一块的思路最早来自于C语言。C语言当时为了解决一个大量的字符串比对的问题，转换成了long型处理。目前在C方面对IP的地址处理，还是用的long型。而为什么long要比string快，这里面都知道string的比对，用得最多的是KMP算法，但再好的算法也避免不了字符带来的多次校对的情况。

2 楼 deepinmind 2014-07-04  

freezingsky 写道

哥们，当需要大量的string 比对时，请将其转换为long型，或者直接点hash之后，再比对！

嗯，Java 7的switch，其实就是这么做的

1 楼 freezingsky 2014-06-28  

哥们，当需要大量的string 比对时，请将其转换为long型，或者直接点hash之后，再比对！