크기를 변경하지 않는 몇 개의 큰 배열이있는 다음 Java 코드가 있습니다. 내 컴퓨터에서 1100ms에 실행됩니다.
C ++에서 동일한 코드를 구현하고 std::vector
.
똑같은 코드를 실행하는 C ++ 구현 시간은 내 컴퓨터에서 8800ms입니다. 내가 뭘 잘못 했나요? 이렇게 느리게 실행 되나요?
기본적으로 코드는 다음을 수행합니다.
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 크기의 다른 배열을 반복합니다.
다음 링크에서 두 가지 구현을 모두 찾을 수 있습니다.
- 자바 : https://ideone.com/R8KqjT
- C ++ : https://ideone.com/Lu7RpE
(ideone에서는 시간 제한으로 인해 2000 번이 아닌 400 번만 루프를 실행할 수 있었지만 여기에서도 세 번의 차이가 있습니다)
답변
다음은 노드 별 데이터가 구조로 수집되고 해당 구조의 단일 벡터가 사용 된 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 버전의 2 배입니다. (846 대 1631).
확률은 JIT가 모든 곳에서 데이터에 액세스하는 캐시 굽기를 발견하고 코드를 논리적으로 유사하지만 더 효율적인 순서로 변환했습니다.
당신이 혼합하는 경우 그에만 필요로 또한, 표준 입출력 동기화를 끌 printf
/ scanf
C ++로 std::cout
와 std::cin
. 발생하는대로 몇 가지 값만 인쇄하지만 C ++의 기본 인쇄 동작은 지나치게 편집증적이고 비효율적입니다.
이 nEdges
실제 상수 값이 아닌 경우 3 개의 “배열”값을 struct
. 그것은 큰 성능 저하를 일으키지 않아야합니다.
struct
크기를 줄임으로써 값을 정렬하여 메모리 풋 프린트를 줄임으로써 (그리고 중요하지 않은 경우 액세스도 정렬하여) 또 다른 성능 향상을 얻을 수 있습니다 . 하지만 확실하지 않습니다.
경험상 단일 캐시 미스가 명령어보다 100 배 더 비쌉니다. 캐시 일관성을 갖도록 데이터를 배열하는 것은 많은 가치가 있습니다.
데이터를 a로 재배 열하는 struct
것이 불가능한 경우 각 컨테이너에 대해 차례로 반복하도록 변경할 수 있습니다.
제쳐두고 Java 및 C ++ 버전에는 약간의 미묘한 차이가 있습니다. 내가 발견 한 것은 Java 버전은 “for each edge”루프에 3 개의 변수가있는 반면 C ++ 버전에는 2 개만 있었다는 것입니다. 저는 Java와 일치하도록 만들었습니다. 다른 사람이 있는지 모르겠습니다.
답변
예, 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;
}
}
}
이것은 캐시 미스가 속도 저하의 원인이라는 것을 합리적으로 보여줍니다. 또한 변수가 종속적이지 않으므로 스레드 솔루션을 쉽게 만들 수 있다는 점에 유의해야합니다.
주문이 복원되었습니다.
stefans 의견에 따라 원래 크기를 사용하여 구조체로 그룹화하려고했습니다. 이것은 유사한 방식으로 즉각적인 캐시 압력을 제거합니다. 그 결과 c ++ (CCFLAG -O3) 버전이 자바 버전보다 약 15 % 빠릅니다.
짧지도 예쁘지도 않은 Varning.
#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와 약간 다릅니다. 나에게는 차이점이 남아 있습니다. 내 자바 버전 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++
OS에 비트와 조각을 요청하는 것으로 생각하고 있습니다.
이 이론을 테스트하기 위해 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