Pytanie Wydajność pamięci VM Java - Czy Array zapisuje szybciej niż odczytuje Array?


Wykonałem krótki test porównawczy na długiej tablicy w Javie z dość dziwnymi wynikami. Wydaje się, że sekwencyjne odczyty z przypadkowymi zapisami są szybsze - o połowę krótsze niż odczyty losowe z sekwencyjnymi zapisami. Czy ktoś ma pojęcia dlaczego?

Oto dwie metody, które piszą tablicę niektórych longów (uruchamianych z -Xmx2G) w kolejności losowej podczas czytania sekwencyjnego i odczytywania sekwencyjnie podczas zapisu losowego:

import java.util.Random;


public class Scratch {
static Random random = new Random();
static long[] arr = new long[100000000];

static void seqReadRandWrite() {
    for(int i=0;i<arr.length;i++) {
        int at = random.nextInt(arr.length);
        arr[at] = arr[i];
    }
}

static void seqWriteRandRead() {
    for(int i=0;i<arr.length;i++) {
        int at = random.nextInt(arr.length);
        arr[i] = arr[at];
    }
}

public static void main(String[] args) throws Exception {

    seqWriteRandRead(); // warm up

    long nanos = System.nanoTime();
    seqReadRandWrite();
    System.out.println("Time: " + (System.nanoTime()-nanos) + "ns");

    nanos = System.nanoTime();
    seqWriteRandRead();
    System.out.println("Time: " + (System.nanoTime()-nanos) + "ns");

}
}

wyniki na moim notesie są

Czas: 2774662168ns

Czas: 6059499068ns

Co oznacza, że ​​jest dwa razy szybszy do zapisania losowo w porównaniu do czytania .. lub? Czy mój laptop jest zepsuty?

ps .: nie oznacza to, że jest to punkt odniesienia, chociaż większość punktów powiązanych porad dotyczących benchmarkingu jest omówiona. Nawet jeśli wielokrotnie uruchamiam już 200 000 000 operacji, to pozostaną one na stałym poziomie. Wydaje się (wydaje się, że) przeniesienie pamięci z przypadkowych pozycji do bloków sekwencyjnych jest wolniejsze niż przenoszenie pamięci z kolejnych pozycji do losowych bloków, przynajmniej z pamięcią o tym rozmiarze i powyższym sposobem wykonania tej operacji. i zastanawiam się, dlaczego?


12
2018-01-31 22:04


pochodzenie


Dlaczego nie rozgrzałeś seqReadRandWrite() metoda również? Czy jesteś pewien, że pojedyncze wywołanie wystarczy do wywołania kompilatora JIT? - maerics
to tylko dla pamięci ... spróbuj, nie ma różnicy - cybye
Moja WAG byłaby tym, że czytanie jest sekwencyjnie zoptymalizowane, ponieważ odbywa się to często w programowaniu. Dlatego pierwszy algorytm jest szybszy. - JustinKSU
@MiserableVariable - Właśnie zrobiłem ten test z ciekawości - sekwencyjne odczyty / zapisy uruchamiane z praktycznie taką samą prędkością (jak oczekiwano). Ale losowe odczyty wydają się być ~ dwa razy wolniejsze niż przypadkowe zapisy. Wierzę, że jest to efekt pamięci podręcznych w grze. - Perception
"Krótki test porównawczy" => nieważny test porównawczy. - user207421


Odpowiedzi:


Twój benchmark produkuje liczby, które zawodzą w "Czy mają sens?" test. W takiej sytuacji zawsze powinieneś podwójnie / potrójnie / poczwórnie sprawdzać swoją metodologię ... PRZED traktowaniem liczb jako prawdziwego odbicia rzeczywistości.

Pisanie wiarygodnych benchmarków jest trudne. A w przypadku Javy jest szczególnie ciężko, ponieważ niektóre aspekty platformy Java mogą wprowadzać systematyczne zniekształcenia do twoich pomiarów wzorcowych ... chyba że wyraźnie pozwolisz / zrekompensujesz je.

Ale reguła "sprawdź swoją metodologię" dotyczy WSZYSTKICH eksperymentów ... szczególnie tych, które dają wyniki, które nie wydają się mieć sensu. (Jak neutrina podróżujące szybciej niż światło ...)


Inną rzeczą, na którą należy zwrócić uwagę, jest to, że po przepisaniu testu porównawczego w celu uwzględnienia czynników zakłócających możesz nadal zobacz nieoczekiwane liczby. Problem w tym, że wydajność takich testów porównawczych może być wrażliwa na takie rzeczy, jak rozmiar pamięci podręcznej L1 i L2, rozmiar linii pamięci podręcznej, prędkości względne różnych poziomów pamięci ... i ich wzajemne oddziaływanie z dokładnymi sekwencjami instrukcje, które benchmark produkuje w ciasnych pętlach.

Te rzeczy są skomplikowane, trudne do analizy i mogą dawać sprzeczne z intuicją zachowania. I nie jest zaskakujące (dla mnie), że różne maszyny dają różne mierzone osiągi.

Więc nawet jeśli liczby są prawdziwe, to wciąż jest niebezpieczne jest wyciąganie ogólnych wniosków na temat szybkości czytania w porównaniu do zapisu z tego testu porównawczego. Nawet jeśli ograniczasz je tylko do laptopa.


3
2018-01-31 23:12



Masz absolutną rację, ale nie wyciągnąłem żadnych wniosków, a zamiast tego znalazłem kilka pytań. - cybye
Tak, ale @Miserable Variable wydaje się wyciągać wnioski, i wątpliwe w tym! - Stephen C


Uważam, że ten benchmark jest całkowicie bezużyteczny. Istnieje wiele parametrów pomiarów, które należy wziąć pod uwagę, a sposób, w jaki podchodzisz do tego problemu, jest całkowicie nieopisany. Aby wyciągnąć jakikolwiek wniosek o szybkości implementacji dotyczących maszyn wirtualnych, komputerów, prędkości RAM, oprogramowania przetwarzanego w tym samym czasie, rodzaju obiektów lub prostych rzeczy, które kopiujesz, i tak dalej, musisz nauczyć się metodycznie. To pytanie nie jest odpowiednie. Musisz zawęzić konkretne okoliczności, które chcesz wiedzieć o prędkości.

Zwłaszcza nie można wyciągnąć żadnych wniosków, używając liczb losowych. To znacznie zwiększa problem najlepszego, najgorszego lub przeciętnego przypadku Złożoność.

Sprawdź złożoność algorytmów, a następnie przejdź do wyszukiwania sposobu wykonania pomiarów wydajności środowiska wykonawczego. Mam nadzieję, że mógłbym ci trochę pomóc.

Ta pierwsza odpowiedź jest niesamowita i pomoże ci ją zrozumieć. Jak napisać poprawny mikro-benchmark w Javie?

Z poważaniem,


1
2018-01-31 22:52





Podsumowując, tytuł pytania jest nieco niepoprawny. Prawda wydaje się być taka w niektórych środowiskach (np. w kopalniach i OP) losowe zapisy w tablicy są szybsze niż odczyty tablic losowych. Ale zauważ, że nie jest to prawdą dla niektórych innych osób.

Na podstawie @ JustinKSU komentarz Wyodrębniłem odczyt i zapis i stwierdziłem, że losowe zapisy są szybsze niż losowe. Wyniki są następujące. Wydaje się, że to jest powód, i wydaje się, że zbiorowa opinia, że ​​błędy odczytu w pamięci podręcznej są droższe niż błędy w zapisie (jeśli w ogóle istnieje zapis pamięci podręcznej).

W produkcji, gdzie jest inna aktywność, hotspot może odgrywać pewną rolę.

/cygdrive/c/Java/jdk1.7.0/bin/javac.exe Scratch.java && /cygdrive/c/Java/jdk1.7.0/bin/java Scratch
Starting
seqRead: 1273719725ns
seqRead: 1243055271ns
seqRead: 1245022497ns
seqRead: 1242868527ns
seqRead: 1241655611ns
randRead: 6900959912ns
randRead: 6965196004ns
randRead: 7379623094ns
randRead: 7020390995ns
randRead: 6938997617ns
seqWrite: 1266963940ns
seqWrite: 1250599487ns
seqWrite: 1246471685ns
seqWrite: 1230472648ns
seqWrite: 1246975416ns
randWrite: 3898382192ns
randWrite: 3897441137ns
randWrite: 3939947844ns
randWrite: 4207906037ns
randWrite: 4103594207ns

Compilation finished at Thu Jan 31 14:38:57

Mój zmodyfikowany kod wygląda następująco:

import java.util.Random;


public class Scratch {
static Random random = new Random();
static long[] arr = new long[100000000];

static void seqReadRandWrite() {
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        arr[at] = arr[i];
    }
}

static void seqWriteRandRead() {
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        arr[i] = arr[at];
    }
}


static void seqRead() {
    int x = 0;
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        x += arr[i];
    }
}

static void randRead() {
    int x = 0;
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        x += arr[at];
    }
}

static void seqWrite() {
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        arr[i] = at;
    }
}

static void randWrite() {
    for(int i=0;i<arr.length;i++) {
        int at = Math.abs(random.nextInt() % arr.length);
        arr[at] = at;
    }
}


public static void main(String[] args) throws Exception {

    // seqWriteRandRead(); // warm up
    System.out.println("Starting");

    long nanos =  -1;
    /*
    for (int i = 0; i < 5; i++) {       
        nanos = System.nanoTime();
        seqWriteRandRead();
        System.out.println("WriteRandRead Time: " + (System.nanoTime()-nanos) + "ns");

        nanos = System.nanoTime();
        seqReadRandWrite();
        System.out.println("ReadRandWrite Time: " + (System.nanoTime()-nanos) + "ns");
    }
    */

    for (int i = 0; i < 5; i++) {       
        nanos = System.nanoTime();
        seqRead();
        System.out.println("seqRead: " + (System.nanoTime()-nanos) + "ns");
    }

    for (int i = 0; i < 5; i++) {       
        nanos = System.nanoTime();
        randRead();
        System.out.println("randRead: " + (System.nanoTime()-nanos) + "ns");
    }


    for (int i = 0; i < 5; i++) {       
        nanos = System.nanoTime();
        seqWrite();
        System.out.println("seqWrite: " + (System.nanoTime()-nanos) + "ns");
    }

    for (int i = 0; i < 5; i++) {       
        nanos = System.nanoTime();
        randWrite();
        System.out.println("randWrite: " + (System.nanoTime()-nanos) + "ns");
    }

}
}

AKTUALIZACJA

@tomcarchrae zrobił ten sam test na Linuksie, ze znacząco różnymi wynikami. Poniżej pierwsza kolumna to liczby z mojego testu, a druga z tomu:

seqRead:   1273719725ns   2810487542ns  
seqRead:   1243055271ns   2780504580ns  
seqRead:   1245022497ns   2746663894ns  
seqRead:   1242868527ns   2746094469ns  
seqRead:   1241655611ns   2763107970ns  
randRead:  6900959912ns   23093543703ns 
randRead:  6965196004ns   22458781637ns 
randRead:  7379623094ns   24421031646ns 
randRead:  7020390995ns   25880250599ns 
randRead:  6938997617ns   26873823898ns 
seqWrite:  1266963940ns   4226886722ns  
seqWrite:  1250599487ns   4537680602ns  
seqWrite:  1246471685ns   3880372295ns  
seqWrite:  1230472648ns   4160499114ns  
seqWrite:  1246975416ns   4008607447ns  
randWrite: 3898382192ns   25985349107ns 
randWrite: 3897441137ns   22259835568ns 
randWrite: 3939947844ns   22556465742ns 
randWrite: 4207906037ns   22143959163ns 
randWrite: 4103594207ns   21737397817ns 

1
2018-01-31 22:42



Chuckle, pobiłeś mnie, że wysłałem to około 15 sekund. Jestem pewien, że te wyniki są spowodowane tym, że błędy odczytu w głównej pamięci podręcznej są droższe niż błędy w pisaniu. Dodaj to do swojej odpowiedzi i jej +1 dla ciebie. - Perception
Edytowałem swoją odpowiedź. Warto zdobyć punkty internetowe, mam na myśli wiedzę :) - Miserable Variable
Dzięki za zasługi :) - JustinKSU
Wydaje się być zależne od sprzętu. A może zależne od JVM. Mogłem też odtworzyć (z najnowszą wersją Java 7), ale niektóre nie. - lbalazscs
Wyniki z moim komputerze (Linux) seqRead wywoławcza: 2810487542ns seqRead: 2780504580ns seqRead: 2746663894ns seqRead: 2746094469ns seqRead: 2763107970ns randRead: 23093543703ns randRead: 22458781637ns randRead: 24421031646ns randRead: 25880250599ns randRead: 26873823898ns seqWrite: 4226886722ns seqWrite: 4537680602ns seqWrite: 3880372295ns seqWrite: 4160499114ns seqWrite: 4008607447ns randWrite: 25985349107ns randWrite: 22259835568ns randWrite: 22556465742ns randWrite: 22143959163ns randWrite: 21737397817ns - Tom Carchrae


Odpowiedź jest w poprzednich komentarzach i sprowadza się do efektów wzorców dostępu do pamięci. Ten blog stanowisko obejmuje efekty losowych odczytów. Pisze nie cierpią podobnie.

Nie jest to problem z Javą (ani żadnym innym językiem), ale rzeczywistość sprzętu, na którym pracujesz (i powszechna rzeczywistość). To nie znaczy, że powinieneś to zignorować! Chociaż początkowy benchmark mógł być wadliwy, wciąż stanowi poważny problem w przypadku niektórych programów, więc jest to cenna lekcja.

Wniosek nie jest taki, że czytanie jest droższe niż pisanie. Jest tak, że losowy dostęp do pamięci nie jest dobrze obsługiwany przez sprzęt. Zasadniczo wynika to z tego, że wydajność programu LinkedList jest o wiele gorsza niż ArrayList w przypadku dostępu sekwencyjnego. Oba mają jednakową złożoność obliczeniową, ale dostęp do macierzy odtwarza siłę sprzętu, której nie ma lista połączona.


1
2018-02-18 10:07





wyniki na moim komputerze: (ns na r / w)

seq read :     1.4 
rnd read :   10x.x   
seq write:     3.3 
rnd write:   10x.x

a seqReadRandWrite i seqWriteRandRead są równie szybkie z szybkością 100ns na pętlę.

więc może to zależeć od sprzętu. także ustawienie VM. próbować java -server i zobacz, czy prędkość się poprawia.


0
2018-01-31 22:59





Twój eksperyment jest zepsuty, a nie twój laptop. Zobacz tutaj dyskusję i kilka narzędzi, które pomogą zmierzyć wydajność: Biblioteka synchronizacji wydajności Java

Poniżej znajdują się wyniki, które zawierają twoje. Zmodyfikowałem również twój kod, aby był bardziej rygorystyczny i ostrożny w sposobie wykonywania pomiarów.


Moim środowiskiem jest Linux (Mint 14 oparty na Ubuntu 12.10) wykorzystujący Sun JDK 1.6.0_38

Z 1,5G sterty dla dużego przykładu, np. -Xmx1512


Uwaga: interesujące. Może być mój wynik jest inny, ponieważ rozmiar tablicy jest inny poniżej. Ponownie uruchomi się i zaktualizuje.

Nie: wynik jest podobny, nie ma dużej różnicy w średniej. Ale interesująca jest różnica w stosunku do krótkiego przebiegu, tj. 21092.5 (/ 10 = 2109.2) vs 1645.2, która może być wolniejsza z powodu stronicowania pamięci.

wynik z static long[] arr = new long[100000000]; (oryginalny rozmiar tablicy, o którym mowa)

Napisz: opisoweStatystyki: n: 10 min: 20893.0 max: 22190,0 oznacza:   21092.5 std dev: 390.90727800848117 mediana: 20953.5 pochylenie: 3,0092198852491543 kurtoza: 9.264808973899097

Read: DescriptiveStatistics: n: 10 min: 21668.0 max: 22736.0 oznacza:   21892.5 std dev: 318,31509546359877 mediana: 21766.5 pochylenie: 2.5034216544466124 kurtoza: 6.560838306717343


Nie widzę dużej różnicy w odczytach i zapisach. Zmieniłem eksperyment na 10-krotny pomiar na nieco mniejszej tablicy (wynik to taka sama liczba odczytów / zapisów). Zapraszam do ponownego uruchomienia z większą tablicą rozmiarów lub wielkością próbki.

Napisz: opisoweStatystyki: n: 10 min: 1584.0 max: 1799.0 średnia:   1645.2 std dev: 59.51619760853156 mediana: 1634.5 skośność: 2.137918517160786 kurtoza: 5.764166551997385

Read: descriptiveStatistics: n: 10 min: 1568.0 max: 2202,0 oznacza:   1689.0 std dev: 186.93908693000031 mediana: 1623.0 skośność: 2.770215113912315 kurtosis: 8.12245132320571

Oto zmodyfikowana wersja twojego kodu, która zawiera więcej próbek:

import java.util.Random;

import org.apache.commons.lang.time.StopWatch;
import org.apache.commons.math.stat.descriptive.DescriptiveStatistics;

public class Test {
    static Random random = new Random();
//  static long[] arr = new long[100000000];
    static long[] arr = new long[10000000];

    static void seqReadRandWrite() {
        for (int i = 0; i < arr.length; i++) {
            int at = Math.abs(random.nextInt()) % arr.length;
            arr[at] = arr[i];
        }
    }

    static void seqWriteRandRead() {
        for (int i = 0; i < arr.length; i++) {
            int at = Math.abs(random.nextInt()) % arr.length;
            arr[i] = arr[at];
        }
    }

    public static void main(String[] args) throws Exception {

        StopWatch timer = new StopWatch();
        int count = 10;

        // warm up
        for (int i=0; i<3; i++){
            seqReadRandWrite();
        }
        DescriptiveStatistics write = new DescriptiveStatistics();
        for (int i=0; i<count; i++){
            timer.reset();
            timer.start();
            seqReadRandWrite();
            timer.stop();
            write.addValue(timer.getTime());
        }
        System.out.println("Write: " + write);

        // warm up
        for (int i=0; i<3; i++){
            seqWriteRandRead(); 
        }
        DescriptiveStatistics read = new DescriptiveStatistics();
        for (int i=0; i<count; i++){
            timer.reset();
            timer.start();
            seqWriteRandRead();
            timer.stop();
            read.addValue(timer.getTime());
        }

        System.out.println("Read: " + read);


    }
}

0
2018-01-31 22:42



Na moim laptopie twój program (bez żadnych zmian) mierzy, że zapisy są ponad dwa razy szybsze od odczytów. Może każdy laptop jest zepsuty, ale twój :) - lbalazscs
Tom: Jakie jest twoje środowisko? Czy możesz spróbować testu w mojej odpowiedzi? - Miserable Variable
Interesujące - z jakiego systemu operacyjnego korzystasz? - Tom Carchrae
@MiserableVariable - na pewno opublikuję mój wynik jako komentarz do Twojego wpisu - Tom Carchrae