string_id
2.0:3
Muitas vezes, é útil para fins de registro em aplicativos em tempo real, como jogos, para dar um nome a cada entidade. Isso facilita o rastreamento de erros, porque encontrar entidades através de nomes exclusivos é mais fácil do que analisar números exclusivos ou outras formas de identificadores. Mas as cordas são enormes e copiá -las e compará -las é lenta, para que muitas vezes não possam ser usadas no código crítico de desempenho.
Uma solução são seqüências de hash que são apenas números inteiros e, portanto, pequenos, rápido para copiar e comparar. Mas os hashes não permitem recuperar o valor original da string, que é exatamente o que é necessário para fins de registro e depuração! Além disso, há uma chance de colisões; portanto, o código de hash igual não significa necessariamente seqüências iguais. Essa chance é pequena, mas uma fonte para bugs difíceis de encontrar.
Outra solução é a internação da string. O string interning usa uma tabela de pesquisa global, onde cada string é armazenada apenas uma vez e é referenciada por meio de um índice ou algo semelhante. Copiar e comparar também é rápido, mas eles ainda não são perfeitos: você só pode acessá -los em tempo de execução. Obter o valor no tempo de compilação, por exemplo, para um comutador, não é possível.
Por um lado, por um lado, queremos identificadores rápidos e leves, mas, por outro lado, também métodos para recuperar o nome.
Esta biblioteca de código aberto fornece uma mistura entre as duas soluções na forma da classe string_id . Cada objeto armazena um valor de string com hash e um ponteiro para o banco de dados no qual o valor original da string é armazenado. Isso permite recuperar o valor da string quando necessário, além de obter o desempenho dos benefícios de strings hashed. Além disso, o banco de dados pode detectar colisões que podem ser tratadas por meio de um manipulador de colisão personalizado. Existe um literal definido pelo usuário para criar um valor de string de hash de tempo de compilação para usá-lo como uma expressão constante.
O banco de dados pode ser qualquer tipo definido pelo usuário derivado de uma determinada classe de interface. Existem vários bancos de dados predefinidos. Isso inclui um banco de dados dummy que não armazena nada, um adaptador para outros bancos de dados para torná -los ThreadSafe e um banco de dados altamente otimizado para armazenamento e recuperação eficientes de strings. Um typedef default_database é um desses bancos de dados e pode ser definido através das seguintes opções de cmake:
FOONATHAN_STRING_ID_DATABASE - Se desativado , o banco de dados está completamente desativado, por exemplo, o banco de dados dummy é usado. Isso não permite recuperar strings ou verificação de colisão, mas não precisa de tanta memória. Está ligado por padrão.
Foonathan_string_id_multithread - Se ativado , o acesso ao banco de dados será sincronizado por meio de um mutex, por exemplo, o adaptador seguro do thread será usado. Não tem efeito se o banco de dados estiver desativado. O valor padrão está ligado .
Existem classes especiais de geradores. Eles têm uma interface semelhante aos geradores de números aleatórios nas bibliotecas padrão, mas geram identificadores de string. Isso é usado para gerar um monte de identificadores de maneira automatizada. Os geradores também se cuidam de que sempre haja novos identificadores gerados. Isso também pode ser controlado através de um manipulador semelhante ao manuseio de colisão.
Consulte o exemplo/main.cpp para um exemplo.
Atualmente, ele usa um hash de 64 bits FNV-1A. As colisões são realmente raras, testei 219.606 palavras em inglês (em minúsculas) misturadas com um monte de números e não encontrei uma única colisão. Como esse é o caso de uso normal para identificadores, a função de hash é muito boa. Além disso, há uma boa distribuição dos valores de hash e é fácil de calcular.
O banco de dados usa uma tabela de hash especializada. As colisões do índice de balde são resolvidas por meio de encadeamento separado com uma lista vinculada única. Cada nó contém a sequência diretamente sem alocação de memória adicional. Os nós na lista vinculada são classificados usando o valor de hash. Isso permite a recuperação e verificação eficiente e a verificação se já existe uma string com o mesmo valor de hash armazenado. Isso o torna muito eficiente e mais rápido que o std :: UNODERED_MAP que foi usado antes (pelo menos mais rápido que a implementação do LIBSTDC ++ que usei para os benchmarks).
Esta biblioteca foi compilada sob os seguintes compiladores:
Existem as opções de compatibilidade e a substituição do MARCOS para operadores ConstexPR, NoExcept, substituição e literais. As funções do manipulador atômico podem ser desativadas opcionalmente e estão fora do GCC 4.6 por padrão, pois não as suporta.
