Witam,

>- niesamowity "general purpose" ZSTD który będzie wypierał gzipa, autor pracuje w Facebook:
>github.com/Cyan4973/zstd

1. Na jakim etapie rozwoju to jest Twoim zdaniem?
Stabilne, testy, użytkowy?

2. To jest na pewno Open Source, patentów bral /etc?

3. Jak widzisz przyszłość tego programu?

Witam,
Format ZSTD został zamrożony ok. 2 miesiące temu: fastcompression.blogspot.fr/
W tym momencie zbliża się do release version 1.0, kwestia może miesiąca, wtedy Facebook pewnie będzie reklamował (szczególnie że konkuruje z Brotli Google od którego jest znacznie szybszy en.wikipedia.org/wiki/Brotli )
Autor ZSTD to Yann Collet, znany m.in. z używanego wszędzie kompresora LZ4:
en.wikipedia.org/wiki/LZ4_(compression_algorithm)
Nie ma żadnych patentów, "open-source BSD-licensed".

Tutaj jest porównanie szybkości i stopnia kompresji - jest rzędu 3x szybszy niż gzip/zlib i pozwala na znacznie lepszy stopień kompresji.


Inne benchmarki, np.
mattmahoney.net/dc/text.html
github.com/inikep/lzbench

Przyszłość? Znacznie lepszy i szybszy, znany autor, marketing z Facebooka, open source - w końcu coś co wyprze archaicznego gzipa.

ps. Duży wkład w jego najwyższe stopnie kompresji miał Przemysław Skibiński (inikep)

Witam,

>Format ZSTD został zamrożony ok. 2 miesiące temu: fastcompression.blogspot.fr/
>W tym momencie zbliża się do release version 1.0, kwestia może miesiąca, wtedy Facebook pewnie będzie reklamował (szczególnie że konkuruje z Brotli Google od którego jest znacznie szybszy en.wikipedia.org/wiki/Brotli )

Przepraszam bardzo za zwłokę w odpowiedzi - moja suczka lekko choruje, wet, badania, posiew, antybiotyki i smarowania nosa ... Dziękuje za informacje.
Chodziło mi głównie o Twoje zdanie.
Testowałem trochę, spodobało mi się, sprawdzę na służbowych archiwach (ok 60 Gb największy plik z tar+gzip).
Zwarty kod, gcc 5.3 64 bit na slackware 14.1 bez problemów.
Trzeba będzie porównac z xz (też mocno reklamowany na unixach) i 7zip.
Ten ostatni jakiś przyciężki.

Pozdrawiam,
JS.

Witam,
Zarówno xz jak i 7zip (głównie lzma) to są kompresory innej klasy - pozwalają na ciut lepszy stopień kompresji, ale są o rząd wielkości wolniejsze/bardziej kosztowne.

Przykładowe benchmarki z github.com/inikep/lzbench:

kompresor, szybkość kodowania, dekodowania, finalna wielkość, stopień kompresji:

xz 5.2.2 -0 16 MB/s 44 MB/s 62579435 29.53
xz 5.2.2 -3 4.56 MB/s 55 MB/s 55745125 26.30
xz 5.2.2 -6 1.98 MB/s 58 MB/s 49195929 23.21
xz 5.2.2 -9 1.80 MB/s 59 MB/s 48745306 23.00

lzma 9.38 -0 18 MB/s 47 MB/s 64013917 30.20
lzma 9.38 -2 15 MB/s 56 MB/s 58867911 27.77
lzma 9.38 -4 9.06 MB/s 59 MB/s 57201645 26.99
lzma 9.38 -5 2.12 MB/s 65 MB/s 49720569 23.46

zstd 0.8.0 -1 238 MB/s 629 MB/s 73659471 34.75
zstd 0.8.0 -2 183 MB/s 560 MB/s 70168958 33.11
zstd 0.8.0 -5 88 MB/s 511 MB/s 65002227 30.67
zstd 0.8.0 -8 32 MB/s 554 MB/s 61026456 28.79
zstd 0.8.0 -11 16 MB/s 547 MB/s 59523199 28.08
zstd 0.8.0 -15 5.22 MB/s 572 MB/s 58007769 27.37
zstd 0.8.0 -18 3.10 MB/s 492 MB/s 55540622 26.20
zstd 0.8.0 -22 1.54 MB/s 464 MB/s 52787120 24.91

zlib 1.2.8 -1 65 MB/s 248 MB/s 77259029 36.45
zlib 1.2.8 -6 20 MB/s 266 MB/s 68228431 32.19
zlib 1.2.8 -9 8.36 MB/s 268 MB/s 67644548 31.92

ZSTD to jest zamiennik dla zlib/gzip - ciut gorszy maksymalny stopień kompresji niż xz, lzma ... ale 10x szybsze/tańsze dekodowanie, co jest kluczowe w wieeeeelu zastosowaniach.

W razie czego jest wersja 7zip z ZSTD: tutaj.

Te szybkie kompresory ZSTD, Apple LZFSE używają wariantu tANS kodowania z automatem jak powyżej.

Kompresor DNA CRAM 3.0 oraz pod kompresję wideo, obrazu używają wariantu rANS kodowania - potrzebuje mnożenia, ale jest bardzo wygodny do modyfikacji prawdopodobieństw w locie.

W grach są bardzo dobre kompresory na rANS: BitKnit i LZNA (jak LZMA tylko 3x szybszy) z RAD Game Tools ... niestety płatne, ale ktoś ostatnio "zdekompilował" dekodery z dll:
encode.ru/(*)kie-LZNA-BitKnit-decompression

Pozdrawiam,
JD

ps. marketing z Facebooka zaczyna się jutro - drugie wystąpienie (Yann Collet autor ZSTD): engine.red(*)29/scale-2016-lineup-announced

>Witam,
>Zarówno xz jak i 7zip (głównie lzma) to są kompresory innej klasy - pozwalają na ciut lepszy stopień kompresji, ale są o rząd wielkości wolniejsze/bardziej kosztowne.

Moj praktyczny rezultat (serwerek domowy,stary grat, oczywiście wielozadaniowo i wieloużytkowo - test praktyczny, mniej więcej stałe obciązenie, system ma 4 wątki).

Dane kompresowane realne, starsze programy exe, kilkadziesiąt sztuk, małe, po pare Mb max, reszta to realne dane z programów finansowo - księgowych i podobnych w DBF i indeksach do tego (Clipper for DOS).

test1.sh:
==============================================
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Testy kompresji bezstratnej
Sat Sep 24 09:13:49 CEST 2016
----------------------------------------------
system
Linux junak2_main 4.4.14 #2 SMP Fri Jun 24 13:38:27 CDT 2016 x86_64 Intel(R) Xeo
n(R) CPU 5140 @ 2.33GHz GenuineIntel GNU/Linux
kompilator

bash-4.3$ gcc -v
Reading specs from /usr/lib64/gcc/x86_64-slackware-linux/5.3.0/specs
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-slackware-linux/5.3.0/lto-wrapper
Target: x86_64-slackware-linux
Configured with: ../gcc-5.3.0/configure --prefix=/usr --libdir=/usr/lib64 --mandir=/usr/man --infodir=/usr/info --enable-shared --enable-bootstrap --enable-languages=ada,c,c++,fortran,go,java,lto,objc --enable-threads=posix --enable-checking=release --enable-objc-gc --with-system-zlib --with-python-dir=/lib64/python2.7/site-packages --enable-libstdcxx-dual-abi --with-default-libstdcxx-abi=gcc4-compatible --disable-libunwind-exceptions --enable-__cxa_atexit --enable-libssp --enable-lto --disable-install-libiberty --with-gnu-ld --verbose --enable-java-home --with-java-home=/usr/lib64/jvm/jre --with-jvm-root-dir=/usr/lib64/jvm --with-jvm-jar-dir=/usr/lib64/jvm/jvm-exports --with-arch-directory=amd64 --with-antlr-jar=/root/slackware64-current/source/d/gcc/antlr-runtime-3.4.jar --enable-java-awt=gtk --disable-gtktest --disable-multilib --target=x86_64-slackware-linux --build=x86_64-slackware-linux --host=x86_64-slackware-linux
Thread model: posix
gcc version 5.3.0 (GCC)

================================================
wersja zstd
*** zstd command line interface 64-bits v1.0.0, by Yann Collet ***
-----------------------------------------------------
wesja xz
xz (XZ Utils) 5.2.2
liblzma 5.2.2
-----------------------------------------------------
dane testowe
-rw-r--r-- 1 jareks jareks 5175275520 Sep 15 14:04 test1.tar
-rw-r--r-- 1 jareks jareks 5175275520 Sep 15 14:13 test2.tar
-rw-r--r-- 1 jareks jareks 1743024816 Sep 24 09:15 test1.tar.zst
-rw-r--r-- 1 jareks jareks 1525085432 Sep 15 14:13 test2.tar.xz

kompresja i czasy

zstd
real 1m32.651s
user 0m33.743s
sys 0m7.105s

xz
real 44m16.615s
user 43m58.176s
sys 0m14.861s

Jak widać różnica w kompresji xz (faworyt) do zstd mała, kilkanaście procent na niekorzyść zstd w standardowych ustawieniach, czas kompresji dla xz jest
druzgocący (ponad 28 razy gorzej). W zasadzie to jest kompromitacja xz i tylko dla specjalnych przypadków (ekstremalnie wolna transmisja na kf typu thor 22 czy dystrybucja oprogramowania źródłowego po kilkaset MB żródlo max przykładowo) xz ma jakikolwiek sens. Chyba że czegoś o licencjonowaniu zstd nie wiem.

Wyniki bardzo zależą od rodzaju danych i widzę że nie zmieniałeś stopnia kompresji: zstd używa od "-1" (najszybszy) do "-22" (najlepsza kompresja).
Czas dekompresji jest dla nich w miarę stały - jak na wykresie powyżej.

Zstd i xz to są kompresory innej klasy: zstd ma być znacznie szybszy szczególnie w dekompresji - ma być tym domyślnym podstawowym kompresorem - zamiast gzip/zlib.
Klas kompresorów jest znacznie więcej (kompromis między szybkością i stopniem kompresji).
- najszybsze to czysty Lempel-Ziv, prawie wszędzie jest używany LZ4 Yanna Colleta (tego samego autora co ZSTD),
- potem LZ+statyczny koder entropii: Huffman (jak gzip), obecnie zastępowany tANS/FSE (jak ZSTD),
- potem klasa LZMA/xz: LZ + adaptacyjny koder entropii: kodowanie arytmetyczne, teraz np. znacznie szybszy ale niestety zamknięty LZNA na rANS,
- przewijają się kompresory na Burrowsie-Wheelerze, jak bzip,
- kompresory na PPM - używające kontekstów różnej długości,
- kompresory na context mixing - używają sieci neuronowych żeby mieszać między różnymi kontekstami ... aż do cmix potrzebującego 32GB RAM i tygodnia do kompresji ...

zobacz sobie duży przegląd: mattmahoney.net/dc/text.html

W każdym razie, jeśli ktoś dzisiaj używa Facebook lub Apple, jego dane są zapisane kodowaniem z Krakowa ...

>Wyniki bardzo zależą od rodzaju danych i widzę że nie zmieniałeś stopnia kompresji: zstd używa od "-1" (najszybszy) do "-22" (najlepsza kompresja).

-rw-r--r-- 1 jareks jareks 5175275520 Sep 15 14:04 test1.tar

bash-4.3$ time ~/bin/zstd -v -22 test1.tar -o test1a.tar.zstd
*** zstd command line interface 64-bits v1.0.0, by Yann Collet ***
Warning : compression level higher than max, reduced to 19
test1.tar : 30.49% (5175275520 => 1577802570 bytes, test1a.tar.zstd)

real 29m45.928s
user 29m10.368s
^^^^^^^^^^^^^^^^^^^^^
I tak o wiele lepej
sys 0m13.228s

-rw-r--r-- 1 jareks jareks 1577802570 Sep 25 08:14 test1a.tar.zstd
^^^^^^^^^^^^^
-rw-r--r-- 1 jareks jareks 1743024816 Sep 25 07:53 test1b.tar.zst
-rw-r--r-- 1 jareks jareks 1525085432 Sep 15 14:13 test2.tar.xz
^^^^^^^^^^^^^^^^^^^^^^

Dla kilkudziesięciu Mb to już na prawde nie warto.
Dla kilkuset przy 5 Gb czy nieco więcej też nie.
Zaznaczam że to test praktyczny, pisze teksty, jakis film puściłem z youtube dla realniości itp.

>Czas dekompresji jest dla nich w miarę stały - jak na wykresie powyżej.
>Zstd i xz to są kompresory innej klasy: zstd ma być znacznie szybszy szczególnie w dekompresji - ma być tym domyślnym podstawowym kompresorem - zamiast gzip/zlib.

Zgadzam się ale wyniki zachwycające.
na bzip2 w danych realnych pracowników (około 100 Gb) to nie starczało za bardzo nocy (tar + gzip albo tar +bzip2) - stary serwer 32 bit. Jako alternatywa dla gzip jest zstd idealny.

>zobacz sobie duży przegląd: mattmahoney.net/dc/text.html

Dzieki, ciekawe.
Chociaż mnie interesują wyłącznie dojrzałe OS, z szansą na wiele lat do przodu.

>W każdym razie, jeśli ktoś dzisiaj używa Facebook lub Apple, jego dane są zapisane

A to nie do mnie

Żródło zstd mogło by być gdzieś na gnu też. A FAceboka nie mam i miał nie będę (Aple tez nie, jak juz to jakąs samoróbke na arm).

Większość z kompresorów z tego przeglądu to raczej ciekawostka, np. próba odpowiedzi na pytanie o teoretyczny maksymalny stopień kompresji, czyli zawartości informacyjnej np. języka mówionego.

Zstd jest używany m.in. wewnętrznie w Facebooku, ale ma duże szanse rzeczywiście powszechnie wyprzeć gzipa jako ten podstawowy kompresor.
Google rok temu też wypuścił kompresor o takich aspiracjach : Brotli, ale ma ze 2x wolniejszą kompresję i dekompresję niż ZSTD przy podobnym stopniu kompresji.
z github.com/inikep/lzbench :

brotli 0.5.2 -0 216 MB/s 256 MB/s 78226979 36.91
brotli 0.5.2 -2 97 MB/s 296 MB/s 68066621 32.11
brotli 0.5.2 -5 24 MB/s 328 MB/s 60801716 28.69
brotli 0.5.2 -8 5.70 MB/s 341 MB/s 57382470 27.07
brotli 0.5.2 -11 0.38 MB/s 277 MB/s 51136345 24.13

zstd 1.0.0 -1 244 MB/s 648 MB/s 73659471 34.75
zstd 1.0.0 -2 186 MB/s 604 MB/s 70168958 33.11
zstd 1.0.0 -5 90 MB/s 571 MB/s 65002211 30.67
zstd 1.0.0 -8 31 MB/s 623 MB/s 61026500 28.79
zstd 1.0.0 -11 16 MB/s 613 MB/s 59523170 28.08
zstd 1.0.0 -15 5.03 MB/s 638 MB/s 58007776 27.37
zstd 1.0.0 -18 2.92 MB/s 538 MB/s 55163525 26.03
zstd 1.0.0 -22 1.55 MB/s 499 MB/s 52772135 24.90

Kodowanie ANS (z Krakowa) jeszcze jest używany w wielu miejscach, np. w rozwijanym kompresorze wideo Alliance for Open Media (Google, Intel, Microsoft, Amazon, Netflix, Nvidia, AMD, ARM,...) - m.in. do YouTube:
en.wikipedia.org/wiki/Alliance_for_Open_Media
aomedia.go(*)com/aom/+/master/aom_dsp/ans.h

O trafiłem, właśnie Facebook ogłosił release ZSTD (Zstandard) 1.0 i posypały się niusy:
code.faceb(*)ta-compression-with-zstandard/
www.wired.(*)ved-isnt-hooli-silicon-valley/
techcrunch(*)hm-and-myrocks-storage-engine/
www.zdnet.(*)replace-technology-behind-zip/
siliconang(*)game-changer-for-data-storage/
www.forbes(*)ebuts-360-video-stabilization/

Jego kodowanie entropii: Finite State Entropy, to jest właśnie tANS: automat jak w pierwszym poście.

>dłuższa lista i różne implementacje, materiały:
>encode.ru/(*)umeral-Systems-implementations
>Pozostało jeszcze dużo ciekawych otwartych pytań, szukam osób chętnych współpracy w tym temacie.

A niby jak i kiedy miałby to obsługiwać np. przeglądarki internetowe...

na stronach jest pełno obrazków jpg, a tam co masz?

W obrazach jpg jest zwykle takie coś:
case M_SOF1: ret = get_sof(FALSE, FALSE); break; // Extended sequential, Huffman
case M_SOF2: ret = get_sof(TRUE, FALSE); break; // Progressive, Huffman
case M_SOF9: ret = get_sof(FALSE, TRUE); break; // Extended sequential, arithmetic
case M_SOF10:ret = get_sof(TRUE, TRUE); break; // Progressive, arithmetic

case M_SOF3: // Lossless, Huffman
case M_SOF5: // Differential sequential, Huffman
case M_SOF6: // Differential progressive, Huffman
case M_SOF7: // Differential lossless, Huffman
case M_JPG: // Reserved for JPEG extensions
case M_SOF11: // Lossless, arithmetic
case M_SOF13: // Differential sequential, arithmetic
case M_SOF14: // Differential progressive, arithmetic
case M_SOF15: // Differential lossless, arithmetic

Huffman lub arithmetic.

No, zatem musiałbyś chyba startować z tym pomysłem do autorów standardu jpg, zip, itp.

W prywatnych programach można sobie to używać,
ale to raczej żaden biznes - zwłaszcza dla ciebie.

Masz chociaż kod tego.. np. w C, lub chociaż jakiś ogólny schemat algorytmu, taki sensowny dla programisty, nie jakieś tam teoretyczne sre-ble w czarnej skrzynce?

---

Lepiej spłonąć niż się tlić.

Oj archaiczny JPEG wielu próbowało wypierać, np. JPEG2000, ale inercja jest gigantyczna - masz sprzętowy koder/dekoder w każdym aparacie, telefonie etc. ...
Najbliżej chyba jest Google WebP ( en.wikipedia.org/wiki/WebP ), obsługiwany przez kilka przeglądarek - to jest właściwie jedna klatka ich kodeka wideo VP8 (intrapredykcja).
Aktualnie jest na kodowaniu arytmetycznym, ale jest w planie upgrade do rANS: chromium-review.googlesource.com/#/c/338781/

Inne podejście to repakowanie JPEG - z jpg wyciągasz współczynniki Fouriera (nie wykonujesz transformaty) i zapisuje w bardziej optymalny sposób: wykorzystując korelacje i używając lepszego kodera entropijnego (niż oryginalny Huffman) - zyski są rzędu 22%, ostatnio było głośno o leptonie z droboxa tego (używają wewnętrznie i jest open source): www.google.pl/search?q=lepton+dropbox
Na razie na kodowaniu arytmetycznym, ale autor rozważa upgrade do ANS: github.com/dropbox/lepton/issues/24

Blisko jest kompresja wideo - dużą szansę na coś powszechnego ma Alliance for Open Media ( en.wikipedia.org/wiki/Alliance_for_Open_Media ): Amazon, Cisco, Google, Intel, Microsoft, Mozilla, Netflix, AMD, ARM, NVIDIA, Adobe, Ateme, Ittiam, Vidyo.
Wspólnie robią darmowy super kodek żeby wyprzeć płatnego h.265 - łącznie ze sprzętową dekompresją do końca 2017 ... i aktualnie jest na rANS: aomedia.go(*)com/aom/+/master/aom_dsp/ans.h

Co do wypierania gzipa, zobacz sobie wspominanego ZSTD (na tANS): www.google.pl/search?q=zstandard&tbm=nws
- wiele razy szybszy od gzipa, zarówno w kompresji jak i dekompresji,
- znacznie lepszy maksymalny stopień kompresji,
- promowany i używany wewnętrznie przez Facebook,
- autor (Yann Collet) napisał wcześniej szybki kompresor LZ4, który jest używany dosłownie wszędzie: en.wikipedia.org/wiki/LZ4_(compression_algorithm)