36 评论

Java 性能优化[2]:字符串过滤实战

  上一个帖子已经介绍了基本类型和引用类型的性能差异(主要是由于内存分配方式不同导致)。为了给列位看官加深印象,今天拿一个具体的例子来实地操作一把,看看优化的效果如何。


★一个简单的需求


  首先描述一下需求:
给定一个 String 对象,过滤掉除了数字(字符'0'到'9')以外的其它字符。要求时间开销尽可能小。过滤函数的原型如下:
String filter(String str);

  针对上述需求,俺写了5个不同的过滤函数。为了叙述方便,函数名分别定为 filter1 到 filter5。其中 filter1 性能最差、filter5 性能最好。在看后续的内容之前,你先暗自思考一下,如果由你来实现该函数,大概会写成什么样?最好把你想好的函数写下来,便于跟俺给出的例子作对比。


★代码——循序渐进的5种实现方式


◇测试代码


  为了方便测试性能,先准备好一坨测试代码,具体如下:

class Test
{
    public static void main(String[] args)
    {
        if(args.length != 1)
        {
            return;
        }

        String str = "";
        long nBegin = System.currentTimeMillis();
        for(int i=0; i<1024*1024; i++)
        {
            str = filterN(args[0]);  // 此处调用某个具体的过滤函数
        }
        long nEnd = System.currentTimeMillis();

        System.out.println(nEnd-nBegin);
        System.out.println(str);
    }
};

  在没有想好你的实现方式之前,先别偷看后续内容哦!另外,先注明一下,俺的 Java 环境是 JDK 1.5.0-09,使用的测试字符串是随机生成的,长度32个 char,只含字母和数字。由于 JDK 版本和机器性能不尽相同,你在自己机器上测试的结果可能跟俺下面给出的数值不太一样。

◇版本1


  先来揭晓性能最差的filter1,代码如下:
private static String filter1(String strOld)
{
    String strNew = new String();
    for(int i=0; i<strOld.length(); i++)
    {
        if('0'<=strOld.charAt(i) && strOld.charAt(i)<='9')
        {
            strNew += strOld.charAt(i);
        }
    }
    return strNew;
}

  如果你的代码不幸和 filter1 雷同,那你的 Java 功底可就是相当糟糕了,连字符串拼接需要用 StringBuffer 来优化都没搞明白。
  为了和后续对比,先记下 filter1 的处理时间,大约在 8.81-8.90秒 之间。

◇版本2


  再来看看 filter2,代码如下:
private static String filter2(String strOld)
{
    StringBuffer strNew = new StringBuffer();
    for(int i=0; i<strOld.length(); i++)
    {
        if('0'<=strOld.charAt(i) && strOld.charAt(i)<='9')
        {
            strNew.append(strOld.charAt(i));
        }
    }
    return strNew.toString();
}

  其实刚才在评价 filter1 的时候,已经泄露了 filter2 的天机。filter2 通过使用 StringBuffer 来优化连接字符串的性能。为什么 StringBuffer 连接字符串的性能比 String 好,这个已经是老生常谈,俺在这儿就不细说啦。尚不清楚的同学自己上 Google 一查便知。估计应该有挺多同学会写出类似 filter2 的代码。
  有些同学可能会问:为啥不用 StringBuilder?
  确实,在 JDK 1.5 新增加了 StringBuilder 这个类,其性能会比 StringBuffer 更好。不过捏,考虑到有可能要拿到其它版本的 JDK 上作对比测试,而且 StringBuilder 和 StringBuffer 之间的差异【不是】本文讨论的重点,所以后面的例子都使用 StringBuffer 来实现。
  filter2 的处理时间大约为 2.14-2.18秒,提升了大约4倍。

◇版本3


  接着看看 filter3,代码如下:
private static String filter3(String strOld)
{
    StringBuffer strNew = new StringBuffer();
    int nLen = strOld.length();
    for(int i=0; i<nLen; i++)
    {
        char ch = strOld.charAt(i);
        if('0'<=ch && ch<='9')
        {
            strNew.append(ch);
        }
    }
    return strNew.toString();
}

  乍一看,filter3 和 filter2 的代码差不多嘛!再仔细瞧一瞧,原来先把 strOld.charAt(i) 赋值给 char 变量,节省了重复调用 charAt() 方法的开销;另外把 strOld.length() 先保存为 nLen,也节省了重复调用 length() 的开销。能想到这一步的同学,估计是比较细心的。
  经过此一优化,处理时间节省为 1.48-1.52秒,提升了约30%。由于 charAt() 和 length() 的内部实现都挺简单的,所以提升的性能不太明显。
  另外补充一下,经网友反馈,在 JDK 1.6 上,filter3 和 filter2 的性能基本相同。俺估计:可能是因为 JDK 1.6 在编译时已经进行了相关的优化。

◇版本4


  然后看看 filter4,代码如下:
private static String filter4(String strOld)
{
    int nLen = strOld.length();
    StringBuffer strNew = new StringBuffer(nLen);
    for(int i=0; i<nLen; i++)
    {
        char ch = strOld.charAt(i);
        if('0'<=ch && ch<='9')
        {
            strNew.append(ch);
        }
    }
    return strNew.toString();
}

  filter4 和 filter3 差别也很小,唯一差别就在于调用了 StringBuffer 带参数的构造函数。通过 StringBuffer 的构造函数设置初始的容量大小,可以有效避免 append() 追加字符时重新分配内存,从而提高性能。
  filter4 的处理时间大约在 1.33-1.39秒,约提高10%左右。可惜提升的幅度有点小 :-(

◇版本5


  最后来看看“终极版本”——性能最好的 filter5。
private static String filter5(String strOld)
{
    int nLen = strOld.length();
    char[] chArray = new char[nLen];
    int nPos = 0;
    for(int i=0; i<nLen; i++)
    {
        char ch = strOld.charAt(i);
        if('0'<=ch && ch<='9')
        {
            chArray[nPos] = ch;
            nPos++;
        }
    }
    return new String(chArray, 0, nPos);
}

  猛一看,你可能会想:这个 filter5 和前几个版本的差别也忒大了吧!filter5 既没有用 String 也没有用 StringBuffer,而是拿字符数组进行中间处理。
  filter5 的处理时间,只用了0.72-0.78秒,相对于 filter4 提升了将近50%。为啥捏?是不是因为直接操作字符数组,节省了 append(char) 的调用?通过查看 append(char) 的源代码,内部的实现很简单,应该不至于提升这么多。
  那是什么原因捏?
  首先,虽然 filter5 有一个字符数组的创建开销,但是相对于 filter4 来说,StringBuffer 的构造函数内部也会有字符数组的创建开销。两相抵消。所以 filter5 比 filter4 还多节省了 StringBuffer 对象本身的创建开销。(在俺的 JDK 1.5 环境中,这个因素比较明显)
  其次,由于 StringBuffer 是线程安全的(它的方法都是 synchronized),因此调用它的方法有一定的同步开销,而字符数组则没有,这又是一个性能提升的地方。(经热心读者反馈,此因素在 JDK 1.6 中比较明显)
  基于上述两个因素,所以 filter5 比 filter4 又有较大幅度的提升。


★对于5个版本的总结


  上述5个版本,filter1 和 filter5 的性能相差约12倍(已经超过一个数量级)。除了 filter3 相对于 filter2 是通过消除函数重复调用来提升性能,其它的几个版本都是通过节省内存分配,降低了时间开销。可见内存分配对于性能的影响有多大啊!如果你是看了上一个帖子才写出 filter4 或者 filter5,那说明你已经领会了个中奥妙,俺那个帖子也就没白写了。


★一点补充说明,关于时间和空间的平衡


  另外,需要补充说明一下。版本4和版本5使用了空间换时间的手法来提升性能。假如被过滤的字符串【很大】,并且数字字符的比例【很低】,这种方式就不太合算了。
  举个例子:被处理的字符串中,绝大部分都只含有不到10%的数字字符,只有少数字符串包含较多的数字字符。这时候该怎么办捏?
  对于 filter4 来说,可以把 new StringBuffer(nLen); 修改为 new StringBuffer(nLen/10); 来节约空间开销。但是 filter5 就没法这么玩了。
  所以,具体该用“版本4”还是“版本5”,要看具体情况了。只有在你【非常】看重时间开销,且数字字符比例很高(至少大于50%)的情况下,用 filter5 才合算。否则的话,建议用 filter4。

  下一个帖子,打算介绍一下“关于垃圾回收(GC)”的话题。


回到本系列的目录
版权声明
本博客所有的原创文章,作者皆保留版权。转载必须包含本声明,保持本文完整,并以超链接形式注明作者编程随想和本文原始地址:
https://program-think.blogspot.com/2009/03/java-performance-tuning-2-string.html?m=0

36 条评论

  1. 写得不错,看过后有收获呢
    继续关注后边的文章

    回复删除
  2. "另外把strOld.length()先保存为nLen,也节省了重复调用length()的开销。"
    好像编译器会优化捏?不过还是不能太依赖 是不 O(∩_∩)O
    lz 好像很全能 管理 设计 编程

    回复删除
  3. 楼上的同学,
    其实length()开销不大。如果不是对性能很敏感,直接写在for里面,问题也不大。
    另外,感谢你的夸奖,“全能”不敢当。

    回复删除
  4. (1) String result = "hello" + " world";
    (2) StringBuffer result = new String().append("hello").append(" world");
    楼主觉得这两个哪个效率高呢?

    回复删除
  5. 楼上的同学,
    这个问题问得好。这正是我后面的帖子打算讨论的话题 :-)
    我先简单提一下:String result = "hello" + " world";并不是真正的字符串拼接,实际上编译时就已经变成"hello world"。

    回复删除
  6. :-)还是依然感谢楼主这么无私的一直写的如此勤快,很有帮组,还特别感谢在我困惑时对我的建议

    回复删除
  7. 很好很强大,俺先看了1,还自己写了例子,才来看2的。

    回复删除
  8. 按理说filter2到filter3的优化是编译技术中最基本的优化,一般编译器都会做的啊(或者JVM)。我机器上是jdk1.6,试了一下,filter3的测试结果要比2慢几十毫秒。

    另外如果不需要考虑线程安全的话,使用StringBuilder替换StringBuffer的版本倒是可以将执行时间缩短到 1/3

    回复删除
  9. 楼上的同学,
    估计是JDK 1.6作了优化,而JDK 1.5没有做。
    不过版本2和版本3之间的差异不是本文讨论的重点,所以我没有再深入探讨。

    回复删除
  10. StringBuffer可以替换成StringBuilder,StringBuffer多了个同步开销。

    回复删除
  11. 测试了下,换成了StringBuilder后,时间减少了一半,但是还是比直接用char数组稍慢

    回复删除
  12. StringBuilder确实比StringBuffer快,当初考虑到会在不同版本间做对比测试,所以还是用StringBuffer。它们两者在内存分配上是类似的,性能的差别主要在于线程安全方面。

    回复删除
  13. “那是什么原因捏?
      虽然filter5有一个字符数组的创建开销,但是相对于filter4来说,StringBuffer的构造函数内部也会有字符数组的创建开销。两相抵消。所以filter5比filter4还多节省了StringBuffer对象本省的创建开销。所以节约了性能。”
    感觉上面这一条并不正确,filter4与filter5性能差别的主要原因应该是filter4方法中StringBuffer同步开销很大所致。

    回复删除
  14. 楼上的同学,
    我在相同的环境下,把filter4改用StringBuilder,测试了一下,大概耗时1.15-1.20秒。性能相比StringBuffer约提升了0.2秒。
    而使用数组的filter5大概耗时0.72-0.78秒,比StringBuilder提升了约0.4秒。数组和StringBuilder之间的差异主要是由内存分配造成。
    所以,同步开销带来的性能影响(0.2秒)应该不如内存分配带来的影响(0.4秒)。
    不过JDK 1.6或许会不一样。我有空的话用JDK 1.6再测试一下。

    回复删除
  15. 我是用JDK1.6测试的:
    filter4用时大约2.5秒,将其中的StringBuffer改成StringBuilder以后用时0.67秒,filter5用时大约0.46秒。
    我的机器是双核的,可能不同的机器不同的版本都有较大的区别 从我的测试结果看,感觉是同步开销使得filter4差别那么大的。
    楼主这篇文章对优化有很好的引导作用,十分感谢。

    回复删除
  16. 不同机器、不同版本之间的差异比较明显:我用JBuilder2006下的JDK1.5进行了测试:filter4用时还是2.5秒,改为StringBuilder后耗时0.95秒,filter5用时0.67秒。从生成的字节码也看出不同版本生成的字节码也有不同。

    回复删除
  17. 楼上的同学,
    看来某些情况下,有可能同步开销造成的差异大于内存分配的差异,我在原文中补充说明一下。

    回复删除
  18. 非常非常的好谢谢!!!!!!!!!!!

    回复删除
  19. 从字符串提出所有数字的需求是怎个上下文呢?
    在我的机器上一百万次的差别在100毫秒, 我想这算不上什么优化.
    如果是为了提出连续的数字, 我宁愿用/[0-9]+/.test(string)这么简单的做法.

    回复删除
  20. 楼上的同学,
    这个例子只要是用来说明内存分配对性能的影响。不过实际工作中也会碰到类似的例子,比如过滤掉字符串中的某些字符。如果对性能比较敏感,用正则不一定合适。假如被过滤的不是字符串,而是非char类型的某种集合,那正则可能也帮不上忙。
    另外,不知道你所说的“一百万次的差别在100毫秒”,是指哪两个版本之间的对比?

    回复删除
  21. 原来JAVA代码也可以如此优化 优化效果也这么明显 赞LZ ^_^

    回复删除
  22. 我像前辈们学习啊

    回复删除
  23. 这是我第一次写的:
    public static String filter_0(String input) {
    if (input == null) {
    return "";
    }
    StringBuffer out_buffer = new StringBuffer();
    char[] input_chars = input.toCharArray();
    for (int i = 0; i < input_chars.length; i ++) {
    if (input_chars[i] >= 48 && input_chars[i] < 58) {
    out_buffer.append(input_chars[i]);
    }
    }

    return out_buffer.toString();
    }
    输出为:
    1125 (大概为1.125秒)
    1867833672165189614000
    经过你的提示,这是我优化后的:
    public static String filter_1(String input) {
    if (input == null) {
    return "";
    }
    char[] chars = input.toCharArray();
    int pos = 0;
    for (int i = 0; i < chars.length; i ++) {
    if (chars[i] >= 48 && chars[i] < 58) {
    chars[pos++] = chars[i];
    }
    }

    return new String(chars, 0, pos);
    }
    输出为:
    531 大概为0.531秒
    1867833672165189614000

    回复删除
  24. 补充,我的两个filter是在jdk6.5下面做的

    还有我惊奇的发现,我的filter2加了下面这个判断后,反而快了几十毫秒,不知为何。
    if (input == null) {
    return "";
    }

    回复删除
  25. 楼上的同学,
    感觉加了这个判断,应该对结果影响非常小。
    “快了几十毫秒”会不会是随机误差?你多测试几次看看。

    回复删除
  26. 下面是测试记录,单位:毫秒
    filter_1()执行次数为:10 * 1024 * 1024
    加了判断: 5187, 5203, 5172, 5188, 5235
    没有加判断:5625, 5719, 5703, 5672, 5687
    感觉虽然对结果的影响非常小,还是有影响的...
    困惑的是,从直觉上来讲,少了一次判断,应该更快才对,可是测试结果却跟直觉相反

    回复删除
  27. 如果排除了随机误差,你试试看用Java反编译器对两个class文件处理一下,看反编译出来的源代码有什么差别?

    回复删除
  28. Good article, but I still see the room for improvement:

    In版本5, change
    if('0'<=ch && ch<='9')
    to
    if (! (ch >'9' || ch <'0'))

    we may reduce total number of the loop and buy some time, partially when the size of original string is BIG!

    回复删除
  29. 关于第五个版本比第四个版本更快的主要原因,并不在于创建stringbuffer对象上(当然这个也是一个原因),更主要的在于第四个版本每次在append的时候,都会判定当前分配的char是否已经满了,如果满了,会重新new一个新的char数组,并进行一次内存的拷贝。经过测试,Stringbuffer(我用的stringbuilder)的创建消耗相对而言可以忽略~~

    回复删除
    回复
    1. 你可能没仔细看 版本3 和 版本4 的差异。

      版本4 相比 版本3,仅仅多了一个 StringBuffer 的构造函数参数。
      这样一来,版本4 的 StringBuffer 就会在构造时事先分配足够的内存。
      所以 版本4 在每次 append 的时候不会再重分配内存,也不会进行内存拷贝。

      你说的内存分配和内存拷贝导致的性能差异,是发生在 版本3 和 版本5 之间的。
      版本4 不存在此问题。

      删除
  30. 09年的帖啦,现在才看到,T..T,用jdk1.7.0小测了下,发现以上结论基本成立,除了filter3提升不明显,偶尔甚至比filter2还慢。于是,对filter3中的优化作了调整,如filter32:
    private static String filter32(String strOld)
    {
    StringBuffer strNew = new StringBuffer();
    //int nLen = strOld.length();

    for(int i=0; i<strOld.length(); i++)
    {

    char ch = strOld.charAt(i);
    if('0'<=ch && ch<='9')
    {
    strNew.append(ch);
    }
    }
    return strNew.toString();
    }
    测试结果显示,filter32明显优于filter2和filter3,怀疑是否因为filter3中重复创建局部变量int的时间开销已超出重复调用length()的时间开销,以至于吃力不讨好? 或者是jdk1.7优化的其他原因

    测试结果示例:
    F2:1090-1099
    F3:1073-1084
    F32:1057-1066

    回复删除
    回复
    1. 俺猜测
      有可能在 JDK 1.7 里面,对 String.length() 的调用已经在编译时优化掉了。
      所以用局部变量先保存长度,没有提升。

      你的测试数据中,F32 和 F3 其实很接近(百分比的差异)
      说明在 JDK 1.7 里面,两种写法差异不大。

      另,
      对比当年俺用 JDk 1.5 的测试数据。
      看来 JDK 后续的版本在编译优化方面,有提升。

      删除
  31. java8 都出来了 这个系列还没有结束。。。。

    回复删除
  32. 正则表达式也可以过滤么

    回复删除
  33. LZ不错,上马治国评天下,下马编程写程序,哈哈!!

    回复删除