tr1 :: hash para boost :: segmento :: id?

Question

Eu comecei a usar a classe unordered_set do namespace tr1 ao acesso velocidades acima de encontro a planície (baseado em árvore) STL map. No entanto, eu queria armazenar referências aos tópicos ID de impulso (boost::thread::id), e percebeu que a API desses identificadores é tão opaco que você não pode obter claramente um hash do mesmo.

Surpreendentemente, impulsionar implementos partes do tr1 (incluindo hash e unordered_set), mas não definem uma classe de hash que é capaz de hash de um identificador do segmento.

Olhando para a documentação de boost::thread::id descobri que IDs thread pode ser a saída para um fluxo, de modo que a minha solução para fazer hashing era uma espécie de:

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());
    }
};

Isto é, serializá-lo, aplicar o hash para a string resultante. No entanto, este parece ser menos eficiente do que realmente usando o map<boost::thread::id> STL.

Então, minhas perguntas: Você encontrar uma maneira melhor de fazer isso? É uma clara inconsistência tanto impulso e tr1 para não forçar a existência de uma classe hash<boost::thread::id>?

Graças.

Answer 1

A sobrecarga de stringifying thread::id (apenas para calcular o hash corda depois) é, como você quase disse a si mesmo, astronômico em comparação com todos os benefícios de desempenho de um tr1::unordered_map podem conferir vis-a-vis std::map. Portanto, a resposta curta seria: vara com std :: map

Se você absolutamente deve usar recipientes não ordenadas, tentar usenative_handle_type em vez de thread::id se possível, ou seja, preferem tr1::unordered_map< thread::native_handle_type, ... >, invocando thread::native_handle() vez de thread::get_id() quando inserting e finding.

NÃO tente qualquer coisa como o seguinte :

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());
   }
};

Ele poderia funcionar, mas é extremamente frágil e um timebomb quase garantida. Assume-se conhecimento profundo do funcionamento interno da implementação thread::id. Ele vai te amaldiçoou por outros desenvolvedores. Não fazê-lo se manutenção é de qualquer preocupação! Mesmo remendar boost/thread/detail/thread.hpp para adicionar size_t hash_value(const id& tid) como um amigo de thread::id é "melhor". :)

Answer 2

A pergunta óbvia é por que você quer realmente usar um hash?

Eu entendo a questão com map / set para o código crítico de desempenho, de fato esses recipientes não são muito de cache amigável porque os itens podem ser alocados em diferentes posições de memória.

Como KeithB sugeriu (não vou comentar sobre o uso da representação binária desde garantias nada que 2 ids têm a mesma representação binária depois de tudo ...), usando um vector ordenada pode acelerar o código no caso de haver muito poucos itens.

vetores classificados / deques são muito mais amigável cache, no entanto, eles sofrem de um O (N) complexidade em inserir / apagar por causa da cópia envolvidos. Depois de chegar a algumas centenas de tópicos (nunca visto que muitos por sinal), ele poderia machucar.

No entanto, existe uma estrutura de dados que tenta associar os benefícios de mapas e ordenados vetores: o B + Tree .

Você pode vê-lo como um mapa para que cada nó conteria mais de um elemento (em ordem de classificação). Apenas são utilizados os nós folha.

Para obter mais algumas desempenho você pode:

• Fazer a ligação das folhas linearmente: ou seja, a raiz armazena um ponteiro para a primeira e última folha e as folhas estão se interligados, de modo que as viagens linear ignorar completamente os nós INTERAL
.
• Cache a última folha acessado na raiz, afinal de contas, é provável que também vai ser o próximo acessado.

Os desempenhos assintóticos são os mesmos que para o mapa, porque ele é implementado como uma árvore binária equilibrada, mas porque os valores são embalados em grupos, você está código pode se tornar mais rápido por uma constante.

A verdadeira dificuldade é a de adequar o tamanho de cada "bucket", você vai precisar de algum profiling para que por isso seria melhor se sua implementação permitiu alguma personalização lá (uma vez que irá depender da arquitetura em que o código é executado).

Answer 3

Por que você quer para armazenar estes em um conjunto. A menos que você está fazendo algo fora do comum, haverá um pequeno número de threads. A sobrecarga de manutenção de um conjunto é provavelmente maior do que apenas colocá-los em um vetor e fazer uma busca linear.

Se a pesquisa vai acontecer com mais frequência do que adicionar e excluir, você pode apenas usar um vetor ordenado. Há um operador lower_bound() fazer uma pesquisa binária. Esta é a mesma complexidade que pesquisar um conjunto, e deve ter menor sobrecarga para pequenas quantidades de dados.

Se você ainda precisa fazer isso, como sobre apenas tratá-la como um sizeof (boost :: rosca: id). Bytes, e operando naqueles

Este exemplo assume que o tamanho do boost :: segmento :: id é um múltiplo do tamanho de um int, e que não há nenhuma embalagem, e há funções virtuais. Se isso não é verdade, ele terá de ser modificado, ou não vai funcionar em tudo.

EDIT: Eu levei um olhar para a classe boost::thread::id, e tem um boost::shared_pointer<> como membro, de modo que o código abaixo é terrivelmente quebrado. Acho que a única solução é ter os autores do boost::thread adicionar uma função hash. Estou deixando o exemplo apenas no caso da sua utilidade em algum outro contexto.

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];

Answer 4

Alguns anos de atraso para responder a esta pergunta, mas este mostrou-se como o mais relevante quando se tenta colocar um boost :: segmento :: id em um std :: unordered_map como chave. Obtendo a alça nativa foi uma boa sugestão na resposta aceita, exceto que ele não está disponível para this_thread.

Em vez disso aumentar por algum tempo tem um hash_value para a linha :: id, então isso funcionou bem para mim:

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);
    }
  };
}

É claro, necessidade de ligação contra a biblioteca libboost_thread.

Answer 5

Você pode criar classe que faz o mapeamento entre o fio :: id e algo (ex .: inteiros), que você pode usar como hash. o único inconveniente é que você deve garantir que há apenas uma instância do objeto de mapeamento no sistema.