boost::thread::id の tr1::hash?

StackOverflow https://stackoverflow.com/questions/772192

質問

を使い始めました unordered_set からのクラス tr1 プレーン (ツリーベース) STL に対するアクセスを高速化する名前空間 map. 。ただし、スレッド ID への参照をブーストに保存したかったのです (boost::thread::id)、これらの識別子の API は非常に不透明であるため、そのハッシュを明確に取得できないことに気付きました。

驚くべきことに、boost は次の部分を実装しています。 tr1 （含む hash そして unordered_set) ですが、スレッド ID をハッシュできるハッシュ クラスは定義されていません。

のドキュメントを見ると、 boost::thread::id スレッド ID をストリームに出力できることがわかったので、ハッシュ化を行うための解決策は次のようなものでした。

struct boost_thread_id_hash
{
    size_t operator()(boost::thread::id const& id) const
    {
        std::stringstream ostr;
        ostr << id;
        std::tr1::hash<std::string> h;
        return h(ostr.str());
    }
};

つまり、シリアル化して、結果の文字列にハッシュを適用します。ただし、これは実際に STL を使用するよりも効率が悪いようです。 map<boost::thread::id>.

それで、私の質問は次のとおりです。もっと良い方法はありますか?boost と tr1 の両方で、存在を強制しないのは明らかな矛盾ですか? hash<boost::thread::id> クラス？

ありがとう。

役に立ちましたか？

解決

文字列化のオーバーヘッド thread::id （後で文字列ハッシュを計算するためだけ）は、あなた自身がほとんど言いましたが、パフォーマンス上の利点と比較すると天文学的です。 tr1::unordered_map 反対に協議するかもしれない std::map. 。したがって、短い答えは次のようになります。 std::map< thread::id, ... に固執します>

もし、あんたが 絶対に 順序付けされていないコンテナを使用する必要があります。 使ってみてくださいnative_handle_type の代わりに thread::id 可能であれば、つまり好む tr1::unordered_map< thread::native_handle_type, ... >, 、呼び出す thread::native_handle() の代わりに thread::get_id() いつ insertと findしてる。

次のようなことは行わないでください:

struct boost_thread_id_hash {
   // one and only member of boost::thread::id is boost::thread::id::thread_data
   //   of type boost::detail::thread_data_ptr;
   // boost::thread::id::operator==(const id&) compares boost::thread::id::thread_data's
   size_t operator()(boost::thread::id const& id) const {
      const boost::detail::thread_data_ptr* pptdp = \
        reinterpret_cast< boost::detail::thread_data_ptr* >(&id);
      return h(pptdp->get());
   }
};

機能する可能性はありますが、非常に脆く、ほぼ確実に時限爆弾になります。内部の仕組みについての深い知識を前提としています。 thread::id 実装。他の開発者から罵倒されることになります。保守性が懸念される場合は、これを行わないでください。均等なパッチング boost/thread/detail/thread.hpp たす size_t hash_value(const id& tid) の友人として thread::id 優れている"。:)

他のヒント

明らかな疑問は、なぜ実際にハッシュを使用したいのかということです。

の問題は理解しています map / set パフォーマンスが重要なコードの場合、項目が非常に異なるメモリ位置に割り当てられる可能性があるため、実際、これらのコンテナはあまりキャッシュに適していません。

KeithB が示唆したように (結局のところ、2 つの ID が同じバイナリ表現を持つことを保証するものは何もないため、バイナリ表現の使用についてはコメントしません...)、並べ替えられた vector 項目が非常に少ない場合はコードを高速化できます。

ソートされたベクター/デックはキャッシュにはるかに適していますが、次のような問題があります。 の上） コピーが含まれるため、挿入/消去が複雑になります。スレッドが数百に達すると（ちなみに、それほど多くのスレッドを見たことがありません）、それは問題になる可能性があります。

ただし、マップと並べ替えられたベクトルからの利点を関連付けようとするデータ構造があります。の B+ツリー.

これを、各ノードに複数の要素が (ソート順に) 含まれるマップとして表示できます。リーフ ノードのみが使用されます。

さらにパフォーマンスを向上させるには、次のことができます。

  • 葉を直線的にリンクします。つまり、ルートは最初と最後のリーフへのポインタをキャッシュし、リーフは相互接続されているため、線形移動は内部ノードを完全にバイパスします。
  • 最後にアクセスされたリーフをルートにキャッシュします。結局のところ、次にアクセスされるリーフもそれになる可能性が高いからです。

マップはバランス バイナリ ツリーとして実装されているため、漸近的なパフォーマンスはマップの場合と同じですが、値がグループにパックされているため、コードは一定の速度で高速化できます。

本当の難しさは、各「バケット」のサイズを調整することです。そのためにはプロファイリングが必要になるため、実装でカスタマイズを許可した方がよいでしょう (コードが実行されるアーキテクチャに依存するため)。

なぜあなたはセットでこれらを保存したいです。あなたは普通の外に何かをしていない限り、スレッドの数が少ないがあるでしょう。セットを維持するオーバーヘッドはちょうどベクターにそれらを入れて、線形探索を行うよりもおそらく高いです。

検索が追加と削除よりも頻繁に発生する場合は、

は、あなただけの並べ替えベクトルを使用することができます。そこブースト用に定義された<演算子::スレッド:: idがあるので、あなたはベクトルを並べ替える（または正しい場所に挿入する）は、それぞれ追加または削除した後、バイナリ検索を実行するためにlower_bound()を使用することができます。これは、セットを検索するのと同じ複雑で、かつ少量のデータのための低オーバーヘッドを持っている必要があります。

あなたはまだどのようにちょうど（後押し::スレッドを：id）をのsizeofとして扱いについては、これを実行する必要がある場合。バイト、およびそれらの上で動作します。

この例では、ブースト::スレッドの:: IDサイズがintのサイズの倍数であること、およびNOパッキング、およびno仮想関数が存在しないことを前提としています。それが真でない場合、それは修正する必要があります、またはまったく動作しません。

編集：私はboost::thread::idクラスを見ていたし、それがメンバーとしてboost::shared_pointer<>を持っているので、以下のコードは恐ろしく壊れています。私が唯一の解決策は、ハッシュ関数を追加boost::threadの著者を持つことだと思います。私はいくつかの他の文脈でその便利念の例を残しています。

boost::thread::id id;
unsigned* data;
// The next line doesn't do anything useful in this case.
data = reinterpret_cast<unsigned *>(&id);
unsigned hash = 0;

for (unsigned int i = 0; i < sizeof(boost::thread::id)/4; i++)
  hash ^= data[i];

この質問に答えるために遅れて何年かが、STDでブースト::スレッド:: ID ::キーとしてunordered_mapを置くしようとしたとき、これは最も関連性の高いものとして現れました。ネイティブハンドルを取得することがthis_threadのために利用できないことを除いて受け入れの回答で良い提案だった。

は、代わりにいつか後押しスレッドのHASH_VALUE :: IDを持っているので、これは私のためにうまく働います：

namespace boost {
  extern std::size_t hash_value(const thread::id &v);
}

namespace std {
  template<>
  struct hash<boost::thread::id> {
    std::size_t operator()(const boost::thread::id& v) const {
      return boost::hash_value(v);
    }
  };
}

もちろん、libboost_threadライブラリにリンクする必要があります。

あなたはハッシュとして使用することができ、スレッド間のマッピングを行い、クラス:: idと何か（例：整数）を作成することができます。唯一の欠点は、あなたがマッピングオブジェクトのインスタンスが1つだけのシステムであることを確認しなければならないということです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top