C ++에서 함수에서 벡터를 반환하는 것은 여전히 나쁜 습관입니까?
짧은 버전 : 많은 프로그래밍 언어에서 벡터 / 배열과 같은 큰 개체를 반환하는 것이 일반적입니다. 클래스에 이동 생성자가있는 경우이 스타일이 이제 C ++ 0x에서 허용됩니까? 아니면 C ++ 프로그래머가 이상 / 추악 / 혐오스러운 것으로 간주합니까?
긴 버전 : C ++ 0x에서 여전히 잘못된 형식으로 간주됩니까?
std::vector<std::string> BuildLargeVector();
...
std::vector<std::string> v = BuildLargeVector();
기존 버전은 다음과 같습니다.
void BuildLargeVector(std::vector<std::string>& result);
...
std::vector<std::string> v;
BuildLargeVector(v);
최신 버전에서 반환 된 값 BuildLargeVector은 rvalue이므로 std::vector(N) RVO가 발생하지 않는다고 가정 하고의 이동 생성자를 사용하여 v가 생성됩니다 .
C ++ 0x 이전에도 첫 번째 형식은 (N) RVO 때문에 종종 "효율적"이었습니다. 그러나 (N) RVO는 컴파일러의 재량에 달려 있습니다. 이제 우리를 rvalue 참조를 가지고 그것을됩니다 보장 더 깊은 복사가 발생하지 것이다.
편집 : 질문은 실제로 최적화에 관한 것이 아닙니다. 표시된 두 형식 모두 실제 프로그램에서 거의 동일한 성능을 보입니다. 반면, 과거에는 첫 번째 형식이 성능이 훨씬 더 나쁠 수있었습니다. 그 결과 첫 번째 형태는 오랫동안 C ++ 프로그래밍에서 주요 코드 냄새였습니다. 더 이상은 아니겠습니까?
Dave Abrahams는 값 전달 / 반환 속도에 대해 매우 포괄적 인 분석을 제공 합니다 .
짧은 대답, 값을 반환해야하는 경우 값을 반환합니다. 어쨌든 컴파일러가 수행하므로 출력 참조를 사용하지 마십시오. 물론주의 사항이 있으므로 해당 기사를 읽어야합니다.
적어도 IMO는 일반적으로 좋지 않지만 효율성상의 이유로는 아닙니다 . 문제의 함수는 일반적으로 반복기를 통해 출력을 생성하는 일반 알고리즘으로 작성되어야하므로 좋지 않습니다. 반복기에서 작동하는 대신 컨테이너를 수락하거나 반환하는 거의 모든 코드는 의심스러운 것으로 간주되어야합니다.
오해하지 마세요. 컬렉션과 같은 객체 (예 : 문자열)를 전달하는 것이 합리적 일 때가 있지만 인용 된 예에서는 벡터를 전달하거나 반환하는 것이 좋지 않은 생각입니다.
요점은 다음과 같습니다.
Copy Elision 및 RVO 는 "무서운 복사본"을 피할 수 있습니다 (컴파일러는 이러한 최적화를 구현하는 데 필요하지 않으며 일부 상황에서는 적용 할 수 없습니다).
C ++ 0x RValue 참조 는 이를 보장 하는 문자열 / 벡터 구현을 허용 합니다.
오래된 컴파일러 / STL 구현을 포기할 수 있다면 벡터를 자유롭게 반환하십시오 (그리고 자신의 개체도이를 지원하는지 확인하십시오). 코드베이스가 "더 적은"컴파일러를 지원해야하는 경우 이전 스타일을 고수하십시오.
불행히도 이는 인터페이스에 큰 영향을 미칩니다. C ++ 0x가 옵션이 아니고 보증이 필요한 경우 일부 시나리오에서 참조 카운트 또는 쓰기시 복사 객체를 대신 사용할 수 있습니다. 하지만 멀티 스레딩에는 단점이 있습니다.
(C ++에서 단 하나의 답변이 조건없이 간단하고 간단하기를 바랍니다.)
사실, C ++ (11) 이후의 비용 복사 는 std::vector대부분의 경우에 사라 졌어요.
그러나 새로운 벡터 를 생성 하는 비용 (그런 다음이를 파괴 )은 여전히 존재하며, 벡터의 용량을 재사용하려는 경우 값으로 반환하는 대신 출력 매개 변수를 사용하는 것이 여전히 유용하다는 점을 명심해야합니다 . 이것은 C ++ 핵심 지침의 F.20 에 예외로 문서화되어 있습니다.
비교해 봅시다 :
std::vector<int> BuildLargeVector1(size_t vecSize) {
return std::vector<int>(vecSize, 1);
}
와:
void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
v.assign(vecSize, 1);
}
이제이 메서드를 numIter타이트 루프에서 호출 하고 몇 가지 작업을 수행 해야한다고 가정 합니다. 예를 들어 모든 요소의 합을 계산해 봅시다.
를 사용 BuildLargeVector1하면 다음을 수행 할 수 있습니다.
size_t sum1 = 0;
for (int i = 0; i < numIter; ++i) {
std::vector<int> v = BuildLargeVector1(vecSize);
sum1 = std::accumulate(v.begin(), v.end(), sum1);
}
를 사용 BuildLargeVector2하면 다음을 수행 할 수 있습니다.
size_t sum2 = 0;
std::vector<int> v;
for (int i = 0; i < numIter; ++i) {
BuildLargeVector2(/*out*/ v, vecSize);
sum2 = std::accumulate(v.begin(), v.end(), sum2);
}
첫 번째 예에서는 불필요한 동적 할당 / 할당 해제가 많이 발생하며, 두 번째 예에서는 이전 방식으로 이미 할당 된 메모리를 재사용하여 출력 매개 변수를 사용하여 방지합니다. 이 최적화가 가치가 있는지 여부는 값을 계산 / 변이하는 비용과 비교하여 할당 / 할당 해제의 상대적 비용에 따라 다릅니다.
기준
vecSize및 의 값을 가지고 놀아 봅시다 numIter. vecSize * numIter를 일정하게 유지하여 "이론상"동일한 시간이 걸리고 (= 정확히 동일한 값을 가진 동일한 수의 할당 및 추가가 있음) 시간 차이는 다음 비용에서만 발생할 수 있습니다. 할당, 할당 해제 및 캐시의 더 나은 사용.
더 구체적으로, vecSize * numIter = 2 ^ 31 = 2147483648을 사용하겠습니다. 왜냐하면 16GB의 RAM이 있고이 숫자는 8GB 이하가 할당되도록 보장하기 때문입니다 (sizeof (int) = 4). 다른 모든 프로그램은 닫 혔고 테스트를 실행할 때 15GB를 사용할 수있었습니다.)
다음은 코드입니다.
#include <chrono>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
class Timer {
using clock = std::chrono::steady_clock;
using seconds = std::chrono::duration<double>;
clock::time_point t_;
public:
void tic() { t_ = clock::now(); }
double toc() const { return seconds(clock::now() - t_).count(); }
};
std::vector<int> BuildLargeVector1(size_t vecSize) {
return std::vector<int>(vecSize, 1);
}
void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
v.assign(vecSize, 1);
}
int main() {
Timer t;
size_t vecSize = size_t(1) << 31;
size_t numIter = 1;
std::cout << std::setw(10) << "vecSize" << ", "
<< std::setw(10) << "numIter" << ", "
<< std::setw(10) << "time1" << ", "
<< std::setw(10) << "time2" << ", "
<< std::setw(10) << "sum1" << ", "
<< std::setw(10) << "sum2" << "\n";
while (vecSize > 0) {
t.tic();
size_t sum1 = 0;
{
for (int i = 0; i < numIter; ++i) {
std::vector<int> v = BuildLargeVector1(vecSize);
sum1 = std::accumulate(v.begin(), v.end(), sum1);
}
}
double time1 = t.toc();
t.tic();
size_t sum2 = 0;
{
std::vector<int> v;
for (int i = 0; i < numIter; ++i) {
BuildLargeVector2(/*out*/ v, vecSize);
sum2 = std::accumulate(v.begin(), v.end(), sum2);
}
} // deallocate v
double time2 = t.toc();
std::cout << std::setw(10) << vecSize << ", "
<< std::setw(10) << numIter << ", "
<< std::setw(10) << std::fixed << time1 << ", "
<< std::setw(10) << std::fixed << time2 << ", "
<< std::setw(10) << sum1 << ", "
<< std::setw(10) << sum2 << "\n";
vecSize /= 2;
numIter *= 2;
}
return 0;
}
결과는 다음과 같습니다.
$ g++ -std=c++11 -O3 main.cpp && ./a.out
vecSize, numIter, time1, time2, sum1, sum2
2147483648, 1, 2.360384, 2.356355, 2147483648, 2147483648
1073741824, 2, 2.365807, 1.732609, 2147483648, 2147483648
536870912, 4, 2.373231, 1.420104, 2147483648, 2147483648
268435456, 8, 2.383480, 1.261789, 2147483648, 2147483648
134217728, 16, 2.395904, 1.179340, 2147483648, 2147483648
67108864, 32, 2.408513, 1.131662, 2147483648, 2147483648
33554432, 64, 2.416114, 1.097719, 2147483648, 2147483648
16777216, 128, 2.431061, 1.060238, 2147483648, 2147483648
8388608, 256, 2.448200, 0.998743, 2147483648, 2147483648
4194304, 512, 0.884540, 0.875196, 2147483648, 2147483648
2097152, 1024, 0.712911, 0.716124, 2147483648, 2147483648
1048576, 2048, 0.552157, 0.603028, 2147483648, 2147483648
524288, 4096, 0.549749, 0.602881, 2147483648, 2147483648
262144, 8192, 0.547767, 0.604248, 2147483648, 2147483648
131072, 16384, 0.537548, 0.603802, 2147483648, 2147483648
65536, 32768, 0.524037, 0.600768, 2147483648, 2147483648
32768, 65536, 0.526727, 0.598521, 2147483648, 2147483648
16384, 131072, 0.515227, 0.599254, 2147483648, 2147483648
8192, 262144, 0.540541, 0.600642, 2147483648, 2147483648
4096, 524288, 0.495638, 0.603396, 2147483648, 2147483648
2048, 1048576, 0.512905, 0.609594, 2147483648, 2147483648
1024, 2097152, 0.548257, 0.622393, 2147483648, 2147483648
512, 4194304, 0.616906, 0.647442, 2147483648, 2147483648
256, 8388608, 0.571628, 0.629563, 2147483648, 2147483648
128, 16777216, 0.846666, 0.657051, 2147483648, 2147483648
64, 33554432, 0.853286, 0.724897, 2147483648, 2147483648
32, 67108864, 1.232520, 0.851337, 2147483648, 2147483648
16, 134217728, 1.982755, 1.079628, 2147483648, 2147483648
8, 268435456, 3.483588, 1.673199, 2147483648, 2147483648
4, 536870912, 5.724022, 2.150334, 2147483648, 2147483648
2, 1073741824, 10.285453, 3.583777, 2147483648, 2147483648
1, 2147483648, 20.552860, 6.214054, 2147483648, 2147483648
(Intel i7-7700K @ 4.20GHz, 16GB DDR4 2400Mhz, Kubuntu 18.04)
표기법 : mem (v) = v.size () * sizeof (int) = v.size () * 4 on my platform.
당연히 numIter = 1(즉, mem (v) = 8GB) 시간이 완벽하게 동일합니다. 실제로 두 경우 모두 메모리에 8GB의 거대한 벡터를 한 번만 할당합니다. 이것은 또한 BuildLargeVector1 ()을 사용할 때 복사가 발생하지 않았 음을 증명합니다. 복사를 수행하기에 충분한 RAM이 없을 것입니다!
When numIter = 2, reusing the vector capacity instead of re-allocating a second vector is 1.37x faster.
When numIter = 256, reusing the vector capacity (instead of allocating/deallocating a vector over and over again 256 times...) is 2.45x faster :)
We can notice that time1 is pretty much constant from numIter = 1 to numIter = 256, which means that allocating one huge vector of 8GB is pretty much as costly as allocating 256 vectors of 32MB. However, allocating one huge vector of 8GB is definitly more expensive than allocating one vector of 32MB, so reusing the vector's capacity provides performance gains.
From numIter = 512 (mem(v) = 16MB) to numIter = 8M (mem(v) = 1kB) is the sweet spot: both methods are exactly as fast, and faster than all other combinations of numIter and vecSize. This probably has to do with the fact that the L3 cache size of my processor is 8MB, so that the vector pretty much fits completely in cache. I don't really explain why the sudden jump of time1 is for mem(v) = 16MB, it would seem more logical to happen just after, when mem(v) = 8MB. Note that surprisingly, in this sweet spot, not re-using capacity is in fact slightly faster! I don't really explain this.
When numIter > 8M things start to get ugly. Both methods get slower but returning the vector by value gets even slower. In the worst case, with a vector containing only one single int, reusing capacity instead of returning by value is 3.3x faster. Presumably, this is due to the fixed costs of malloc() which start to dominate.
Note how the curve for time2 is smoother than the curve for time1: not only re-using vector capacity is generally faster, but perhaps more importantly, it is more predictable.
Also note that in the sweet spot, we were able to perform 2 billion additions of 64bit integers in ~0.5s, which is quite optimal on a 4.2Ghz 64bit processor. We could do better by parallelizing the computation in order to use all 8 cores (the test above only uses one core at a time, which I have verified by re-running the test while monitoring CPU usage). The best performance is achieved when mem(v) = 16kB, which is the order of magnitude of L1 cache (L1 data cache for the i7-7700K is 4x32kB).
Of course, the differences become less and less relevant the more computation you actually have to do on the data. Below are the results if we replace sum = std::accumulate(v.begin(), v.end(), sum); by for (int k : v) sum += std::sqrt(2.0*k);:
Conclusions
- Using output parameters instead of returning by value may provide performance gains by re-using capacity.
- On a modern desktop computer, this seems only applicable to large vectors (>16MB) and small vectors (<1kB).
- Avoid allocating millions/billions of small vectors (< 1kB). If possible, re-use capacity, or better yet, design your architecture differently.
Results may differ on other platforms. As usual, if performance matters, write benchmarks for your specific use case.
I still think it is a bad practice but it's worth noting that my team uses MSVC 2008 and GCC 4.1, so we're not using the latest compilers.
Previously a lot of the hotspots shown in vtune with MSVC 2008 came down to string copying. We had code like this:
String Something::id() const
{
return valid() ? m_id: "";
}
... note that we used our own String type (this was required because we're providing a software development kit where plugin writers could be using different compilers and therefore different, incompatible implementations of std::string/std::wstring).
I made a simple change in response to the call graph sampling profiling session showing String::String(const String&) to be taking up a significant amount of time. Methods like in the above example were the greatest contributors (actually the profiling session showed memory allocation and deallocation to be one of the biggest hotspots, with the String copy constructor being the primary contributor for the allocations).
The change I made was simple:
static String null_string;
const String& Something::id() const
{
return valid() ? m_id: null_string;
}
Yet this made a world of difference! The hotspot went away in subsequent profiler sessions, and in addition to this we do a lot of thorough unit testing to keep track of our application performance. All kinds of performance test times dropped significantly after these simple changes.
Conclusion: we're not using the absolute latest compilers, but we still can't seem to depend on the compiler optimizing away the copying for returning by value reliably (at least not in all cases). That may not be the case for those using newer compilers like MSVC 2010. I'm looking forward to when we can use C++0x and simply use rvalue references and not ever have to worry that we're pessimizing our code by returning complex classes by value.
[Edit] As Nate pointed out, RVO applies to returning temporaries created inside of a function. In my case, there were no such temporaries (except for the invalid branch where we construct an empty string) and thus RVO would not have been applicable.
Just to nitpick a little: it is not common in many programming languages to return arrays from functions. In most of them, a reference to array is returned. In C++, the closest analogy would be returning boost::shared_array
If performance is a real issue you should realise that move semantics aren't always faster than copying. For example if you have a string that uses the small string optimization then for small strings a move constructor must do the exact same amount of work as a regular copy constructor.
'Programing' 카테고리의 다른 글
| 모든 프로젝트와 하위 프로젝트의 차이점은 무엇입니까 (0) | 2020.08.16 |
|---|---|
| 카나리아 릴리스 전략 vs. 블루 / 그린 (0) | 2020.08.16 |
| Spring Security / SpringMVC에서 인증 된 사용자를 수동으로 설정하는 방법 (0) | 2020.08.16 |
| Rust에서 'let x = x'는 무엇을합니까? (0) | 2020.08.16 |
| 정적 메서드와 인스턴스 메서드의 성능 (0) | 2020.08.16 |