9

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

驚くべきことに、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>です。

だから、私の質問：これを行うためのより良い方法を見つけますか？hash<boost::thread::id>クラスの存在を強制しないのは、boost と tr1 の両方で明らかな矛盾ですか?

ありがとう。

4

5 に答える 5

8

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

絶対に順序付けされていないコンテナーを使用する必要がある場合は、可能であれば代わりに使用するnative_handle_typeようにしてください。thread::idtr1::unordered_map< thread::native_handle_type, ... >thread::native_handle()thread::get_id()insertfind

次のようなことを試みないでください。

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

于 2010-09-08T17:13:47.293 に答える
3

明らかな質問は、実際にハッシュを使用する理由です。

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

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

ソートされたベクトル/deque は、はるかにキャッシュに適していますが、コピーが含まれるため、挿入/消去でO(N)の複雑さに悩まされます。スレッド数が数百に達すると (ちなみに、それほど多くは見られません)、問題が発生する可能性があります。

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

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

より多くのパフォーマンスを得るには、次のことができます。

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

平衡二分木として実装されているため、漸近的なパフォーマンスはマップの場合と同じですが、値がグループにパックされているため、コードを一定の分だけ高速化できます。

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

于 2010-05-17T18:05:27.297 に答える
2

この質問に答えるのに数年遅れましたが、ブースト::スレッド::idを std::unordered_map にキーとして配置しようとすると、これが最も関連性の高いものとして表示されました。ネイティブ ハンドルを取得することは、this_thread では利用できないことを除いて、受け入れられた返信で良い提案でした。

代わりに、boost for sometime には thread::id の hash_value があるため、これは私にとってはうまくいきました。

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 ライブラリにリンクする必要があります。

于 2016-06-01T19:03:29.440 に答える
2

なぜこれらをセットで保管したいのですか？特別なことをしない限り、スレッドの数は少なくなります。セットを維持するオーバーヘッドは、それらをベクトルに入れて線形検索を行うよりもおそらく高くなります。

追加や削除よりも検索が頻繁に発生する場合は、並べ替えられたベクトルを使用できます。boost::thread::id には < 演算子が定義されているため、追加または削除するたびにベクトルをソート (または正しい場所に挿入)lower_bound()し、バイナリ検索を実行するために使用できます。これはセットの検索と同じ複雑さであり、少量のデータの場合はオーバーヘッドが少なくなります。

それでもこれを行う必要がある場合は、それを sizeof(boost::thread:id) バイトとして扱い、それらを操作するのはどうですか。

この例では、boost::thread::id のサイズが int のサイズの倍数であり、パッキングも仮想関数もないと仮定しています。そうでない場合は、変更する必要があるか、まったく機能しません。

編集: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];
于 2009-04-21T15:31:28.190 に答える
0

ハッシュとして使用できる thread::id と何か (例: 整数) の間のマッピングを行うクラスを作成できます。唯一の欠点は、システム内にマッピング オブジェクトのインスタンスが 1 つしかないことを確認する必要があることです。

于 2010-06-01T06:13:31.407 に答える