9

我开始使用命名空间中的unordered_set类tr1来加速对普通（基于树的） STL 的访问map。但是，我想在 boost( boost::thread::id) 中存储对线程 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>。

所以，我的问题是：你找到更好的方法了吗？不强制一个hash<boost::thread::id>类的存在是否在 boost 和 tr1 中都存在明显的不一致？

谢谢。

4

5 回答 5

8

thread::id正如您自己所说的那样，字符串化（仅用于随后计算字符串哈希）的开销与 atr1::unordered_map可能赋予的任何性能优势相比是天文数字 vis-a-vis std::map。所以简短的回答是：坚持使用 std::map< thread::id, ... >

如果您绝对必须使用无序容器，请尽可能尝试使用native_handle_type而不是thread::id，即更喜欢tr1::unordered_map< thread::native_handle_type, ... >，调用thread::native_handle()而不是thread::get_id()when inserting 和finding。

不要尝试以下任何事情：

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 具有相同的二进制表示毕竟......），vector如果项目很少，使用排序可以加快代码速度。

排序的向量/双端队列对缓存更加友好，但是由于涉及复制，它们在插入/擦除时会遇到O(N)复杂性。一旦你达到几百个线程（顺便说一句，从未见过这么多线程），它可能会受到伤害。

然而，有一种数据结构试图将映射和排序向量的好处联系起来：B+Tree。

您可以将其视为一个地图，其中每个节点将包含多个元素（按排序顺序）。仅使用叶节点。

要获得更多性能，您可以：

  • 线性链接叶子：即根缓存指向第一个和最后一个叶子的指针，并且叶子本身相互连接，因此线性行进完全绕过内部节点。
  • 将最后访问的叶子缓存在根目录中，毕竟它很可能也是下一个访问的叶子。

渐近性能与映射相同，因为它是作为平衡二叉树实现的，但是由于值是分组打包的，因此您的代码可以通过常数变得更快。

真正的困难是定制每个“桶”的大小，您需要为此进行一些分析，因此如果您的实现允许在那里进行一些定制会更好（因为它将取决于执行代码的架构）。

于 2010-05-17T18:05:27.297 回答
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 回答
2

回答这个问题晚了几年，但是当试图将 boost::thread::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 回答
0

您可以创建在 thread::id 和某些东西（例如：整数）之间进行映射的类，您可以将其用作哈希。唯一的缺点是您必须确保系统中只有一个映射对象实例。

于 2010-06-01T06:13:31.407 回答