Jarek Duda

Z jednej strony dawno już minęły czasy szachów w 2kB RAM ZX81, czy pisania jądra systemu przez jedną osobę ... Teraz wszystko powinno być super zoptymalizowane, szczególnie kluczowe algorytmy/implementacje u podstaw wszystkiego, jak sortowanie, biblioteki do numeryki ... kompresory (dodatkowo dochodzi problem kompatybilności) ... Pisze je wąska grupa specjalistów, zwykłemu programiście (99%) wystarczy użycie tych gotowych narzędzi ... Z drugiej strony powinien jednak mieć świadomość co jest w środku używanych narzędzi, mieć na uwadze ich słabości, użycie zasobów ... zastanawiać się jak efektywnie rozwiązać problem, a nie tylko żeby działało ... A szczególnie przy tworzeniu nowych narzędzi - wierzę że powinien być przynajmniej jeden teoretyk w drużynie, szczególnie że inżynierowie często nie mają nawet podstaw algorytmiki - tylko bezmyślne użycie gotowych narzędzi.

Optymalizacja niskopoziomowa jest prawdziwą sztuką, np. coś co się wydaje trywialne: dekoder Huffmana - napisane naiwnie kilka linijek daje np. 50 MB/s/rdzeń ... podczas gdy super-implementacje robią to samo powyżej 1000MB/s/rdzeń: https://sites.google.com/site/powturbo/entropy-coder Przykładowym trikiem tutaj jest interleaving: instrukcja musi przejść przez cały pipeline procesora (ok. 8 taktów), więc jest sporo czekania jeśli kolejna porcja bitów zależy od poprzedniej. Naprawia to właśnie interleaving: kodujemy na raz w cyklu np. 4 osobne bufory, dzięki czemu pipeline nie musi czekać. Dalej jest olbrzymia potęga SIMD: współczesny procesor operuje na 128 bitowych wektorach, np. 4 x 32 bity, co można wykorzystać do kodowania: http://arxiv.org/abs/1402.3392 Od pół godziny jest już oficjalnie ZSTD_HC: https://github.com/Cyan4973/zstd Close source lzturbo ma dalej ok. 1.5 razy szybsze dekodowanie czyli są możliwości poprawy - jak ktoś chce stać się częścią historii to dobry moment spróbować coś doszlifować - gzip był napisany żeby dział - dzisiejsze kompresory już ciężko będzie istotnie poprawić, może się okazać że już nigdy nie będzie warto wymieniać ...

Myślę że bardziej byłoby interesujące gdybyś napisał dwa razy szybszy W dzisiejszych czasach zdecydowana większość danych jest poddawanych kompresji - dla zmniejszenia kosztów transmisji i przechowywania, przyśpieszania odczytu i transmisji, coraz częściej nawet pliki systemowe są domyślnie skompresowane ... poprawianie algorytmów kompresji oznacza w skali świata niewyobrażalną oszczędności energii i innych zasobów.

Oczywiście, gadamy głównie o dobrze widocznych korporacjach jak Apple, choć pewnie to są grzeczne baranki w porównaniu z tymi których bezpośrednio nie widzimy, jak Monsanto, cały przemysł zbrojeniowy ... albo bardzo polecam na przykład "Dubai: A city of dreams" - miasto marzeń ... budowane dosłownie przez niewolników ... "teoria skapywania" nie działa ponieważ bogaci często widzą zwykłych ludzi jako jakąś podrasę ... trailer: https://www.youtube.com/watch?v=jERvxazU6qQ Niestety obecny model państwa tonie w długach i korupcji ... ale chyba tylko one mogą nas obronić - o ile będziemy o to walczyć. Coś takiego udało się w Argentynie - podczas gdy politycy nie lubią żeby zwykli ludzie mieszali się w politykę, tam zrobiono to w ramach systemu: utworzyli partię której reprezentanci głosują zgodnie z dyskusją obywateli, oraz zdają sprawozdania z tego co się dzieje (transparency): https://www.ted.com/talks/pia_mancini_how_to_upgrade_democracy_for_the_internet_era?language=en ps. Wracając do wspomnianego ANS, jest obecnie bardzo ciekawa sytuacja odnośnie zastąpienia gzip, który jest mocno przestarzały ale dosłownie wszędzie. No więc Google kilka lat temu wprowadziło Zopfli który jest kompatybilny z gzip. A z miesiąc temu w wielu mediach było głośno o ich fenomenalnym Brotli (na Huffmanie) który będzie wszystko zastępował, wsparcie od Firefox 44 etc ... http://thenextweb.com/insider/2015/09/22/googles-new-brotli-compression-algorithm-is-26-percent-better-than-existing-solutions/ http://www.theregister.co.uk/2015/09/23/googles_brotli_compression_opensourced/ ... chwilę później okazało się że znacznie szybszy jest lzturbo (na ANS), tyle że close source: http://encode.ru/threads/2313-Brotli?p=44970&viewfull=1#post44970 Ale dwa dni temu pojawiły się pierwsze testy świeżego ZSTD_HC (też ANS, Apple LZFSE prawdopodobnie jest kopią ZSTD) - okazuje się że jest rzędu 2 razy szybszy w dekodowaniu niż Brotli, a co najważniejsze jest open source. http://encode.ru/threads/2345-zstd-HC Czyli zapowiada się ciekawa walka jak w przyszłości będzie zapisywana cała nasza informacja ...

Taki mamy świat - korporacje rosną w siłę, państwa słabną dodatkowo tonąc w w długach ... ciekawe (albo i nie) do czego to zmierza ... http://di.com.pl/cyberewolucja-news-deal-news-age-rozwazania-nad-losem-cywilizacji-europejskiej-czesc-3-53516

Z takich ciekawszych historii, warto wspomnieć o głównym wojowniku o poszanowanie własności intelektualnej: Hollywood - mianowicie nasuwa się pytanie dlaczego powstało na zachodnim wybrzeżu, podczas gdy większość technologii na wschodnim (Edison) ... http://www.racjonalista.pl/forum.php/s,478372 Niestety koncept ochrony intelektualnej został współcześnie zupełnie wypaczony - np. Apple patent na prostokąt z zaokrąglonymi rogami czy slide to unlock - nie chodzi o innowacyjność tylko głównie zablokowanie konkurencji (szczególnie patentowanie sekwencjonowanego materiału genetycznego), samodzielny wynalazca nie ma praktycznie żadnych szans ... Jak wszędzie liczy się tylko pazerność, idealiści to frajerzy, zawsze znajdą się tacy którzy będą oddawać za darmo swoje pomysły czy pracę ... ale fajnie żebym np. mógł napisać w publikacji coś więcej niż tylko spekulacje że setki milionów użytkowników Apple ma większość danych zakodowane w dyskutowany sposób ...

Czyli jeśli oprócz copy&paste dokonasz jakichś modyfikacji, albo np. przepiszesz na inny język oprogramowania, licencja open-source już nie obowiązuje? Miło że uszanowali nazwę, dając wyraźne poszlaki, pewnie w wielu przypadkach nawet tego nie było - mimo że zwykle jedyne czego oczekuje twórca open-source za swoją pracę to uszanowanie autorstwa. Gdybym opatentował ANS ( inni obecnie próbują ... http://cbloomrants.blogspot.com/2015/05/05-21-15-software-patents-are-fucking.html ), to z czasem może mógłbym się domagać nawet wyższych kwot niż we wspomnianym artykule (dotyczy też wszelkich przyszłych modeli) ... natomiast gdy ktoś oddaje swoje pomysły za darmo, nie warto go nawet wspomnieć? Śmierć frajerom ...

Apple jest jedną z głośniej krzyczących korporacji odnośnie przestrzegania własności intelektualnych ... oczywiście tylko swoich. Na przykład od kilku tygodni (iOS9 i OS X 10.11) ich domyślnym kompresorem (iOS9 zmniejszył się z 4.6GB do 1.3GB) jest LZFSE, czyli Lempel-Ziv + Finite State Entropy, jak wyraźnie pokazywali na swojej prezentacji ( http://encode.ru/attachment.php?attachmentid=3708&d=1433933124 ) czy slajdach ( http://devstreaming.apple.com/videos/wwdc/2015/7125ovmdf36/712/712_low_energy_high_performance_compression_and_accelerate.pdf ). Finite State Entropy jest znaną w środowisku implementacją kodowania ANS (które kiedyś wymyśliłem i obecnie zastępuje kodowanie Huffmana), wystarczy zapytać googla chociażby o "finite entropy" i wyraźnie kieruje do: https://github.com/Cyan4973/FiniteStateEntropy Tego samego autora (Yann Collet, znany też z https://en.wikipedia.org/wiki/LZ4_%28compression_algorithm%29 ) jest też ZSTD ( https://github.com/Cyan4973/zstd ), który też jest LZ+FSE i pojawił się (open-source) kilka miesięcy przed LZFSE Apple. Czyli wszystko wskazuje na to że ot tak skopiowali (przepisali?) oprogramowanie open source, robiąc je domyślnym w swoim systemach operacyjnych, zostawiając tylko wyraźne poszlaki - mimo że licencja tego oprogramowania nakazuje powiedzieć to wprost, np. " Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer." z licencji FSE. Bardzo to smutne dla ludzi tworzących open-source ... korporacja może ot tak użyć wszystkiego nazywając swoim dziełem, nawet nie wspominając o autorze ...

Jasne, w kryteriach efektywnego użycia odległości, bardzo dobrze wypada np. wspomniana drzemka Aczkolwiek myślę że jednak istotniejsza jest efektywność użycia czasu, szczególnie że dystans można łatwo sztucznie wydłużyć ... a z czasem już niestety tak łatwo nie jest ...

Badanie godne Amerykanów którzy męczą się w korkach żeby móc pochodzić na bieżni w gym, ale chyba nie uwierzę że mogę więcej spalić w danym czasie jeśli zamiast szybkiego marszu będę zwalniał i się zatrzymywał ... to pewnie najwięcej przy uwzględnieniu przerwy na drzemkę

Możliwość "szybko znowu utworzyć superpozycję" nie wystarcza - konieczne jest utrzymanie jednej przez cały proces. Ogólnie polecam zainteresować się kwantową korekcją błędów, czyli właśnie walką z tą dekoherencją - ochrona przed prostym błędem wymaga np. zdziesięciokrotnienia ilości bramek ... co prowadzi do możliwych kolejnych błędów przed którymi należy zabezpieczyć ... i tak dalej ...

Teoria teorią ... dobry wykład fizyka: https://www.ted.com/talks/david_mackay_a_reality_check_on_renewables?language=en

To nie jest tak że wystarczy połączyć bramki kwantowe i dostaniemy komputer kwantowy - kluczowe jest utrzymanie superpozycji, którą błyskawicznie niszczy termodynamika, jak np. "puszczenie kubita kablem".

Energia słoneczna może być pewnym uzupełnieniem - dla pokrycia dachów, pustyni, wewnątrz szyb ( http://www.extremetech.com/extreme/188667-a-fully-transparent-solar-cell-that-could-make-every-window-and-screen-a-power-source ) ... ale ogólnie może lepiej żeby dana powierzchnia była wykorzystywana przez naturę dla fotosyntezy, naturalnego życia ... Żeby stała się podstawowym źródłem energii musielibyśmy zastąpić olbrzymie tereny zielone krzemową pustynią ... i finansowo jeszcze długo to nie będzie realne ... Kluczowe są te podstawowe źródła energii - wszystko czego nie zastąpimy będzie pozyskiwane z najgorszego źródła: węgla - samych ofiar śmiertelnych jest rzędu miliona rocznie, a do tego olbrzymie zniszczenie środowiska https://en.wikipedia.org/wiki/Environmental_impact_of_the_coal_industry Jedynym źródłem które realnie mogłoby przejąć dominację spalania jest energia jądrowa (w jakiejś postaci) - tutaj łączna ilość ofiar przez burzliwy okres rozwoju jest pewnie porównywalny z jednodniowym z węgla: https://en.wikipedia.org/wiki/List_of_nuclear_and_radiation_accidents_by_death_toll

Co do "reaktorów atomowych" ... specjalnie napisałem o spalaniu węgla ... taki ogólny piec niektórzy dziennikarze pewnie nazwaliby "reaktorem molekularnym" No właśnie zachodzą reakcje jądrowe - o energii w skali milionów elektronowoltów ... natomiast fizyka atomowa (blisko optyki) zajmuje się zjawiskami na poziomie pojedynczych elektronowoltów. Artykuł na Wikipedii nawet nie ma przekierowania z "reaktorów atomowych": https://pl.wikipedia.org/wiki/Reaktor_j%C4%85drowy Ten termin, razem np. z rezonansem magnetycznym (który bardziej się kojarzy z biorezonansem niż z MRI/NMR), wziął się pewnie z czasów zimnej wojny, ciągłym strachem przed bronią jądrową ... Dzisiaj to jest raczej ogłupianie społeczeństwa - bo co? Bo w Czarnobylu był jądrowy a my robimy atomowy? Jak chcemy zmniejszyć strach przed energetyką jądrową, mimo że to może być politycznie niepoprawne, lepiej podkreślajmy koszty/porównanie z innymi źródłami - szczególnie głównej alternatywy: węgla. Coś jak że słyszymy głównie o wypadkach samolotów, podczas gdy dużo bardziej prawdopodobna jest śmierć na drodze. Śmierci na TWh: http://nextbigfuture.com/2011/03/deaths-per-twh-by-energy-source.html " Coal – world average 161 (26% of world energy, 50% of electricity)Coal – China 278Coal – USA 15Oil 36 (36% of world energy)Natural Gas 4 (21% of world energy)Biofuel/Biomass 12Peat 12Solar (rooftop) 0.44 (less than 0.1% of world energy)Wind 0.15 (less than 1% of world energy)Hydro 0.10 (europe death rate, 2.2% of world energy)Hydro - world including Banqiao) 1.4 (about 2500 TWh/yr and 171,000 Banqiao dead)Nuclear 0.04 (5.9% of world energy)" ps. Gucio, ogniwa fotowoltaiczne brzmią super, ale - świata jeszcze długo nie będzie stać na nie na istotnym poziomie, - mają żywotność rzędu powiedzmy 20 lat - pewnie znacznie mniej gdy rysowane piaskiem pędzącym z wiatrem, - wymagają paskudnej chemii do wytworzenia - szczególnie że mówimy o skali tysięcy kilometrów kwadratowych ... i że po 20 latach trzeba wszystko wymienić ... - wymagają olbrzymich przestrzeni, zastępując np. las produkujący cenny dla nas tlen (i eksmitując jego mieszkańców) ...

Owszem tokamaki są super ... "i tylko wysp tych nie ma" - od 50 lat krzyczą że za 20 lat to już na pewno będzie działać. Ekonomiści mogą wykonywać wspaniałe analizy finansowe ... tyle że bardzo one zależą od zysku energetycznego ... i nawet nie mamy pewności że będzie on pozytywny dla ITERa. Kolejną olbrzymią trudnością są koszty degradacji takiego reaktora - bombardowanego olbrzymią ilością neutronów, co bardzo niszczy materiały. Warto wspomnieć że poza mainstreamem jest jeszcze rozważane kilka podejść do fuzji: - laserami: https://en.wikipedia.org/wiki/National_Ignition_Facility ... ale chyba nawet najwięksi bajkopisarze już nie twierdzą że to mogłoby mieć jakikolwiek sens finansowo, - ciekawe jest https://en.wikipedia.org/wiki/General_Fusion w którym kilkadziesiąt tłoków synchronicznie wytwarza fale mechaniczne mające doprowadzić do fuzji w centrum kuli, - https://en.wikipedia.org/wiki/Tri_Alpha_Energy,_Inc. - inna geometria niż tokamak, - https://en.wikipedia.org/wiki/Dense_plasma_focus - ukierunkowany strumień jonów (podejście zapoczątkowane w Świerku: http://web.archive.org/web/20121031093355/http://www.paa.gov.pl/dokumenty/ptj/sadowski10.pdf ) - fuzję ponoć mają, ale jeszcze negatywny balans energii, - https://en.wikipedia.org/wiki/Polywell - krążące elektrony w pułapce w kształcie sześcianu - też ponoć są blisko, - mały reaktor z MIT: http://news.mit.edu/2015/small-modular-efficient-fusion-plant-0810 , skunk works: https://en.wikipedia.org/wiki/High_beta_fusion_reactor - no i niesławna zimna fuzja dla której ostatnio co chwilę obiecują bliską komercjalizację, np. http://www.huffingtonpost.com/david-h-bailey/post_10010_b_8052326.html ps. jako fizyka skręca mnie gdy widzę "reaktor atomowy" - każdy reaktor jest zbudowany z atomów, o pozyskiwanie energii atomowej to bardziej chodzi np. przy spalaniu węgla ... natomiast w artykule chyba jednak chodzi o reaktor jądrowy.

Patenty to straszna sprawa, na przykład kodowanie arytmetyczne (serce kompresorów) przez 20 lat było praktycznie nieużywane ze względu na patenty: https://en.wikipedia.org/wiki/Arithmetic_coding#US_patents Wspominałem o Asymmetric Numeral Systems - moim kodowanu które właśnie wypiera Huffmana i arytmetyczne w kolejnych kompresorach ze względu na znacznie lepsze parametry, np. w LZFSE Apple, CRAM 3.0 European Bioinformatics Institute, LZNA RAD Tools Games i wielu innych ( http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations ) ... a tu jacyś dwaj goście w lutym tego roku zgłosili bardzo ogólny patent na ANS: https://www.ipo.gov.uk/p-ipsum/Case/ApplicationNumber/GB1502286.6 . Przez 18 miesięcy nawet nie można sprawdzić co w nim jest.

github: https://github.com/cisco/thor Jest wiele otwartych kompresorów wideo, mówi się szczególnie o https://en.wikipedia.org/wiki/Daala z kontrowersyjnym lapped transofrm. VP Google niby też jest otwarte choć niekoniecznie darmowe: https://github.com/webmproject/libvpx/tree/nextgen Z zamkniętych, polecam sprawdzić V-Nova Perseus ...

Owszem giezip to prehistoria (Huffman) - proponuję porównać sobie z czymś na ANS, np. (LZ+tANS jak LZFSE Apple) https://sites.google.com/site/powturbo/

Apple też się odchudza: http://thenextweb.com/apple/2015/06/09/app-thinning-in-ios-9-might-finally-mean-your-16gb-iphone-isnt-always-out-of-space/ obiecują zmniejszyć z 4.6 do 1.3 GB - dość ostro. Jednym z czynników jest ich nowy kompresor: LZFSE, czyli Lempel Ziv Finite State Entropy, gdzie to FSE to już nie standardowy Huffman czy kodowanie arytmetyczne, tylko wspomniany ANS: https://github.com/Cyan4973/FiniteStateEntropy Twierdzą że LZFSE jest 3x szybszy, dając lepszą kompresję od standardowego ZLIB. ANS niedługo spotkamy też w grach ( http://cbloomrants.blogspot.de/2015/05/05-09-15-oodle-lzna.html ), kompresji DNA (CRAM 3.0: http://www.ebi.ac.uk/ena/software/cram-toolkit ) i wielu innych miejscach (np. https://github.com/Cyan4973/zstd czy https://sites.google.com/site/powturbo/ ).

Przy szybkiej kompresji, nawet w RAMie może bardziej się opłacać trzymać skompresowane, jak w przypadku kompresji tekstur: http://en.wikipedia.org/wiki/Texture_compression Szczególnie przy rozwoju sprzętowej - może warto kompresować nawet np. komunikację między CPU i GPU ...

A jak przestanie obsługiwać nowe modele gwoździ... Pewnie i tak ma sprzętową kompresję dźwięku.

Odnośnie kosztownych kompresorów, szczególnie wideo, pewnie masz ASIC w telefonie ... Dla reszty chyba wystarczy procesor - dostając rzędu 2GB/s/rdzeń dla kiepskiej kompresji, czy rzędu 500MB/s/rdzeń dla przyzwoitej. Ale jasne można też robić FPGA czy ASIC - tutaj ANS też poprawia sytuację bo ma prostą tanią inicjalizację, podczas gdy Huffman wymaga sortowania symboli - budowanie drzewa jest sprzętowo dość kosztowne.

Szybka kompresja raczej poprawia wydajność dysków, których fizyczny transfer jest zwykle tym wąskim gardłem - dzięki kompresji wystarczy odczytać mniejszy plik. Np. LZ4 ( https://code.google.com/p/lz4/ ), używany w dziesiątkach produktów, osiąga 2GB/s/rdzeń - dużo taniej zdekodować w locie niż przeczytać z dysku większy plik. Tak samo kompresja w locie pozwala zmniejszyć wymagania transmisji (np. walka H.264 -> H.265) - przyszłość to trzymać wszystko skompresowane. Niestety problem jest zwykle z dostępem wewnątrz takich danych, ale też idzie się w tą stronę: http://en.wikipedia.org/wiki/Compressed_data_structure

Kompresja w locie wymaga szybkich/tanich kompresorów - i trochę się ostatnio zmieniło na tym polu. Standardowo używamy np. gzipa - tutaj jest porównanie z kilkoma kompresorami które już przeszły z kodowania Huffmana lub Range coding na Asymmetric Numeral Systems (zhuff, lzturbo, LZA, ZSTD) z http://mattmahoney.net/dc/text.html : kompresor, wielkość enwiki8 po skompresowaniu, czas kompresji, dekompresji (ns/bajt) LZA 0.82b –mx9 –b7 –h7 26,396,613 449 9.7 lzturbo 1.2 –39 –b24 26,915,461 582 2.8 WinRAR 5.00 –ma5 –m5 27,835,431 1004 31 WinRAR 5.00 –ma5 –m2 29,758,785 228 30 lzturbo 1.2 –32 30,979,376 19 2.7 zhuff 0.97 –c2 34,907,478 24 3.5 gzip 1.3.5 –9 36,445,248 101 17 pkzip 2.0.4 –ex 36,556,552 171 50 ZSTD 0.0.1 40,024,854 7.7 3.8 WinRAR 5.00 –ma5 –m1 40,565,268 54 31 Czyli są rzędu 5 razy szybsze zarówno w kodowaniu jak i dekodowaniu od opartych na Huffmanie (rar, gzip, pkzip) dla podobnego stopnia kompresji. Dekodowanie ~500MB/s na rdzeń procesora to teraz standard dla ANS ( https://github.com/Cyan4973/FiniteStateEntropy ) - przy takich prędkościach można sobie pozwolić na kompresję w biegu - zarówno żeby oszczędzić miejsce na dysku, ale także żeby przyśpieszyć transmisję.