Existe alguma vantagem na manipulação de bits no estilo c sobre std :: bitset?

16

Eu trabalho quase exclusivamente em C ++ 11/14 e geralmente encolho quando vejo código como este:

std::int64_t mArray;
mArray |= someMask << 1;

Este é apenas um exemplo; Eu estou falando sobre manipulação bit-wise em geral. Em C ++, existe realmente algum ponto? O exposto acima é distorcido e propenso a erros, enquanto o uso de um std::bitsetpermite:

  1. modifique mais facilmente o tamanho do std::bitsetconforme necessário, ajustando um parâmetro de modelo e deixando a implementação cuidar do resto, e
  2. gaste menos tempo descobrindo o que está acontecendo (e possivelmente cometendo erros) e escreva de std::bitsetmaneira semelhante a std::arrayoutros contêineres de dados.

Minha pergunta é; existe alguma razão para não usar std::bitsetsobre tipos primitivos, exceto para compatibilidade com versões anteriores?

quant
fonte
O tamanho de a std::bitseté fixado em tempo de compilação. Essa é a única desvantagem incapacitante em que consigo pensar.
Rwong 18/05/19
1
@rwong Estou falando sobre std::bitsetmanipulação de bits no estilo c (por exemplo int), que também é corrigida em tempo de compilação.
quant
Um motivo pode ser o código legado: o código foi gravado quando std::bitsetnão estava disponível (ou era conhecido pelo autor) e não houve um motivo para reescrever o código a ser usado std::bitset.
Bart van Ingen Schenau
Pessoalmente, acho que a questão de como tornar "operações em um conjunto / mapa / array de variáveis ​​binárias" fáceis de entender para todos ainda não foi resolvida, porque existem muitas operações usadas na prática que não podem ser reduzidas a operações simples. Também existem muitas maneiras de representar esses conjuntos, sendo bitsetum deles, mas um pequeno vetor ou conjunto de ints (de índice de bits) também pode ser legítimo. A filosofia do C / C ++ não esconde essas complexidades de escolha do programador.
Rwong 18/05/19

Respostas:

12

Do ponto de vista lógico (não técnico), não há vantagem.

Qualquer código C / C ++ simples pode ser quebrado dentro da "construção de biblioteca" adequada. Após esse envolvimento, a questão de "se isso é mais vantajoso do que isso" se torna uma questão discutível.

Do ponto de vista da velocidade, o C / C ++ deve permitir que a construção da biblioteca gere um código tão eficiente quanto o código simples que ele envolve. No entanto, isso está sujeito a:

  • Função embutida
  • Verificação em tempo de compilação e eliminação de verificações desnecessárias em tempo de execução
  • Eliminação de código morto
  • Muitas outras otimizações de código ...

Usando esse tipo de argumento não técnico, qualquer "função ausente" pode ser adicionada por qualquer pessoa e, portanto, não é contada como desvantagem.

No entanto, requisitos e limitações integrados não podem ser superados com código adicional. Abaixo, argumento que o tamanho de std::bitseté uma constante em tempo de compilação e, portanto, embora não seja considerado uma desvantagem, ainda é algo que afeta a escolha do usuário.


Do ponto de vista estético (legibilidade, facilidade de manutenção, etc.), há uma diferença.

No entanto, não é aparente que o std::bitsetcódigo conquiste imediatamente o código C simples. É preciso examinar partes maiores do código (e não algumas amostras de brinquedos) para dizer se o uso de std::bitsetmelhorou a qualidade humana do código-fonte.


A velocidade da manipulação de bits depende do estilo de codificação. O estilo de codificação afeta a manipulação de bits C / C ++ e é igualmente aplicável std::bitsettambém, conforme explicado a seguir.


Se alguém escreve um código que usa operator []para ler e gravar um bit de cada vez, será necessário fazer isso várias vezes se houver mais de um bit a ser manipulado. O mesmo pode ser dito do código no estilo C.

No entanto, bitsettambém tem outros operadores, tais como operator &=, operator <<=, etc., que opera sobre a largura total da bitset. Como o maquinário subjacente geralmente pode operar em 32 bits, 64 bits e às vezes 128 bits (com SIMD) por vez (no mesmo número de ciclos de CPU), código projetado para tirar proveito de tais operações de vários bits pode ser mais rápido que o código de manipulação de bits "em loop".

A idéia geral é chamada SWAR (SIMD dentro de um registro) e é um subtópico sob manipulações de bits.


Alguns fornecedores de C ++ podem implementar bitsetentre 64 bits e 128 bits com o SIMD. Alguns fornecedores podem não o fazer (mas eventualmente o fazem). Se for necessário saber o que a biblioteca do fornecedor C ++ está fazendo, a única maneira é observar a desmontagem.


Quanto a std::bitsetter limitações, posso dar dois exemplos.

  1. O tamanho de std::bitsetdeve ser conhecido em tempo de compilação. Para criar uma matriz de bits com tamanho escolhido dinamicamente, será necessário usar std::vector<bool>.
  2. A especificação atual do C ++ para std::bitsetnão fornece uma maneira de extrair uma fatia consecutiva de N bits de um bitsetM maior de bits.

O primeiro é fundamental, o que significa que, para as pessoas que precisam de conjuntos de bits de tamanho dinâmico, precisam escolher outras opções.

O segundo pode ser superado, porque é possível escrever algum tipo de adaptador para executar a tarefa, mesmo que o padrão bitsetnão seja extensível.


Existem certos tipos de operações avançadas do SWAR que não são fornecidas de imediato std::bitset. Pode-se ler sobre essas operações neste site sobre permutações de bits . Como de costume, é possível implementá-las por conta própria, operando em cima std::bitset.


Em relação à discussão sobre desempenho.

Uma advertência: muitas pessoas perguntam por que (algo) da biblioteca padrão é muito mais lento do que um código simples no estilo C. Não repetiria aqui o pré-requisito do microbenchmarking, mas tenho apenas este conselho: verifique o benchmark no "modo de liberação" (com otimizações ativadas) e verifique se o código não está sendo eliminado (eliminação do código morto) ou está sendo içada em um loop (movimento de código invariante em loop) .

Como, em geral, não podemos dizer se alguém (na Internet) estava fazendo as marcas de microbench corretamente, a única maneira de obter uma conclusão confiável é fazer nossas próprias marcas de microbench, documentar os detalhes e enviar para revisão e crítica públicas. Não faz mal refazer as marcas de micropigmentação que outras pessoas fizeram antes.

rwong
fonte
O problema nº 2 também significa que o conjunto de bits não pode ser usado em nenhuma instalação paralela em que cada thread funcione em um subconjunto do conjunto de bits.
user239558
@ user239558 Duvido que alguém queira paralelizar o mesmo std::bitset. Não há garantia de consistência de memória (in std::bitset), o que significa que não deve ser compartilhado entre núcleos. As pessoas que precisam compartilhá-lo entre núcleos tendem a criar sua própria implementação. Quando os dados são compartilhados entre diferentes núcleos, é comum alinhá-los ao cache da linha. Não fazer isso reduz o desempenho e expõe mais armadilhas da não-atomicidade. Não tenho conhecimento suficiente para dar uma visão geral de como construir uma implementação paralelamente agradável std::bitset.
Rwong
a programação paralela de dados geralmente não requer consistência de memória. você sincroniza apenas entre fases. Eu absolutamente gostaria de processar um conjunto de bits em paralelo, acho que qualquer pessoa com uma grande bitsetvontade.
user239558
@ user239558 que soa como cópia (a faixa relevante de bits a ser processada por cada núcleo deve ser copiada antes do início do processamento). Eu concordo com isso, embora eu ache que alguém que pensa em paralelismo já pense em implantar sua própria implementação. Em geral, muitos recursos de biblioteca padrão do C ++ são fornecidos como implementações de linha de base; quem tem necessidades mais sérias vai implementar as suas próprias.
Rwong
não, não há cópia. é simplesmente acessar diferentes partes de uma estrutura de dados estática. nenhuma sincronização é necessária então.
user239558
2

Isso certamente não se aplica a todos os casos, mas, ocasionalmente, um algoritmo pode depender da eficiência da modificação de bits no estilo C para fornecer ganhos significativos de desempenho. O primeiro exemplo que me vem à mente é o uso de placas de bit , codificações inteiras inteligentes das posições dos jogos de tabuleiro, para acelerar os mecanismos de xadrez e similares. Aqui, o tamanho fixo dos tipos inteiros não é problema, uma vez que os tabuleiros de xadrez sempre têm 8 * 8.

Para um exemplo simples, considere a seguinte função (retirada desta resposta por Ben Jackson ) que testa uma posição do Connect Four para vitória:

// return whether newboard includes a win
bool haswon2(uint64_t newboard)
{
    uint64_t y = newboard & (newboard >> 6);
    uint64_t z = newboard & (newboard >> 7);
    uint64_t w = newboard & (newboard >> 8);
    uint64_t x = newboard & (newboard >> 1);
    return (y & (y >> 2 * 6)) | // check \ diagonal
           (z & (z >> 2 * 7)) | // check horizontal -
           (w & (w >> 2 * 8)) | // check / diagonal
           (x & (x >> 2));      // check vertical |
}
David Zhang
fonte
2
Você acha que um std::bitsetseria mais lento?
Dez
Bem, de uma rápida olhada na fonte, o conjunto de bits libc ++ é baseado em um único size_t ou em uma matriz deles, então provavelmente seria compilado para algo essencialmente equivalente / idêntico, especialmente em um sistema em que sizeof (size_t) == 8 - então não, provavelmente não seria mais lento.
Ryan Pavlik