Java в 8 раз быстрее с массивами, чем std::vector в С++. Что я сделал не так?
У меня есть следующий код Java с несколькими большими массивами, которые никогда не меняют свой размер. Он работает через 1100 мс на моем компьютере.
Я реализовал тот же код в С++ и использовал std::vector.
Время реализации С++, которое работает с одним и тем же кодом, составляет 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 раз из-за ограничения по времени, но даже здесь есть разница три раза)
Ответы
Ответ 1
Вот версия С++ с данными per-w630 > , собранными в структуру, и используется один вектор этой структуры:
#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";
}
живой пример
Время теперь составляет 2x скорости Java-версии. (846 против 1631).
Скорее всего, JIT заметил, что кэш-память с доступом к данным повсюду и преобразовал ваш код в логически схожий, но более эффективный порядок.
Я также отключил синхронизацию stdio, поскольку это необходимо, только если вы смешиваете printf/scanf с С++ std::cout и std::cin. Так как это происходит, вы печатаете только несколько значений, но поведение по умолчанию для С++ для печати слишком параноидально и неэффективно.
Если nEdges не является фактическим постоянным значением, тогда значения 3 "массива" должны быть удалены из struct. Это не должно приводить к огромному результату.
Возможно, вам удастся повысить производительность, сортируя значения в struct, уменьшая размер, тем самым уменьшая объем памяти (а также доступ к сортировке, когда это не имеет значения). Но я не уверен.
Эмпирическое правило состоит в том, что один промах кеша в 100 раз дороже, чем инструкция. Учет данных для обеспечения согласованности кеша имеет большую ценность.
Если переупорядочить данные в struct невозможно, вы можете поменять свою итерацию на каждый контейнер по очереди.
В качестве примечания обратите внимание, что версии Java и С++ имели в них некоторые тонкие различия. Единственное, что я заметил, это то, что версия Java имеет 3 переменные в цикле "для каждого края", а у С++ - только 2. Я сделал мое соответствие Java. Я не знаю, есть ли другие.
Ответ 2
Да, кеш в версии С++ забивает. Кажется, 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;
}
}
}
Это показывает в разумной степени, что промахи в кэше являются причиной замедления. Также важно отметить, что переменные не зависят, поэтому легко создавать потоковое решение.
Восстановленный заказ
В соответствии с комментарием stefans я попытался группировать их в структуру с использованием исходных размеров. Аналогичным образом удаляется непосредственное давление в кеше. В результате версия С++ (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.
Ответ 3
Как @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";
}
Скомпилированный с помощью компилятора из CTP VС++ 2015, используя -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% медленнее, чем версия VС++, и примерно на 16% медленнее, чем версия из g++.
Если мы увеличим количество итераций до желаемого 2000, разница снизится до 3%, что говорит о том, что часть преимущества С++ в этом случае - это просто более быстрая загрузка (многолетняя проблема с Java), а не на самом деле сам. Это не удивляет меня в этом случае - вычисление, измеряемое (в размещенном коде), настолько тривиально, что я сомневаюсь, что большинство компиляторов могут сделать многое для его оптимизации.
Ответ 4
Я подозреваю, что это касается выделения памяти.
Я думаю, что 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
Время выполнения с вектором preallocating:
0
100
200
300
Time: 331.214
Время выполнения для версии Java:
0
100
200
300
Time: 407
