tr1 :: hash для boost :: thread :: id? - PullRequest
Новая
       25

tr1 :: hash для boost :: thread :: id?

9 голосов
/ 21 апреля 2009

Я начал использовать класс unordered_set из пространства имен tr1 для ускорения доступа к простому (на основе дерева) STL map. Однако я хотел сохранить ссылки на ID потоков в boost (boost::thread::id) и понял, что API этих идентификаторов настолько непрозрачен, что вы не можете получить его хэш.

Удивительно, но boost реализует части tr1 (включая hash и unordered_set), но не определяет класс хеша, который может хэшировать идентификатор потока.

Глядя на документацию boost::thread::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 ]

8 голосов
/ 08 сентября 2010

Затраты на строковое преобразование thread::id (только для вычисления хеш-строки после этого), как вы почти сказали сами, астрономичны по сравнению с любыми преимуществами производительности, которые tr1::unordered_map может дать по сравнению с std::map. Таким образом, короткий ответ будет: придерживаться std :: map

Если вы абсолютно должны использовать неупорядоченные контейнеры, попытайтесь использовать native_handle_type вместо thread::id, если это возможно, то есть предпочитаете tr1::unordered_map< thread::native_handle_type, ... >, вызывая thread::native_handle() вместо thread::get_id() когда insert ing и find ing.

НЕ пытайтесь делать что-либо подобное следующему : 

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 "лучше". :)

3 голосов
/ 17 мая 2010

Очевидный вопрос: почему вы хотите использовать хеш?

Я понимаю проблему с map / set для кода, критичного к производительности, ведь эти контейнеры не очень удобны для кэширования, поскольку элементы могут размещаться в очень разных местах памяти.

Как предложил KeithB (я не буду комментировать использование двоичного представления, так как ничто не гарантирует, что 2 идентификатора имеют одинаковое двоичное представление в конце концов ...), использование отсортированного vector может ускорить код в случае, если есть очень мало предметов.

Сортированные векторы / запросы намного более удобны для кэша, однако они страдают от сложности O (N) при вставке / удалении из-за копирования. Как только вы достигнете пары сотен потоков (кстати, никогда их не видели), это может повредить.

Однако существует структура данных, которая пытается связать выгоды от карт и отсортированных векторов: B + Tree .

Вы можете просмотреть его как карту, для которой каждый узел будет содержать более одного элемента (в отсортированном порядке). Используются только листовые узлы.

Чтобы повысить производительность, вы можете:

  • Линейное связывание листьев: т. Е. Корень кэширует указатель на первый и последний лист, и листья связаны между собой, так что линейное перемещение полностью обходит внутренние узлы.
  • Кэшируйте последний доступный лист в корне, в конце концов, вероятно, это также будет следующий доступ.

Асимптотические характеристики те же, что и для карты, поскольку она реализована в виде сбалансированного двоичного дерева, но поскольку значения упакованы в группы, ваш код может стать быстрее благодаря константе.

Реальная сложность состоит в том, чтобы настроить размер каждого «сегмента», для этого вам потребуется некоторое профилирование, поэтому было бы лучше, если бы ваша реализация позволила внести некоторые изменения в него (поскольку это будет зависеть от архитектуры, на которой написан код). выполняется).

2 голосов
/ 01 июня 2016

Несколько лет спустя, чтобы ответить на этот вопрос, но он оказался наиболее актуальным при попытке добавить boost :: thread :: id в std :: unordered_map в качестве ключа. Получение правильного дескриптора было хорошим предложением в принятом ответе, за исключением того, что оно недоступно для this_thread.

Вместо повышения в течение некоторого времени есть hash_value для thread :: 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.

2 голосов
/ 21 апреля 2009

Почему вы хотите хранить их в наборе. Если вы не сделаете что-то необычное, там будет небольшое количество потоков. Затраты на поддержание набора, вероятно, выше, чем просто поместить их в вектор и выполнить линейный поиск.

Если поиск будет происходить чаще, чем добавление и удаление, вы можете просто использовать отсортированный вектор. Для boost :: thread :: id определен оператор <, так что вы можете отсортировать вектор (или вставить в правильное место) после каждого добавления или удаления и использовать <code>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];
0 голосов
/ 01 июня 2010

вы можете создать класс, который выполняет отображение между thread :: id и чем-то (например, целыми числами), который вы можете использовать как хеш. единственный недостаток заключается в том, что вы должны убедиться, что в системе существует только один экземпляр объекта сопоставления.

...