- Ao reduzir a struct de registro de ICMP Echo Request em um sistema de monitoramento de conectividade, o uso de memória do ring buffer caiu de 12KiB para 4KiB
- Ao não armazenar
sent_ns e received_ns ao mesmo tempo e manter apenas a latência após o recebimento usando uma união, o tamanho do array caiu para 8KiB
- A precisão foi reduzida de nanossegundos para unidades de 100 microssegundos, e
received virou bitfield, mas não houve economia adicional por causa do padding da struct
- Ao substituir parte do significado do
identifier do ICMP por um contador de 4 bits no lugar do endereço de origem, a struct caiu para 8 bytes e o array de 512 elementos passou a 4KiB
- Como a aplicação não tinha restrições de memória, não havia necessidade prática, mas isso virou um experimento de otimização considerando até layout de campos e custo de acesso a bits
Definição do problema: como armazenar registros de ping
- O sistema de monitoramento de conectividade envia ICMP Echo Requests para vários servidores e observa as médias de latência e perda de pacotes em janelas de 1, 5 e 15 minutos
- A forma de armazenamento imaginada inicialmente era um ring buffer com 512 entradas, em que cada entrada guarda horário de envio, horário de recebimento, endereço de origem, número de sequência e se houve recebimento
- O tamanho inicial do array da struct
pings_rb[512] foi medido em 12KiB
struct ping_timestamp {
uint64_t sent_ns;
uint64_t received_ns;
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
Primeira redução: unir horário de envio e tempo decorrido em uma união
- O valor que realmente se quer manter após o recebimento é a latência
received - sent, então não há necessidade de guardar ao mesmo tempo o horário de envio e o tempo decorrido
- Na struct que agrupa
sent_ts e elapsed_ts em uma união, o mesmo slot é usado como horário de envio antes da resposta e como tempo decorrido depois do recebimento
- Após essa mudança, o tamanho do array com 512 elementos caiu de 12KiB para 8KiB
struct ping_timestamp_2 {
union {
uint64_t sent_ts;
uint64_t elapsed_ts;
};
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
Segunda tentativa: reduzir a precisão e usar bitfields
- Como os tempos de ping são medidos em dezenas, centenas ou milhares de milissegundos, não é necessário armazenar toda a precisão em nanossegundos
- Ao mudar a unidade de tempo para 100 microssegundos, ou seja, 0,1ms, 43 bits passam a permitir rastrear pings por até 20 anos
- Usar 8 bits para o valor verdadeiro/falso de
received é excessivo, então foi aplicado um bitfield
- No entanto, o tamanho do array de
ping_timestamp_3 também permaneceu em 8KiB, sem economia adicional
struct ping_timestamp_3 {
uint64_t sent_or_elapsed_ts: 43;
uint64_t received: 1;
uint64_t seq_no: 16;
in_addr_t source_addr;
};
O tamanho não caiu por causa do padding da struct
ping_timestamp_2 recebe bytes de padding no final para satisfazer os requisitos de alinhamentoping_timestamp_3 coloca tempo, indicador de recebimento e número de sequência nos primeiros 8 bytes, mas ainda sobram o endereço de origem e padding depois disso- Mesmo com bitfields, ainda restam 36 bits de padding, então o tamanho total da struct não diminui
- Apenas reduzir
bool para um bit não resolve, por si só, os problemas de layout de memória e alinhamento
Remoção do endereço de origem e contador de 4 bits
- Como o produto operava em rede de dados móvel, o endereço de origem mudava com frequência, então a struct original armazenava esse endereço
- Quando o endereço mudava, o número de sequência também era reiniciado, e no passado já houve processamento simultâneo de pacotes com o mesmo número de sequência, mas endereços de origem diferentes
- O ICMP Echo Request tem um campo
identifier de 16 bits que permite à aplicação identificar os pacotes que ela mesma enviou
- Como não era necessário usar todos os 16 bits, 4 bits livres passaram a ser usados como um contador cíclico incrementado quando o endereço de origem muda
- Esse contador é incrementado em outro ponto da aplicação, sincronizado com o monitoramento de mudanças no endereço de origem
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t received : 1;
uint64_t counter: 4;
uint64_t seq_no: 16;
};
Resultado final e layout dos campos
- A struct final remove o campo de endereço de origem e acomoda tempo, indicador de recebimento, contador e número de sequência dentro de 64 bits
- O array do ring buffer com 512 elementos passou a ter 4KiB, cabendo em uma única página de dados
- Em relação aos 12KiB iniciais, a economia total foi de 8KiB
- A ordem dos campos foi ajustada para que
seq_no ficasse alinhado em uma fronteira de 16 bits, permitindo leitura com um único comando ldrh sem deslocamento
- Para ler
elapsed_or_sent_ts, basta aplicar uma máscara
Otimização adicional: reduzir o custo de acesso ao bit de recebimento
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t counter: 4;
uint64_t not_received : 1;
uint64_t seq_no: 16;
};
Conclusão
- O resultado da otimização reduziu o uso de memória de 12KiB para 4KiB, mas a aplicação em si não sofria restrições de memória
- Independentemente da necessidade real, isso acabou virando um experimento sobre layout de structs, padding, bitfields e custo de acesso em nível de instrução
- No comentário final, o autor também diz que usou a palavra “problema” de forma bem solta e admite que nem chegou a fazer benchmark
1 comentários
Opiniões no Lobste.rs
Se chegar o dia em que pensar nesse tipo de problema não for mais divertido, acho que esse será o dia de parar de programar
Otimização prematura é sempre divertida
Lidar com as consequências que aparecem depois que você percebe por que aquela otimização foi prematura normalmente não é divertido
Fiquei meio confuso com a parte de usar 43 bits no timestamp. 24 bits parecem suficientes
Pelo fato de mencionar um ring buffer de 512 posições, parece que ele envia um novo ping a cada 2 segundos e rastreia os pings dos últimos 17 minutos e 4 segundos
Como primeiro passo, daria para usar codificação delta em relação ao temporizador/contador ideal. Basta incrementar o último horário de envio em 2 segundos e observar o índice do ring buffer para saber facilmente quando o pacote deveria ter sido enviado; aí é só registrar se foi enviado exatamente na hora, com 0,1 ms de atraso, com 2,3 ms de atraso etc.
Também não parece necessário que o tempo decorrido ultrapasse 17 minutos e 4 segundos, já que depois disso o ping expiraria. 512 × 2s = 10.240.000 × 100μs, então nessa precisão cerca de 23,3 bits já bastariam, e você pode arredondar para 24 bits se quiser. Talvez os cerca de 6.536.216 padrões de bits inválidos que sobrarem possam até ser usados para outra coisa
Como bônus, com 24 bits dá para aumentar bastante a precisão de “enviado” e reduzir o erro de quantização. Mesmo com precisão de microssegundos, o ping ainda poderia ser enviado com até 16 segundos de atraso, então parece haver bastante folga
Não sei se reduzir as amostras de 64 bits para 48 bits ajudaria ou atrapalharia o desempenho. Não me surpreenderia se o resultado variasse entre ambientes 32 bits/64 bits em x86 e ARM
Dito isso, o tamanho original já cabe com muita facilidade no cache de dados até de processadores bem antigos, então não parece que economizar memória faria diferença
Tenho certeza de que é exatamente por isso que fazemos otimização prematura. É um esporte por diversão
Ao projetar sistemas ou trabalhar com linguagens de sistema de baixo nível, otimização prematura é sinceramente uma das minhas coisas favoritas
Pelo menos existe a esperança de economizar tempo e memória mais tarde. Um resultado intermediário só significa um pouco mais de dor de cabeça para descobrir “por que eu fiz desse jeito?”, e o pior caso — e às vezes até o melhor — é a otimização crescer tanto durante o projeto que você acaba não conseguindo fazer o projeto em si. Você fecha o programa pensando: “Ah, isso ficou enrolado demais, por que eu estou fazendo isso?”