8

約 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 のみを使用できます。

4

7 に答える 7

4

最初の質問は次のとおりです。余分なインターフェースをどのくらい使用しますか? の追加インターフェースのほとんどは( 、 、など) のstd::string関数を使用して簡単に実装できますが、多くの場合、とにかく使用されない大きなチャンクがあります。必要に応じて実装するだけです。<algorithm>std::findstd::find_ifstd::search

カスタムアロケーターでこれを機能させることはできないと思います。メモリを「スタック上」に取得する唯一の方法は、メモリをカスタム アロケータのメンバーとして宣言することです。これにより、メモリをコピーするときにあらゆる種類の問題が発生します。また、アロケーターはコピー可能でなければならず、コピーは冪等でなければなりません。

std::stringおそらく、小さな文字列の実装を使用するネット上の無料の実装を見つけることができます 。次に、カットオフ サイズ (動的割り当てを使用するサイズを超える) が実際に使用する文字列よりも大きくなるように変更します。(利用可能な標準ライブラリのオープンソース実装がいくつかあります。g++ で提供されるものはまだ COW を使用していますが、他のほとんどは SSO を使用していると思います。)

于 2014-10-14T09:53:33.367 に答える
1

簡単です。スタック アロケータを記述します。以下に例を示します。

https://codereview.stackexchange.com/questions/31528/a-working-stack-allocator

アロケータを使用すると、たとえば、メモリ マップ ファイルから、つまりディスク ドライブから、またはchars の静的配列から簡単に割り当てることができます。

于 2014-10-14T09:18:37.670 に答える
1

An excellent starting point is Alexandrescu's policy-based string class, described in this Dr Dobbs article. It includes a SSO policy that basically does what you want (search the page for SmallStringOpt), and is easy to modify if/as you deem necessary. It's predates C++11 so you're fine there too.

于 2014-10-14T11:04:03.930 に答える
1

多くのbasic_string実装があり、完全に動的割り当てに基づいているものもあれば、指定された長さよりも広い文字列のみを動的に割り当てているものもあります (実際、収まる場合は独自の内部バッファーを使用します)。

文字列とアロケーターの間のインターフェースは、アロケーターオブジェクトがコンテナーの一部であると想定しているため、アロケーターを使用することはおそらく適切ではありませんが、割り当てられたメモリはコンテナー自体の外部から取得されます。POSIX を使用してアロケータを実装することで、これを調整できますがalloca、すべての欠点があります。

スタックに文字列を実装するときの問題は、動的に大きくすることができないことです (その時点でスタックに何か余分なものがある可能性があります) が+=、文字列をどんどん長くするような操作にも注意する必要があります。

そのため、(配列または alloca が提供するバッファーとして、クラス内またはアロケーター内で問題は変わらない) 事前に割り当ててしまうことになります文字列が大きくなりすぎて動的にする必要がある場合。

メモリからキャッシュへの通信プロセス (通常は 128 バイトまたは 4K バイトで実行される) にはおそらくトレードオフがありますが、これはハードウェアに大きく依存するため、許容できる複雑さはほとんどの場合見逃せません。

より手頃なソリューションは、引き続きヒープに割り当てるアロケーターですが、返されたブロックを (一定の制限まで) 保持して再利用する機能を備えているため、システムに割り当て/割り当て解除を依頼する必要がなくなります。

ただし、この場合、基盤となるシステムがすでにそのように実装されている場合、パフォーマンスが必ずしも向上するとは限りませんnew/delete。

于 2014-10-14T09:32:25.097 に答える
0

実装で定義された VLA と標準アルゴリズムを組み合わせて使用​​すると思います。

于 2014-10-14T09:46:46.590 に答える