C++ では、関数からベクトルを返すのは依然として悪い習慣ですか?
-
01-10-2019 - |
質問
短縮版: 多くのプログラミング言語では、ベクトルや配列などの大きなオブジェクトを返すのが一般的です。クラスに移動コンストラクターがある場合、このスタイルは 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
は右辺値であるため、 v は次の移動コンストラクターを使用して構築されます。 std::vector
, (N)RVO が発生しないと仮定します。
C++0x より前でも、(N)RVO のおかげで最初の形式は「効率的」であることがよくありました。ただし、(N)RVO はコンパイラの裁量にあります。これで右辺値参照ができました。 保証されています ディープコピーは行われません。
編集:質問は実際には最適化に関するものではありません。示されている両方の形式は、実際のプログラムではほぼ同じパフォーマンスを示します。一方、以前は、最初の形式のパフォーマンスは桁違いに悪かった可能性があります。結果として、最初の形式は、長い間、C++ プログラミングにおける主要なコード臭でした。もうそうではないでしょうか?
解決
Dave Abrahamsには、かなり包括的な分析があります 値を通過/返す速度.
短い答え、値を返す必要がある場合は、値を返します。とにかくコンパイラがそれを行うので、出力参照を使用しないでください。もちろん注意がありますので、その記事を読む必要があります。
他のヒント
少なくともIMO、それは通常貧しい考えですが、 いいえ 効率的な理由から。問題の関数は通常、イテレーターを介して出力を生成する一般的なアルゴリズムとして記述されるべきであるため、それは悪い考えです。イテレーターを操作する代わりにコンテナを受け入れるか返すコードはほとんどないと見なされる必要があります。
誤解しないでください。コレクションのようなオブジェクト(文字列など)を渡すことは理にかなっていますが、引用された例では、ベクターを貧弱なアイデアに渡すか返すことを検討します。
要点は次のとおりです。
ELISIONとRVOをコピーします できる 「恐ろしいコピー」を避けてください(コンパイラはこれらの最適化を実装する必要はありません。状況によっては適用できません)
C ++ 0x RValue参照 許可する 文字列/ベクトルの実装 保証 それ。
古いコンパイラ / STL実装を放棄できる場合は、ベクトルを自由に返します(そして、自分のオブジェクトもそれをサポートしていることを確認してください)。コードベースが「Lesser」コンパイラをサポートする必要がある場合は、古いスタイルに固執します。
残念ながら、それはあなたのインターフェイスに大きな影響を与えます。 C ++ 0xがオプションではなく、保証が必要な場合は、代わりにいくつかのシナリオで参照カウントまたはコピーオンワイトオブジェクトを使用できます。ただし、マルチスレッドの欠点があります。
(C ++での答えが1つだけでなく、簡単で簡単で、条件なしであることを願っています)。
実際、C++11 以降、 コピーする の std::vector
ほとんどの場合消えてしまいます。
ただし、コストがかかることに留意する必要があります。 建設中 新しいベクトル (その後 破壊する それ) はまだ存在しており、ベクトルの容量を再利用したい場合には、値で返す代わりに出力パラメーターを使用することが依然として便利です。これは例外として文書化されています F.20 C++ コア ガイドラインの。
比較してみましょう:
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);
}
最初の例では、多くの不必要な動的割り当て/割り当て解除が発生していますが、2 番目の例では、出力パラメータを古い方法で使用し、既に割り当てられているメモリを再利用することで防止されます。この最適化を実行する価値があるかどうかは、値の計算/変更のコストと比較した、割り当て/割り当て解除の相対コストによって決まります。
基準
の値で遊んでみましょう vecSize
そして numIter
. 。vecSize*numIter を一定に保つので、「理論上」同じ時間がかかる (= まったく同じ値で同じ数の代入と加算が行われる) ため、時間の差は次のコストからのみ発生します。割り当て、割り当て解除、およびキャッシュの有効活用。
具体的には、vecSize*numIter = 2^31 = 2147483648 を使用しましょう。16 GB の RAM があり、この数値により 8 GB 以上が割り当てられなくなり (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
(インテル i7-7700K @ 4.20GHz;16GB DDR4 2400Mhz;クブントゥ 18.04)
表記:私のプラットフォームでは mem(v) = v.size() * sizeof(int) = v.size() * 4 です。
驚くことではないが、そのとき、 numIter = 1
(つまり、mem(v) = 8GB)、時間は完全に同じです。実際、どちらの場合も、8 GB の巨大なベクトルをメモリに一度だけ割り当てているだけです。これは、BuildLargeVector1() の使用時にコピーが発生しなかったことも証明します。コピーを行うのに十分な RAM がありません。
いつ numIter = 2
, 、2 番目のベクトルを再割り当てする代わりにベクトル容量を再利用すると、1.37 倍高速になります。
いつ numIter = 256
, 、ベクトルの容量を再利用すると (ベクトルの割り当て/割り当て解除を 256 回繰り返し行う代わりに)、2.45 倍高速になります:)
time1 が次からほぼ一定であることがわかります。 numIter = 1
に numIter = 256
, これは、8 GB の 1 つの巨大なベクトルを割り当てるのは、32 MB の 256 のベクトルを割り当てるのとほぼ同じコストがかかることを意味します。ただし、8 GB の巨大なベクトルを 1 つ割り当てると、32 MB のベクトルを 1 つ割り当てるよりも明らかにコストが高くなるため、ベクトルの容量を再利用するとパフォーマンスが向上します。
から numIter = 512
(mem(v) = 16MB) から numIter = 8M
(mem(v) = 1kB) がスイート スポットです。どちらのメソッドもまったく同じ速度であり、numIter と vecSize の他のすべての組み合わせよりも高速です。これはおそらく、私のプロセッサの L3 キャッシュ サイズが 8MB であるため、ベクトルがほぼ完全にキャッシュに収まるという事実と関係があると思われます。なぜ突然のジャンプが起こったのかはよくわかりません time1
これは mem(v) = 16MB の場合ですが、その直後、mem(v) = 8MB の場合に発生する方が論理的だと思われます。驚くべきことに、このスイート スポットでは、容量を再利用しない方が実際にはわずかに高速であることに注意してください。これについては特に説明しません。
いつ numIter > 8M
物事は醜くなり始めます。どちらのメソッドも遅くなりますが、ベクトルを値で返すとさらに遅くなります。最悪の場合、ベクトルに単一のものが 1 つしか含まれていない場合、 int
, 、値によって返す代わりに容量を再利用すると、3.3 倍高速になります。おそらく、これは、malloc() の固定コストが支配的になり始めているためです。
time2 の曲線が time1 の曲線よりも滑らかであることに注目してください。ベクトル容量の再利用は一般に高速であるだけでなく、おそらくもっと重要なことは、 予測可能な.
また、スイート スポットでは、64 ビット整数の 20 億個の加算を約 0.5 秒で実行できました。これは、4.2Ghz 64 ビット プロセッサ上では非常に最適です。8 コアすべてを使用するために計算を並列化することで、より良い結果を得ることができます (上記のテストでは一度に 1 コアのみを使用します。これは、CPU 使用率を監視しながらテストを再実行することで確認しました)。最高のパフォーマンスは、mem(v) = 16kB のときに達成されます。これは、L1 キャッシュの桁違いです (i7-7700K の L1 データ キャッシュは 4x32kB です)。
もちろん、実際にデータに対して実行する必要がある計算が増えるほど、違いはますます重要でなくなります。置き換えた場合の結果は以下の通りです sum = std::accumulate(v.begin(), v.end(), sum);
による for (int k : v) sum += std::sqrt(2.0*k);
:
結論
- 値で返す代わりに出力パラメータを使用する 5月 容量を再利用することでパフォーマンスが向上します。
- 最近のデスクトップ コンピューターでは、これは大きなベクトル (>16MB) と小さなベクトル (<1kB) にのみ適用されるようです。
- 数百万または数十億の小さなベクトル (< 1kB) を割り当てることは避けてください。可能であれば、容量を再利用するか、できればアーキテクチャを別の方法で設計してください。
他のプラットフォームでは結果が異なる場合があります。いつものように、パフォーマンスが重要な場合は、特定の使用例のベンチマークを作成します。
私はまだ悪い習慣だと思いますが、私のチームがMSVC 2008とGCC 4.1を使用していることは注目に値するので、最新のコンパイラを使用していません。
以前は、MSVC 2008を使用してVtuneに表示されている多くのホットスポットが弦のコピーにかかってきました。このようなコードがありました:
String Something::id() const
{
return valid() ? m_id: "";
}
...独自の文字列タイプを使用したことに注意してください(これは、プラグインライターが異なるコンパイラを使用しているため、STD :: String/STD :: WSTRINGの異なる互換性のない実装を使用できるソフトウェア開発キットを提供しているため、これが必要でした)。
コールグラフサンプリングプロファイリングセッションに応答して、String :: String(const String&)がかなりの時間をかけることを示す簡単な変更を行いました。上記の例のような方法が最大の貢献者でした(実際、プロファイリングセッションでは、メモリの割り当てと取引が最大のホットスポットの1つであり、String Copyコンストラクターが割り当ての主要な貢献者であることを示しました)。
私が行った変更は簡単でした:
static String null_string;
const String& Something::id() const
{
return valid() ? m_id: null_string;
}
しかし、これは違いの世界を作りました!ホットスポットはその後のプロファイラーセッションで消え、これに加えて、アプリケーションのパフォーマンスを追跡するために多くの徹底的なユニットテストを行います。これらの単純な変更後、あらゆる種類のパフォーマンステスト時間が大幅に低下しました。
結論:絶対的な最新のコンパイラを使用していませんが、コンパイラが信頼できるほど(少なくともすべての場合ではない)バリューによってコピーを最適化することに依存することはできません。 MSVC 2010のような新しいコンパイラを使用している人の場合はそうではないかもしれません。C++ 0xを使用してRValue参照を使用することができることを楽しみにしています。価値によるクラス。
編集]ネイトが指摘したように、RVOは関数内で作成された一時的なリターンに適用されます。私の場合、そのような一時的なものはありませんでした(空の文字列を構築する無効な分岐を除く)。したがって、RVOは適用されませんでした。
ちょっとnitpickするには、関数から配列を返すことは多くのプログラミング言語では一般的ではありません。それらのほとんどでは、配列への参照が返されます。 C ++では、最も近い類推は戻ってきます boost::shared_array
パフォーマンスが本当の問題である場合、あなたは動きのセマンティクスがそうではないことを理解する必要があります いつも コピーよりも速い。たとえば、を使用する文字列がある場合 小さな文字列の最適化 次に、小さな文字列の場合、移動コンストラクターは通常のコピーコンストラクターとまったく同じ量の作業を行う必要があります。