Por que malloc + memset é mais lento que calloc?

256

Sabe-se que callocé diferente do mallocque inicializa a memória alocada. Com calloc, a memória é definida como zero. Com malloc, a memória não é limpa.

Assim, no trabalho diário, eu considero calloccomo malloc+ memset. Aliás, por diversão, escrevi o seguinte código para uma referência.

O resultado é confuso.

Código 1:

#include<stdio.h>
#include<stdlib.h>
#define BLOCK_SIZE 1024*1024*256
int main()
{
        int i=0;
        char *buf[10];
        while(i<10)
        {
                buf[i] = (char*)calloc(1,BLOCK_SIZE);
                i++;
        }
}

Saída do código 1:

time ./a.out  
**real 0m0.287s**  
user 0m0.095s  
sys 0m0.192s  

Código 2:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BLOCK_SIZE 1024*1024*256
int main()
{
        int i=0;
        char *buf[10];
        while(i<10)
        {
                buf[i] = (char*)malloc(BLOCK_SIZE);
                memset(buf[i],'\0',BLOCK_SIZE);
                i++;
        }
}

Saída do código 2:

time ./a.out   
**real 0m2.693s**  
user 0m0.973s  
sys 0m1.721s  

Substituir memsetpor bzero(buf[i],BLOCK_SIZE)no Código 2 produz o mesmo resultado.

Minha pergunta é: Por que malloc+ é memsetmuito mais lento que calloc? Como pode callocfazer isso?

kingkai
fonte

Respostas:

455

A versão curta: sempre use em calloc()vez de malloc()+memset(). Na maioria dos casos, eles serão os mesmos. Em alguns casos, calloc()fará menos trabalho porque pode pular memset()completamente. Em outros casos, calloc()pode até trapacear e não alocar nenhuma memória! No entanto, malloc()+memset()sempre fará a quantidade total de trabalho.

Para entender isso, é necessário um breve tour pelo sistema de memória.

Visita rápida à memória

Existem quatro partes principais aqui: seu programa, a biblioteca padrão, o kernel e as tabelas de páginas. Você já conhece seu programa, então ...

Os alocadores de memória gostam malloc()e calloc()estão lá para pegar pequenas alocações (de 1 byte a 100s de KB) e agrupá-las em conjuntos de memória maiores. Por exemplo, se você alocar 16 bytes, malloc()primeiro tentará obter 16 bytes de um de seus pools e, em seguida, solicitará mais memória do kernel quando o pool ficar seco. No entanto, como o programa que você está perguntando está alocando uma grande quantidade de memória de uma só vez, malloc()e calloc()apenas solicitará essa memória diretamente do kernel. O limite para esse comportamento depende do seu sistema, mas vi 1 MiB usado como limite.

O kernel é responsável por alocar a RAM real para cada processo e garantir que os processos não interfiram na memória de outros processos. Isso é chamado de proteção de memória, é uma sujeira comum desde os anos 90, e é a razão pela qual um programa pode travar sem derrubar todo o sistema. Portanto, quando um programa precisa de mais memória, ele não pode apenas pegar a memória, mas pede a memória do kernel usando uma chamada de sistema como mmap()ou sbrk(). O kernel fornecerá RAM para cada processo, modificando a tabela de páginas.

A tabela de páginas mapeia os endereços de memória para a RAM física real. Os endereços do seu processo, 0x00000000 a 0xFFFFFFFF em um sistema de 32 bits, não são memória real, mas endereços na memória virtual. O processador divide esses endereços em 4 páginas KiB, e cada página pode ser atribuída a uma parte diferente da RAM física, modificando a tabela de páginas. Somente o kernel tem permissão para modificar a tabela de páginas.

Como não funciona

Veja como a alocação de 256 MiB não funciona:

  1. Seu processo liga calloc()e pede 256 MiB.

  2. A biblioteca padrão liga mmap()e pede 256 MiB.

  3. O kernel encontra 256 MiB de RAM não utilizada e o fornece ao seu processo, modificando a tabela de páginas.

  4. A biblioteca padrão zera a RAM memset()e retorna de calloc().

  5. Seu processo acaba sendo encerrado e o kernel recupera a RAM para que possa ser usada por outro processo.

Como realmente funciona

O processo acima funcionaria, mas simplesmente não acontece dessa maneira. Existem três grandes diferenças.

  • Quando seu processo obtém nova memória do kernel, essa memória provavelmente foi usada por algum outro processo anteriormente. Este é um risco de segurança. E se essa memória tiver senhas, chaves de criptografia ou receitas secretas de salsa? Para impedir que dados confidenciais vazem, o kernel sempre limpa a memória antes de entregá-la a um processo. Podemos também limpar a memória zerando-a e, se a nova memória estiver zerada, também podemos garantir isso, mmap()garantindo assim que a nova memória retornada seja sempre zerada.

  • Existem muitos programas por aí que alocam memória, mas não a usam imediatamente. Algumas vezes a memória é alocada, mas nunca usada. O kernel sabe disso e é preguiçoso. Quando você aloca nova memória, o kernel não toca na tabela de páginas e não fornece nenhuma RAM ao seu processo. Em vez disso, ele encontra algum espaço de endereçamento no seu processo, anota o que deveria ser feito lá e promete que colocará RAM lá se o seu programa realmente o usar. Quando seu programa tenta ler ou gravar nesses endereços, o processador aciona uma falha de página e o kernel inicia a atribuição de RAM a esses endereços e retoma o programa. Se você nunca usar a memória, a falha da página nunca ocorrerá e o seu programa nunca obterá a RAM.

  • Alguns processos alocam memória e, em seguida, leem dela sem modificá-la. Isso significa que muitas páginas na memória em diferentes processos podem ser preenchidas com zeros primitivos retornados mmap(). Como essas páginas são todas iguais, o kernel faz com que todos esses endereços virtuais aponte uma única página compartilhada de 4 KiB de memória cheia de zeros. Se você tentar gravar nessa memória, o processador acionará outra falha de página e o kernel entrará em ação para fornecer uma nova página de zeros que não são compartilhados com outros programas.

O processo final se parece mais com isso:

  1. Seu processo liga calloc()e pede 256 MiB.

  2. A biblioteca padrão liga mmap()e pede 256 MiB.

  3. O kernel encontra 256 MiB de espaço de endereço não utilizado , faz uma anotação sobre o que esse espaço de endereço agora é usado e retorna.

  4. A biblioteca padrão sabe que o resultado de mmap()sempre é preenchido com zeros (ou será quando ele realmente receber memória RAM), para que não toque na memória, para que não haja falha na página e a RAM nunca seja fornecida ao seu processo .

  5. Seu processo acaba sendo encerrado e o kernel não precisa recuperar a RAM, porque nunca foi alocada em primeiro lugar.

Se você memset()zerar a página, memset()acionará a falha da página, fará com que a RAM seja alocada e zere-a, mesmo que ela já esteja cheia de zeros. Isso é uma quantidade enorme de trabalho extra e explica por que calloc()é mais rápido que malloc()e memset(). Se acabar usando a memória de qualquer maneira, calloc()ainda é mais rápido que malloc()e, memset()mas a diferença não é tão ridícula.


Isso nem sempre funciona

Nem todos os sistemas possuem memória virtual paginada; portanto, nem todos os sistemas podem usar essas otimizações. Isso se aplica a processadores muito antigos, como o 80286, bem como a processadores embarcados, pequenos demais para uma sofisticada unidade de gerenciamento de memória.

Isso também nem sempre funciona com alocações menores. Com alocações menores, calloc()obtém memória de um pool compartilhado em vez de ir diretamente para o kernel. Em geral, o pool compartilhado pode ter dados indesejados armazenados nele da memória antiga que foi usada e liberada free(), assim calloc()pode levar a memória e chamar memset()para limpá-la. As implementações comuns rastrearão quais partes do pool compartilhado são primitivas e ainda preenchidas com zeros, mas nem todas as implementações fazem isso.

Dissipando algumas respostas erradas

Dependendo do sistema operacional, o kernel pode ou não zerar a memória em seu tempo livre, caso você precise obter alguma memória zerada posteriormente. O Linux não zera a memória antes do tempo, e o Dragonfly BSD recentemente também removeu esse recurso de seu kernel . No entanto, alguns outros kernels não possuem memória zero antes do tempo. A zeragem de páginas durante a ociosidade não é suficiente para explicar as grandes diferenças de desempenho.

A calloc()função não está usando uma versão especial alinhada à memória memset()e, de qualquer maneira , não seria muito mais rápida. A maioria das memset()implementações para processadores modernos é mais ou menos assim:

function memset(dest, c, len)
    // one byte at a time, until the dest is aligned...
    while (len > 0 && ((unsigned int)dest & 15))
        *dest++ = c
        len -= 1
    // now write big chunks at a time (processor-specific)...
    // block size might not be 16, it's just pseudocode
    while (len >= 16)
        // some optimized vector code goes here
        // glibc uses SSE2 when available
        dest += 16
        len -= 16
    // the end is not aligned, so one byte at a time
    while (len > 0)
        *dest++ = c
        len -= 1

Como você pode ver, memset()é muito rápido e você não vai conseguir nada melhor para grandes blocos de memória.

O fato de memset()zerar a memória que já está zerada significa que a memória é zerada duas vezes, mas isso explica apenas uma diferença de desempenho de 2x. A diferença de desempenho aqui é muito maior (medi mais de três ordens de magnitude no meu sistema entre malloc()+memset()e calloc()).

Truque de festa

Em vez de repetir 10 vezes, escreva um programa que aloque memória até malloc()ou calloc()retorne NULL.

O que acontece se você adicionar memset()?

Dietrich Epp
fonte
7
@ Dietrich: é fácil verificar a explicação da memória virtual de Dietrich sobre o SO que aloca a mesma página com zero preenchimento muitas vezes para o calloc. Basta adicionar um loop que grava dados indesejados em todas as páginas de memória alocada (escrever um byte a cada 500 bytes deve ser suficiente). O resultado geral deve ficar muito mais próximo, pois o sistema seria forçado a realmente alocar páginas diferentes nos dois casos.
kriss
1
@kriss: de facto, apesar de um byte de cada 4096 é suficiente na maioria vasta de sistemas de
Dietrich Epp
Na verdade, calloc()muitas vezes faz parte do mallocconjunto de implementação e, portanto, otimizado para não chamar bzeroao obter memória mmap.
mirabilos
1
Obrigado pela edição, isso é quase o que eu tinha em mente. No início, você declara sempre usar calloc em vez de malloc + memset. Declare como 1. padrão para malloc 2. se uma pequena parte do buffer precisar ser zerada, memset essa parte 3. use o calloc. Em particular, NÃO malloc + memset o tamanho inteiro (use calloc para isso) e NÃO padronize a chamada de tudo, pois isso dificulta coisas como valgrind e analisadores de código estático (toda a memória é inicializada repentinamente). Fora isso, acho que está tudo bem.
empregado do mês
5
Embora não esteja relacionado à velocidade, calloctambém é menos propenso a erros. Ou seja, onde large_int * large_intresultaria um estouro, calloc(large_int, large_int)retorna NULL, mas malloc(large_int * large_int)é um comportamento indefinido, pois você não sabe o tamanho real do bloco de memória que está sendo retornado.
Dunes
12

Como em muitos sistemas, no tempo de processamento disponível, o sistema operacional define a memória livre como zero por si própria e a marca como segura calloc(); portanto, quando você liga calloc(), ele pode já ter memória zerada e gratuita para fornecer a você.

Chris Lutz
fonte
2
Você tem certeza? Quais sistemas fazem isso? Eu pensei que a maioria dos sistemas operacionais apenas desligava o processador quando estavam ociosos e zerava a memória sob demanda dos processos alocados assim que gravavam na memória (mas não quando a alocavam).
Dietrich Epp
@ Dietrich - Não tenho certeza. Ouvi uma vez e parecia uma maneira razoável (e razoavelmente simples) de tornar calloc()mais eficiente.
22610 Chris Lutz #
@Pierreten - Não consigo encontrar nenhuma informação boa sobre calloc()otimizações específicas e não sinto vontade de interpretar o código-fonte libc para o OP. Você pode procurar algo para mostrar que essa otimização não existe / não funciona?
22710 Chris Lutz
13
@ Dietrich: O FreeBSD deve zerar as páginas em tempo ocioso: Veja sua configuração vm.idlezero_enable.
Zan Lynx
1
@ DietrichEpp desculpe necro, mas por exemplo o Windows faz isso.
Andreas Grapentin
1

Em algumas plataformas, em alguns modos, o malloc inicializa a memória com um valor tipicamente diferente de zero antes de retorná-la, portanto a segunda versão pode muito bem inicializar a memória duas vezes

Stewart
fonte