Por que é que estruturas de dados geralmente tem um tamanho de 2^n?

https://stackoverflow.com/questions/1816727

08-07-2019
|

Pergunta

Há um histórico razão ou algo assim ?Eu vi muito poucas vezes algo como char foo[256]; ou #define BUF_SIZE 1024.Mesmo que eu faço, principalmente, só uso 2ⁿ tamanho de buffers, principalmente porque eu acho que ele parece mais elegante e de que forma eu não tenho que pensar em um número específico.Mas eu não tenho certeza se essa é a razão a maioria das pessoas usá-los, mais informações serão bem-vindos.

Solução

Pode haver várias razões, embora muitas pessoas, como você diz, apenas faça isso por hábito.

Um lugar onde é muito útil é a implementação eficiente de buffers circulares, especialmente em arquiteturas em que o % operador é caro (aqueles sem um hardware dividem - principalmente micro -controladores de 8 bits). Usando um buffer de 2^n neste caso, o módulo é simplesmente um caso de massagem de bits nos bits superiores ou no caso de um buffer de 256 bytes, simplesmente usando um índice de 8 bits e deixando-o envolver.

Em outros casos, o alinhamento com os limites da página, os caches etc. pode oferecer oportunidades de otimização em algumas arquiteturas - mas isso seria muito específico da arquitetura. Mas pode ser que esses buffers forneçam ao compilador possibilidades de otimização, então todas as outras coisas são iguais, por que não?

Outras dicas

As linhas de cache geralmente são um múltiplo de 2 (geralmente 32 ou 64). Dados que são um múltiplo integral desse número seriam capazes de se encaixar (e utilizar totalmente) o número correspondente de linhas de cache. Quanto mais dados você puder embalar em seu cache, melhor o desempenho. Então, acho que as pessoas que projetam suas estruturas dessa maneira estão otimizando para isso.

Outra razão, além do que todos os outros mencionaram é, as instruções do SSE levam vários elementos, e o número de elementos de entrada é sempre um poder de dois. Tornando o buffer um poder de duas garantias, você não estará lendo a memória não alocada. Isso só se aplica se você estiver realmente usando instruções SSE.

Eu acho que no final, porém, a razão avassaladora na maioria dos casos é que programadores gostam de poderes de dois.

Mesas de hash, alocação por páginas

Isso realmente ajuda para tabelas de hash, porque você calcula o módulo de índice do tamanho e, se esse tamanho for um poder de dois, o módulo pode ser calculado com um simples bit-ta-e ou & em vez de usar uma instrução de classe de divisão muito mais lenta, implementando o % operador.

Olhando para um antigo livro Intel i386, and é 2 ciclos e div é 40 ciclos. Uma disparidade persiste hoje devido à complexidade fundamental muito maior da divisão, mesmo que os 1000x mais rápidos dos tempos de ciclo geral tendam a ocultar o impacto até das operações mais lentas da máquina.

Houve também um momento em que o Malloc Overhead era ocasionalmente evitado por muito tempo. A alocação está disponível diretamente no sistema operacional seria (ainda é um número específico de páginas e, portanto, é provável que um poder de dois faça o maior uso da granularidade da alocação.

E, como outros observaram, programadores como poderes de dois.

Eu posso pensar em algumas razões em cima da minha cabeça:

2^n é um valor comum em todas computador tamanhos.Isto está diretamente relacionado com a forma como os bits são representados em computadores (2 valores possíveis), o que significa que as variáveis tendem a ter intervalos de valores cujos limites são 2^n.
Porque do ponto acima, você vai encontrar muitas vezes o valor de 256 como o tamanho do buffer.Isso é porque ele é o maior número que pode ser armazenado em um byte.Então, se você deseja armazenar uma cadeia de caracteres em conjunto com o tamanho da seqüência de caracteres e, em seguida, você será mais eficiente se você armazená-lo como: SIZE_BYTE+ARRAY, onde o tamanho de byte indica o tamanho da matriz.Isso significa que a matriz pode ser de qualquer tamanho de 1 a 256.
Muitas outras vezes, os tamanhos são escolhidos com base nas coisas físicas (por exemplo, o tamanho da memória de um sistema operacional pode escolher é relacionado com o tamanho dos registradores da CPU, etc.) e estas são também vai ser uma quantidade específica de bits.Ou seja, a quantidade de memória que você pode usar normalmente será algum valor de 2^n (para um de 32 bits do sistema, 2^32).
Pode haver benefícios de desempenho/problemas de alinhamento de tais valores.A maioria dos processadores podem acessar uma determinada quantidade de bytes de cada vez, assim mesmo se você tiver uma variável cujo tamanho é digamos) 20 bits, um processador de 32 bit ainda vai ler de 32 bits, não importa o quê.Por isso é muitas vezes mais eficiente para apenas fazer com que a variável de 32 bits.Além disso, alguns processadores exigir variáveis a serem alinhados a uma determinada quantidade de bytes (porque eles não podem ler a memória, por exemplo, os endereços de memória que são ímpares).É claro que, às vezes, não é sobre ímpar locais de memória, mas os locais que são múltiplos de 4, ou 6, 8, etc.Assim, nestes casos, é mais eficiente, basta fazer buffers que serão sempre ser alinhados.

Ok, esses pontos saiu um pouco baralhado.Deixe-me saber se você precisar de mais explicação, especialmente do ponto 4, que IMO é o mais importante.

Por causa da simplicidade (leia também custo) da base 2 aritmética em eletrônicos: deslocamento para a esquerda (multiplique por 2), desligue a direita (divida por 2).

No domínio da CPU, muitas construções giram em torno da base 2 aritmética. Barramentos (controle e dados) para acessar a estrutura de memória são frequentemente alinhados na potência 2. o custo A implementação lógica na eletrônica (por exemplo, CPU) contribui para a aritmética na base 2 atraente.

Obviamente, se tivéssemos computadores analógicos, a história seria diferente.

FYI: Os atributos de um sistema sentado na camada x é uma conseqüência direta do servidor Atributos da camada do sistema sentado abaixo da camada <x. A razão pela qual estou afirmando essas hastes de alguns comentários que recebi com relação à minha postagem.

Por exemplo, as propriedades que podem ser manipuladas no nível do "compilador" são herdado & derivado das propriedades do sistema abaixo dele, ou seja, os eletrônicos na CPU.

Eu ia usar o argumento de mudança, mas poderia pensar em um bom motivo para justificá -lo.

Uma coisa que é legal em um buffer que é um poder de dois é que o manuseio de tampão circular pode usar e não dividir: em vez de dividir:

#define BUFSIZE 1024

++index;                // increment the index.
index &= BUFSIZE;       // Make sure it stays in the buffer.

Se não fosse um poder de dois, seria necessária uma divisão. Antigamente (e atualmente em fichas pequenas) que importavam.

Também é comum que as páginas sejam poderes de 2.

No Linux, eu gosto de usar getPagesize () ao fazer algo como fazer um buffer e escrever em um soquete ou descritor de arquivo.

Ele faz um bom, rodada de número na base 2.Assim como 10, 100 ou 1000000 são agradáveis, arredondar números na base 10.

Se não fosse uma potência de 2 (ou algo próximo, como 96=64+32 ou 192=128+64), então você poderia perguntar por que há a maior precisão.Não da base de dados de 2 arredondados tamanho pode vir de restrições externas, ou programador ignorância.Você vai querer saber o que é.

Outras respostas apontou para um monte de razões de ordem técnica, bem como que são válidas em casos especiais.Eu não vou repetir nenhum deles aqui.

Nas tabelas de hash, 2^n facilita a lidar com as principais colisões de uma certa maneira. Em geral, quando há uma colisão chave, você faz uma subestrutura, por exemplo, uma lista, de todas as entradas com o mesmo valor de hash; Ou você encontra outro slot gratuito. Você pode simplesmente adicionar 1 ao índice de slot até encontrar um slot gratuito; Mas essa estratégia não é ideal, porque cria grupos de lugares bloqueados. Uma estratégia melhor é calcular um segundo número de hash H2, de modo que GCD (n, h2) = 1; Em seguida, adicione o H2 ao índice de slot até encontrar um slot gratuito (com embrulho). Se n é uma potência de 2, encontrar um H2 que atenda ao GCD (n, h2) = 1 é fácil, todo número ímpar serve.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow