Googles compressiealgoritme Brotli volgt Zopfli op

Google brengt twee jaar na Zopfli een nieuw compressiealgoritme uit met de naam Brotli. Waar Zopfli nog compatibel was met Deflate, is Brotli een volledig nieuw dataformaat. Het nieuwe formaat moet een 20 tot 26 procent hogere compressieverhouding kunnen halen over Zopfli.

Een eigen studie van de Google-ontwikkelaars liet zien dat Brotli ongeveer zo snel is als zlib's Deflate-implementatie, terwijl het gemiddeld iets kleinere files oplevert dan lzma en bzip2. De naam van het nieuwe opensource-compressiealgoritme is net als Zopfli weer afgeleid van een Zwitsers bakkerijproduct, Brötli, wat 'broodje' in Zwitsers Duits betekent.

Google ontwikkelde het nieuwe algoritme naar aanleiding van de ontwikkeling van Zopfli. Volgens de eigen onderzoekspaper werden na de brede acceptatie van Zopfli 'geluiden gehoord' dat het tijd zou worden om het Deflate-bestandsformaat te gaan verlaten en een nieuwe vorm te bedenken. Met Brotli doet de internetgigant een poging een lossless compressieformaat te maken dat fundamenteel anders is dan Deflate.

Voor Google en anderen helpen alle kleine beetjes omdat kleinere bestanden zorgen voor het sneller laden van pagina's. De hoop is dat het formaat in de toekomst wordt ondersteund door alle grote webbrowsers omdat het formaat voordeel zou opleveren voor gebruikers van mobiele verbindingen.

Reacties (65)

[atlaste]

Sinds vele jaren volg ik eigenlijk alle algoritmische vernieuwingen in compressie-land. In navolging van het artikel heb ik daarom maar eens even de specificatie opgezocht. Die is hier te vinden:

- http://www.ietf.org/id/draft-alakuijala-brotli-05.txt

De methode die beschreven wordt is op hoofdlijnen:
- Run-length encoding (LZ77-variant)
- Vervolgens deflate over het resultaat.
- Daarnaast passen ze de 'standaard' compressie technieken toe die tekst aanzienlijk kleiner maken.

Omdat sommige combinaties makkelijk samen te voegen zijn wordt dit ook gedaan. Dat levert een paar bytes op. Behalve dat, is het eigenlijk niet heel veel meer dan bovenstaande. Dit is overigens allemaal niet heel erg vernieuwend; het voornaamste "vernieuwende" is dat het geheel relentlessly optimized is.

De voornaamste reden dat het snel is wijt ik aan de gebruikte combinaties. Omdat LZ77 de data inslinkt, kan je daarnaast meer data verwerken zonder extra memory access. Kortom, er wordt meer in je cache verwerkt, waardoor het niet echt iets extra's kost.

Oh en ik moest wel even lachen om de appendices die ongetwijfeld op veel data zijn getraind. Dat is inderdaad hoe je dat doet

Kortom, leuke combinatie, nieuw bestandsformaat, het werkt vast goed -- maar wmb. geen nieuw compressie-algoritme.

[Sando]

Debian packages (Ubuntu, Debian, Linux Mint) worden veelal gecomprimeerd in het xz formaat (lzma2) omdat dit als het beste algoritme wordt beschouwd voor compressie. Maar voor 'even snel' gaat alles toch door de gzip heen, omdat xz veel trager is.

Als die brotli echt sneller zijn werk doet, dan is dat toch wel waardevol.

[Verwijderd]

Als iemand met een optimalizatie achtergrond vind ik je observatie dat een algoritme niet nieuw is omdat de afzonderlijke stapjes van het algoritme geen nieuwe technieken bevatten nogal kort door de bocht. Optimalizatie is verre van triviaal en een ontzettend complex gebied binnen de wiskunde.

Als ik in je redenatie meega dan is blijkbaar CPLEX ook weinig vernieuwend, ze gebruiken bijvoorbeeld wat cuts en branch-and-bound, allemaal bestaande technieken.

[atlaste]

Het artikel suggereert dat ze bij Google een nieuw compressie algoritme hebben bedacht. Dat punt ben ik het niet mee eens: hoe complex en vernieuwend optimalisatie en combinatie van algoritmes ook zijn, het blijven dezelfde algoritmes. Beiden kunnen wel gewoon innovatie zijn.

Vwb. optimalisatie in de wiskunde, met alle respect voor de complexiteit, dit is iets compleet anders dan het combineren van software algoritmes en op optimaliseren naar hardware.

CPLEX ken ik niet, daar ga ik geen uitspraken over doen.

[Bruin Poeper]

[quote]
het voornaamste "vernieuwende" is dat het geheel relentlessly optimized meedogenloos geoptimaliseerd is.

[MadEgg]

Geen advertenties plaatsen door Google, dat zou de pagina's een stuk sneller laten laden... Maar ja, daar zitten zij niet op de wachten natuurlijk

Een eigen studie van de Google-ontwikkelaars liet zien dat Brotli ongeveer zo snel is als zlib's Deflate-implementatie, terwijl het gemiddeld iets kleinere files oplevert dan lzma en bzip2.

Dat is ook nogal een verschil. Bzip2 is aanmerkelijk sneller dan bijvoorbeeld xz (die LZMA gebruikt) maar xz maakt flink kleinere bestanden. Als het dus iets kleiner is dan xz zal het flink kleiner zijn dan bzip2.

In ieder geval een indrukwekkende prestatie als ze xz weten te verslaan qua compressie op een hogere snelheid dan zlib/deflate.

[increddibelly]

waar zie jij xz in het artikel of in de bron?
Brotli maakt kleinere bestanden dan bzip2 en heeft daar ongeveer net zoveel tijd voor nodig, als de tijd die zlib nodig heeft om hetzelfde bestand te Deflate-en.

[Reactie gewijzigd door increddibelly op 23 juli 2024 02:49]

[MadEgg]

Ik quote waar ik op reageer? Er wordt geen xz genoemd in het artikel, maar wel LZMA. Xz gebruikt lzma voor compressie. Zlib gebruikt deflate. Bzip2 gebruikt BWT.

Het gebruik van de implementaties en algoritmes door elkaar in het artikel maakt het er niet duidelijk op.

[moozzuzz]

Idd MadEgg, opnieuw een artikel waar de klok en klepel elkaar mislopen... Ik stem voor een (ver)taal-opleiding voor de Tnet-redactie .

[RoestVrijStaal]

Ik had eigenlijk wel een vergelijking met RAR, RARv5 en PAQ willen zien.

[CH4OS]

Dat zijn compressie methoden voor een ander doeleinde (opslag) en (daardoor) niet echt te vergelijken zijn met deze methoden (besparen bandbreedte).

[Reactie gewijzigd door CH4OS op 23 juli 2024 02:49]

[blorf]

Ik had die vergelijking zeker ook wel willen zien. Volgens mij is het grootste deel van dit verhaal slechts commercieel geleuter en gaat het voornamelijk om het hebben van eigen standaarden.

Het gaat over compressie van een bepaalde hoeveelheid data. Dat staat helemaal los van de opslag/transport daarvan. Wat je ermee doet is niet relevant. Of het om een bestand gaat of een blok RAM-geheugen met data, de compressie kan gewoon hetzelfde blijven. Binaire data is binaire data.

Ik ben er wel benieuwd naar hoeveel we sinds pkzip en arj nou echt vooruitgegaan zijn. Ik kan me om eerlijk te zijn geen latere namen herinneren die daar echt noemenswaardig superieur aan waren. Wel een boel die dat zo deden voorkomen wat in de realiteit altijd tegen bleek te vallen of soms zelfs slechter was.

[Reactie gewijzigd door blorf op 23 juli 2024 02:49]

[CH4OS]

De toepassing is totaal anders; waar je bij Brotli en Zopfli (en compression voor het web, want voor bzip2 en gzip geldt hetzelfde) ook wil dat het supersnel is, hoeft dat voor RAR en consorten totaal niet het geval te zijn (ook omdat het doeleinde totaal anders is). Wat RAM daarmee te maken heeft, geen idee. Het is en blijft appels met peren vergelijken en uiteindelijk zegt het dus helemaal niks.

Wat je in vergelijking vraagt, is een trein te vergelijken met een kleine auto.

[Reactie gewijzigd door CH4OS op 23 juli 2024 02:49]

[Gomez12]

RAM heeft er in zoverre iets mee te maken dat je bij storage opslag in principe niets geeft om RAM, terwijl je bij transport compressie te maken hebt met dat mensen 20 tabs open kunnen hebben staan waarin data loopt en dat je dan een redelijk voorspelbaar en redelijk laag RAM-gebruik wilt hebben.

[blorf]

Mijn punt was eigenlijk dat wat er met de in te pakken data gebeurt of gedaan wordt en wat daar allemaal nog omheen plaatsvindt niet van belang is. Je hebt 2 dingen: een stuk data en een compressie-algoritme. Die laatste is de enige factor die de kwaliteit van je compressie bepaalt, oftewel het ratio en de benodigde rekenkracht. Andere zaken die daar nog invloed op hebben zijn er niet behalve in reclame en P&R praatjes.

Daarnaast is het schuiven naar een lagere compressie-ratio in ruil voor minder tijdsduur ("slim" toepassen van compressie) gewoon een kwestie van je compressie niet volledig doen. Daar is geen speciale techniek voor nodig.
Stellen dat een dergelijke implementatie waarbij dat gedaan wordt beter zou zijn is slechts een totaal ongefundeerde slag in de lucht.

[Verwijderd]

Compressie en transport staan in praktische zin voor dit doeleinde absoluut niet los van elkaar. Op het web ondersteunen browsers gzip en deflate, waarbij gzip eigenlijk ook gewoon deflate is.

Je hebt op het web alleen iets aan een compressie algoritme als de browser het ook kan decompressen. Browsers kunnen geen rar, pkzip or arj decompressen, ze kunnen alleen deflate decompressen.

Dus, indien Google wil dat hun nieuwe compressie formaat daadwerkelijk te gebruiken is voor web pagina's, dient het zowel browser makers als web servers aan boord te krijgen van deze nieuwe standaard, en om die reden is het open source.

[Verwijderd]

Het gaat over compressie van een bepaalde hoeveelheid data. Dat staat helemaal los van de opslag/transport daarvan. Wat je ermee doet is niet relevant. Of het om een bestand gaat of een blok RAM-geheugen met data, de compressie kan gewoon hetzelfde blijven. Binaire data is binaire data.

Case 1, je bent een complexe webpagina aan het downloaden, je wilt die graag zo klein mogelijk hebben maar niet 30 seconden wachten op het uitpakken.
Case 2, je bent een groot Max file aan het downloaden, Je wilt dat graag goed gecompressed hebben en het maakt niet veel uit of je 3 min moet wachten tot het uitgepakt is.
Case 3, je hebt een complex file van 500Gb dat je wilt archieveren. Je wilt dan een optimale compressie. In het gevla van sommige van mijn files kan ik die tot 35 Gb verkleinen als ik een dik uur wil wachten op het uitpakken (met 7z).
Een vergelijking tussen die drie case om te zien wat de kleinste files oplevert was gewoon van geen enkel belang.

Je uitspraak over 'commercieel geleuter' moet je ven uitleggen want die kan ik niet plaatsen

[Verwijderd]

Kijk, dat doet Google toch weer mooi met een opensource donatie

[FreezeXJ]

Ze moeten wel, als ze dit in web-browsers ondersteund willen hebben zal het compleet vrij moeten zijn, of moeten ze wel heel veel voordeel aantonen, en dan nog. Het is niet alsof Mozilla of andere freeware-browsers erg happig zijn op closed source implementaties... Bzip2 en aanverwanten zijn ook gewoon open source, dus die concurrentie hebben ze al.

[DDuce]

Google speelt eerder een lange termijn spel. Hoe beter de compressie, des te sneller de laad tijden. Hoe sneller de laad tijden, des te meer pageloads en gebruiksgemak. Hoe meer gebruiksgemak, des te meer gebruikers, en dus meer advertentie inkomsten.

Ze sturen aan op innovatie binnen de markt. Niet op winst op product niveau.

[CH4OS]

Grappig, volgens Google images is de afbeelding zowel een Brotli als een Zopfli.

Ben benieuwd wat de adoptie gaat worden van dit algoritme op bijvoorbeeld webservers, want volgens mij is Zopfli ook niet echt gigantisch veel gebruikt in/met Deflate als compressie algoritme.

[Reactie gewijzigd door CH4OS op 23 juli 2024 02:49]

[Simyager]

Als je goed kijkt zie je dan ook dat dat komt door dit Tweakers.net nieuws . Maar het plaatje in dit nieuws is die van Brotli en de Zopfli is de vlechtbrood

[letatcest]

Hebben we het internet stukgemaakt?

[Youtoofan]

Nee, dat was Jenny

https://www.google.be/url...g2=ofqmMUFia63wRitBoiroEg

[tszcheetah]

Ziet er veelbelovend uit. Brötli lijkt vooral snelheidswinst te halen bij het decomprimeren: daar liggen de snelheden consequent fors hoger dan lzma/bzip en inderdaad vergelijkbaar met deflate.

Als je kijkt naar de getallen mbt compressie (ratio + snelheid), dan scheelt het op het sterkste niveau niet veel met bijv. lzma. De snelheid zakt bij Brotli:11 echter wel fors in t.o.v. level 9; die zit qua compressieratio weer in de buurt van lzma:9, maar dan wel met een stuk hogere snelheid.

Enigszins jammer dat de focus van de studie wel grotendeels op decompressie ligt, en een stuk minder op compressie (snelheid en ratio). Ook daar lijkt het goed te presteren, maar dat wordt minder duidelijk gemaakt.

[Henk Poley]

Richten ze zich soms op mobiele en 'internet of things' (M2M) toepassingen? Waar de server ergens in een data centrum of thuis staat, maar de doel processor maar een klein batterijtje heeft. Dan wil je dus het liefst zo gemakkelijk mogelijk decomprimeren.

[momania]

Brötli betekend trouwens gewoon broodje, niet klein brood.
-li is de Zwitserse variant van het Hollandse -(t)je

[roy-t]

Is broodje niet synoniem voor klein brood?

[momania]

Kleine betweter

[B00m3rang]

of betwetertje?

[roy-t]

[trogdor]

Voor grote bestanden (ik verwerk vele gigabytes aan data) maak ik de laatste tijd veel gebruik van pbzip2, een parallele implementatie van het bzip2 algorithme. Met een 12 core machine scheelt dat gigantisch.
Er bestaat ook nog lbzip2 wat vaak sneller is, maar die heeft bij grote bestanden wat problemen met geheugengebruik.

Een nieuw algorithme is natuurlijk altijd welkom, maar in dit geval wel onder de voorwaarde dat het geparalleliseerd kan worden.
Voor in een browser is dat natuurlijk minder van belang...

[Henk Poley]

pbzip2 homepage: http://compression.ca/pbzip2/

Is beschikbaar in `brew` op OS X en `apt-get` op Ubuntu.

[Reactie gewijzigd door Henk Poley op 23 juli 2024 02:49]

[trogdor]

vanuit epel op centos6: http://pkgs.org/centos-6/...1.6-1.el6.x86_64.rpm.html
en begint nu eindelijk door te sijpelen voor centos 7 : https://bugzilla.redhat.com/show_bug.cgi?id=1144161
tot dat dat zover is gewoon vanaf pkgs: http://pkgs.org/centos-7/...-1.el7.rf.x86_64.rpm.html

[freaky]

Waarom geen threaded xz? Heb er nog niet mee gespeeld, maar xz zou beter dan bz2 moeten zijn.

[trogdor]

xz comprimeert beter maar het heeft flink meer cpu tijd nodig en daardoor duurt het een stuk langer. Met een paar files is dat niet zo belangrijk, maar met honderden gigabytes wel.
Ook dit nieuwe algorithme van google wordt vergeleken met xz qua compressie en bzip qua performance.
Ik ben benieuwd of het inderdaad echt een nieuw algorithme is, of alleen een nieuwe manier van opslaan waardoor er wat minder van de leggacy overhead in zit.

[Reactie gewijzigd door trogdor op 23 juli 2024 02:49]

[Mitsuko]

Het lijkt erop dat naast Chromium ook Firefox het nieuwe formaat zal ondersteunen, althans voor https: bug 366559 (oude bug, weer uit de kast gehaald voor Brotli).

[Henk Poley]

Vraag me af waar het in de pareto productiemogelijkhedengrens valt: http://compressionratings.com/rating_sum.html

Relevantere weergave is misschien, het beste compressie-algoritme (instelling) voor een bepaalde bandbreedte (gegeven een C2D Q6600): http://fastcompression.bl...ompression-benchmark.html