Перевел на ассемблер вариант арифметического сжатия, 8-битный алфавит, с уменьшенным количеством делений, работает на основе частот с накоплением. В варианте SISD один из самых медленных вариантов, но какой приход даст SIMD?
Приход будет хороший! У Ивана Колесникова вроде получилось даже быстрее, чем с пирамидой. Но в том варианте Delphi, что я использую, AVX не завезли😕, пришлось ограничиться только SSE.
В результате у меня скорость сжатия получилось ровно такая же, как в варианте с пирамидой и полным количеством команд деления, а вот распаковка все же проигрывает: 10.0 и 6.7 МиБ/с против 10.0 и 7.0 соответственно, на FX-4350. Тем не менее, этот вариант мне больше нравится своей простотой.
Что дальше? Если не смотреть на вариант с очень коротким алфавитом, который используется в сжатии видео очень высокой четкости, то вижу пока два варианта: либо перейти в варианте с пирамидой на уменьшенное количество делений, либо в варианте с таблицей перейти на более низкую точность, используя UInt16 вместо UInt32 в таблице частот.
Пока что выбрал последний вариант: приход от снижения количества делений безусловно будет, но прогнозируемо не очень большой. А вот снижения размера таблицы частот в два раза может дать, на мой взгляд, гораздо более значительный эффект.
Кстати, опытным путем выяснил, что сокращение количества делений увеличивает требование к точности расчетов примерно на 2 бита. То есть там, где раньше хватало 64, потребуется 66. Впрочем, опять же опытным путем выяснил, что проявится это на достаточно длинных данных, как минимум в четыре раза более длинных, чем диапазон данных для хранения частоты.
Перевод на ассемблер варианта с 16-битным алфавитом отложил пока на неопределенное будущее. Уж больно специфическая область применения: либо данные существенно 16-битные, либо большой их объем. Но на большом объеме, судя по всему, рулят методы с коротким алфавитом.
Из забавного: все же CISC немного развращает разработчиков процессоров. Например, есть две команды: MOVDQU и LDDQU. Вот смотрю я на них и понять не могу, зачем вторая, если первая более универсальна и делает все то же самое и даже больше?
Начал искать в инете, и вроде как выходит, что вторую ввели разработчики процессоров Intel для обхода какого-то узкого места при работе с памятью какого-то конкретного процессора. Все отличия в этих двух командах в каких-то очень тонких нюансах работы с памятью.
Какой из двух команд использовать? Попробовал оба варианта — результат одинаковый.
Все же RISC, особенно если количество команд жестко ограничено их форматом, сильнее дисциплинирует разработчиков 😄.
Еще из забавного: пособие для оптимизации от AMD рекомендует использовать при сохранении XMM регистров в память вместо уже упоминавшейся MOVDQU пару MOVLPx/MOVHPx. Проверил. — на моем процессоре разницы нет.
> вроде получилось даже быстрее, чем с пирамидой
ОтветитьУдалитьПо последним цифрам у меня при сжатии разницы нет, а на распаковке пирамида почему-то быстрее:
- массив: 11.5 / 9.4 MB/s
- пирамида: 11.4 / 11.3 MB/s
> AVX не завезли
Эх, они бы здесь наверное пригодились :)
> этот вариант мне больше нравится своей простотой
Это точно, пирамида хоть и быстрее, на больших алфавитах, но реализация не такая компактная получается. Я тут еще придумал как большие алфавиты можно обрабатывать: условно 1 8-ми битная модель на старший байт, а потом 256 моделей на младший байт. Сжали байт, переключились к следующей модели, сжали 2-й, вернулись на изначальную модель. Также как бинарный алгоритм работает, но только для байтов, а не битов.
> увеличивает требование к точности расчетов примерно на 2 бита
Вроде как раз наоборот при уменьшенном числе делений можно увеличить число битов в модели:
- когда считаем range * count / total, то чтобы избежать переполнения range * count должно входить в 64 бита, а так как range может уменьшаться до 1/4 от максимума, то получается на модель максимум 31 бит остается, а на диапазон 33.
- когда же считаем range / total * count, то главное чтобы range >= total, получается на модель 32 бита и на range 34-64 битов можно спокойно оставлять.
Или я ошибся где-то?
> Но на большом объеме, судя по всему, рулят методы с коротким алфавитом.
Я уже сомневаюсь что бинарные методы про скорость, похоже скорее про возможность относительно легко и быстро реализовать в железе, плюс, как оказалось, там есть возможность реализовать аппроксимированное скользящее окно, что увеличивает точность модели.
После долгого копания в интернете, я наконец-то нашел более-менее подробную статью как они работают и как реализовать эффективно: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.685.7582&rep=rep1&type=pdf увлекся и закодировал :)
Со скоростью все не очень весело: 7-8 MB/s. Хоть операции и простые: ни делений, ни умножений, пару обращений по индексу в массиве и несколько условий, сложений, сдвигов, да еще и 10 битной арифметики хватает, но это все происходит на каждый бит... Обычные процессоры заточены на более сложные операции, тут прям просится реализовать в железе. Может правда еще Java палки в колеса вставляет...
Зато так как модель, хоть и чуток аппроксимированная, но использует подобие скользящего окна, степень сжатия получается несколько выше на 3-4% на моих тестовых данных.
Еще я тут прикинул: я раньше писал что 15МБ/с, это не серьезно, но если перевести в такты 5ГГц процессора, то это всего 40 тактов на бит получается, вроде и не дурно.
> Эх, они бы здесь наверное пригодились :)
ОтветитьУдалитьНаверное. Но я тут задумался. Именно для таких операций, как в арифметическом сжатии, можно вроде SIMD легко и на обычных регистрах организовать. Вот и интересно, может, и вообще разницы не будет между SSE/AVX и GPI.
> Я тут еще придумал как большие алфавиты можно обрабатывать:
> условно 1 8-ми битная модель на старший байт, а потом 256 моделей на младший байт.
Ну да, можно. Но как-то сложно получается...
> Вроде как раз наоборот при уменьшенном числе делений можно увеличить число битов в модели...
Теоретически вроде все так, но у меня, пока точность не увеличил, на больших объемах данных модель расходилась. Может, конечно, нагнал где-то в коде, надо проверить...
> плюс, как оказалось, там есть возможность реализовать аппроксимированное скользящее окно...
ОтветитьУдалитьПри желании его всегда можно реализовать.
> Еще я тут прикинул: я раньше писал что 15МБ/с, это не серьезно...
Можно оценить. Н.264 стандартно для видео 4К в профиле 5.1 требует до 960000 КиБит/с = 117 МиБ/с. Так что в таких делах ни 15, ни тем более 7-8 МиБ/с никак не подходят. Не знаю даже, какие они там решения используют. Возможно, при жесткой аппаратной реализации бинарный вариант и дает такую скорость.
> можно вроде SIMD легко и на обычных регистрах организовать
ОтветитьУдалитьПравда, наверное можно, будет интересно посмотреть на результат :)
> Но как-то сложно получается
Всяко проще чем пирамида :) примерно так:
model = models[modelIndex] (где models - массив из 257 моделей)
encode(model, symbol)
modelIndex = (modelIndex > 0) ? 0 : symbol + 1
> При желании его всегда можно реализовать.
Я честно не представляю как это сделать эффективно для не бинарной модели, и какой должен быть размер окна, если для одного бита, H.264 использует в районе 20-ти. Все биты не хранятся, окно аппроксимированное, упрощенно в вещественных числах:
Если s - количество единиц в окне (состояние модели), w - размер окна, p = s/w - вероятность модели, x - новый бит. С добавлением бита понятно, а как удалять старый бит? И здесь вот проявляется аппроксимирование: вместо удаления самого старого бита, удаляется случайный, с вероятность p. И того обновление модели: s = s - s/w + x.
> Можно оценить
Хм действительно, спасибо за оценку! Алгоритм то вроде я тот же реализовал M-Coder, но скорости совсем другие :))) Думаю там несколько ядер декодируют, ведь кодируется все не одним сплошным потоком как у нас (иначе не понятно как просмотр со случайного места делать), а значит можно несколько ядер загрузить. Но все равное цифры не сравнимы! У меня основное время уходит на выделение общего префикса, вот придумать бы как этот код с 3 условиями ускорить...
> Возможно, при жесткой аппаратной реализации бинарный вариант и дает такую скорость.
Согласен, аппаратная реализация думаю хорошо ускоряет.
> Всяко проще чем пирамида :) примерно так:
УдалитьНет, это-то понятно, я про другие сложности. Во-первых, больший объем памяти, требуемой для такой реализации. Во вторых, для получения максимального сжатия неплохо бы задать начальную статистическую модель, исходя из характера обрабатываемых данных. В таком варианте сложнее задать начальную модель.
> Я честно не представляю как это сделать эффективно для не бинарной модели...
Насчет эффективности по скорости не знаю, но просто поделив все частоты, например, на два и обеспечив их монотонное возрастание, если используются частоты с накоплением.
Кстати, слишком частая адаптация ухудшает сжатие, так как большое сжатие возможно лишь, когда какой-то символ встречается существенно чаще других, а понять это на короткой серии данных невозможно. Не знаю, как там для окна в 20 битов получается улучшить сжатие и на каких данных. Возможно, тут помогает древовидная структура кодека и 20 бит окна для младших бит на самом деле гораздо длиннее оказываются, так как срабатывают далеко не каждый бит входящего потока.
> Алгоритм то вроде я тот же реализовал M-Coder
Вроде H.264 предлагает для использования три варианта кодека, и арифметическое кодирование - самое затратное. Возможно, на высоких профайлах они менее оптимальный, но зато более эффективный вариант сжатия используют вместо арифметического.
> Во-первых, больший объем памяти
УдалитьЭто да.
> Насчет эффективности по скорости не знаю
Для динамического размера окна нужно деление, а оно дорогое и сложно реализуемое в железе. Фиксированное окно позволяет избавиться от деления предварительно рассчитанным конечным автоматом или используя для окна степень 2-ки и заменив деление сдвигом.
> как там для окна в 20 битов получается улучшить сжатие
Так как используется некая аппроксимация, то поднимание от минимальной частоты (0.01875) до максимальной (0.98125) занимает 77 шагов, а не 20, при этом от 0.5 до 0.98125 подъем занимает всего 14 шагов. Лучше это или хуже чем полноценное окно я не знаю и почему именно так. Судя по объему научных работ вокруг этого, там не одну кандидатскую защитили :)
> Возможно, тут помогает древовидная структура кодека
Думаю да.