Java 8 razy szybciej z tablicami niż std :: vector w C ++. Co zrobiłem źle?

88

Mam następujący kod Java z kilkoma dużymi tablicami, które nigdy nie zmieniają swojego rozmiaru. Na moim komputerze działa w 1100 ms.

Zaimplementowałem ten sam kod w C ++ i użyłem std::vector.

Czas implementacji C ++, który uruchamia dokładnie ten sam kod, to 8800 ms na moim komputerze. Co zrobiłem źle, żeby działało to powoli?

Zasadniczo kod wykonuje następujące czynności:

for (int i = 0; i < numberOfCells; ++i) {
        h[i] =  h[i] + 1;
        floodedCells[i] =  !floodedCells[i];
        floodedCellsTimeInterval[i] =  !floodedCellsTimeInterval[i];
        qInflow[i] =  qInflow[i] + 1;
}

Iteruje przez różne tablice o rozmiarze około 20000.

Obie implementacje można znaleźć pod poniższymi linkami:

(W ideone mogłem uruchomić pętlę tylko 400 razy zamiast 2000 razy z powodu ograniczenia czasowego. Ale nawet tutaj jest różnica trzech razy)

java c++ arrays performance stdvector RobinXSI
źródło
42
std::vector<bool>wykorzystuje jeden bit na element, aby zaoszczędzić miejsce, co prowadzi do częstego przesuwania bitów. Jeśli chcesz prędkości, trzymaj się od niej z daleka. Użyj std::vector<int>zamiast tego.
molbdnilo
44
@molbdnilo lub std :: vector <char>. Nie ma potrzeby tracić że wiele ;-)
stefan
7
Wystarczająco zabawne. Wersja C ++ jest szybsza, gdy liczba komórek wynosi 200. Lokalizacja pamięci podręcznej?
Captain Giraffe
9
Część II: Byłoby znacznie lepiej, gdybyś utworzył oddzielną klasę / strukturę, która zawierałaby po jednym z każdego elementu tablicy, a następnie miałaby pojedynczą tablicę obiektów tej struktury, ponieważ wtedy faktycznie przechodzisz przez pamięć tylko raz, w w jednym kierunku.
Timo Geusch
9
@TimoGeusch: Chociaż wydaje mi się, że h[i] += 1;lub (lepiej) ++h[i]jest bardziej czytelny niż h[i] = h[i] + 1;, byłbym nieco zaskoczony, widząc jakąkolwiek znaczącą różnicę w szybkości między nimi. Kompilator może „dowiedzieć się”, że obaj robią to samo i wygenerować ten sam kod w obie strony (przynajmniej w większości przypadków).
Jerry Coffin

Odpowiedzi:

36

Oto wersja C ++ z danymi dla każdego węzła zebranymi w strukturę i wykorzystany pojedynczy wektor tej struktury:

#include <vector>
#include <cmath>
#include <iostream>



class FloodIsolation {
public:
  FloodIsolation() :
      numberOfCells(20000),
      data(numberOfCells)
  {
  }
  ~FloodIsolation(){
  }

  void isUpdateNeeded() {
    for (int i = 0; i < numberOfCells; ++i) {
       data[i].h = data[i].h + 1;
       data[i].floodedCells = !data[i].floodedCells;
       data[i].floodedCellsTimeInterval = !data[i].floodedCellsTimeInterval;
       data[i].qInflow = data[i].qInflow + 1;
       data[i].qStartTime = data[i].qStartTime + 1;
       data[i].qEndTime = data[i].qEndTime + 1;
       data[i].lowerFloorCells = data[i].lowerFloorCells + 1;
       data[i].cellLocationX = data[i].cellLocationX + 1;
       data[i].cellLocationY = data[i].cellLocationY + 1;
       data[i].cellLocationZ = data[i].cellLocationZ + 1;
       data[i].levelOfCell = data[i].levelOfCell + 1;
       data[i].valueOfCellIds = data[i].valueOfCellIds + 1;
       data[i].h0 = data[i].h0 + 1;
       data[i].vU = data[i].vU + 1;
       data[i].vV = data[i].vV + 1;
       data[i].vUh = data[i].vUh + 1;
       data[i].vVh = data[i].vVh + 1;
       data[i].vUh0 = data[i].vUh0 + 1;
       data[i].vVh0 = data[i].vVh0 + 1;
       data[i].ghh = data[i].ghh + 1;
       data[i].sfx = data[i].sfx + 1;
       data[i].sfy = data[i].sfy + 1;
       data[i].qIn = data[i].qIn + 1;


      for(int j = 0; j < nEdges; ++j) {
        data[i].flagInterface[j] = !data[i].flagInterface[j];
        data[i].typeInterface[j] = data[i].typeInterface[j] + 1;
        data[i].neighborIds[j] = data[i].neighborIds[j] + 1;
      }
    }

  }

private:

  const int numberOfCells;
  static const int nEdges = 6;
  struct data_t {
    bool floodedCells = 0;
    bool floodedCellsTimeInterval = 0;

    double valueOfCellIds = 0;
    double h = 0;

    double h0 = 0;
    double vU = 0;
    double vV = 0;
    double vUh = 0;
    double vVh = 0;
    double vUh0 = 0;
    double vVh0 = 0;
    double ghh = 0;
    double sfx = 0;
    double sfy = 0;
    double qInflow = 0;
    double qStartTime = 0;
    double qEndTime = 0;
    double qIn = 0;
    double nx = 0;
    double ny = 0;
    double floorLevels = 0;
    int lowerFloorCells = 0;
    bool floorCompleteleyFilled = 0;
    double cellLocationX = 0;
    double cellLocationY = 0;
    double cellLocationZ = 0;
    int levelOfCell = 0;
    bool flagInterface[nEdges] = {};
    int typeInterface[nEdges] = {};
    int neighborIds[nEdges] = {};
  };
  std::vector<data_t> data;

};

int main() {
  std::ios_base::sync_with_stdio(false);
  FloodIsolation isolation;
  clock_t start = clock();
  for (int i = 0; i < 400; ++i) {
    if(i % 100 == 0) {
      std::cout << i << "\n";
    }
    isolation.isUpdateNeeded();
  }
  clock_t stop = clock();
  std::cout << "Time: " << difftime(stop, start) / 1000 << "\n";
}

przykład na żywo

Czas jest teraz 2x szybszy niż wersja Java. (846 przeciwko 1631).

Szanse są takie, że JIT zauważył spalanie pamięci podręcznej dostępu do danych w każdym miejscu i przekształcił twój kod w logicznie podobny, ale bardziej wydajny porządek.

Wyłączyłem również synchronizację stdio, ponieważ jest ona potrzebna tylko wtedy, gdy mieszasz printf/ scanfz C ++ std::couti std::cin. Tak się składa, że ​​wypisujesz tylko kilka wartości, ale domyślne zachowanie C ++ podczas drukowania jest zbyt paranoiczne i nieefektywne.

Jeśli nEdgesnie jest rzeczywistą wartością stałą, wówczas 3 wartości „tablicy” będą musiały zostać usunięte z struct. To nie powinno spowodować wielkiego uderzenia w wydajność.

Możesz uzyskać kolejny wzrost wydajności, sortując wartości, structzmniejszając rozmiar, zmniejszając w ten sposób zużycie pamięci (i dostęp do sortowania, gdy nie ma to znaczenia). Ale nie jestem pewien.

Ogólna zasada jest taka, że ​​pojedynczy brak pamięci podręcznej jest 100 razy droższy niż instrukcja. Uporządkowanie danych w celu zachowania spójności pamięci podręcznej ma dużą wartość.

Jeśli zmiana kolejności danych na a structjest niewykonalna, możesz zmienić iterację, aby po kolei obejmowała każdy kontener.

Na marginesie, zauważ, że wersje Java i C ++ miały w sobie pewne subtelne różnice. Zauważyłem, że wersja Javy ma 3 zmienne w pętli „for each edge”, podczas gdy w C ++ tylko dwie, które dopasowałem do Javy. Nie wiem, czy są inni.

Yakk - Adam Nevraumont
źródło
44

Tak, pamięć podręczna w wersji c ++ ma problemy. Wydaje się, że zespół JIT jest lepiej przygotowany do tego.

Jeśli zmienisz zewnętrzne forw isUpdateNeeded () na krótsze fragmenty. Różnica znika.

Poniższy przykład daje czterokrotne przyspieszenie.

void isUpdateNeeded() {
    for (int i = 0; i < numberOfCells; ++i) {
        h[i] =  h[i] + 1;
        floodedCells[i] =  !floodedCells[i];
        floodedCellsTimeInterval[i] =  !floodedCellsTimeInterval[i];
        qInflow[i] =  qInflow[i] + 1;
        qStartTime[i] =  qStartTime[i] + 1;
        qEndTime[i] =  qEndTime[i] + 1;
    }

    for (int i = 0; i < numberOfCells; ++i) {
        lowerFloorCells[i] =  lowerFloorCells[i] + 1;
        cellLocationX[i] =  cellLocationX[i] + 1;
        cellLocationY[i] =  cellLocationY[i] + 1;
        cellLocationZ[i] =  cellLocationZ[i] + 1;
        levelOfCell[i] =  levelOfCell[i] + 1;
        valueOfCellIds[i] =  valueOfCellIds[i] + 1;
        h0[i] =  h0[i] + 1;
        vU[i] =  vU[i] + 1;
        vV[i] =  vV[i] + 1;
        vUh[i] =  vUh[i] + 1;
        vVh[i] =  vVh[i] + 1;
    }
    for (int i = 0; i < numberOfCells; ++i) {
        vUh0[i] =  vUh0[i] + 1;
        vVh0[i] =  vVh0[i] + 1;
        ghh[i] =  ghh[i] + 1;
        sfx[i] =  sfx[i] + 1;
        sfy[i] =  sfy[i] + 1;
        qIn[i] =  qIn[i] + 1;
        for(int j = 0; j < nEdges; ++j) {
            neighborIds[i * nEdges + j] = neighborIds[i * nEdges + j] + 1;
        }
        for(int j = 0; j < nEdges; ++j) {
            typeInterface[i * nEdges + j] = typeInterface[i * nEdges + j] + 1;
        }
    }

}

To pokazuje w rozsądnym stopniu, że przyczyną spowolnienia są chybienia w pamięci podręcznej. Należy również zauważyć, że zmienne nie są zależne, więc można łatwo utworzyć rozwiązanie wątkowe.

Przywrócono zamówienie

Jak mówi stefans, próbowałem pogrupować je w strukturę, używając oryginalnych rozmiarów. W podobny sposób usuwa to natychmiastowe obciążenie pamięci podręcznej. W rezultacie wersja c ++ (CCFLAG -O3) jest około 15% szybsza niż wersja java.

Varning nie jest ani krótki, ani ładny.

#include <vector>
#include <cmath>
#include <iostream>
 
 
 
class FloodIsolation {
    struct item{
      char floodedCells;
      char floodedCellsTimeInterval;
      double valueOfCellIds;
      double h;
      double h0;
      double vU;
      double vV;
      double vUh;
      double vVh;
      double vUh0;
      double vVh0;
      double sfx;
      double sfy;
      double qInflow;
      double qStartTime;
      double qEndTime;
      double qIn;
      double nx;
      double ny;
      double ghh;
      double floorLevels;
      int lowerFloorCells;
      char flagInterface;
      char floorCompletelyFilled;
      double cellLocationX;
      double cellLocationY;
      double cellLocationZ;
      int levelOfCell;
    };
    struct inner_item{
      int typeInterface;
      int neighborIds;
    };

    std::vector<inner_item> inner_data;
    std::vector<item> data;

public:
    FloodIsolation() :
            numberOfCells(20000), inner_data(numberOfCells * nEdges), data(numberOfCells)
   {

    }
    ~FloodIsolation(){
    }
 
    void isUpdateNeeded() {
        for (int i = 0; i < numberOfCells; ++i) {
            data[i].h = data[i].h + 1;
            data[i].floodedCells = !data[i].floodedCells;
            data[i].floodedCellsTimeInterval = !data[i].floodedCellsTimeInterval;
            data[i].qInflow = data[i].qInflow + 1;
            data[i].qStartTime = data[i].qStartTime + 1;
            data[i].qEndTime = data[i].qEndTime + 1;
            data[i].lowerFloorCells = data[i].lowerFloorCells + 1;
            data[i].cellLocationX = data[i].cellLocationX + 1;
            data[i].cellLocationY = data[i].cellLocationY + 1;
            data[i].cellLocationZ = data[i].cellLocationZ + 1;
            data[i].levelOfCell = data[i].levelOfCell + 1;
            data[i].valueOfCellIds = data[i].valueOfCellIds + 1;
            data[i].h0 = data[i].h0 + 1;
            data[i].vU = data[i].vU + 1;
            data[i].vV = data[i].vV + 1;
            data[i].vUh = data[i].vUh + 1;
            data[i].vVh = data[i].vVh + 1;
            data[i].vUh0 = data[i].vUh0 + 1;
            data[i].vVh0 = data[i].vVh0 + 1;
            data[i].ghh = data[i].ghh + 1;
            data[i].sfx = data[i].sfx + 1;
            data[i].sfy = data[i].sfy + 1;
            data[i].qIn = data[i].qIn + 1;
            for(int j = 0; j < nEdges; ++j) {
                inner_data[i * nEdges + j].neighborIds = inner_data[i * nEdges + j].neighborIds + 1;
                inner_data[i * nEdges + j].typeInterface = inner_data[i * nEdges + j].typeInterface + 1;
            }
        }
 
    }
 
    static const int nEdges;
private:
 
    const int numberOfCells;

};
 
const int FloodIsolation::nEdges = 6;

int main() {
    FloodIsolation isolation;
    clock_t start = clock();
    for (int i = 0; i < 4400; ++i) {
        if(i % 100 == 0) {
            std::cout << i << "\n";
        }
        isolation.isUpdateNeeded();
    }

    clock_t stop = clock();
    std::cout << "Time: " << difftime(stop, start) / 1000 << "\n";
}

Mój wynik różni się nieco od Jerry Coffins pod względem oryginalnych rozmiarów. Dla mnie różnica pozostaje. Może to być moja wersja java, 1.7.0_75.

Kapitanie Żyrafa
źródło
12
Dobrym pomysłem może być pogrupowanie tych danych w strukturę i posiadanie tylko jednego wektora
stefan
Cóż, jestem na telefonie komórkowym, więc nie mogę dokonywać pomiarów ;-), ale jeden wektor powinien być dobry (również pod względem przydziałów)
stefan
1
Czy korzystasz z ++pomocy w jakimkolwiek charakterze? x = x + 1wydaje się okropnie niezgrabny w porównaniu do ++x.
tadman
3
Popraw błędnie napisane słowo „wynik”. To mnie zabija ... :)
fleetC0m
1
Jeśli cały iterator mieści się w jednym rejestrze, to wykonanie kopii może w niektórych przypadkach być faktycznie szybsze niż aktualizacja na miejscu. Jeśli wykonujesz aktualizację w miejscu, dzieje się tak, ponieważ najprawdopodobniej używasz zaktualizowanej wartości zaraz potem. Więc masz zależność odczytu po zapisie. Jeśli aktualizujesz, ale potrzebujesz tylko starej wartości, operacje te nie zależą od siebie, a procesor ma więcej miejsca na wykonywanie ich równolegle, np. Na różnych potokach, zwiększając efektywne IPC.
Piotr Kołaczkowski
20

Jak zgadł @Stefan w komentarzu do odpowiedzi @ CaptainGiraffe, możesz sporo zyskać, używając wektora struktur zamiast struktury wektorów. Poprawiony kod wygląda następująco:

#include <vector>
#include <cmath>
#include <iostream>
#include <time.h>

class FloodIsolation {
public:
    FloodIsolation() :
            h(0),
            floodedCells(0),
            floodedCellsTimeInterval(0),
            qInflow(0),
            qStartTime(0),
            qEndTime(0),
            lowerFloorCells(0),
            cellLocationX(0),
            cellLocationY(0),
            cellLocationZ(0),
            levelOfCell(0),
            valueOfCellIds(0),
            h0(0),
            vU(0),
            vV(0),
            vUh(0),
            vVh(0),
            vUh0(0),
            vVh0(0),
            ghh(0),
            sfx(0),
            sfy(0),
            qIn(0),
            typeInterface(nEdges, 0),
            neighborIds(nEdges, 0)
    {
    }

    ~FloodIsolation(){
    }

    void Update() {
        h =  h + 1;
        floodedCells =  !floodedCells;
        floodedCellsTimeInterval =  !floodedCellsTimeInterval;
        qInflow =  qInflow + 1;
        qStartTime =  qStartTime + 1;
        qEndTime =  qEndTime + 1;
        lowerFloorCells =  lowerFloorCells + 1;
        cellLocationX =  cellLocationX + 1;
        cellLocationY =  cellLocationY + 1;
        cellLocationZ =  cellLocationZ + 1;
        levelOfCell =  levelOfCell + 1;
        valueOfCellIds =  valueOfCellIds + 1;
        h0 =  h0 + 1;
        vU =  vU + 1;
        vV =  vV + 1;
        vUh =  vUh + 1;
        vVh =  vVh + 1;
        vUh0 =  vUh0 + 1;
        vVh0 =  vVh0 + 1;
        ghh =  ghh + 1;
        sfx =  sfx + 1;
        sfy =  sfy + 1;
        qIn =  qIn + 1;
        for(int j = 0; j < nEdges; ++j) {
            ++typeInterface[j];
            ++neighborIds[j];
        }       
    }

private:

    static const int nEdges = 6;
    bool floodedCells;
    bool floodedCellsTimeInterval;

    std::vector<int> neighborIds;
    double valueOfCellIds;
    double h;
    double h0;
    double vU;
    double vV;
    double vUh;
    double vVh;
    double vUh0;
    double vVh0;
    double ghh;
    double sfx;
    double sfy;
    double qInflow;
    double qStartTime;
    double qEndTime;
    double qIn;
    double nx;
    double ny;
    double floorLevels;
    int lowerFloorCells;
    bool flagInterface;
    std::vector<int> typeInterface;
    bool floorCompleteleyFilled;
    double cellLocationX;
    double cellLocationY;
    double cellLocationZ;
    int levelOfCell;
};

int main() {
    std::vector<FloodIsolation> isolation(20000);
    clock_t start = clock();
    for (int i = 0; i < 400; ++i) {
        if(i % 100 == 0) {
            std::cout << i << "\n";
        }

        for (auto &f : isolation)
            f.Update();
    }
    clock_t stop = clock();
    std::cout << "Time: " << difftime(stop, start) / 1000 << "\n";
}

Skompilowany za pomocą kompilatora z VC ++ 2015 CTP, używając -EHsc -O2b2 -GL -Qpar, otrzymuję wyniki takie jak:

0
100
200
300
Time: 0.135

Kompilacja z g ++ daje wynik, który jest nieco wolniejszy:

0
100
200
300
Time: 0.156

Na tym samym sprzęcie, używając kompilatora / JVM z Java 8u45, otrzymuję wyniki takie jak:

0
100
200
300
Time: 181

Jest to około 35% wolniejsze niż wersja z VC ++ i około 16% wolniejsze niż wersja z g ++.

Jeśli zwiększymy liczbę iteracji do pożądanych 2000, różnica spadnie do zaledwie 3%, co sugeruje, że część zalet C ++ w tym przypadku to po prostu szybsze ładowanie (odwieczny problem z Javą), a nie samo wykonanie. Nie wydaje mi się to zaskakujące w tym przypadku - mierzone obliczenia (w opublikowanym kodzie) są tak trywialne, że wątpię, by większość kompilatorów mogła zrobić wiele, aby je zoptymalizować.

Jerry Coffin
źródło
1
Nadal jest miejsce na ulepszenia, chociaż najprawdopodobniej nie wpłynie to znacząco na wydajność: grupowanie zmiennych boolowskich (ogólnie grupowanie zmiennych tego samego typu).
stefan
1
@stefan: Jest, ale celowo unikałem wykonywania ciężkiej optymalizacji kodu, a zamiast tego robiłem (z grubsza) minimum niezbędne do usunięcia najbardziej oczywistych problemów z oryginalnej implementacji. Gdybym naprawdę chciał zoptymalizować, dodałbym #pragma ompi (być może) trochę pracy, aby upewnić się, że każda iteracja pętli jest niezależna. Uzyskanie przyspieszenia ~ Nx wymagałoby dość minimalnej pracy, gdzie N to liczba dostępnych rdzeni procesora.
Jerry Coffin
Słuszna uwaga. To wystarczy, aby odpowiedzieć na to pytanie
stefan
W jaki sposób 181 jednostek czasu jest 35% wolniejszych niż 0,135 jednostek czasu i 16% wolniejszych niż 0,156 jednostek czasu? Czy chodziło Ci o to, że czas trwania wersji Javy to 0.181?
jamesdlin
1
@jamesdlin: używają różnych jednostek (pozostawionych w ten sposób, ponieważ tak było w oryginale). Kod C ++ podaje czas w sekundach, ale kod Java podaje czas w milisekundach.
Jerry Coffin
9

Podejrzewam, że chodzi o alokację pamięci.

Myślę, że Javachwyta duży, ciągły blok podczas uruchamiania programu, podczas gdy C++prosi system operacyjny o bity i części w trakcie.

Aby przetestować tę teorię, wprowadziłem jedną modyfikację do C++wersji i nagle zaczęła działać nieco szybciej niż Javawersja:

int main() {
    {
        // grab a large chunk of contiguous memory and liberate it
        std::vector<double> alloc(20000 * 20);
    }
    FloodIsolation isolation;
    clock_t start = clock();
    for (int i = 0; i < 400; ++i) {
        if(i % 100 == 0) {
            std::cout << i << "\n";
        }
        isolation.isUpdateNeeded();
    }
    clock_t stop = clock();
    std::cout << "Time: " << (1000 * difftime(stop, start) / CLOCKS_PER_SEC) << "\n";
}

Środowisko wykonawcze bez wektora wstępnej alokacji:

0
100
200
300
Time: 1250.31

Środowisko wykonawcze z wektorem wstępnej alokacji:

0
100
200
300
Time: 331.214

Środowisko wykonawcze dla Javawersji:

0
100
200
300
Time: 407
Galik
źródło
Cóż, nie możesz na tym polegać. Dane w FloodIsolationmogą być nadal przydzielane gdzie indziej.
stefan
@stefan Wciąż ciekawy wynik.
Captain Giraffe
@CaptainGiraffe to jest, nie powiedziałem, że to bezużyteczne ;-)
stefan
2
@stefan Nie proponuję tego jako rozwiązania, po prostu zbadam, co moim zdaniem jest problemem. Wygląda na to, że może to nie mieć nic wspólnego z buforowaniem, ale czym różni się C ++ RTS od Javy.
Galik
1
@Galik Nie zawsze jest to przyczyna, chociaż dość interesujące jest to, że ma tak duży wpływ na Twoją platformę. Na ideone nie mogę odtworzyć twojego wyniku (wydaje się, że przydzielony blok nie jest ponownie używany): ideone.com/im4NMO Jednak wektor rozwiązania structs
stefan