Java в 8 раз быстрее работает с массивами, чем std :: vector в C ++. Что я сделал не так?

88

У меня есть следующий код Java с несколькими большими массивами, которые никогда не меняют своего размера. На моем компьютере он работает за 1100 мс.

Я реализовал тот же код на C ++ и использовал std::vector.

Время реализации C ++, которая запускает тот же самый код, составляет 8800 мс на моем компьютере. Что я сделал не так, что так медленно работает?

В основном код делает следующее:

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

Он выполняет итерацию по различным массивам размером около 20000.

Вы можете найти обе реализации по следующим ссылкам:

(На ideone я мог запустить цикл только 400 раз вместо 2000 из-за ограничения по времени. Но даже здесь есть разница в три раза)

java c++ arrays performance stdvector РобинXSI
источник
42
std::vector<bool>использует один бит на элемент для экономии места, что приводит к большому смещению битов. Если вы хотите скорости, держитесь от нее подальше. std::vector<int>Вместо этого используйте .
molbdnilo
44
@molbdnilo Или std :: vector <char>. Там нет необходимости тратить что много ;-)
стефановского
7
Как ни странно. Версия c ++ работает быстрее, когда количество ячеек равно 200. Расположение кеша?
Captain Giraffe
9
Часть II: вам было бы намного лучше создать отдельный класс / структуру, содержащую по одному из каждого члена массивов, а затем иметь один массив объектов этой структуры, потому что тогда вы фактически выполняете итерацию по памяти только один раз, в Одно направление.
Timo Geusch
9
@TimoGeusch: Хотя я думаю, что h[i] += 1;or (что еще лучше) ++h[i]более читабельно h[i] = h[i] + 1;, я был бы несколько удивлен, увидев значительную разницу в скорости между ними. Компилятор может «выяснить», что они оба делают одно и то же, и в любом случае сгенерировать один и тот же код (по крайней мере, в большинстве распространенных случаев).
Джерри Коффин

Ответы:

36

Вот версия C ++ с данными для каждого узла, собранными в структуру, и одним используемым вектором этой структуры:

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

живой пример

Время теперь в 2 раза быстрее, чем у версии Java. (846 против 1631).

Скорее всего, JIT заметила, что кеш-память доступа к данным повсюду, и преобразовала ваш код в логически похожий, но более эффективный порядок.

Я также отключил синхронизацию stdio, так как она нужна только если вы смешиваете printf/ scanfс C ++ std::coutи std::cin. Как это бывает, вы распечатываете только несколько значений, но поведение C ++ по умолчанию для печати чрезмерно параноидально и неэффективно.

Если nEdgesэто не фактическое постоянное значение, тогда 3 значения «массива» должны быть удалены из struct. Это не должно сильно сказаться на производительности.

Возможно, вы сможете получить еще один прирост производительности, отсортировав значения в нем, structуменьшив размер, тем самым уменьшив объем памяти (а также доступ к сортировке, когда это не имеет значения). Но я не уверен.

Практическое правило состоит в том, что один промах в кэше в 100 раз дороже, чем инструкция. Обеспечение согласованности данных в кэше имеет большое значение.

Если преобразование данных в a structневозможно, вы можете изменить итерацию, чтобы она проходила по каждому контейнеру по очереди.

Кстати, обратите внимание, что версии для Java и C ++ имели некоторые тонкие различия. Я заметил, что версия для Java имеет 3 переменные в цикле «для каждого края», а в C ++ - только 2. Я сделал свою версию такой же, как у Java. Не знаю, есть ли другие.

Якк - Адам Неврамонт
источник
44

Да, кеш в версии c ++ требует больших усилий. Кажется, что JIT лучше справляется с этим.

Если вы измените внешний вид forв isUpdateNeeded () на более короткие фрагменты. Разница уходит.

Пример ниже дает 4-кратное ускорение.

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

}

Это в достаточной степени показывает, что промахи в кэше являются причиной замедления. Также важно отметить, что переменные не зависят, поэтому легко создать многопоточное решение.

Заказ восстановлен

В соответствии с комментарием Стефана я попытался сгруппировать их в структуру, используя исходные размеры. Это устраняет непосредственное давление кеша аналогичным образом. В результате версия c ++ (CCFLAG -O3) примерно на 15% быстрее, чем версия java.

Варнинг ни короткий, ни красивый.

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

Мой результат немного отличается от Jerry Coffins по исходным размерам. Для меня различия остаются. Это вполне может быть моя версия java, 1.7.0_75.

Капитан жираф
источник
12
Было бы неплохо сгруппировать эти данные в структуру и иметь только один вектор
Стефан
Ну, я на мобильном телефоне, поэтому я не могу проводить измерения ;-), но один вектор должен быть хорош (также с точки зрения распределения)
Стефан
1
Использует ли ++помощь в каком-либо качестве? x = x + 1кажется ужасно неуклюжим по сравнению с ++x.
tadman
3
Исправьте слово с ошибкой "результат". Это меня убивает .. :)
fleetC0m
1
Если весь итератор помещается в один регистр, то создание копии в некоторых случаях может быть на самом деле быстрее, чем обновление на месте. Если вы выполняете обновление на месте, это связано с тем, что вы, скорее всего, используете обновленное значение сразу после этого. Итак, у вас есть зависимость чтения после записи. Если вы обновляете, но вам нужно только старое значение, эти операции не зависят друг от друга, и у ЦП есть больше места для их параллельного выполнения, например, на разных конвейерах, что увеличивает эффективный IPC.
Петр Колачковский
20

Как догадался @Stefan в комментарии к ответу @ CaptainGiraffe, вы получите довольно много, используя вектор структур вместо структуры векторов. Исправленный код выглядит так:

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

Скомпилировано компилятором из VC ++ 2015 CTP, используя -EHsc -O2b2 -GL -Qpar, получаю такие результаты, как:

0
100
200
300
Time: 0.135

Компиляция с помощью g ++ дает немного более медленный результат:

0
100
200
300
Time: 0.156

На том же оборудовании, используя компилятор / JVM из Java 8u45, я получаю такие результаты, как:

0
100
200
300
Time: 181

Это примерно на 35% медленнее, чем версия из VC ++, и примерно на 16% медленнее, чем версия из g ++.

Если мы увеличим количество итераций до желаемых 2000, разница упадет до 3%, что говорит о том, что частью преимущества C ++ в этом случае является просто более быстрая загрузка (постоянная проблема с Java), а не само выполнение. В данном случае это не кажется мне удивительным - вычисление, которое измеряется (в опубликованном коде), настолько тривиально, что я сомневаюсь, что большинство компиляторов могут многое сделать для его оптимизации.

Джерри Гроб
источник
1
Еще есть возможности для улучшения, хотя это, скорее всего, не повлияет существенно на производительность: группировка логических переменных (в общем группировка переменных одного типа).
Стефан
1
@stefan: Есть, но я намеренно избегал какой-либо серьезной оптимизации кода, а вместо этого делал (примерно) минимум, необходимый для устранения наиболее очевидных проблем в исходной реализации. Если бы я действительно хотел оптимизировать, я бы добавил #pragma ompи (возможно) немного поработал, чтобы гарантировать независимость каждой итерации цикла. Это потребует минимальных усилий, чтобы получить ускорение ~ Nx, где N - количество доступных ядер процессора.
Джерри Коффин
Хорошая точка зрения. Этого вполне достаточно для ответа на этот вопрос
Стефан
Как 181 единица времени на 35% медленнее 0,135 единицы времени и на 16% медленнее 0,156 единицы времени? Вы имели в виду, что продолжительность Java-версии 0.181?
jamesdlin
1
@jamesdlin: они используют разные единицы (оставлены такими, потому что так было в оригинале). Код C ++ показывает время в секундах, а код Java дает время в миллисекундах.
Джерри Коффин
9

Я подозреваю, что дело в распределении памяти.

Я думаю, что Javaпри запуске программы захватывает большой непрерывный блок, в то C++время как при запуске запрашивает у ОС бит и куски.

Чтобы проверить эту теорию, я внес одну модификацию в C++версию, и она внезапно стала работать немного быстрее, чем Javaверсия:

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

Время выполнения без вектора предварительного выделения:

0
100
200
300
Time: 1250.31

Среда выполнения с вектором предварительного выделения:

0
100
200
300
Time: 331.214

Время выполнения для Javaверсии:

0
100
200
300
Time: 407
Галик
источник
Ну, на это нельзя полагаться. Данные в FloodIsolationмогут быть размещены в другом месте.
Стефан
@stefan Еще интересный результат.
Captain Giraffe
@CaptainGiraffe, я не говорил, что это бесполезно ;-)
Стефан
2
@stefan Я не предлагаю это как решение, просто исследую, в чем, по моему мнению, проблема. Кажется, это может не иметь ничего общего с кешированием, но чем C ++ RTS отличается от Java.
Галик
1
@Galik Это не всегда причина, хотя довольно интересно наблюдать, как это оказывает такое большое влияние на вашу платформу. На ideone я не могу воспроизвести ваш результат (похоже, выделенный блок не используется повторно): ideone.com/im4NMO Однако решение вектора структур оказывает более последовательное влияние на производительность: ideone.com/b0VWSN
stefan