Benchmarks de algoritmos de compressão

Estava lendo um pouco sobre o histórico do Zstd (o algortitmo de compressão criado pelo Facebook, que agora virou praticamente o padrão do Arch Linux). Tinha lá algumas tabelas fazendo várias comparações entre os algoritmos e tals, e eu pensei… “bora fazer isso, só que em casa”.

Código que eu usei (Python 3):

Enfim, ao experimento altamente científico que eu fiz:

Lutadores

  • gzip (algoritmo dos .zip e dos .gz, incluindo tar.gz). Padrão de mercado dos últimos 20 anos. pigz é uma versão levemente modificada (mas ainda compatível) projetada para funcionar melhor em sistemas multicore.
  • zstd (algoritmo interno do Facebook, usado nos pacotes do Arch Linux). Almeja ser o padrão do futuro.
  • compress (algoritmo do GIF). Padrão de mercado dos anos 80 e 90.
  • xz (algoritmo do 7-zip). Apesar de “invisível”, ocupa um nicho importante: os pacotes do Debian e Ubuntu, e o kernel Linux, são distribuídos nesse formato. Queria testar o pixz (tenta fazer com o xz o mesmo que o pigz fez com o gzip), mas não consegui fazer funcionar.
  • bzip2 - usado em alguns projetos open-source para distribuir código fonte.
  • lz4, lzop - usado em algumas distribuições para comprimir o initramfs

Arena

Usei os arquivos do Silesia Corpus, o mesmo que o Facebook cita no artigo que eu linkei lá em cima. Aqui a nós fazemo siença e reproduzimos os resultatos dos pares. Eu os pus numa subpasta ./in da pasta onde rodei o script.

Resultados (médias)

Método    Comprimiu X vezes  Consome X MB/s  Produz X MB/s
gzip      3.72               28.62           187.60
pigz      3.72               132.20          320.42
zstd      3.92               139.31          641.42
compress  2.94               62.20           204.84
xz        5.57               2.49            84.73
bzip2     5.45               13.30           36.97
lz4       2.34               267.83          984.40
lzop      2.25               246.87          452.38

Bom, é isso, é um tópico completamente aleatório. Sintam-se livres para postar os resultados de vocês.

O teste carrega os arquivos na RAM antes de passar o compressor, então HD/SSD não deve afetar o resultado.

5 Curtidas

O que e um algoritmo de compressão?

Testa depois o algoritmo PAQ6

1 Curtida

O nome é bem sugestivo.

Se quiser a opinião de um dicionário, um algoritmo é um conjunto das regras e procedimentos lógicos bem definidos que levam à solução de um problema (no caso, representar as informações do arquivo em uma forma que demande menos armazenamento) em um número finito de etapas.

1 Curtida

A fragmentação dos algoritmos PAQ é bem grande, devo dizer. Achei bem umas 10 versões incompatíveis dele.

Acho que o código fonte do PAQ6 (2004), mas ele só compila/roda como 32 bits (no início ele verifica isso, e estou com medo de retirar essa verificação - vai que ele não funciona bem com valores de 64 bits?).

Usa o kgb archiver vc vai adorar

São várias técincas de compressão. Em palavras mais do tipo “parabolas” é o mesmo que simplificar frações na matemática:

64/40

dividimos por 2 até o minimo
32/20
16/10
8/5
8/5 é o tamanho compressado de 64/40

Exemplo hipotético:
Forma não compressada
alert(‘Hi’);
alert(‘there’);
alert(’!!!’);

Forma compressada
alert(‘Hi there !!!’);

Outro exemplo é 2 ou mais software usam ferramentas em comum então o programa que comprensa pode reduzir por estas ferramentas comuns, etc… Em sons eles podem tirar ruidos “em branco” mais ou menos como o mp3 faz…

tava no hype de testar algoritmo de compressão semana passada, testei os algoritmos que o btrfs suporta, e eu cheguei nesses resultados:
image
o script que eu usei foi esse:

#btrfs datacow
mkfs.btrfs /dev/sda3 -f
mount /dev/sda3 /mnt -o autodefrag,nodatacow
time pacstrap /mnt grub linux base networkmanager --cachedir /var/cache/pacman/pkg/
sleep 5
df -h
sleep 5

#btrfs nodatacow
umount /mnt
mkfs.btrfs /dev/sda3 -f
mount /dev/sda3 /mnt -o autodefrag,nodatacow
time pacstrap /mnt grub linux base networkmanager --cachedir /var/cache/pacman/pkg/
sleep 5
df -h
sleep 5

#btfs compress=lzo
umount /mnt
mkfs.btrfs /dev/sda3 -f
mount /dev/sda3 /mnt -o autodefrag,compress=lzo
time pacstrap /mnt grub linux base networkmanager --cachedir /var/cache/pacman/pkg/
sleep 5
df -h
sleep 5

#btrfs compress=zlib
umount /mnt
mkfs.btrfs /dev/sda3 -f
mount /dev/sda3 /mnt -o autodefrag,compress=zlib
time pacstrap /mnt grub linux base networkmanager --cachedir /var/cache/pacman/pkg/
sleep 5
df -h
sleep 5

#btrfs compress=zstd
umount /mnt
mkfs.btrfs /dev/sda3 -f
mount /dev/sda3 /mnt -o autodefrag,compress=zstd
time pacstrap /mnt grub linux base networkmanager --cachedir /var/cache/pacman/pkg/
sleep 5
df -h
sleep 5

nada comparado ao script do OP, mas foi legal a experiência
obs: o baobab (Analisador de discos do GNOME) reportou esse mesmo tamanho em todos, não faço a mínima ideia do porque o df reporta valor diferente

1 Curtida

Sugerido pelo camarada @Natanael.755, benchmark com PAQ6 (no caso, KGB, um derivado).

Infelizmente, não vai dar para fazer um benchmark “só na memória” como eu fiz com os algoritmos em cima, já que o KGB não aceita dados “isolados” para comprimir direto do stdin. Então, para tornar a comparação mais justa, eu comparei o KGB com outros formatos que tentam comprimir vários arquivos.

Eis o script do teste, para favorecer a ciência:

Usei os mesmos arquivos do teste acima.

Concorrentes:

  • zip - o gzip do primeiro teste, atuando em vários arquivos.
  • 7z - o xz do primeiro teste, atuando em vários arquivos.
  • kgb - Versão modernizada do algoritmo PAQ6, vencedor de uma competição em 2004 de formato de compressão mais potente do mundo.
  • zpaq - Uma outra modernização do PAQ6, otimizada para processadores multicore. Coloquei dois graus de compressão, 3 (padrão) e 5 (o mais potente), para ver como se compara com o kgb.

Resultados

Método    Comprimiu X vezes  Consome X MB/s  Produz X MB/s
zip       3.11               28.91           171.00
7z        4.26               7.24            72.37
kgb       4.55               0.42            0.50
zpaq      3.05               45.25           262.49
zpaq -m5  5.32               0.92            0.96