java - Vector 的填充时间比 ArrayList 少

Question

我正在阅读以下文章:

Understanding Collections and Thread Safety in Java

文章说:

You know, Vector and Hashtable are the two collections exist early in Java history, and they are designed for thread-safe from the start (if you have chance to look at their source code, you will see their methods are all synchronized!). However, they quickly expose poor performance in multi-threaded programs. As you may know, synchronization requires locks which always take time to monitor, and that reduces the performance.

[我还使用 Caliper 进行了基准测试；请听我说完]

还提供了示例代码:

public class CollectionsThreadSafeTest {

    public void testVector() {
        long startTime = System.currentTimeMillis();

        Vector<Integer> vector = new Vector<>();
        for (int i = 0; i < 10_000_000; i++) {
            vector.addElement(i);
        }

        long endTime = System.currentTimeMillis();
        long totalTime = endTime - startTime;
        System.out.println("Test Vector: " + totalTime + " ms");
    }

    public void testArrayList() {
        long startTime = System.currentTimeMillis();

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10_000_000; i++) {
            list.add(i);
        }

        long endTime = System.currentTimeMillis();
        long totalTime = endTime - startTime;
        System.out.println("Test ArrayList: " + totalTime + " ms");
    }

    public static void main(String[] args) {
        CollectionsThreadSafeTest tester = new CollectionsThreadSafeTest();

        tester.testVector();
        tester.testArrayList();
    }
}

他们为上述代码提供的输出如下:

Test Vector: 9266 ms
Test ArrayList: 4588 ms

但是当我在我的机器上运行它时，它给出了以下结果:

Test Vector: 521 ms
Test ArrayList: 2273 ms

我发现这很奇怪。我认为进行微基准测试会更好。因此，我使用卡尺为上述内容编写了一个基准测试。代码如下:

public class CollectionsThreadSafeTest extends SimpleBenchmark {

    public static final int ELEMENTS = 10_000_000;

    public void timeVector(int reps) {
        for (int i = 0; i < reps; i++) {
            Vector<Integer> vector = new Vector<>();
            for (int k = 0; k < ELEMENTS; k++) {
                vector.addElement(k);
            }
        }
    }

    public void timeArrayList(int reps) {
        for (int i = 0; i < reps; i++) {
            List<Integer> list = new ArrayList<>();
            for (int k = 0; k < ELEMENTS; k++) {
                list.add(k);
            }
        }
    }

    public static void main(String[] args) {
        String[] classesToTest = { CollectionsThreadSafeTest.class.getName() };
        Runner.main(classesToTest);
    }
}

但我得到了类似的结果:

 0% Scenario{vm=java, trial=0, benchmark=ArrayList} 111684174.60 ns; ?=18060504.25 ns @ 10 trials
50% Scenario{vm=java, trial=0, benchmark=Vector} 67701359.18 ns; ?=17924728.23 ns @ 10 trials

benchmark    ms linear runtime
ArrayList 111.7 ==============================
   Vector  67.7 ==================

vm: java
trial: 0

我有点困惑。这里发生了什么？我在这里做错了什么吗(这真的很尴尬)？

如果这是预期的行为，那么这背后的解释是什么？

---

更新#1

阅读后@Kayaman的answer ，我通过更改 Vector 和 ArrayList 的初始容量值来运行卡尺测试。以下是时间(以毫秒为单位):

Initial Capacity    Vector  ArrayList
-------------------------------------
10_000_000          49.2    67.1
10_000_001          48.9    71.2
10_000_010          48.1    61.2
10_000_100          43.9    70.1
10_001_000          45.6    70.6
10_010_000          44.8    68.0
10_100_000          52.8    64.6
11_000_000          52.7    71.7
20_000_000          74.0    51.8
-------------------------------------

感谢您的所有投入:)

Answer 1

您并没有真正在此处测试 add() 方法。您正在测试 Vector 和 ArrayList 增长的不同方式。 Vector 填满时大小会加倍，但 ArrayList 有一些更精细的逻辑来防止内部数组呈指数增长并浪费内存。

如果您使用两个类的初始容量 > 10000000 来运行测试，则它们不需要调整大小，您只需分析添加部分。