java - एक अनुक्रमित सरणी की तुलना में एक क्रमबद्ध सरणी * धीमी * प्रसंस्करण क्यों कर रहा है?(जावा का ArrayList.indexOf)




performance (4)

मुझे लगता है कि हम मेमोरी कैश मिस के प्रभाव को देख रहे हैं:

जब आप अपरिवर्तित सूची बनाते हैं

for (int i = 0; i < LIST_LENGTH; i++) {
    list.add(r.nextDouble());
}

सभी डबल एक संभावित स्मृति क्षेत्र में आवंटित किए जाने की संभावना है। इसके माध्यम से छेड़छाड़ कुछ कैश मिस पैदा करेगा।

दूसरी ओर क्रमबद्ध सूची में संदर्भ एक अराजक तरीके से स्मृति को इंगित करते हैं।

अब यदि आप संगत स्मृति के साथ एक क्रमबद्ध सूची बनाते हैं:

Collection.sort(list);
List<Double> list2 = new ArrayList<>();
for (int i = 0; i < LIST_LENGTH; i++) {
    list2.add(new Double(list.get(i).doubleValue()));
}

इस क्रमबद्ध सूची में मूल एक (मेरा समय) से समान प्रदर्शन होता है।

शीर्षक एक संदर्भित सरणी की तुलना में एक क्रमबद्ध सरणी को संसाधित करने के लिए तेज़ क्यों है?

क्या यह एक शाखा भविष्यवाणी प्रभाव भी है? सावधान रहें: यहां सॉर्ट किए गए सरणी के लिए प्रसंस्करण धीमा है !!

निम्नलिखित कोड पर विचार करें:

private static final int LIST_LENGTH = 1000 * 1000;
private static final long SLOW_ITERATION_MILLIS = 1000L * 10L;

@Test
public void testBinarySearch() {
    Random r = new Random(0);
    List<Double> list = new ArrayList<>(LIST_LENGTH);
    for (int i = 0; i < LIST_LENGTH; i++) {
        list.add(r.nextDouble());
    }
    //Collections.sort(list);
    // remove possible artifacts due to the sorting call
    // and rebuild the list from scratch:
    list = new ArrayList<>(list);

    int nIterations = 0;
    long startTime = System.currentTimeMillis();
    do {
        int index = r.nextInt(LIST_LENGTH);
        assertEquals(index, list.indexOf(list.get(index)));
        nIterations++;
    } while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
    long duration = System.currentTimeMillis() - startTime;
    double slowFindsPerSec = (double) nIterations / duration * 1000;
    System.out.println(slowFindsPerSec);

    ...
}

यह मेरी मशीन पर लगभग 720 के मूल्य का प्रिंट करता है।

अब अगर मैं संग्रह सॉर्ट कॉल को सक्रिय करता हूं, तो वह मान 142 तक गिर जाता है। क्यों?!

परिणाम निर्णायक हैं, अगर मैं पुनरावृत्तियों / समय की संख्या में वृद्धि करता हूं तो वे नहीं बदलते हैं।

जावा संस्करण 1.8.0_71 (ओरेकल वीएम, 64 बिट) है, जो विंडोज 10 के तहत चल रहा है, ग्रहण मंगल ग्रह में जुनीट परीक्षण।

अद्यतन करें

लगता है कि संगत स्मृति पहुंच से संबंधित होना चाहिए (अनुक्रमिक क्रम में बनाम डबल ऑब्जेक्ट्स यादृच्छिक क्रम में बनाम)। लगभग 10k और उससे कम की सरणी लंबाई के लिए प्रभाव मेरे लिए गायब हो जाता है।

परिणाम प्रदान करने के लिए assylias के लिए धन्यवाद:

/**
 * Benchmark                     Mode  Cnt  Score   Error  Units
 * SO35018999.shuffled           avgt   10  8.895 ± 1.534  ms/op
 * SO35018999.sorted             avgt   10  8.093 ± 3.093  ms/op
 * SO35018999.sorted_contiguous  avgt   10  1.665 ± 0.397  ms/op
 * SO35018999.unsorted           avgt   10  2.700 ± 0.302  ms/op
 */

एक साधारण उदाहरण के रूप में जो wero द्वारा जवाब और apangin (+1!) द्वारा उत्तर की पुष्टि करता है: निम्नलिखित दोनों विकल्पों की एक साधारण तुलना करता है:

  • यादृच्छिक संख्या बनाना, और उन्हें वैकल्पिक रूप से सॉर्ट करना
  • क्रमिक संख्या बनाना, और वैकल्पिक रूप से उन्हें शफल करना

इसे जेएमएच बेंचमार्क के रूप में भी लागू नहीं किया गया है, लेकिन मूल कोड के समान, प्रभाव को देखने के लिए केवल मामूली संशोधन के साथ:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class SortedListTest
{
    private static final long SLOW_ITERATION_MILLIS = 1000L * 3L;

    public static void main(String[] args)
    {
        int size = 100000;
        testBinarySearchOriginal(size, true);
        testBinarySearchOriginal(size, false);
        testBinarySearchShuffled(size, true);
        testBinarySearchShuffled(size, false);
    }

    public static void testBinarySearchOriginal(int size, boolean sort)
    {
        Random r = new Random(0);
        List<Double> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
        {
            list.add(r.nextDouble());
        }
        if (sort)
        {
            Collections.sort(list);
        }
        list = new ArrayList<>(list);

        int count = 0;
        int nIterations = 0;
        long startTime = System.currentTimeMillis();
        do
        {
            int index = r.nextInt(size);
            if (index == list.indexOf(list.get(index)))
            {
                count++;
            }
            nIterations++;
        }
        while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
        long duration = System.currentTimeMillis() - startTime;
        double slowFindsPerSec = (double) nIterations / duration * 1000;

        System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
            size, sort, slowFindsPerSec, count);
    }

    public static void testBinarySearchShuffled(int size, boolean sort)
    {
        Random r = new Random(0);
        List<Double> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
        {
            list.add((double) i / size);
        }
        if (!sort)
        {
            Collections.shuffle(list);
        }
        list = new ArrayList<>(list);

        int count = 0;
        int nIterations = 0;
        long startTime = System.currentTimeMillis();
        do
        {
            int index = r.nextInt(size);
            if (index == list.indexOf(list.get(index)))
            {
                count++;
            }
            nIterations++;
        }
        while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
        long duration = System.currentTimeMillis() - startTime;
        double slowFindsPerSec = (double) nIterations / duration * 1000;

        System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
            size, sort, slowFindsPerSec, count);
    }

}

मेरी मशीन पर आउटपुट है

Size   100000 sort  true iterations   8560,333 count      25681
Size   100000 sort false iterations  19358,667 count      58076
Size   100000 sort  true iterations  18554,000 count      55662
Size   100000 sort false iterations   8845,333 count      26536

अच्छी तरह से दिखा रहा है कि समय बिल्कुल दूसरे के विपरीत हैं: यदि यादृच्छिक संख्या क्रमबद्ध की जाती है, तो क्रमबद्ध संस्करण धीमा होता है। यदि अनुक्रमिक संख्या shuffled हैं, तो shuffled संस्करण धीमा है।


यह कैशिंग / प्रीफेचिंग प्रभाव की तरह दिखता है।

सुराग यह है कि आप डबल्स (ऑब्जेक्ट्स) की तुलना करते हैं, डबल्स (प्राइमेटिव्स) नहीं। जब आप एक थ्रेड में ऑब्जेक्ट आवंटित करते हैं, तो उन्हें आमतौर पर स्मृति में क्रमशः आवंटित किया जाता है। तो जब indexOf एक सूची स्कैन करता है, तो यह क्रमिक स्मृति पते के माध्यम से जाता है। यह सीपीयू कैश prefetching heuristics के लिए अच्छा है।

लेकिन सूची को सॉर्ट करने के बाद, आपको अभी भी औसत मेमोरी लुकअप की संख्या समान रूप से करना है, लेकिन इस बार मेमोरी एक्सेस यादृच्छिक क्रम में होगी।

अद्यतन करें

यह साबित करने के लिए बेंचमार्क यहां दिया गया है कि आवंटित वस्तुओं का क्रम महत्वपूर्ण है।

Benchmark            (generator)  (length)  (postprocess)  Mode  Cnt  Score   Error  Units
ListIndexOf.indexOf       random   1000000           none  avgt   10  1,243 ± 0,031  ms/op
ListIndexOf.indexOf       random   1000000           sort  avgt   10  6,496 ± 0,456  ms/op
ListIndexOf.indexOf       random   1000000        shuffle  avgt   10  6,485 ± 0,412  ms/op
ListIndexOf.indexOf   sequential   1000000           none  avgt   10  1,249 ± 0,053  ms/op
ListIndexOf.indexOf   sequential   1000000           sort  avgt   10  1,247 ± 0,037  ms/op
ListIndexOf.indexOf   sequential   1000000        shuffle  avgt   10  6,579 ± 0,448  ms/op

इंटरफ़ेस कार्यान्वयन पर @ ओवरराइड असंगत है क्योंकि जावा में "इंटरफ़ेस ओवरराइडिंग" जैसी कोई चीज़ नहीं है।

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

इंटरफ़ेस कार्यान्वयनकर्ताओं पर @ ओवरराइड को 1.6 में कभी अनुमति नहीं दी जानी चाहिए, और ग्रहण के साथ उदासीनता को डिफ़ॉल्ट व्यवहार के रूप में एनोटेशन डालने का चयन करना, हमें बहुत सारी अव्यवस्थित स्रोत फ़ाइलें मिलती हैं। 1.6 कोड पढ़ने पर, आप @ ओवरराइड एनोटेशन से नहीं देख सकते हैं यदि कोई विधि वास्तव में सुपरक्लास में किसी विधि को ओवरराइड करता है या केवल एक इंटरफ़ेस लागू करता है।

एक सुपरक्लास में वास्तव में एक विधि को ओवरराइड करते समय @ ओवरराइड का उपयोग करना ठीक है।







java performance arraylist