Hiệu suất của ArrayList

Question

Tôi đã cố gắng để thấy sự khác biệt hiệu suất giữa trước khi khởi tạo một ArrayList đến một khả năng nhất định vs đi với khả năng mặc định và mở rộng theo yêu cầu. Chỉ tò mò thôi. Tôi thấy rằng mã mảng dung lượng mặc định là ~ 10% FASTER so với mã khởi tạo mảng với công suất được yêu cầu. Đây là mã tôi đã sử dụng:

public class Test { 
    public static void main(String[] args) { 

     long t1 = System.currentTimeMillis(); 
     for(int j=0;j<10;++j) { 
      List<Integer> list = new ArrayList<Integer>(); 
      for(int i=0;i<1000000;++i) { 
       list.add(i); 
      } 
     } 
     long t2 = System.currentTimeMillis(); 
     System.out.println("Time taken: " + (t2-t1)/10.0); 
    } 
} 

tôi luôn có được ~ 77 ms cho phiên bản này trên hộp của tôi, trong khi tôi nhận được ~ 85 ms nếu tôi thay đổi danh sách khởi tạo để new ArrayList<Integer>(1000000). Tại sao nó như vậy? Nó không phải là cách khác vòng? Trong thực tế, Danh sách không có tiền tố init luôn nhỏ hơn một chút (~ 0,5-1 ms) nhanh hơn so với sử dụng đồng bằng Integer[]. Về cơ bản, những gì nó nói là default capacity arraylist > simple array > pre-capacity-ensured arraylist trong hiệu suất chèn.

Điều này rất lạ đối với tôi. Đoán ban đầu của tôi là nó có cái gì đó để làm với phân bổ bộ nhớ, một cái gì đó giống như cho 1000000 khối int trong một đi là có thể chậm hơn so với từ từ nhận được nhiều không gian hơn? Điều này thậm chí có thể tái sản xuất trong các máy khác? Tôi đang sử dụng jdk 1.6.0, Mac OS X, chạy qua nhật thực.

Tôi đã thử trong hai môi trường khác: -> Đã thử chạy java + javac từ dòng lệnh thay vì nhật thực - Ở đây tôi nhận được pre-capacity-ensured arraylist > simple array > default capacity arraylist, nhất quán.

-> Đã thử chạy java + javac trên máy tính để bàn Linux (RHEL) của tôi. Hộp này có RAM 24 GB, trong khi máy tính xách tay của tôi chỉ có 8 GB. Ở đây, tôi nhận được plain array >>> default capacity arraylist > pre-capacity-ensured arraylist. Mảng đồng bằng là siêu nhanh, nhanh hơn khoảng 2-3 lần trong trường hợp này so với hai loại còn lại.

EDIT: Sau @ đề nghị JonSkeet của trong các ý kiến, tôi đã sử dụng nanoTime(), và Integer thay vì int. Nó vẫn không giải quyết vấn đề mà JIT hâm nóng không được xem xét mặc dù. Sau những thay đổi này, tôi nhất quán thấy rằng mảng đồng bằng là nhanh nhất trong tất cả các thử nghiệm. Nhưng danh sách đảm bảo dung lượng vẫn chậm hơn khoảng 5-10% so với danh sách dung lượng mặc định cho tôi trên tất cả 3 môi trường ở trên. NHƯNG một số người dùng dường như có được hành vi chính xác, vì vậy đây có thể là một trường hợp rất cụ thể.

EDIT2: Nếu tôi sử dụng String thay vì Integer làm phần tử, hành vi là chính xác (plain array > pre-capacity-ensured arraylist > default capacity array). Vì vậy, tôi nghĩ autoboxing thực sự là thủ phạm.

Answer 1

Tôi đã thử nghiệm với điều này một chút, và kết luận của tôi là điểm chuẩn của bạn là thiếu sót. Khi tôi khắc phục các vấn đề rõ ràng nhất, tôi nhận được các kết quả khác nhau đáng kể. Thời gian của tôi như sau:

 
default list: 74ms 
pre-sized list: 54ms 
Integer array: 42ms 
int array: 9ms 

Lưu ý rằng đây là đơn vị mili giây. Mã của bạn thực hiện các phép đo trong hàng chục mili giây: (t2-t1)/10.0.

Để tham khảo, các mã tôi đã sử dụng như sau:

public class Clazz { 

    static final int N = 1000000; 

    interface Test { 
     void test(); 
    } 
    static final class DfltListTest implements Test { 
     public void test() { 
      for (int j = 0; j < 10; ++j) { 
       List<Integer> list = new ArrayList<Integer>(); 
       for (int i = 0; i < N; ++i) { 
        list.add(i); 
       } 
      } 
     } 
    } 
    static final class SizedListTest implements Test { 
     public void test() { 
      for (int j = 0; j < 10; ++j) { 
       List<Integer> list = new ArrayList<Integer>(N); 
       for (int i = 0; i < N; ++i) { 
        list.add(i); 
       } 
      } 
     } 
    } 
    static final class IntegerArrayTest implements Test { 
     public void test() { 
      for (int j = 0; j < 10; ++j) { 
       Integer[] arr = new Integer[N]; 
       for (int i = 0; i < N; ++i) { 
        arr[i] = i; 
       } 
      } 
     } 
    } 
    static final class IntArrayTest implements Test { 
     public void test() { 
      for (int j = 0; j < 10; ++j) { 
       int[] arr = new int[N]; 
       for (int i = 0; i < N; ++i) { 
        arr[i] = i; 
       } 
      } 
     } 
    } 

    static void test(Test t, String name) { 
     final int iter = 11; 
     final long timings[] = new long[iter]; 
     for (int k = 0; k < iter; ++k) { 
      long t1 = System.currentTimeMillis(); 
      t.test(); 
      long t2 = System.currentTimeMillis(); 
      timings[k] = t2 - t1; 
      System.gc(); 
     } 
     Arrays.sort(timings); 
     System.out.printf("%s: %dms\n", name, timings[iter/2]); 
    } 

    public static void main(String[] args) { 
     for (int i = 0; i < 5; ++i) { 
      test(new DfltListTest(), "default list"); 
      test(new SizedListTest(), "pre-sized list"); 
      test(new IntegerArrayTest(), "Integer array"); 
      test(new IntArrayTest(), "int array"); 
     } 
    } 
} 

Tôi đã thử nghiệm nó sử dụng Java 1.7.0_09 với -XX:+AggressiveOpts -XX:CompileThreshold=1.

Khi tôi thử nghiệm cùng một mã bằng cách sử dụng Java 6, thứ hạng giống nhau, nhưng sự khác biệt giữa danh sách mặc định và danh sách có kích thước trước là quan trọng hơn nhiều. Tôi đã không cố gắng để hiểu những gì nó là về Java 7 mà làm cho sự khác biệt nhỏ hơn rất nhiều.

Đối với một số gợi ý về cách mã Java benchmark, xem How do I write a correct micro-benchmark in Java?

Answer 2

Hãy làm thí nghiệm này, đo thời gian cần thiết cho một đơn add(), trên danh sách các khả năng khác nhau

 ArrayList<Integer> list = new ArrayList<Integer>(N); 
     for(int i=0;i<N;++i) 
      list.add(new Integer(i)); // how many ns does this take? 

Trên máy tính của tôi

 N  ns per add(new) 

    32000  10 
    64000  10 
    128000  10 
    256000  10 
    512000  11 
1024000  11 
2048000  11 
4096000  15 
8192000  48 
16384000  132 
    1000  23 
    2000  13 
    4000  11 
    8000  11 
    16000  11 
    32000  10 

Dường như nhanh hơn rất nhiều khi điền vào 4 danh sách có dung lượng 2M hơn để điền 1 danh sách có dung lượng 8M.

Điều này cho thấy rằng những gì bạn đã quan sát là có thể - khi danh sách bắt đầu với dung lượng nhỏ, mọi thứ chạy nhanh hơn và thời gian được lưu nhiều hơn chi phí sao chép sau này.

Nhưng tại sao nó trở nên chậm hơn khi tăng công suất? Tôi không chắc. Có lẽ nó có liên quan đến bộ đệm L2. Có lẽ JVM có nhiều chi phí hơn trong việc phân bổ các mảng lớn hơn.

---

mã kiểm tra:

static void test(int N) 
{ 
    long t0 = System.nanoTime(); 
    long x = 0; 
    long t = 0; 
    while(true) 
    { 
     ArrayList<Integer> list = new ArrayList<Integer>(N); 
     for(int i=0;i<N;++i) 
      list.add(new Integer(i)); 

     t = System.nanoTime()-t0; 
     x+=N; 

     if(t>1000_000_000) 
      break; 
    } 

    System.out.printf("%8s\t%4s%n", N, t/x); 
} 

public static void main(String[] args) 
{ 
    while(true) 
     for(int N=1000; N<20_000_000; N*=2) 
      test(N); 
}