在数组中，Java的速度比std :: vector快8倍。 我做错了什么？
我有以下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的不同数组。
您可以在以下链接下find两个实现：
- Java： https ： //ideone.com/R8KqjT
- C ++： https ： //ideone.com/Lu7RpE
（因为时间限制，我只能运行400次，而不是2000次），但是即使在这里也有三次的差别）
以下是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"; }
活的例子
时间现在是Java版本的两倍。 （846对1631）。
几率是JIT注意到在整个地方访问数据的caching燃烧，并将您的代码转换为逻辑上相似但更有效的顺序。
我也closures了stdio同步，因为只有当您将printf / scanf与C ++ std::cout和std::cin混合时才需要。 碰巧，你只打印出一些值，但是C ++的默认打印行为太偏执，效率低下。
如果nEdges不是一个实际的常量值，那么3个“数组”值将不得不从struct去除。 这不应该造成巨大的性能打击。
通过减less大小来sortingstruct的值，可以获得另一个性能提升，从而减less内存占用（sorting访问以及无关紧要）。 但我不确定。
经验法则是单个caching未命中比指令高100倍。 安排您的数据具有caching一致性有很多价值。
如果重新排列数据到一个struct是不可行的，你可以改变你的迭代轮stream在每个容器上。
另外请注意，Java和C ++版本在它们之间有一些细微的差别。 我看到的是，Java版本在“for each edge”循环中有3个variables，而C ++只有2个variables。我使我的匹配成为了Java。 我不知道是否有其他人。
是的，c ++版本的caching需要一个锤子。 JIT似乎更好地处理这个问题。
如果将isUpdateNeeded（）中的outer更改为更短的片段。 差异消失了。
下面的示例产生了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; } } }
这在合理的程度上表明caching未命中是缓慢的原因。 注意到这些variables不是独立的，所以很容易创build一个线程化的解决scheme。
订单已恢复
根据stefans的评论，我尝试使用原始大小将它们分组在一个结构体中。 这以类似的方式消除了即时caching压力。 结果是，c ++（CCFLAG -O3）版本比java版本快大约15％。
收益既不短也不漂亮。
#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。
正如@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
在同一个硬件上，使用来自Java 8u45的编译器/ JVM，得到如下结果：
0 100 200 300 Time: 181
这比VC ++版本慢35％左右，比g ++版本慢16％左右。
如果我们将迭代次数增加到所需的2000次，那么差异就会降低到只有3％，这意味着在这种情况下C ++的部分优势就是更快的加载速度（Java的一个长期问题），而不是真正的执行本身。 在这种情况下，这并不令我吃惊 – 被测量的计算（在发布代码中）是如此微不足道，以至于我怀疑大多数编译器可以做很多工作来优化它。
我怀疑这是关于内存分配。
我在想， Java在程序启动时会抓取一个大的连续块，而C++在操作系统中C++询问操作系统。
为了把这个理论join到testing中，我对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"; }
运行时没有预分配vector：
0 100 200 300 Time: 1250.31
运行时预分配vector：
0 100 200 300 Time: 331.214
Java版运行时：
0 100 200 300 Time: 407
