問題タブ [stack-allocation]

私が通常使用する C++ コンパイラでは可変長配列 (実行時のサイズに応じた配列など) が許可されているためstd::array、可変サイズのようなものがあるのだろうか? もちろんstd::vector可変サイズですが、ヒープに割り当て、必要に応じて再割り当てします。

実行時にサイズが定義されたスタック割り当て配列が好きです。これを特徴とするテンプレートはありますstdか? たぶんstd::vector、固定最大サイズで使用していますか？

約 10 年前のプロジェクトで、std::vectorの動的割り当てが深刻なパフォーマンスの低下を引き起こしていることがわかりました。この場合、多くの小さなベクトルが割り当てられたので、迅速な解決策は、charその容量の未加工ストレージとして使用されるスタックベースの事前割り当て配列をラップするベクトルのようなクラスを作成することでした。結果はstatic_vector<typename T, std::size_t Max>. いくつかの基本を知っていれば、そのようなことは簡単に書くことができ、ウェブ上でそのような獣をかなり見つけることができます. 実際、現在、 boost にも 1 つがあります。

現在、組み込みプラットフォームで作業していると、たまたまstatic_basic_string. これは、スタックに固定最大量のメモリを事前に割り当て、それを容量として使用する文字列です。

static_vector最初は、これはかなり簡単なはずだと思っていました (結局のところ、既存の に基づいている可能性があります) std::basic_string。std::vectorのインターフェースよりもはるかに複雑です。特に、付属の一連のfind()関数を実装するstd::basic_stringことは、単なる面倒な作業ではありません。

そこで改めて考えさせられました。結局のところ、これがアロケーターが作成された目的です: に基づいて、newおよびdelete他の手段で割り当てを置き換えます。ただし、アロケータ インターフェイスが扱いにくいと言うのは控えめな表現です。それを説明する記事がいくつかありますが、過去 15 年間に自作のアロケータがほとんど見られなかったのには理由があります。

だからここに私の質問があります：

類似を実装する必要がbasic_stringあるとしたら、どのように実装しますか?

• 自分で書くstatic_basic_string？
• に渡すアロケーターを作成しますstd::basic_stringか?
• 私が考えていなかった何かをしますか？
• 私が気付いていないブーストから何かを使用しますか?

^{いつものように、かなり重要な制限があります。組み込みプラットフォーム上にあるため、GCC 4.1.2 に縛られているため、C++03、TR1、およびブースト 1.52 のみを使用できます。}

一部のオブジェクトがより静的な動作をする可能性があるというコンパイラのヒントを与え、ヒープではなくスタックに割り当てる方法はありますか? たとえば、文字列オブジェクトは、一部の関数内で一種の一定サイズを持つ場合があります。OpenMP を使用してアプリケーションのパフォーマンスを向上させようとしているので、これを尋ねています。私はすでにシリアル部分を 50 秒から 20 秒に改善しており、並列処理を行うと 12 秒になります (ほとんどのコードは並列で実行できることに言及しています)。改善を続けようとしています。1 つの制限は、同じプロセス内での動的メモリの連続的な割り当てと解放に関連していると思います。これまでの逐次最適化は、よりハードコードされた変数の割り当て (動的に割り当てられ、ただし、最悪のシナリオを考慮すると、すべてが一度に割り当てられます)。多くの C++ アプローチを持つコードの一部に到達したため、今はかなり行き詰まっています。

可変長配列 (VLA) を多用する C99 コードを C++ に移植しています。

VLA (スタック割り当て) を、ヒープにメモリを割り当てる配列クラスに置き換えました。パフォーマンスへの影響は大きく、3.2 倍の速度低下でした (以下のベンチマークを参照)。 C++ で使用できる高速な VLA の置き換えは何ですか? 私の目標は、C++ のコードを書き直すときにパフォーマンスへの影響を最小限に抑えることです。

私に提案された 1 つのアイデアは、クラス内に固定サイズのストレージを含む (つまり、スタック割り当て可能) 配列クラスを作成し、それを小さな配列に使用し、大きな配列のヒープ割り当てに自動的に切り替えることでした。これの私の実装は、投稿の最後にあります。これはかなりうまく機能しますが、元の C99 コードのパフォーマンスにはまだ達していません。それに近づくには、この固定サイズのストレージ (MSL以下) を、私が慣れていないサイズに増やす必要があります。スタックオーバーフローを引き起こすのではないかと心配しているため、それを必要としない多くの小さな配列に対しても、スタックに大きすぎる配列を割り当てたくありません。C99 VLA は、必要以上のストレージを使用することはないため、実際にはこの傾向はありません。

私は出くわしましstd::dynarrayたが、私の理解では、それは標準に受け入れられていませんでした (まだ?)。

Clang と gcc が C++ で VLA をサポートしていることは知っていますが、MSVC でも動作させる必要があります。実際、移植性の向上は、C++ として書き直す主な目標の 1 つです (もう 1 つの目標は、元はコマンド ライン ツールであったプログラムを再利用可能なライブラリにすることです)。

基準

MSLヒープ割り当てに切り替える配列サイズを指します。1D 配列と 2D 配列に異なる値を使用します。

元の C99 コード: 115 秒。
MSL = 0 (ヒープ割り当て): 367 秒 (3.2x)。
1D-MSL = 50、2D-MSL = 1000: 187 秒 (1.63x)。
1D-MSL = 200、2D-MSL = 4000: 143 秒 (1.24x)。
1D-MSL = 1000、2D-MSL = 20000: 131 (1.14x)。

さらに増やすMSLとパフォーマンスが向上しますが、最終的にプログラムは間違った結果を返し始めます (スタックオーバーフローが原因だと思います)。

これらのベンチマークは OS X の clang 3.7 を使用したものですが、gcc 5 は非常に類似した結果を示しています。

コード

これは、私が使用している現在の「smallvector」実装です。1D および 2D ベクトルが必要です。size を超えるヒープ割り当てに切り替えますMSL。

Common Lisp のほとんどの実装では、コンス セルは通常/常にヒープに割り当てられていると思います ( Why is consing in Lisp slow? を参照) 。

Common Lisp は、関数から複数の値を返すための機能を提供します (values戻るときとmultiple-value-bind呼び出しサイトで使用します)。ここで少し推測していますが、この構築の動機は2つあると思います.1）truncate破棄された値を気にしない典型的なケースで関数を使いやすくする.2）ヒープに割り当てられたデータ構造をまったく使用せずに複数の値を返し、(実装によっては (?)) ヒープを完全に回避します (後で GC オーバーヘッドを回避します)。

Common Lisp (またはおそらく SBCL のような特定の実装) を使用すると、スタックに割り当てられたデータを (おそらく弱い参照のようなものと組み合わせて) 使用したり、複合/大規模な値の型 (C の構造体のようなもの) を作成したりできますか?