Suspensão da Descrença

Nossa implementação de malloc() e free() avançou bastante. No último post, vimos por exemplo como unificar blocos de memória menores para evitar fragmentação. Para evitar ainda mais problemas nessa linha, vamos resolver detalhe importante para performance que estamos negligenciando há um tempo: alinhamento de memória.

O que é alinhamento de memória?

Computadores modernos leem blocos de memória de tamanho fixo, correspondente à palavra do processador. Um processador de 32 bits, por exemplo, lê quatro bytes por vez, enquanto um de 64 bits lê oito. No entanto, essa leitura só ocorre a partir de um endereço alinhado — ou seja, um processador de 32 bits só consegue ler seus quatro bytes se o endereço na memória for múltiplo de quatro.

Se o endereço não for múltiplo do tamanho da palavra, o processador precisará acessar a memória duas vezes: primeiro para buscar a primeira parte da palavra e depois para a segunda. Isso se torna ainda pior se o alocador retornar ponteiros desalinhados, pois todos os nós seguintes também estarão desalinhados, dobrando a quantidade de acessos à memória no heap.

Garantindo o alinhamento dos blocos alocados

Para evitar esse problema, é preciso alocar um múltiplo do tamanho da palavra do processador. No entanto, determinar esse tamanho pode ser complicado. Uma solução simples e eficaz para nosso caso é adotar múltiplos de 8 bytes, já que o barramento mais comum atualmente é de 64 bits. Assim, todos os endereços de blocos alocados devem ser múltiplos de 8. Vamos, então, definir uma constante para o tamanho do alinhamento:

define _ABMALLOC_ALIGNMENT_SIZE 8

Na função abmalloc(), verificamos se o tamanho solicitado está alinhado, ou seja, se é múltiplo de _ABMALLOC_ALIGNMENT_SIZE. Se já estiver alinhado, não precisamos fazer nada:

void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  size_t rest = size % _ABMALLOC_ALIGNMENT_SIZE;Code language: JavaScript (javascript)

Se o tamanho solicitado não estiver alinhado, precisamos aumentá-lo. Primeiro, calculamos o resto da divisão do tamanho solicitado por _ABMALLOC_ALIGNMENT_SIZE e subtraímos este valor do tamanho originalmente solicitado. Em seguida, adicionamos _ABMALLOC_ALIGNMENT_SIZE. Isso garante que o novo tamanho seja o menor múltiplo possível do alinhamento necessário.

if (rest != 0) {
  size = size - rest + _ABMALLOC_ALIGNMENT_SIZE;
}

Pronto! Agora, abmalloc() sempre retorna endereços alinhados.

Uma dúvida e uma vantagem extra

Um questionamento válido é: isto não vai resultar em desperdício de memória? Em plataformas com barramentos de 32 bits, por exemplo, isto pode nos levar a alocar 7 bytes não usados quando poderíamos alocar apenas 3 bytes não usados. Aqui, assumimos que este não é um problema, mas existe uma solução relativamente simples: apenas altere o valor da constante para 4, por exemplo, e recompile nosso código.

Este ajuste traz outra vantagem: blocos muito pequenos deixam de ser alocados. Por exemplo, se alguém pedir um bloco de apenas 1 byte, ele dificilmente seria reutilizado, já que raramente se precisa de um único byte. (Idealmente, nunca se deve alocar blocos tão pequenos, mas esta é uma decisão do usuário.) Com um tamanho mínimo de 8 bytes, esses blocos menores, quando liberados, terão mais chances de serem reaproveitados.

Conclusão

Com isso, terminamos nossa experiência. Esta não é uma implementação muito boa de malloc(). Para começar, não é thread-safe. Além disso, implementações modernas utilizam técnicas e heurísticas muito mais eficientes, como binning. Há também avanços bem interessantes em pesquisas, como Mesh.

Nosso objetivo foi apenas conhecer um pouco mais, com um pouco de prática e um código evoluindo aos poucos, como alocação de memória funciona. Diga nos comentários se você conseguiu ou não entender um pouco mais do tema! E caso queira explorar mais, você pode conferir o resultado final no repositório do GitHub.