`
deepinmind
  • 浏览: 452231 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
1dc14e59-7bdf-33ab-841a-02d087aed982
Java函数式编程
浏览量:41682
社区版块
存档分类
最新评论

字符串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
    ModeSamplesMeanMean errorUnits
    t.CallTest.testEqualsIgnoreCase9thrpt10998445.6433518.385ops/s
    t.CallTest.testEqualsIgnoreCase99thrpt1083494.9671237.927ops/s
    t.CallTest.testEqualsIgnoreCase100thrpt103701991.45721054.106ops/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
    ModeSamplesMeanMean errorUnits
    t.CallTest.testEqualsIgnoreCasethrpt103722062.95096314.315ops/s
    t.CallTest.testEqualsLowerCasethrpt101399947.40211651.113ops/s
    t.CallTest.testJava7Mapthrpt102640137.15017767.132ops/s
    t.CallTest.testJava8Mapthrpt102673449.94013438.176ops/s
    t.CallTest.testSwitchCallthrpt102653356.31222085.341ops/s 
     



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


    100个同样长度的命令:


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


       
    Benchmark
    ModeSamplesMeanMean errorUnits
    t.CallTest.testEqualsIgnoreCasethrpt1062066.170157.287ops/s
    t.CallTest.testEqualsLowerCasethrpt10450102.1651121.556ops/s
    t.CallTest.testJava7Mapthrpt102411420.33711454.230ops/s
    t.CallTest.testJava8Mapthrpt102400935.81054165.643ops/s
    t.CallTest.testSwitchCallthrpt102406538.56310945.766ops/s 
      


    500个相同长度的命令

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


       
    Benchmark
    ModeSamplesMeanMean errorUnits
    t.CallTest.testEqualsIgnoreCasethrpt1012899.127886.002ops/s
    t.CallTest.testEqualsLowerCasethrpt1049137.482976.380ops/s
    t.CallTest.testJava7Mapthrpt102435168.66028192.640ops/s
    t.CallTest.testJava8Mapthrpt102488337.117170484.548ops/s
    t.CallTest.testSwitchCallthrpt10948982.3502652.893ops/s 



    1000个相同长度的命令

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


       
    Benchmark
    ModeSamplesMeanMean errorUnits
    t.CallTest.testEqualsIgnoreCasethrpt104338.513153.786ops/s
    t.CallTest.testEqualsLowerCasethrpt107602.722746.926ops/s
    t.CallTest.testJava7Mapthrpt102147853.31745741.062ops/s
    t.CallTest.testJava8Mapthrpt102339853.84510194.687ops/s
    t.CallTest.testSwitchCallthrpt10896876.7725740.585ops/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
    ModeSamplesMeanMean errorUnits
    t.CallTest.testLCthrpt103262501.308610471.458ops/s
    t.CallTest.testEQthrpt1053070517.985232819.742ops/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



    英文原文链接
    1
    0
    分享到:
    评论
    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之后,再比对!

    相关推荐

      单片机解析字符串命令示例

      在单片机编程中,解析字符串命令是一种常见的交互方式,特别是在STM8S003这样的微控制器上。本文将深入探讨如何在STM8S003单片机最小系统上实现这一功能,以及相关的编程技术和注意事项。 首先,我们需要了解STM8S...

      JAVA编码习惯和几款JAVA性能分析工具

      6. **避免字符串字面量的重复定义**:如果一个字符串在多处被使用,应将其定义为常量,以减少内存开销和提高代码可读性。例如: ```java public static final String MY_APP = "My Application"; private void ...

      plugin_sched_switch.rar_The Switch

      - 性能监控:收集任务切换的统计数据,用于性能分析和优化。 - 调度策略扩展:引入新的调度策略,比如专门为实时任务或特定应用设计的策略。 `plugin_sched_switch` 可能会添加钩子(hooks)或回调函数,以便在任务...

      计算机网络课程设计-词法分析器.docx

      词法分析器的输入是所给文法的源程序字符串,而输出是一个二元组(syn,token 或 sum)构成的序列,其中 syn 为单词种别码,token 为存放的单词自身字符串,sum 为整型常数。 词法分析器的实现 词法分析器的实现...

      编译原理实验报告词法分析器语法分析器.doc

      2. 输入字符串的分析:在词法分析器中,需要逐个分析输入字符串,判断其是否为‘#’,若是则表示字符串输入分析完毕,结束分析程序,否则继续分析。 3. 字符的判断:在词法分析器中,需要判断输入字符是否为数字、...

      u3d ColourSwitch颜色切换源码

      此外,通过分析源码,我们可以学习到如何优化性能,减少内存占用,以及如何利用Unity的脚本系统(如C#)来编写高效、易维护的代码。 总的来说,对这个项目的源码进行研究,不仅能让我们掌握Unity 3D的基本开发技巧...

      Lua性能优化技巧

      通过性能分析器确定问题所在后,他们对字符串序列化过程进行了特别优化,使得性能得到了显著提升。 性能优化往往需要深入理解语言的内部机制。以Lua为例,语言的底层是虚拟机,代码运行前会被预编译成虚拟机指令...

      性能优化手册-202004版1

      此外,文档还提到了HashMap的遍历方式、switch语句的性能分析、if-else的优雅写法、GC优化、SQL编写建议、MySQL和Redis的性能优化实践等多方面的内容。这些都属于性能优化的重要组成部分。 对于HashMap,了解其遍历...

      C语言词法分析器可识别常数、字符、关键字等

      遇到以'或"开头的序列,它会将其视为字符串常数。 在实际的编译过程中,词法分析器通常会产生一个Token流,这个Token流接着会被语法分析器处理,构建出抽象语法树(Abstract Syntax Tree, AST),最终生成目标代码...

      Switchhosts_39881.zip

      这包括查看不同数据类型(如字符串、哈希、列表、集合和有序集合)以及搜索特定键。 2. **图形化操作**:通过图表和仪表板,用户可以直观地看到Redis实例的性能指标,如内存使用、CPU利用率、网络流量等。 3. **...

      MATLAB-实用教程-课后习题答案 (1).docx

      * 字符串数组:MATLAB 提供了char函数来创建字符串数组,如 `a = char('Picture', 'Pitch');`。 * 字符串匹配:MATLAB 提供了strfind函数来匹配字符串,如 `e = strfind(c, 'e');`。 五、其他知识点 * MATLAB 提供...

      编译原理:词法分析器实现(C)

      同时,词法分析器还需要处理字符串常量和注释的识别,这通常需要嵌套状态的处理。 在处理过程中,词法分析器需要维护一个当前字符的位置,以便在需要时回溯或前进。此外,为了存储和返回标记,我们可能需要设计一个...

      词法分析器C++版本

      8. **迭代器**:C++的迭代器可以方便地遍历字符或字符串,这对于构建词法分析器的扫描过程非常有用。 9. **设计模式**:例如,工厂模式可以用来生成不同类型的标记对象,访问者模式可以用来处理标记的后处理,如...

      引入缓存机制提升性能 提高PHP编程效率

      - 使用性能分析工具:利用Xdebug等工具监控和分析PHP程序的实际运行情况,找出瓶颈所在。 12. **缓存机制** - 引入缓存:通过缓存机制减少数据库的负担,例如使用memcached等内存缓存系统。这不仅可以加快数据...

      swift语言知识点便利贴

      switch语句在Swift中比以往语言中的switch更加强大,它不仅可以用于整数,还可以用于任何数据类型的值,包括字符串和元组。它能够根据不同的case执行不同的代码块,如果所有case都不匹配,则执行默认的default代码块...

      matlab编程和其他语言的区别.pdf

      字符串通常用单引号包围,如果需要在字符串内包含单引号,需使用两个单引号表示。例如: ```matlab a = 'this''is an apple' ``` 字符串连接通常使用中括号`[]`,而不是加号`+`,因为MATLAB中的字符串实际上是矩阵...

      Visual C++ 2005入门经典--源代码及课后练习答案

      4.1.4 字符数组和字符串处理 147 4.1.5 多维数组 150 4.2 间接数据存取 153 4.2.1 指针的概念 153 4.2.2 声明指针 154 4.2.3 使用指针 155 4.2.4 初始化指针 157 4.2.5 sizeof运算符 162 4.2.6 ...

      javascript的switch用法注意事项分析

      在上面的例子中,`t_jb51_net`是一个数字,而`'65'`是一个字符串,所以它们不相等,导致第一个`case`未执行。如果将`'65'`改为数字`65`,则会匹配成功,`alert`将被执行。 2. **缺失`break`**: 如果忘记在每个`...

      2011计算机二级考试C语言十套上机题汇总(5).pdf

      这篇文档是针对2011年计算机二级考试中C语言的部分上机试题,主要涉及到的是字符串处理和条件判断。在给定的代码片段中,任务是编写一个名为`fun`的函数,该函数用于统计输入字符串中元音字母(a, e, i, o, u)和...

      编译原理词法编译器

      5. **错误处理**:如果输入源码不符合预期格式,词法分析器需要能够检测并报告错误,比如非法字符、未闭合的字符串或注释等。 `要求.txt`文件可能包含了项目实施的具体需求和指导,如预期的功能、输入输出格式、...

    Global site tag (gtag.js) - Google Analytics