代码之家 › 专栏 › 技术社区 › Diego Sevilla

tr1::boost::thread::id的哈希?

unordered-set boost-thread hash boost c++

Diego Sevilla · 技术社区 · 16 年前

我开始使用 unordered_set tr1 map . 然而,我想在boost中存储对线程ID的引用( boost::thread::id ),并意识到这些标识符的API是如此不透明,以至于您无法清楚地获得它的散列。

令人惊讶的是,boost实现了 tr1 (包括 hash 和 无序集

查看我发现线程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> 班

谢谢

5 回复 | 直到 15 年前

vladr 14 年前

架线的开销 thread::id (只是在事后计算字符串散列)就像你自己几乎说过的那样,与任何性能优势相比都是天文数字 tr1::unordered_map 可能会产生对立 std::map . 因此,简单的答案是: 坚持使用std::map<线程::id&燃气轮机;

如果你 绝对地 必须使用无序容器, 尝试使用 native_handle_type 而不是 线程::id 如果可能,也就是说,更喜欢 tr1::unordered_map< thread::native_handle_type, ... > ,调用 thread::native_handle() 而不是 thread::get_id() 什么时候 insert ing和 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());
   }
};

它可以工作,但极为脆弱,几乎是一颗定时炸弹。它假定对系统的内部工作有深入的了解 线程::id 实施它会让你被其他开发者诅咒。如果担心可维护性,就不要这样做!甚至修补 boost/thread/detail/thread.hpp 加 size_t hash_value(const id& tid) 线程::id 是“更好”。)

Matthieu M. 15 年前

显而易见的问题是,为什么要实际使用哈希?

map / set 对于性能关键型代码,实际上,这些容器不是非常缓存友好的,因为这些项可能分配在非常不同的内存位置。

正如KeithB所建议的(我不会评论使用二进制表示法,因为没有任何东西可以保证2个ID具有相同的二进制表示法……),使用排序的 vector 如果项目很少,可以加快代码速度。

排序向量/数据块对缓存友好得多,但是它们会受到 O(N) 由于涉及复制,因此插入/擦除的复杂性。一旦你达到几百个线程(顺便说一句,从来没有见过这么多),它可能会受伤。

然而,有一种数据结构试图将地图和排序向量的好处联系起来: B+Tree .

您可以将其视为每个节点将包含多个元素(按排序顺序)的映射。仅使用叶节点。

要获得更高的性能,您可以:

线性链接叶子:即根缓存指向第一个和最后一个叶子的指针,叶子之间相互连接,因此线性移动完全绕过内部节点。

渐近性能与映射相同,因为它实现为一个平衡的二叉树,但由于值是分组的,所以代码的速度可以加快一个常数。

BenMorel Manish Pradhan 11 年前

为什么要将这些存储在一组中。除非你做了一些不同寻常的事情,否则会有少量的线程。维护一个集合的开销可能比仅仅将它们放在向量中并进行线性搜索要高。

如果搜索比添加和删除更频繁,则可以使用排序向量。有一个<为boost::thread::id定义的运算符,因此您可以在每次添加或删除后对向量进行排序(或插入到正确的位置),并使用 lower_bound()

如果您仍然需要这样做,那么将其视为sizeof(boost::thread:id)字节并对其进行操作如何。

编辑:我看了一下 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];

Sumedh 9 年前

回答这个问题已经晚了几年,但在试图将boost::thread::id作为键放入std::unordered_映射时,这是最相关的问题。在接受的回复中,获取本机句柄是一个很好的建议,只是它不适用于此线程。

相反,boost for time为thread::id提供了一个hash_值,所以这对我来说很好:

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_线程库。

BaSz 15 年前