Компания Google анонсировала (http://google-opensource.blogspot.ru/2015/09/introducing-bro... алгоритм сжатия данных Brotl, который отнесён к алгоритмам сжатия общего назначения, но позиционируется как решение для минимизации объёма данных, передаваемых по сети. Спецификация Brotli передана (http://www.ietf.org/id/draft-alakuijala-brotli-05.txt) в комитет IETF (Internet Engineering Task Force), занимающийся развитием протоколов и архитектуры Интернет, в качестве претендента на получение звания интернет-стандарта. В настоящее время Brotli уже применяется в качестве алгоритма сжатия шрифров Web Open Font Format 2.0. Эталонная реализация Brotl написана на языке С++ и распространяется (https://github.com/google/zopfli) под лицензией Apache 2.0.
Brotli демонстрирует (http://www.gstatic.com/b/brotlidocs/brotli-2015-09-22.pdf) уровень сжатия, сопоставимый с лучшими современными методами сжатия общего назначения, но опережая их по скорости кодирования и декодирования. Например, в тесте Canterbury Corpus (http://corpus.canterbury.ac.nz/) алгоритм Brotli превосходит по уровню сжатия LZMA и bzip2 и при этом меньше потребляет ресурсов CPU.Brotli близок по производительности к алгоритму Deflate (https://ru.wikipedia.org/wiki/Deflate), но превосходит его по степени сжатия. По сравнению с представленным (https://www.opennet.dev/opennews/art.shtml?num=36267) в 2013 году алгоритмом Zopfli, совместимым с Zlib и Deflate, Brotli позволяет сжимать данные на 20–26% эффективнее.
<center><a href="http://www.gstatic.com/b/brotlidocs/brotli-2015-09-22.pdf&qu... src="https://www.opennet.dev/opennews/pics_base/0_1442916096.png&q... style="border-style: solid; border-color: #606060; border-width: 1px;max-width:100%;" title="" border=0></a></center>
Brotli является комбинацией современного варианта алгоритма LZ77 (https://ru.wikipedia.org/wiki/LZ77), адаптивного кодирования Хаффмана (https://ru.wikipedia.org/wiki/%D0%9A%D0%... и методов контекстного моделирования второго порядка (http://www.intuit.ru/studies/courses/1069/206/lecture/5328?p.... При сжатии разнородных данных. Высокий уровень сжатия достигается применением контекстного моделирования второго порядка, повторным использованием кодов энтропии, более крупным размером окна кодирования и использованием совместных кодов распределения (joint distribution code). Компания Google надеется, что в скором времени поддержка данного формата будет реализована во всех основных браузерах (в рамках поддержки Web Open Font Format 2.0), что позволит уменьшить размер передаваемых данных и, как следствие, приведёт к меньшему потреблению энергии при открытии контента на мобильных устройствах.
URL: http://google-opensource.blogspot.ru/2015/09/introducing-bro...
Новость: http://www.opennet.dev/opennews/art.shtml?num=43006
цитата кода
"#define NUM 9 /* Good value: 9. */"
В подобной алгоритмике экспериментально подобранные "хорошие значения" сплошь и рядом, особенно на ранних этапах. Иногда потом теория под них находится, иногда - нет.
возможно, аноним имел ввиду что лучше написать "const int NUM = 9;"
А чё не " const static unsigned short volatile const NUM __attribute__ ((aligned (16))) = 0b1001u;" ?
Ну так, чисто чтоб всех анонимов сразу в моск пробило. :)
убил
> убилЧорт, забыл inline
И дважды const поставил.
А вот register - забыл.
> И дважды const поставил.Курить стандарт срочно.
> А вот register - забыл.
Туда же.
>> И дважды const поставил.
> Курить стандарт срочно.
>> А вот register - забыл.
> Туда же.Вам бы самому тоже не помешало.
Слив засчитан.
О, Ктулху, что тебя разбудило? :)
> О, Ктулху, что тебя разбудило? :)Осень, велосезон заканчивается, обострение. :-P
оффтоп: изнутри наружу =)
Почему Хаффман, а не арифметическое кодирование?
Потому что хаффман быстрее, скорее всего.
К тому же вокруг арифметического кодирования патентов много.
Патент IBM уже давно истек
#>патентов много.
> Патент IBM уже давно истекОдин из "много"? АргУмент.
Что-то с графиком странное. deflate:1 медленнее deflate:9? Что за бред?
все с ним в порядке.....это у вас там...
Чем больше распаковывается данных из окна совпадений - тем быстрее, т.к. это hot cache, при низком сжатии данные распаковываются меньшими частями, т.е. чаще вычитываются из входного потока, который тоже больше
А, ну да. Decompression же.
Поздно, меняй ник
Гугл таки купил Pied Piper?
Не, это они Nucleus переименовали.
Мда, основной вывод - gzip можно выкидывать окончательно - эта штука его перекрывает полностью - и на 1 и на 9 жмёт быстрее и лучше и распаковывает быстрее, чем gzip на аналогичном уровне. bzip2 и подавно идёт лесом - при сравнимом сжатии скорость различается в разы.А вот lzma в скорости сжатия при сравнимом ratio новичок проигрывает, хотя распаковывает быстрее - то есть надо выбирать в зависимости от задачи. Хотя, моежт, можно уровень 10 подобрать, чтобы был сравним - тогда получится совсем универсал.
gzip (как и zip), скорее всего, не выкинут, ибо совместимо с любыми системами. А bzip2 уже давно можно выкидывать - примерно со времен появления xz.
Там, где сжимаешь чаще, чем распаковываешь (бэкапы те же) bzip2 часто интереснее.А совместимость... нарастёт со временем. Во всяком случае, понятно, в какую сторону двигаться.
Но о zip я ничего не говорил. zip, в отличие от, стал скорее контейнером, чем компрессором. Там само сжатие вообще не критично в большинстве случаев.
> Там, где сжимаешь чаще, чем распаковываешь (бэкапы те же) bzip2 часто интереснее.Ничем он не интересный: ресурсоемкий и на сжатие и на распаковку и плохо (по сравнению с другими сильными компрессорами) жмет.
> Но о zip я ничего не говорил. zip, в отличие от, стал скорее контейнером,
При том достаточно дурным, изначально там ограничения на размера файла. А субформат без таковых уже как бы полусовместимый...
Cильные - жмут дольше, вообще-то, потому bzip2 и лучше. А в случае тех же бекапов в большинстве случаев их вообще не приходится ни разу распаковывать, а если приходится - время не сильно критично. Но это всё от конкретного случая зависит, конечно.zip - ну ограничения, но обычно это не особо важно. Часто вы встречали те же офисные документы или jar, которые в эти ограничения не укладываются?
> Cильные - жмут дольше, вообще-то,Вообще, сильно зависит от настроек: разогнать большинство "сильных" алгоритмов с небольшой потерей сжатия не особая проблема. А вот bzip2... он просто по современным меркам как-то не очень хорошо жмет, хотя ресурсоемкость и сжатия и распаковки - вполне на уровне.
> это всё от конкретного случая зависит, конечно.
Ну да. Не, коненчо бывают любители пожать .tar.bz2, а потом убив сдуру пару файлов и не имея снапшота - доооооооолго смотреть на декомпрессию 20Гб чушки...
> zip - ну ограничения, но обычно это не особо важно. Часто вы
> встречали те же офисные документы или jar, которые в эти ограничения
> не укладываются?Насчет офисных документов не скажу, но как именно generic контейнер он таки полусовместимые недограбли. Пожалели несколько байтов в заголовках в свое время, а теперь зато половина софта большие архивы читать не может. И в каком-нибудь navit например - большой зипарь вполне обычное явление. Достаточно всего ничего: планетарные данные OSM захотеть прицепить. И вот уже знакомимся с экзотичным субформатом зипаря, который половина программ просто не поймет...
>Мда, основной вывод - gzip можно выкидывать окончательноЕсть мнение, что gzip вас переживёт.
Кхм, ну, пережить меня - это вряд ли, но да, древний мусор болтается долго, даже не имея вообще никаких преимуществ. Что весьма печально.
Crazy Alex ... Саша, ты дурак!
На "старьё" ресурсы не тратятся. Лежит оно где то в тёмных углах /*bin/* и жрать не просит. Раз в пятилетку его надо перекомплять текущим набором компиляторов, пересобитать с текущей версией [g]libc и прогонять тесты на текущих оЗЪ.вёдрах. Всё. И это изюавит тебя от эшелона гиммороя, если старьё реально выкинуть. АЗЪ!
и как, много нынче желающих таскать древний compress? Вот gzip куда-то туда же уже метит. Поганенько жмет при том что ресурсоемкость у него вполне себе на уровне иных "LZ+дожатие".У gzip и вообще deflate - максимум словарь в 32 кило. Это не память, это склероз.
> Мда, основной вывод - gzip можно выкидывать окончательно - эта штука его перекрывает полностью...Они разве что про ресурсы как-то тактично умолчали (или это я с ходу не нашел?).
Разве что:
> The test computer we used is an Intel® Xeon® CPU E51650 v2 running at 3.5 GHz with six cores and six additional hyper threading contexts.
хотя и:
> All tests were run singlethreaded on an otherwise idle computer.
Это может и ни о чем не говорить, конечно, но исходники пока копать лень, а вопросы-то остаются: Будет ли это настолько же круче на сильно более слабом железе? на другой платформе? сможет ли вообще отработать при малом ОЗУ?
Если по всем трем - "да", то тогда gzip может и пора на покой совсем, а так пока есть у него ещё потенциальные ниши где ресурсов совсем мало и архитектура сильно отличается от x86-64.
Ниш со слабыми ресурсами становится всё меньше и так, разумеется, будет и дальше. Что до разницы архитектур - как минимум, между ARM и x86 я неожиданых различий в плане скорости не видел на довольно широком диапазоне задач - приходится по работе обращать внимание на это.
В "не бытовухе" ресурсы систем растут далеко не так стремительно, хоть в целом и растут, да.
Про архитектурное - речь идет в основном про активное использование всяких mmx, sse, neon и т. п. Само по себе это неплохо и выигрыши очевидны, но за счет этого, на тех платформах где нет технологий, аналогичных используемым авторами алгоритма, уже не скажешь об однозначной победе и что старые алгоритмы пора выкидывать на свалку (бывают и ARM попроще и/или постарее, бывают и вовсе не ARM если мы говорим не о планшетах/телефонах). Тоже самое касается и требований к ОЗУ, с маленьким отличием - если нужных аппаратных возможностей нет в процессоре, то эмуляция просто убъет весь выигрыш, а нехватка ОЗУ не даст работать вообще.
Поэтому, глядя на новые блестящие алгоритмы (я не вот сейчас конкретно про этот - не копался ещё в нем), уделывающих всех и все на разных бенчмарках, я не спешу хоронить старые - слишком часто достигают прям решительного преимущества за счет конкретных оптимизаций на конкретных платформах и при помощи ОЗУ. Повторю, это вовсе не плохо и даже хорошо, просто подходит не везде, а значит и старое списывать пока рановато.
> Они разве что про ресурсы как-то тактично умолчали (или это я с
> ходу не нашел?).ну, если загнуть все параметры по максимуму — задумается надолго, а прирост почти никакой. если середнячком — то будет относительно (средней температуры по больнице) шустрый, прирост (точнее, убыль размера) по сравнению с deflate не «O_O», но таки иногда приятный. таскать с собой словарь задалбывает — у deflate при желании все таблицы можно построить в рантайме, а тут железными гвоздями вбит словарь (хотя используется не во всех методах, но иметь его надо, чтобы разжимать всё, что пришлют).
ресурсов жрёт, понятно, больше deflate.
p.s. впрочем, я бы сказал, что «сжимать лучше deflate» — это вообще не достижение, а минимально необходимое условие для любого компрессора сложнее, чем «тупо LZ».
в общем, обычный «ещё один алгоритм», где‐то лучше, где‐то хуже, статический словарь дурных размеров дико бесит.
> Мда, основной вывод - gzip можно выкидывать окончательно - эта штука его
> перекрывает полностьюособенно по размеру кода и размеру бинарей.
и да, жмёт она не настолько лучше, чтобы стоило скакать от радости. deflate, конечно, давно уже не вершина технологий, но всё не настолько плохо (или хорошо).
и словарь, словарь… фэйспалм.
только щас представила? эта хрень же в WOFF2 уже хз сколько времени используется
что это "WOFF2"?
> только щас представила?"Google анонсировала" + "Спецификация Brotli передана [...] в комитет"
> эта хрень же в WOFF2 уже хз сколько времени используется
"В настоящее время Brotli уже применяется в качестве алгоритма сжатия шрифров Web Open Font Format 2.0."
Трудная языка? Понимаю. Читаю новости вверху -- дорого, паяльник свой.
Круто, конечно, но не очень понятно при чем тут Интернет. Чтобы им что-то начали жать, надо еще стандартизировать что и когда можно жать и как клиент с сервером об этом могут договориться.
Ну вот они и подали для стандартизации.
> Круто, конечно, но не очень понятно при чем тут Интернет.при том, что они собрали дурных размеров словарь из обрывков слов, чтобы «лучше жать страницы».
Проталкивают новый формат, а сами не удосужились даже bzip, lzma, ppmd реализовать. В итоге будет как с WebP.
А зачем реализовывать заведомо худшие алгоритмы?
> А зачем реализовывать заведомо худшие алгоритмы?Сейчас Chrome поддерживает только gzip, deflate. Перечисленные выше алгоритмы явно лучше этих.
Ну вот этот и реализуют. Чем убьют любой смысл использования в вебе чего-то кроме. Это, конечно, злоупотребление монопольным положением - но в данном случае я буду аплодировать стоя, потому что иначе старыфе алгоритмы ещё лет десять не подохнут.
> Ну вот этот и реализуют. Чем убьют любой смысл использования в вебе
> чего-то кроме. Это, конечно, злоупотребление монопольным положением - но в данном
> случае я буду аплодировать стоя, потому что иначе старыфе алгоритмы ещё
> лет десять не подохнут.Firefox и остальные как будет на такую монополию смотреть? Конечно же точно также как и на WebP. Тот тоже был лучше и убивал всякий смысл продолжать использовать JPEG, а воз и ныне там.
>> Ну вот этот и реализуют. Чем убьют любой смысл использования в вебе
>> чего-то кроме. Это, конечно, злоупотребление монопольным положением - но в данном
>> случае я буду аплодировать стоя, потому что иначе старыфе алгоритмы ещё
>> лет десять не подохнут.
> Firefox и остальные как будет на такую монополию смотреть? Конечно же точно
> также как и на WebP. Тот тоже был лучше и убивал
> всякий смысл продолжать использовать JPEG, а воз и ныне там.Firefox ка бы почти Chrome уже... :)
> Firefox и остальные как будет на такую монополию смотреть? Конечно же точно
> также как и на WebP.Да им тоже прилетело за такую некооперативность: на их apng тоже как-то подзабили.
И вообще, если мозилла будет щелкать клювом - ну ок, у юзерей хрома контент пожатый более сильным алгоритмом будет грузиться быстрее. А юзеры лисы опять в минусе? Ну ок, тогда пусть мозилла не обижается когда у нее останется 2% как у оперы.
А файрфокс посмотрел... и поддержал в выпуске 44: http://www.opennet.dev/opennews/art.shtml?num=43764
> bzip, lzma, ppmdПочитай про zip-бомбы, про скорость сжатия.
> Почитай про zip-бомбы, про скорость сжатия.И? gzip и Brotli точно также подвержены этому. Это концептуальная проблема любой архивации, единственным способом нейтрализации которой, являются выставление лимита размера распакованных данных.
оно для веба слабо годится
>В итоге будет как с WebPС WebP всё прекрасно - я все скриншоты только им и кодирую. Визуально качество как jpeg, а весит в разы меньше
> С WebP всё прекрасно - я все скриншоты только им и кодирую.
> Визуально качество как jpeg, а весит в разы меньшеВообще-то для скриншотов PNG есть. Он вообще lossless. Размер правда как повезет, однородная графика жмется хорошо, а градиентная... ну это не жыпег.
>С WebP всё прекрасноКонечно. Но открыть можно только Chrome и Opera которая фактически Chrome.
> С WebP всё прекрасно - я все скриншоты только им и кодирую.
> Визуально качество как jpeg, а весит в разы меньше...но есть способ лучше! BARF! http://mattmahoney.net/dc/barf.html - сжимает вообще любые файлы. Быстро. До 0 байтов. И даже может распаковать обратно.
...но правда те кто немного знает математику, начнут что-то подозревать, хотя формально он делает именно то что заявлено :)
Почему они взяли "LZMA implementation in 7zip 9.20.1"?
7zip 9.20 был выпущен 2010-11-18 и не использовал LZMA2
По умолчанию не использовал, но поддержка LZMA2 там уже была.Вообще эти черти удивляют. Зачем они столько времени бету гоняют и не делают релиз?
забавно, судя по графику, он вообще-то на 20% сильнее сжимает, чем deflate9, при этом на 18% медленнее. Так что не надо спешить и сломя голову бросаться менять ваши системы :)
Мы разные графики смотрим? Brotli1 и 9 во всех номинациях лучше/быстрее deflate1 и 9, соотв-но.
разные deflate9 быстрее Brotli1
deflate9 надо менять на Brotli9 - будет быстрее и сжатие, и распаковка, и лучше ратио
это если сравнивать "ратио", а если, как гугл, сравнивать "скорость", то получается наоборот :)
Так у него и скорость больше. Можете pdf открыть, там цифры есть. deflate проигрывает вообще по всем статьям.
> Так у него и скорость больше. Можете pdf открыть, там цифры есть.
> deflate проигрывает вообще по всем статьям.а теперь ограничим доступную память 64-мя килобайтами.
А как его самостоятельно с p7zip сравнить по скорости, степени сжатия и потреблению ресурсов?
В новости есть сылка на гитхаб
гугл таки купил фирму "пегий дудочник" (крысолов) ? =D
И чем же он лучше arj?
а что там насчет lzo
> а что там насчет lzoТо же что и LZ4: алгоритмы другой весовой категории. Они на скорость ориентированы, при приемлимом сжатии. А эти - на степень сжатия, при приемлимой скорости. Очень разные оптимизации.
> а что там насчет lzoНе нужен при наличии lz4
какой у него коэффициент Вальцмана?
> какой у него коэффициент Вальцмана?7
с ходу что получилось
hobot@SERVER:~/WORK/brotli/tools# time cat bro |./bro > bro.broreal 0m2.487s
user 0m2.444s
sys 0m0.040s
hobot@SERVER:~/WORK/brotli/tools# ls -lh /bin/^C
hobot@SERVER:~/WORK/brotli/tools# time cat bro |gzip > bro.gzipreal 0m0.053s
user 0m0.044s
sys 0m0.008s
hobot@SERVER:~/WORK/brotli/tools# ls -lh ./bro*
-rwxr-xr-x 1 root root 947K сент. 24 12:33 ./bro
-rw-r--r-- 1 root root 243K сент. 24 12:35 ./bro.bro
-rw-r--r-- 1 root root 426K сент. 24 12:35 ./bro.gzip2.4 секунды с bro и 50ms с gzip
> 2.4 секунды с bro и 50ms с gzipА ничего что bro у вас кажись фигарил с максимальным сжатием? И в результате уделал gzip-а по сжатию ... всего-ничего, В ДВА РАЗА. И да, там нелинейная зависимость: улучшить результат сжатия в 2 раза вообще удается далеко не всегда и тем более это сложнее не в 2 раза. Поиск например более удачных совпадений, повышающий степень сжатия - очень быстро становится крайне медленной операцией. Практические реализации LZ-based - забивают по некоторому таймауту на поиск "еще более удачного совпадения", иначе они будут вкалывать ооооочень долго.
Предполагаю, что результаты вашего теста некорректны, т.к. в первом случае файл поднимался с диска, а во втором уже из page cache.
А почему они про zstd забыли в тесте?
…а ещё дурацкого словаря, высосаного из… неизвестно октуда (обрывки русского в нём умилили), и дичайших тормозов при попытке чуть‐чуть подкрутить уровень сжатия. плавали, знаем, не впечатлило.
