tr1::хэш для повышения::thread::id?
https://stackoverflow.com/questions/772192
-
12-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я начал использовать unordered_set класс из tr1 пространство имен для ускорения доступа по сравнению с обычным (древовидным) STL map.Однако я хотел сохранить ссылки на идентификатор потоков в 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> класс?
Спасибо.
Решение
Накладные расходы на упорядочивание thread::id (только для последующего вычисления хэша строки) является, как вы сами чуть не сказали, астрономическим по сравнению с любыми преимуществами производительности a tr1::unordered_map мог бы посовещаться с визави std::map.Таким образом, короткий ответ был бы следующим: придерживайтесь std:: карта< поток::идентификатор, ...>
Если вы абсолютно необходимо использовать неупорядоченные контейнеры, попробуйте использоватьnative_handle_type вместо того , чтобы thread::id если это возможно, т.е.предпочитаю tr1::unordered_map< thread::native_handle_type, ... >, вызывающий thread::native_handle() вместо того , чтобы thread::get_id() когда insertинг и 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 это "лучше".:)
Другие советы
Очевидный вопрос заключается в том , зачем вам на самом деле использовать хэш ?
Я понимаю проблему с map / set для кода, критичного к производительности, действительно, эти контейнеры не очень удобны для кэширования, поскольку элементы могут быть размещены в очень разных ячейках памяти.
Как предложил KeithB (я не буду комментировать использование двоичного представления, поскольку ничто не гарантирует, что 2 идентификатора в конце концов имеют одинаковое двоичное представление ...), используя отсортированную vector может ускорить код в случае, если элементов очень мало.
Отсортированные векторы / deques гораздо более удобны для кэширования, однако они страдают от O(N) сложность при вставке / стирании из-за задействованного копирования.Как только вы достигнете пары сотен потоков (кстати, никогда не видели столько), это может повредить.
Однако существует структура данных, которая пытается связать преимущества карт и отсортированных векторов:в B+Дерево.
Вы можете просмотреть его как карту, для которой каждый узел будет содержать более одного элемента (в отсортированном порядке).Используются только конечные узлы.
Чтобы получить еще больше производительности, вы можете:
- Соедините листья линейно:т.е. корень кэширует указатель на первый и последний лист, а сами листья связаны между собой, так что линейное перемещение полностью обходит внутренние узлы.
- Кэшируйте последний доступный лист в корневом каталоге, в конце концов, вполне вероятно, что он также будет следующим доступным.
Асимптотические характеристики те же, что и для карты, потому что она реализована в виде сбалансированного двоичного дерева, но поскольку значения упакованы в группы, ваш код может стать быстрее на постоянную величину.
Реальная трудность заключается в том, чтобы настроить размер каждого "ведра", для этого вам потребуется некоторое профилирование, поэтому было бы лучше, если бы ваша реализация допускала некоторую настройку там (поскольку это будет зависеть от архитектуры, на которой выполняется код).
Почему вы хотите хранить их в наборе?Если вы не делаете что-то из ряда вон выходящее, потоков будет небольшое количество.Накладные расходы на поддержание набора, вероятно, выше, чем просто помещение их в вектор и выполнение линейного поиска.
Если поиск будет происходить чаще, чем добавление и удаление, вы можете просто использовать отсортированный вектор.Существует < оператор, определенный для 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];
На несколько лет опоздал с ответом на этот вопрос, но это оказалось наиболее актуальным при попытке ввести boost::thread::id в std::unordered_map в качестве ключа.Получение собственного дескриптора было хорошим предложением в принятом ответе, за исключением того, что оно недоступно для this_thread .
Вместо этого boost for sometime имеет 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.
вы можете создать класс, который выполняет сопоставление между thread::id и чем-то еще (например.:целые числа), которые вы можете использовать в качестве хэша.единственным недостатком является то, что вы должны убедиться, что в системе есть только один экземпляр mapping object.
