ArrayList

Question

का प्रदर्शन मैं ArrayList को पूर्व निर्धारित करने के लिए प्रदर्शन क्षमता को देखने की कोशिश कर रहा था, जो डिफ़ॉल्ट क्षमता के साथ चल रहा था और आवश्यकता पर विस्तार कर रहा था। जिज्ञासा के कारण। मैंने पाया कि डिफ़ॉल्ट क्षमता सरणी कोड कोड की तुलना में ~ 10% तेजी से है जो आवश्यक क्षमता के लिए सरणी शुरू करता है। जबकि मैं ~ 85 एमएस मिल अगर मैं new ArrayList<Integer>(1000000) सूची प्रारंभ बदलने के लिए,

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); 
    } 
} 

मैं लगातार मेरी बॉक्स पर इस संस्करण के लिए 77 एमएस मिल ~: यहाँ कोड मैं प्रयोग किया जाता है। ऐसा क्यों है? क्या यह दूसरा रास्ता नहीं होना चाहिए? वास्तव में, प्री-इनिट के बिना सूची सादा Integer[] का उपयोग करने से लगातार एक छोटा सा (~ 0.5-1 एमएस) तेज है। मूल रूप से, यह कहता है कि default capacity arraylist > simple array > pre-capacity-ensured arraylist सम्मिलित प्रदर्शन में क्या है।

यह मेरे लिए बहुत अजीब है। मेरा प्रारंभिक अनुमान यह है कि इसमें स्मृति आवंटन के साथ कुछ करना है, एक बार में 1000000 इंट ब्लॉक देने जैसी कुछ धीमी गति से अधिक जगह हो रही है? क्या यह अन्य मशीनों में भी पुनरुत्पादित है? मैं jdk 1.6.0, मैक ओएस एक्स का उपयोग कर रहा हूं, ग्रहण के माध्यम से चल रहा हूं।

मैंने इसे दो अन्य वातावरण में आजमाया: -> ग्रहण के बजाए कमांड लाइन से जावा + जावैक चलाने का प्रयास किया - यहां मुझे लगातार pre-capacity-ensured arraylist > simple array > default capacity arraylist मिल गया है।

-> मेरे लिनक्स (आरएचईएल) डेस्कटॉप पर जावा + जावैक चलाने का प्रयास किया। इस बॉक्स में 24 जीबी रैम है, जबकि मेरे लैपटॉप में केवल 8 जीबी थी। यहां, मुझे plain array >>> default capacity arraylist > pre-capacity-ensured arraylist मिल गया है। सादा सरणी सुपर-फास्ट है, इस मामले में अन्य दो की तुलना में 2-3x तेज है।

संपादित: टिप्पणी में @ JonSkeet के सुझाव के बाद, मैं nanoTime(), और Integer बजाय int इस्तेमाल किया। यह अभी भी इस मुद्दे को संबोधित नहीं करता है कि हालांकि जेआईटी गर्मजोशी पर विचार नहीं किया जा रहा है। इन परिवर्तनों के बाद, मैं लगातार देखता हूं कि सादे सरणी सभी परीक्षणों में सबसे तेज है। लेकिन उपरोक्त सभी 3 वातावरणों में मेरे लिए डिफ़ॉल्ट-क्षमता सूची की तुलना में क्षमता-सुनिश्चित सूची अभी भी 5-10% धीमी है। लेकिन कुछ उपयोगकर्ताओं को सही व्यवहार मिल रहा है, इसलिए यह एक बहुत ही विशिष्ट मामला हो सकता है।

EDIT2: यदि मैं तत्व के रूप में इंटीजर की बजाय स्ट्रिंग का उपयोग करता हूं, तो व्यवहार सही है (plain array > pre-capacity-ensured arraylist > default capacity array)। तो मुझे लगता है कि autoboxing वास्तव में अपराधी है।

Answer 1

मैंने इसका थोड़ा सा प्रयोग किया है, और मेरा निष्कर्ष यह है कि आपका बेंचमार्क त्रुटिपूर्ण है। जब मैं सबसे स्पष्ट मुद्दों को ठीक करता हूं, तो मुझे नाटकीय रूप से अलग-अलग परिणाम मिलते हैं। मेरे समय इस प्रकार हैं:

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

ध्यान दें कि ये मिलीसेकंड की इकाइयों में हैं। आपका कोड दस मिलीसेकंड: (t2-t1)/10.0 में माप करता है।

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"); 
     } 
    } 
} 

मैं -XX:+AggressiveOpts -XX:CompileThreshold=1 साथ जावा 1.7.0_09 का उपयोग कर जाँच की है:

संदर्भ के लिए, कोड मैं का उपयोग किया है इस प्रकार है।

जब मैंने जावा 6 का उपयोग करके एक ही कोड का परीक्षण किया, तो रैंकिंग समान थी, लेकिन डिफ़ॉल्ट सूची और पूर्व-आकार की सूची के बीच का अंतर बहुत महत्वपूर्ण था। मैंने यह समझने का प्रयास नहीं किया कि यह जावा 7 के बारे में क्या है जो अंतर को इतना छोटा बनाता है।

कैसे बेंचमार्क जावा कोड के लिए पर कुछ संकेत के लिए

, देख How do I write a correct micro-benchmark in Java?

Answer 2

के इस प्रयोग करते हैं, समय यह एक एकल add() के लिए ले जाता है को मापने, अलग क्षमता

 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? 

मेरी मशीन पर की सूची पर

 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 

जाहिर है क्षमता 8 एम के साथ 1 सूची भरने की तुलना में क्षमता 2 एम के साथ 4 सूचियों को भरने के लिए यह बहुत तेज है।

यह बताता है कि जो आपने देखा है वह संभव है - जब सूची छोटी क्षमता से शुरू होती है, चीजें तेजी से चलती हैं, और सहेजा गया समय सरणी प्रतिलिपि के बाद के ओवरहेड से अधिक होता है।

लेकिन क्षमता बढ़ने पर यह धीमी क्यों हो जाती है? मुझे यकीन नहीं है। शायद यह एल 2 कैश के साथ कुछ करने के लिए है। शायद बड़े एरे आवंटित करने में जेवीएम में अधिक ओवरहेड है।

---

परीक्षण कोड:

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); 
}