谜之 Loop 性能优化

本贴最后更新于 2737 天前,其中的信息可能已经天翻地覆

背景

大家都知道,在写循环语句时有个优化技巧就是将条件计算尽量放到循环外部,避免每次循环时触发不必要的调用和计算,比如将

for (int i = 0; i < s.length(); i++) {
    // ....
}

优化为:

int len = s.length();
for (int i = 0; i < len; i++) {
    // ....
}

问题

有了以上的优化技巧, 你对下面代码的执行结果预期是 innerLen 更快还是 outerLen 更快呢?

package test;

import java.util.HashSet;
import java.util.Set;

public class Loop {

    public static void main(String[] args) throws Exception {
        String str = "dummy";

        for (int i = 0; i < 25; i++) {
            str += str;
        }

        System.out.println("len: " + str.length());

        System.out.print("inner: ");
        final long startInner = System.currentTimeMillis();
        innerLen(str);
        System.out.println(System.currentTimeMillis() - startInner);

        System.out.print("outer: ");
        final long startOuter = System.currentTimeMillis();
        outerLen(str);
        System.out.println(System.currentTimeMillis() - startOuter);
    }

    public static void outerLen(final String s) {
        final Set<String> set = new HashSet<>();

        final int len = s.length();
        for (int i = 0; i < len; i++) {
            set.add("i");
        }
    }

    public static void innerLen(final String s) {
        final Set<String> set = new HashSet<>();

        for (int i = 0; i < s.length(); i++) {
            set.add("i");
        }
    }
}

如果你也得到和我类似的结果(inner 更快):

len: 167772160
inner: 352
outer: 480

握个爪先,我们来分析分析。

反汇编

因为 JVM 的强大,很多时候我们都会觉得:“是不是编译器偷偷做了什么优化导致结果反常?”带着这个疑问,我们就先看下字节码文件反汇编出来的结果:

C:\Users\s\Documents\NetBeansProjects\Test\build\classes>javap -c test\Loop.class
Compiled from "Loop.java"
public class test.Loop {
  public test.Loop();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public static void main(java.lang.String[]) throws java.lang.Exception;
    Code:
       略过

  public static void outerLen(java.lang.String);
    Code:
       0: new           #19                 // class java/util/HashSet
       3: dup
       4: invokespecial #20                 // Method java/util/HashSet."<init>":()V
       7: astore_1
       8: aload_0
       9: invokevirtual #9                  // Method java/lang/String.length:()I
      12: istore_2                          // len 结果保存在变量 2 中
      13: iconst_0                          // 将整型值 0 入栈
      14: istore_3                          // 出栈并存入变量 3 中
      15: iload_3                           // 载入变量 3(循环开始,i = 0)
      16: iload_2                           // 载入变量 2,即 len
      17: if_icmpge     35                  // 变量 3 大于等于变量 2 的话跳到 35(结束循环) 
      20: aload_1                            
      21: ldc           #21                 // String i
      23: invokeinterface #22,  2           // InterfaceMethod java/util/Set.add:(Ljava/lang/Object;)Z
      28: pop
      29: iinc          3, 1                // 变量 3 自加 1
      32: goto          15
      35: return

  public static void innerLen(java.lang.String);
    Code:
       0: new           #19                 // class java/util/HashSet
       3: dup
       4: invokespecial #20                 // Method java/util/HashSet."<init>":()V
       7: astore_1
       8: iconst_0
       9: istore_2
      10: iload_2
      11: aload_0
      12: invokevirtual #9                  // Method java/lang/String.length:()I
      15: if_icmpge     33
      18: aload_1
      19: ldc           #21                 // String i
      21: invokeinterface #22,  2           // InterfaceMethod java/util/Set.add:(Ljava/lang/Object;)Z
      26: pop
      27: iinc          2, 1
      30: goto          10
      33: return
}

outerLen 的 15-32 是循环部分,innerLen 的 10-30 是循环部分。我们可以清晰看到 innerLen 在循环中调用了 String#length() 方法,所以理论上它的耗时是会更多的。

那为什么还会出现 innerLen 耗时更短的现象呢?

更多的测试

编译器永远是对的,代码也没看出来问题,那就是测试方式不对了?

加入多种测试方式并记录结果:

  • 重复 10 次运行,发现全部都是 innerLen

  • 通过调换 outerLeninnerLen 执行顺序(让 outerLen 先跑),我们发现结果逆转了,outerLen 终于符合预期,更快了

  • 同一次运行中加入重复次数

    for (int i = 0; i < 10; i++) {
        System.out.print("inner: ");
        long startInner = System.currentTimeMillis();
        innerLen(str);
        System.out.println(System.currentTimeMillis() - startInner);
    
        System.out.print("outer: ");
        long startOuter = System.currentTimeMillis();
        outerLen(str);
        System.out.println(System.currentTimeMillis() - startOuter);
    
        System.out.println("----");
    }
    

    发现除了第一次是 innerLen 快,其余 9 次均是 outerLen 快,这 9 次符合预期

看来问题是因为 JVM 某种“动态”因素决定的,这个因素很可能和 GC 有关。

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖 • 1 关注
  • 性能
    62 引用 • 180 回帖
  • GC
    17 引用 • 45 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • senowang

    /**
    * Constructs a new, empty set; the backing HashMap instance has
    * the specified initial capacity and default load factor (0.75). * * @param initialCapacity the initial capacity of the hash table
    * @throws IllegalArgumentException if the initial capacity is less
    * than zero */public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
    }
    @88250 你不会说 map 也不扩容吧。

    1 回复
  • 其他回帖
  • 88250

    我这里的结果:

    len: 167772160
    inner: 341
    outer: 499
    

    并且如果调换一下顺序,让 outer 先执行,那么就会变成 outer 更快,难道是后者会发生 gc 而耗时更长?

    2 回复
  • flhuoshan

    outerLen 这么改就对了

    public static void outerLen(final String s,final int len) {
            final Set<String> set = new HashSet<>();
            for (int i = 0; i < len; i++) {
                set.add("i");
            }
    }
    
  • senowang

    @88250
    public static void innerLen1(String s) {
    Set set = new HashSet<>();
    for (int i = 0,length=s.length(); i < length; i++) {
    set.add("i");
    }
    }
    我发现这样更快
    len: 167772160
    outer: 1184
    inner: 1064
    inner1: 956

    1 回复
  • 查看全部回帖