19

std::deque のメモリ オーバーヘッドで一体何が起こっているのかをフォローアップしてください。

Visual C++ はdeque、これを使用してコンテナー要素の型に従ってブロックを管理します。

#define _DEQUESIZ   (sizeof (value_type) <= 1 ? 16 \
    : sizeof (value_type) <= 2 ? 8 \
    : sizeof (value_type) <= 4 ? 4 \
    : sizeof (value_type) <= 8 ? 2 \
    : 1)    /* elements per block (a power of 2) */

これにより、小さな要素のメモリ フットプリントが非常に大きくなります。最初の行の 16 を 128 に変更することで、大きなdeque<char>. プロセス エクスプローラーのプライベート バイトが 181MB から 100m のpush_back(const char& mychar)呼び出し後に 113MB に減少しました)。

  • その値を正当化できる人はい#defineますか?
  • deque他のコンパイラはブロックのサイズをどのように処理しますか?
  • push_backへの 100m呼び出し の単純なテストのフットプリント (32 ビット操作) はどうなるでしょうdeque<char>か?
  • STL では、 <deque>コードを変更せずに、コンパイル時にこのブロック サイズをオーバーライドできますか?
4

3 に答える 3

5

gccには

return __size < 512 ? size_t(512 / __size) : size_t(1);

コメント付き

/*  The '512' is
 *  tunable (and no other code needs to change), but no investigation has
 *  been done since inheriting the SGI code.
 */
于 2010-11-04T15:34:30.760 に答える
3

Dinkumware（MS）の実装では、dequeを一度に16バイトずつ増やしたいと考えています。これは、メモリの全体的な割り当てと枯渇を防ぐために（今日の標準では）メモリが非常に少ないプラットフォーム用に調整された非常に古い実装（これまでの最初の実装のように）である可能性std::vectorがありますか？

std::queue（を使用する）の2.5倍のメモリフットプリントstd::dequeが許容できないため、作業中のアプリケーションに独自のキューを実装する必要がありました。

人々がこの非効率性に遭遇したという証拠はインターウェブ上にほとんどないようです。これは私にとって驚くべきことです。キュー（標準ライブラリ、それ以上）のような基本的なデータ構造は、実際にはかなり遍在し、パフォーマンス/時間/スペースが重要なアプリケーションにあると思います。しかし、ここにあります。

最後の質問に答えるために、C++標準はブロックサイズを変更するためのインターフェイスを定義していません。私はそれが実装を義務付けているのではなく、両端での挿入/削除の複雑さの要件だけを義務付けていると確信しています。

于 2010-11-04T17:00:53.530 に答える
2

STLPort

...使用しているようです：

::: <stl/_alloc.h>
...
enum { _MAX_BYTES = 32 * sizeof(void*) };
...
::: <deque>
...
static size_t _S_buffer_size()
{
  const size_t blocksize = _MAX_BYTES;
  return (sizeof(_Tp) < blocksize ? (blocksize / sizeof(_Tp)) : 1);
}

つまり、32 x 4 = 32ビットで128バイトのブロックサイズ、32 x 8=64ビットで256バイトのブロックサイズになります。

私の考え：サイズオーバーヘッドPOVから、任意の実装が可変長ブロックで動作することは理にかなっていると思いますが、これは、の一定時間のランダムアクセス要件で正しく行うのは非常に難しいと思いますdeque。

質問は

STLでは、コードを変更せずに、コンパイル時にこのブロックサイズをオーバーライドできますか？

ここでも不可能です。

Apache

（Rogue Wave STLバージョンのようです）明らかに以下を使用します：

static size_type _C_bufsize () {
    // deque only uses __rw_new_capacity to retrieve the minimum
    // allocation amount; this may be specialized to provide a
    // customized minimum amount
    typedef deque<_TypeT, _Allocator> _RWDeque;
    return _RWSTD_NEW_CAPACITY (_RWDeque, (const _RWDeque*)0, 0);
}

したがって、特殊化によってブロックサイズをオーバーライドするメカニズムがあるようで、...の定義は次のようになります。

// returns a suggested new capacity for a container needing more space
template <class _Container>
inline _RWSTD_CONTAINER_SIZE_TYPE
__rw_new_capacity (_RWSTD_CONTAINER_SIZE_TYPE __size, const _Container*)
{
    typedef _RWSTD_CONTAINER_SIZE_TYPE _RWSizeT;

    const _RWSizeT __ratio = _RWSizeT (  (_RWSTD_NEW_CAPACITY_RATIO << 10)
                                       / _RWSTD_RATIO_DIVIDER);

    const _RWSizeT __cap =   (__size >> 10) * __ratio
                           + (((__size & 0x3ff) * __ratio) >> 10);

    return (__size += _RWSTD_MINIMUM_NEW_CAPACITY) > __cap ? __size : __cap;
}

だから、それは、えーと、複雑だと思います。

（誰かがこれをさらに理解したいと思う場合は、私の答えを直接編集するか、コメントを残してください。）

于 2011-11-24T13:38:01.567 に答える