std :: pair vs struct 두 개의 int 's

StackOverflow https://stackoverflow.com/questions/1606894

  •  05-07-2019
  •  | 
  •  

문제

ACM 예에서는 동적 프로그래밍을위한 큰 테이블을 만들어야했습니다. 각 셀에 두 개의 정수를 저장해야했기 때문에 std::pair<int, int>. 그러나 많은 배열을 할당하는 데 1.5 초가 걸렸습니다.

std::pair<int, int> table[1001][1001];

그 후이 코드를 변경했습니다

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

그리고 할당은 0 초가 걸렸습니다.

시간 의이 큰 차이를 설명하는 것은 무엇입니까?

도움이 되었습니까?

해결책

std::pair<int, int>::pair() 생성자는 기본값으로 필드를 초기화합니다 ( int) 그리고 당신의 struct Cell (아무것도하지 않는 자동 생성 기본 생성자 만 가지고 있기 때문에).

초기화에는 비교적 시간이 많이 걸리는 많은 메모리 액세스가 필요한 각 필드에 쓰기가 필요합니다. 와 함께 struct Cell 대신 아무 일도하지 않고 아무것도하지 않는 것이 조금 더 빠릅니다.

다른 팁

지금까지 답은 문제의 전체 크기를 설명하지 않습니다.

Sharptooth가 지적했듯이 쌍 솔루션은 값을 0으로 초기화합니다. Lemurik이 지적했듯이, 쌍 솔루션은 인접한 메모리 블록을 초기화하는 것이 아니라 대신 테이블의 모든 요소에 대해 쌍 생성자를 호출합니다. 그러나 그조차도 1.5 초가 걸리는 것을 설명하지 않습니다. 다른 일이 일어나고 있습니다.

내 논리는 다음과 같습니다.

고대 기계에 있다고 가정하면 1.33GHz에서 달리는 것은 1.5 초가 2E9 클럭 사이클이라고 가정합니다. 건설 할 2E6 쌍이있어서 각 쌍 생성자가 1000 사이클을 겪고 있습니다. 두 개의 정수를 0으로 설정하는 생성자를 호출하는 데 1000 사이클이 걸리지 않습니다. 캐시가 어떻게 그리워하는지 알 수 없습니다. 숫자가 100 사이클 미만이라면 믿을 것입니다.

나는이 모든 CPU 사이클이 어디로 가고 있는지 보는 것이 흥미로울 것이라고 생각했다. 가장 오래된 C ++ 컴파일러를 사용하여 필요한 낭비 수준을 얻을 수 있는지 확인할 수있었습니다. 그 컴파일러는 vc ++ v6입니다. 디버그 모드에서는 이해하지 못하는 일을합니다. 테이블의 각 항목에 대한 쌍 생성자를 호출하는 큰 루프가 있습니다. 해당 생성자는 두 값을 0으로 설정합니다. 그러나 그렇게 직전에 68 바이트 영역의 모든 바이트를 0xcc로 설정합니다. 그 지역은 큰 테이블이 시작되기 직전에 있습니다. 그런 다음 해당 영역의 마지막 요소를 0x28F61200으로 덮어 씁니다. 쌍 생성자의 모든 호출은 이것을 반복합니다. 아마도 이것은 컴파일러에 의한 일종의 도서 유지이므로 런타임에 포인터 오류를 확인할 때 어떤 영역이 초기화되는지 알고 있습니다. 나는 이것이 무엇인지 정확히 알고 싶습니다.

어쨌든, 그것은 여분의 시간이 어디로 가고 있는지 설명 할 것입니다. 분명히 다른 컴파일러는 이렇게 나쁘지 않을 수 있습니다. 그리고 확실히 최적화 된 릴리스 빌드는 그렇지 않을 것입니다.

내 생각에 그것은 std :: 쌍이 만들어지는 방식이라고 생각합니다. 메모리 범위를 할당 할 때보 다 쌍 생성자를 1001x1001로 호출하는 동안 더 많은 오버 헤드가 있습니다.

이것들은 모두 아주 좋은 추측이지만 모두가 알고 있듯이 추측은 신뢰할 수 없습니다.

나는 단지 무작위로 말할 것입니다 일시 중지하십시오 그 1.5 초 안에, 당신은 꽤 빨리해야합니다. 각 차원을 약 3 배로 늘리면 10 초 이상이 걸리면 잠시 멈추는 것이 더 쉬워집니다.

또는 디버거 아래에서 가져 와서 쌍 생성자 코드로 분해 한 다음 단일 단계를 수행하여 수행하는 작업을 확인할 수 있습니다.

어느 쪽이든, 당신은 단순히 추측이 아니라 질문에 대한 확고한 답변을 얻을 것입니다.

C ++를 작성하고 STL을 신중하게 사용해야하는 것은 정말 좋은 예입니다. 이견있는 사람?

내 프로젝트는 C & C ++ 코드 레벨 벤치 마크 테스트 도구를 사용하여 "좋은"코드와 "나쁜"코딩 습관이 무엇인지 알아 내기 위해 많은 코드 샘플을 만들 것입니다. 보다 http://effodevel.googlecode.com C9B.M.에 대해 자세히 알아 보려면 계획. 그러한 경우를 많이 경험했다면 누구나 우리를 도와주기 위해 프로젝트에 참여하십시오.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top