«

»

Дек 05 2013

R&D-проект по сжатию общего назначения закончен

Некоторое время назад встал вопрос о необходимости библиотеки для сжатия assert`ов в движке. На тот момент для этих целей использовалась библиотека LZO (к слову, единственная используемая мной сторонняя библиотека), однако из-за её GPL-лицензии надо было или покупать её pro-версию, или менять на что-то другое (возможно даже своё). Кроме того, давно назревал вопрос о целесообразности использования для поставленной задачи именно алгоритма семейства LZ77. С целью сбора и анализа данных о различных алгоритмах сжатия в контексте указанной задачи и был начал этот R&D проект.

Учитывая задачу, для которой планировалось применять сжатие, были выработаны следующие требования к реализуемому алгоритму сжатия:

  1. Возможность работать с независимыми блоками размером от 1КБ до 1ГБ
  2. Отсутствие требований к быстрой компрессии
  3. Высокая скорость декомпрессии (~256 МБ/с) на блоках в 256КБ-1МБ
  4. Необходимость вычислять CRC32 хеш результатов декомпрессии (либо в процессе декомпрессии, либо дополнительным шагом)

Столь высокие требования к скорости декомпрессии сразу же исключали любые сложные алгоритмы, вроде PPM, да и вообще любые адаптивные алгоритмы.

Дальнейшие изыскания показали также нецелесообразность использования статического арифметического кодирования, т.к. оно лишь незначительно выигрывает в сжатии у кодов Хаффмана, но при этом значительно проигрывает ему в производительности. Простые реализации алгоритмов семейства LZ78 также не дали желаемых результатов – отсутствие сколько-нибудь существенного преимущества над LZ77 при значительно меньшей скорости работы.

Таким образом с алгоритмической стороны остались только Хаффман, LZ77 и их комбинация (широко известная реализация такой комбинации – формат deflate, используемый в zip). Кроме того, компрессор LZ77 обычно ещё разделяют на 2 варианта – быстро/качественно. Со стороны библиотек в тестировании участвовали LZO, LZ4 (как возможная замена LZO) и ZIP (как классическая вещь, которую очень часто советуют для этой задачи). Кроме них естественно участвовали и собственные реализации всех 3-х вариантов.

Так уж сложилось, что изначально для сравнения алгоритмов был выбран отнюдь не лучший, с точки зрения планируемого применения, набор файлов:

  1. Английский текст – 186 223 байта
  2. Исполняемая программа – 123 808 байт
  3. Малоцветная монохромная картинка – 65 580 байт
  4. Полноцветная монохромная картинка – 65 580 байт
  5. 3D-модель – 1 030 256 байт

На данном наборе были получены следующие результаты:

Cравнение алгоритмов на первом наборе файлов (данные сжаты до/скорость компрессии/декомпрессии)
Алгоритм Файл 1 Файл 2 Файл 3 Файл 4 Файл 5
Huffman 56,5%|214,47|293,42 70,1%|205,26|252,29 35,2%|221,43|312,28 95,7%|195,94|279,50 73,6%|209,70|269,63
LZ77_3S 53,4%|197,39|398,66 44,4%|221,83|530,26 39,3%|271,87|436,07 95,4%|141,03|690,15 52,7%|203,71|649,44
LZ77_4S 48,6%|238,98|453,17 42,0%|285,51|626,14 33,5%|349,19|535,10 95,9%|316,32|1267,6 51,7%|261,60|816,50
LZ77_3L 54,2%|198,50|403,75 45,3%|228,23|523,12 40,3%|272,32|441,99 94,6%|140,64|683,96 51,8%|207,99|601,65
LZ77_4L 49,0%|238,64|454,76 42,7%|301,02|626,37 34,4%|344,37|528,38 95,5%|313,70|1231,5 51,5%|291,08|738,51
LZO_1x_15 55,6%|174,93|385,35 42,2%|183,68|553,26 37,2%|337,89|525,10 97,0%|81,06|1117,5 50,8%|170,28|679,16
LZ4 60,6%|331,1|1598,6 45,3%|444,5|1924,0 45,2%|553,9|1135,9 97,6%|490,1|3809,6 55,0%|491,9|1858,8
LZ77_3S+ 40,0%|13,51|510,63 37,8%|13,24|604,22 23,0%|2,80|826,08 93,5%|52,80|652,13 47,7%|5,03|761,20
LZ77_4S+ 41,0%|26,28|517,27 38,1%|22,52|668,74 23,0%|4,15|802,75 95,2%|68,79|1145,2 47,6%|6,64|932,57
LZ77_3L+ 40,7%|5,70|519,77 38,7%|8,87|595,49 23,9%|2,77|835,34 92,9%|43,87|654,18 40,4%|2,07|895,64
LZ77_4L+ 41,2%|11,81|531,00 38,8%|14,20|674,83 23,8%|4,09|820,50 94,8%|50,92|1118,6 40,2%|2,97|1082,0
LZO_1x_999 41,2%|6,74|423,14 33,8%|5,87|599,35 24,6%|1,86|659,60 92,6%|12,22|553,69 43,0%|6,09|781,05
LZ4HC 42,0%|23,6|1598,6 36,3%|38,6|1924,0 26,6%|7,6|1135,9 94,4%|50,1|3809,6 47,0%|30,9|1858,8
LZHuffS 49,3%|138,65|258,24 39,5%|156,79|310,92 28,7%|177,06|275,92 94,1%|90,85|241,94 45,1%|143,78|310,36
LZHuffL 50,1%|138,71|255,47 40,3%|158,74|306,64 29,1%|176,82|278,19 93,5%|91,11|243,81 44,6%|145,82|300,46
ZIP1 43,5%|40,10|116,62 35,7%|45,34|131,51 25,7%|54,29|152,83 87,0%|25,54|90,45 41,9%|37,48|125,12
LZHuffS+ 38,2%|13,15|306,70 34,6%|12,92|352,01 21,9%|2,79|460,89 92,5%|42,11|239,20 42,4%|5,00|350,57
LZHuffL+ 38,5%|5,64|311,69 35,3%|8,74|351,26 22,1%|2,77|466,74 92,1%|36,53|243,23 36,4%|2,07|406,02
ZIP9 36,1%|10,83|133,71 31,6%|3,48|148,20 19,5%|1,42|196,60 87,6%|19,34|93,34 38,3%|4,62|139,42

Исходя из полученых данных, можно было сделать следующие выводы:

  • Использование кодов Хаффмана в чистом виде нецелесообразно
  • LZ4 обеспечивает просто огромные скорости декомпрессии, однако ценой худшего сжатия по сравнению с другими LZ-собратьями
  • Использование связки LZ4+Huffman попросту глупо, т.к. декомпрессия всё равно упрётся в скорость именно декодера Хаффмана
  • Библиотека LZO очень удачно спроектирована и, если нужно только LZ77-сжатие, то она довольно неплохой вариант
  • LZ4 демонстрирует очень высокую скорость сжатия в режиме HighCompression, и причина тому – использование поискового алгоритма Morphing Match Chain (который я, к сожалению, так и не понял)
  • Deflate демонстрирует наилучшие результаты почти всегда (проигрывая только на больших файлах из-за наличия у моей реализации режима с окном в 1МБ), однако его скорость декомпрессии непозволительно низкая для поставленной задачи

Как я уже писал выше, набор тестовых данных был слегка неудачным, потому были добавлены ещё 4 файла:

  1. 3D-стека – 11 526 376 байт
  2. Текстура 1024х1024, сжатая BC1 – 524 416 байт
  3. Текстура 1024х1024, сжатая BC7 – 1 048 576 байт
  4. 16-ти битная карта высот – 134 250 498 байт

Результаты новых тестов (без чистого Хаффмана и LZ4):

Cравнение алгоритмов на втором наборе файлов (данные сжаты до/скорость компрессии/декомпрессии)
Алгоритм Файл 6 Файл 7 Файл 8 Файл 9
LZ77_3S 47,1%|284,84|970,1 81,9%|128,42|413,60 96,9%|117,56|806,91 25,6%|331,22|1040,3
LZ77_4S 44,0%|348,31|1296,3 82,0%|193,18|597,13 96,9%|221,24|1204,0 24,7%|360,20|1184,2
LZ77_3L 47,2%|275,23|937,9 82,1%|136,18|398,41 96,0%|127,63|824,39 23,5%|315,52|1022,9
LZ77_4L 43,9%|382,33|1196,7 81,9%|222,58|563,46 96,2%|281,17|1163,2 23,0%|346,25|1056,9
LZO_1x_15 43,6%|292,86|1221,0 84,1%|94,75|533,81 98,5%|75,98|1075,1 30,1%|263,97|984,17
LZ77_3S+ 42,1%|16,51|1117,0 76,9%|24,40|413,97 95,3%|33,51|745,36 19,7%|84,11|1340,5
LZ77_4S+ 42,0%|26,23|1342,6 79,0%|36,05|528,28 95,9%|44,92|1021,3 19,8%|113,22|1586,0
LZ77_3L+ 42,0%|1,04|1101,1 75,8%|6,54|374,37 92,4%|4,26|612,75 15,2%|11,45|1462,6
LZ77_4L+ 40,4%|1,11|1206,4 77,4%|10,61|436,90 92,8%|4,99|699,73 15,2%|15,08|1518,1
LZO_1x_999 36,1%|4,68|1198,8 73,2%|8,44|348,51 95,8%|10,40|656,89 19,3%|24,35|1098,3
LZHuffS 35,6%|191,10|437,29 73,1%|92,81|211,28 94,6%|82,73|264,27 22,5%|253,61|590,40
LZHuffL 36,2%|186,35|414,21 73,9%|96,28|206,38 94,2%|88,29|270,32 21,0%|247,71|599,26
ZIP1 29,0%|47,35|147,81 68,6%|22,78|85,67 90,8%|20,06|92,24 25,6%|62,90|169,15
LZHuffS+ 33,9%|16,00|484,70 69,1%|22,41|212,20 93,0%|29,35|258,18 17,1%|78,13|738,25
LZHuffL+ 33,3%|1,04|466,05 69,1%|6,39|203,87 90,3%|4,20|248,97 13,8%|11,34|841,39
ZIP9 27,5%|4,44|162,48 65,9%|10,55|92,00 90,4%|15,39|96,25 19,1%|34,22|200,83

По результатам напрашивается еще один вывод: если текстуры в BC1 есть смысл сжимать, то для BC7 особого смысла делать это нет.

LZHuffS+ и LZHuffL+ демонстрируют неплохие показатели: средняя скорость декодирования ~432МБ/с, минимальная – 204МБ/с. И при этом выигрывают у LZO как в степени сжатия, так и в скорости сжатия (относится только к LZHuffS+, т.к. плата за 1МБ окно у LZHuffL+ весьма высока).

Таким образом у нас остаётся последний вопрос – CRC32 хеш результата декомпрессии. Алгоритмы LZHuffS и LZHuffL вполне позволяют встроить его рассчёт прямо в декомпрессор, остаётся только проверить эффективность такого шага.

Относительная скорость декомпрессии при необходимости рассчёта CRC32-хеша результата
Алгоритм сжатия С внешним расчётом хеша С внутренним расчётом хеша
LZHuffS 96,96% 98,72%
LZHuffL 96,91% 98,80%
LZHuffS+ 96,33% 99,17%
LZHuffL+ 96,13% 99,53%

Итог тут один – встроенному рассчёту хеша быть!

Добавить комментарий