17

とはまったく同じコードを使用できるため、unordered_map型消去を使用して実装されているのではないかと思いました（マシンコードのno-opであるキャストを除く）。つまり、両方の実装は、コードサイズを節約することに基づくことができます。unordered_map<Key, A*>unordered_map<Key, B*>unordered_map<Key, void*>

更新：この手法は、一般にシンテンプレートイディオムと呼ばれます（それを指摘してくれた以下のコメント提供者に感謝します）。

アップデート2：ハワード・ヒナントの意見に特に興味があります。彼がこれを読んでくれることを願っています。

だから私はこの小さなテストを書きました：

#include <iostream>

#if BOOST
# include <boost/unordered_map.hpp>
  using boost::unordered_map;
#else
# include <unordered_map>
  using std::unordered_map;
#endif

struct A { A(int x) : x(x) {} int x; };
struct B { B(int x) : x(x) {} int x; };

int main()
{
#if SMALL
    unordered_map<std::string, void*> ma, mb;
#else
    unordered_map<std::string, A*> ma;
    unordered_map<std::string, B*> mb;
#endif

    ma["foo"] = new A(1);
    mb["bar"] = new B(2);

    std::cout << ((A*) ma["foo"])->x << std::endl;
    std::cout << ((B*) mb["bar"])->x << std::endl;

    // yes, it leaks.
}

そして、さまざまな設定でコンパイルされた出力のサイズを決定しました。

#!/bin/sh

for BOOST in 0 1 ; do
    for OPT in 2 3 s ; do
        for SMALL in 0 1 ; do
            clang++ -stdlib=libc++ -O${OPT} -DSMALL=${SMALL} -DBOOST=${BOOST} map_test.cpp -o map_test
            strip map_test
            SIZE=$(echo "scale=1;$(stat -f "%z" map_test)/1024" | bc)
            echo boost=$BOOST opt=$OPT small=$SMALL size=${SIZE}K
        done
    done
done

私が試したすべての設定で、の多くの内部コードがunordered_map2回インスタンス化されているようです。

With Clang and libc++:
          |   -O2   |   -O3   |   -Os
-DSMALL=0 |  24.7K  |  23.5K  |  28.2K
-DSMALL=1 |  17.9K  |  17.2K  |  19.8K


With Clang and Boost:
          |   -O2   |   -O3   |   -Os
-DSMALL=0 |  23.9K  |  23.9K  |  32.5K
-DSMALL=1 |  17.4K  |  17.4K  |  22.3K


With GCC and Boost:
          |   -O2   |   -O3   |   -Os
-DSMALL=0 |  21.8K  |  21.8K  |  35.5K
-DSMALL=1 |  16.4K  |  16.4K  |  26.2K

（AppleのXcodeのコンパイラを使用）

ここで質問になります。実装者がこの単純な最適化を省略することを選択したために、説得力のある技術的な理由がありますか？

また、なぜ地獄-Osは宣伝されているものとは正反対の効果なのですか？

アップデート3：

Nicol Bolasが提案したように、私はshared_ptr<void/A/B>裸のポインター（で作成され、make_sharedでキャストされたstatic_pointer_cast）の代わりに測定を繰り返しました。結果の傾向は同じです。

With Clang and libc++:
          |   -O2   |   -O3   |   -Os
-DSMALL=0 |  27.9K  |  26.7K  |  30.9K
-DSMALL=1 |  25.0K  |  20.3K  |  26.8K


With Clang and Boost:
          |   -O2   |   -O3   |   -Os
-DSMALL=0 |  35.3K  |  34.3K  |  43.1K
-DSMALL=1 |  27.8K  |  26.8K  |  32.6K
4

2 に答える 2

10

特にコメントを求められたので、これまでに述べた以上に追加できるかどうかはわかりませんが、コメントします。（申し訳ありませんが、ここに到着するのに8日かかりました）

以前、いくつかのコンテナ、つまりvector、deque、listに対して、シンテンプレートイディオムを実装しました。現在、libc++のどのコンテナにも実装されていません。そして、私はそれを順序付けられていないコンテナに実装したことはありません。

コードサイズを節約できます。また、参照されているウィキブックスのリンクが示すよりもはるかに複雑になります。単なるポインタ以上のこともできます。同じサイズのすべてのスカラーに対してこれを行うことができます。たとえば、とのインスタンス化が異なるのはなぜintですかunsigned？と同じインスタンス化で保存することもptrdiff_tできますT*。結局のところ、それはすべて下部にある単なるバッグビットです。ただし、これらのトリックを実行するときに、さまざまなイテレータを正しく使用するメンバーテンプレートを取得するのは非常に困難です。

ただし、欠点があります（実装の難しさ以外に）。デバッガーではうまく機能しません。少なくとも、デバッガーがコンテナーの内部を表示することははるかに困難になります。コードサイズの節約は重要ですが、コードサイズの節約を劇的なものと呼ぶには至りません。特に、写真、アニメーション、オーディオクリップ、ストリートマップ、親友や家族からのすべての添付ファイルを含む何年もの電子メールなどを保存するために必要なメモリと比較すると、コードサイズを最適化することが重要です。ただし、今日の多くのアプリでは（組み込みデバイスでも）、コードサイズを半分にすると、アプリのサイズが5％縮小する可能性があることを考慮に入れる必要があります（統計は明らかに薄い空気から引き出されています）。

私の現在の立場は、この特定の最適化は、テンプレートコンテナではなく、リンカで最もよく支払われ、実装されるものであるということです。これをリンカに実装するのは簡単ではないことは知っていますが、実装が成功したと聞いています。

そうは言っても、私はまだテンプレートでコードサイズの最適化を試みています。たとえば、のようなlibc ++ヘルパー構造で__hash_map_node_destructorは、可能な限り少ないパラメーターでテンプレート化されているため、コードのいずれかが概説されている場合、ヘルパーの1つのインスタンス化がの複数のインスタンス化を提供できる可能性が高くなりますunordered_map。この手法はデバッガーに対応しており、正しく理解するのはそれほど難しくありません。また、イテレータ（ N2980 ）に適用すると、クライアントにプラスの副作用をもたらす可能性もあります。

要約すると、私は、さらに一歩進んでこの最適化を実装するためのコードに反対するつもりはありません。しかし、リンカーテクノロジーが進歩し、アプリケーションサイズに対するコードサイズの比率がかなり劇的に減少する傾向にあるため、10年前ほど優先度を高く分類することもしませんでした。

于 2012-07-03T22:20:20.883 に答える
-1

void *パラメータがある場合、コンパイル時に型チェックは行われません。

あなたが提案するようなマップは、タイプA *、B *の値要素、およびそのマップでは何の関係もないさらに想像を絶する派手なタイプを受け入れるため、プログラムの欠陥になります。（たとえば、int *、float *; std :: string *、CString *、CWnd * ...マップの混乱を想像してください...）

最適化は時期尚早です。そして、時期尚早の最適化はすべての悪の根源です。

于 2012-06-25T11:17:21.073 に答える