벡터 삽입

Question

, 나는에서 병목 현상을 발견했다. 다음 코드로 바꾸면 성능이 크게 향상되었습니다. 는 (. 위의 전체 시간의 10 %를 복용 한 코드는 아래의 코드는 0.34 % 소요)

vec->insert(vec->end(), buffer, buffer + len); 

문제의 벡터는 다음과 같은 유형이 있습니다 vector<char>* vec이

이 사람이 되거 수를 왜 두 번째 버전은 훨씬 빠릅니다.

첫 번째 버전에서는 공간을 예약했지만 시도가 개선되지 않았습니다.

Answer 1

벡터는 기본 저장소로 배열을 사용합니다. 따라서 자동으로 배열의 크기를 2 배로 확장 한 후 push_back과 같은 메서드를 사용하면서 배열 의 끝에 도달 할 때까지 확장합니다.

그러나 삽입의 경우 vector는 삽입 될 요소의 수를 벡터가 알고 있기 때문에 삽입하기에 충분한 저장 공간을 준비합니다. 확장이 1 회 발생한다는 의미입니다.

Answer 2

엄청난 양의 데이터가 없으면 특히 중요한 코드가 포함 된 경우 (특히이 경우 내부 코드 vector)에는 중요한 코드가 다른 코드보다 빠르게 실행되는 이유를 명확히 말하기는 정말 어렵습니다. 그러나 일반적으로 추측 할 수 있습니다.

앞서 reserve이 아무런 차이가 없으므로, 필자의 추측에 따르면 필요한 작업 수가 줄어 듭니다. 원래의 코드에서 첫 번째 근사값으로 항상 buffer에 len 인덱싱 작업을 수행하고 push_back^*을 호출하고 루프 실행으로 인해 약간의 오버 헤드가 발생합니다. 그러나 insert으로 전화하는 경우에도 마찬가지입니다. 이 함수를 순진하게 구현하면 범위 전체에서 반복자를 걷고 각 값에 대해 push_back을 호출 할 수 있습니다.이 경우 거의 동일한 성능을 기대할 수 있습니다. 그러나 더 잘 알고있는 구현은 동작이 len 바이트의 연속 된 단일 복사본을 복사하고 단일 작업으로 효과적으로 수행 할 수있는 컴퓨터 명령어를 사용한다는 것을 알 수 있습니다 (초기 버퍼 크기 너무 작다). 그러나 실제로 알 수있는 유일한 방법은 실제 표준 라이브러리 및/또는 관련된 기계 코드를 보는 것입니다.

당신이 사용하는 컴파일러는 언급하지 않았지만 VS2012에서 코드를 구현하고 추적했습니다. insert은 결국 memmove에 대한 단일 호출을 사용하여 복사본을 수행했습니다 . push_back이 및 컴파일러 설정은 인라인 될 수 있도록 인라인 함수로 구현되는 경우, 최적화가 루프 필드의 일을 가질 수 있기 때문에 *이

---

^{은 근사값이다. 이런 종류의 것은 성능에 대한 추론이 많은 구체적인 데이터없이 까다로울 수 있다고 말했을 때 내가 얻었던 것입니다.}