तुलनात्मक के माध्यम से जावा सॉर्ट <T> तुलना में अपने अधिकांश समय (ऑब्जेक्ट, ऑब्जेक्ट)

Question

में हमारे कोड आधार को प्रोफाइल करते समय मैंने कुछ अजीब देखा। ऐसा लगता है कि एक टाइप किए गए तुलनित्र के साथ सॉर्टिंग (उदा। Comparator<MyClass>) हमेशा पहले एक विधि Comparator<MyClass>.compare(Object,Object) कहा जाता है जिसे तब विधि Comparator<MyClass>.compare(MyClass,MyClass) कहा जाता है। इसके अलावा, उस समय का विशाल बहुमत Comparator<MyClass>.compare(Object,Object) में बिताया गया था। आगे का पता लगाने के लिए, मैं एक छोटे से परीक्षण कार्यक्रम बनाया:

public class Sandbox { 
    public static void main(String argv[]) { 
     for(int j=0; j<100; j++) { 
      int n = 10000; 
      SortMe[] sortMes = new SortMe[n]; 
      for (int i=0; i<n; i++) { 
       sortMes[i] = new SortMe(Math.random()); 
      } 
      Arrays.sort(sortMes, new SortMeComp()); 
      System.out.println(Arrays.toString(sortMes)); 
     } 
     for(int j=0; j<100; j++) { 
      int n = 10000; 
      SortMe[] sortMes = new SortMe[n]; 
      for (int i=0; i<n; i++) { 
       sortMes[i] = new SortMe(Math.random()); 
      } 
      Arrays.sort(sortMes, new SortMeCompTypeless()); 
      System.out.println(Arrays.toString(sortMes)); 
     } 
    } 
} 

टाइप किया तुलनाकारी:

public class SortMeComp implements Comparator<SortMe>{ 
    public int compare(SortMe one, SortMe two) { 
     if(one.getValue()>two.getValue()) { 
      return -1; 
     } else if (one.getValue()<two.getValue()) { 
      return 1; 
     } else { 
      return 0; 
     } 
    } 
} 

untyped तुलनाकारी मैं तुलना के लिए बने:

public class SortMeCompTypeless implements Comparator{ 
    public int compare(Object oneObj, Object twoObj) { 
     SortMe one = (SortMe) oneObj; 
     SortMe two = (SortMe) twoObj; 
     if(one.getValue()>two.getValue()) { 
      return -1; 
     } else if (one.getValue()<two.getValue()) { 
      return 1; 
     } else { 
      return 0; 
     } 
    } 
} 

यहाँ परिणाम (से हैं YourKit profiler; अगर आपको स्क्रीनशॉट होना है तो मुझे बताएं):

+----------------------------------------------------+-----------------+-----------------+--------------------+ 
|      Name      | Time (ms) | Own Time (ms) | Invocation Count | 
+----------------------------------------------------+-----------------+-----------------+--------------------+ 
| +---java.util.Arrays.sort(Object[], Comparator) | 23,604 100 % |   8,096 |    200 | 
| |            |     |     |     | 
| +---SortMeComp.compare(Object, Object)   | 11,395 48 % |   7,430 |  12,352,936 | 
| | |            |     |     |     | 
| | +---SortMeComp.compare(SortMe, SortMe)  | 3,965 17 % |   3,965 |  12,352,936 | 
| |            |     |     |     | 
| +---SortMeCompTypeless.compare(Object, Object) | 4,113 17 % |   4,113 |  12,354,388 | 
+----------------------------------------------------+-----------------+-----------------+--------------------+ 

मैंने फ़िल्टरिंग के बिना प्रोफाइल चलाया, और आप विलय करने के लिए रिकर्सिव कॉल देखते हैं (जो इसे पढ़ने में मुश्किल बनाते हैं), लेकिन ब्याज की कोई बात नहीं।

तो यहां क्या हो रहा है? उस विधि को SortMeComp.compare (ऑब्जेक्ट, ऑब्जेक्ट) कहां से आ रहा है? हमने सोचा कि यह ऐसा कुछ था जो जावा जेनेरिक से निपटने के लिए आंतरिक रूप से बनाता है, लेकिन इतना समय लग सकता है? मुझे लगता है कि जेवीएम सिर्फ एक सामान्य विधि का इलाज करेगा जैसे "untyped"/ऑब्जेक्ट विधि। जैसा कि आप देख सकते हैं, एक साधारण कास्ट बहुत तेज़ है। इसके अलावा, मुझे लगता है कि यह वास्तव में ऐसी चीज है जो जेवीएम को दूर की तरह सामान की आवश्यकता होती है, भले ही वह दूर हो जाए। यहाँ क्या चल रहा है?

वैसे:

$ java -version 
java version "1.6.0_26" 
Java(TM) SE Runtime Environment (build 1.6.0_26-b03) 
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode) 

संपादित करें:

जवाब में जवाब savinos लिए, मैं एक 'untyped' तुलनाकारी कि बस की तुलना एक टाइप करने के लिए डाली के साथ अतिरिक्त विधि कॉल का अनुकरण करने की कोशिश की:

+---------------------------------------------------------+-----------------+-----------------+--------------------+ 
|       Name       | Time (ms) | Own Time (ms) | Invocation Count | 
+---------------------------------------------------------+-----------------+-----------------+--------------------+ 
| +---java.util.Arrays.sort(Object[], Comparator)  | 31,044 100 % |   8,061 |    200 | 
| |             |     |     |     | 
| +---SortMeComp.compare(Object, Object)    | 11,554 37 % |   7,617 |  12,354,392 | 
| | |             |     |     |     | 
| | +---SortMeComp.compare(SortMe, SortMe)    | 3,936 13 % |   3,936 |  12,354,392 | 
| |             |     |     |     | 
| +---SortMeCompMethodCalls.compare(Object, Object) | 11,427 37 % |   7,613 |  12,352,146 | 
|  |             |     |     |     | 
|  +---SortMeCompMethodCalls.compare(SortMe, SortMe) | 3,814 12 % |   3,814 |  12,352,146 | 
+---------------------------------------------------------+-----------------+-----------------+--------------------+ 

:

public class SortMeCompMethodCalls implements Comparator{ 
    public int compare(Object oneObj, Object twoObj) { 
     return compare((SortMe)oneObj, (SortMe)twoObj); 
    } 
    public int compare(SortMe one, SortMe two) { 
     if(one.getValue()>two.getValue()) { 
      return -1; 
     } else if (one.getValue()<two.getValue()) { 
      return 1; 
     } else { 
      return 0; 
     } 
    } 
} 

यहाँ के परिणाम हैं

तो ऐसा लगता है कि savinos सही है! अतिरिक्त समय केवल अतिरिक्त विधि कॉल (साथ ही कलाकार के लिए थोड़ा सा) है। वह मेरे लिए पागल लगता है; आपको लगता है कि जेआईटी दूर हो जाएगा? ठीक है।

मैंने संपादन 2 हटा दिया और इसे उत्तर के रूप में जोड़ा क्योंकि यह मूल रूप से होना चाहिए था।

Answer 1

मैंने यह सोचना शुरू कर दिया कि क्या यह पूरी बात ट्रेसिंग का एक आर्टिफैक्ट था (मैं ट्रेस प्रोफाइलिंग का उपयोग कर रहा था, नमूना नहीं कर रहा था)। मैंने विधि कॉल भारी क्षेत्रों में अतीत में ट्रेसिंग कारण विकृतियों को देखा है। के रूप में यह नहीं कर रहा है

[bunch of doubles...] 
sortTest(10000, 10000, new SortMeComp()): 18168 
[bunch of doubles...] 
sortTest(10000, 10000, new SortMeCompTypeless()): 19366 

आप देख सकते हैं, आपके द्वारा लिखा गया एक वास्तव में तेजी से करता है, जो उम्मीद की जा करने के लिए है:

public class Sandbox { 
    public static void main(String argv[]) { 
     long startTime = System.currentTimeMillis(); 
     sortTest(10000, 10000, new SortMeComp()); 
     System.err.println("\n"+(System.currentTimeMillis()-startTime)); 
     startTime = System.currentTimeMillis(); 
     sortTest(10000, 10000, new SortMeCompTypeless()); 
     System.err.println("\n"+(System.currentTimeMillis()-startTime)); 
    } 

    public static void sortTest(int n, int l, Comparator<SortMe> c) { 
     for(int i=0; i<n; i++) { 
      SortMe[] sortMes = new SortMe[l]; 
      for(int j=0; j<l; j++) { 
       sortMes[j] = new SortMe(Math.random()); 
      } 
      System.out.print(sortMes[(int)(Math.random()*l)].getValue()); 
      Arrays.sort(sortMes, c); 
     } 
    } 
} 

यहाँ परिणाम हैं: तो मैं एक सीधी समय परीक्षण किया अभिनेता का चयन। इस प्रकार, ऐसा प्रतीत होता है कि जो अंतर मैं देख रहा था वह पूरी तरह से ट्रेसिंग के कारण था। होट्सएप में मेरा विश्वास बहाल कर दिया गया है!

वैसे, मैंने यह सुनिश्चित करने के लिए प्रिंटलन्स लगाए हैं कि जेवीएम लूप को किसी भी तरह से अनुकूलित नहीं करेगा।

Answer 2

मैं गलत हो सकता हूं, लेकिन मैं कहूंगा कि "ऑब्जेक्ट" तुलनित्र और टाइप किए गए तुलनित्र (जिसे जेनेरिक द्वारा कहा जाता है) के बीच डेल्टा अतिरिक्त फ़ंक्शन कॉल के कारण है।

मान लें कि आप 12,352,936 आमंत्रण कर रहे हैं, जिसका अर्थ है प्रति समारोह कॉल लगभग 5.7 * 10^-7 सेकंड, जो अनुचित नहीं है।

Answer 3

विषय से थोड़ी दूर, लेकिन आपको इसे तेज़ होना चाहिए ...

आप यादृच्छिक डेटा के साथ, लगभग 50% भीतरी तुलना() के समय को कम करता हूँ अगर आप इसे की तरह कुछ करने के लिए बदलने के लिए:

public int compare(SortMe one, SortMe two) { 
    return one.getValue() - two.getValue(); 
} 

हालांकि

, इस ही मान्य है अगर की भयावहता इनपुट की रेंज 2^31 से छोटी है। यदि बड़ा हो, तो अंतर बहती है।

Answer 4

वह तरीका कहां से SortMeComp.compare(Object,Object) आ रही है? हमने पाया कि यह जेनिक्स से निपटने के लिए आंतरिक रूप से बनाता है,

यह सही है। यह संकलक द्वारा आपके द्वारा SortMeComp.compare(SortMe one, SortMe two) लिखा गया विधि के लिए एक थंक के रूप में डाला गया है।