Для работы на не слишком распространенной платформе ищу очень быстрый и простой алгоритм сжатия, на языке С (не С++).
Конкретный формат не важен, можно на основе zip, просто lzw, или вообще какой-то другой. Совместимость ни с чем не требуется. Надо сжать данные и разжать обратно. Никакие другие функции не нужны.
Быстродействие — ключевой параметр. Скорость обработки требуется порядка 20-40 МБайт в секунду на среднем сервере, до 100 МБ/с на мощном.
Одна из найденных методом тыка библиотек показала результат 12 МБ/с, что слишком мало, поэтому ищу побыстрее...
Здравствуйте, _RL_, Вы писали:
_RL>Для работы на не слишком распространенной платформе ищу очень быстрый и простой алгоритм сжатия, на языке С (не С++). _RL>Конкретный формат не важен, можно на основе zip, просто lzw, или вообще какой-то другой. Совместимость ни с чем не требуется. Надо сжать данные и разжать обратно. Никакие другие функции не нужны.
_RL>Быстродействие — ключевой параметр. Скорость обработки требуется порядка 20-40 МБайт в секунду на среднем сервере, до 100 МБ/с на мощном. _RL>Одна из найденных методом тыка библиотек показала результат 12 МБ/с, что слишком мало, поэтому ищу побыстрее...
_RL>Кто-нибудь видел такие библиотеки/алгоритмы?
попробуй PPM алгоритмы и лучше задай это вопрос на compression.ru
Sic luceat lux!
Re: Ищу простой быстрый алгоритм сжатия на С (не ++)
Здравствуйте, _RL_, Вы писали:
_RL>Для работы на не слишком распространенной платформе ищу очень быстрый и простой алгоритм сжатия, на языке С (не С++). _RL>Конкретный формат не важен, можно на основе zip, просто lzw, или вообще какой-то другой. Совместимость ни с чем не требуется. Надо сжать данные и разжать обратно. Никакие другие функции не нужны.
_RL>Быстродействие — ключевой параметр. Скорость обработки требуется порядка 20-40 МБайт в секунду на среднем сервере, до 100 МБ/с на мощном. _RL>Одна из найденных методом тыка библиотек показала результат 12 МБ/с, что слишком мало, поэтому ищу побыстрее...
_RL>Кто-нибудь видел такие библиотеки/алгоритмы?
Здравствуйте, _RL_, Вы писали:
_RL>Для работы на не слишком распространенной платформе ищу очень быстрый и простой алгоритм сжатия, на языке С (не С++). _RL>Конкретный формат не важен, можно на основе zip, просто lzw, или вообще какой-то другой. Совместимость ни с чем не требуется. Надо сжать данные и разжать обратно. Никакие другие функции не нужны.
_RL>Быстродействие — ключевой параметр. Скорость обработки требуется порядка 20-40 МБайт в секунду на среднем сервере, до 100 МБ/с на мощном. _RL>Одна из найденных методом тыка библиотек показала результат 12 МБ/с, что слишком мало, поэтому ищу побыстрее...
_RL>Кто-нибудь видел такие библиотеки/алгоритмы?
А чем zlib не подходит? На практике, он даже на слабеньких КПК быстро сжимает пакеты.
Re: Ищу простой быстрый алгоритм сжатия на С (не ++)
Здравствуйте, _RL_, Вы писали:
_RL>Для работы на не слишком распространенной платформе ищу очень быстрый и простой алгоритм сжатия, на языке С (не С++). _RL>Конкретный формат не важен, можно на основе zip, просто lzw, или вообще какой-то другой. Совместимость ни с чем не требуется. Надо сжать данные и разжать обратно. Никакие другие функции не нужны.
_RL>Быстродействие — ключевой параметр. Скорость обработки требуется порядка 20-40 МБайт в секунду на среднем сервере, до 100 МБ/с на мощном. _RL>Одна из найденных методом тыка библиотек показала результат 12 МБ/с, что слишком мало, поэтому ищу побыстрее...
_RL>Кто-нибудь видел такие библиотеки/алгоритмы?
Здравствуйте, bobik1, Вы писали: B>А чем zlib не подходит? На практике, он даже на слабеньких КПК быстро сжимает пакеты.
Как раз текущая реализация основана на zlib.
Его исходники уже давно и успешно использовались в других проектах. Но для одного конкретного проекта понадобилось встроить сжатие данных. Взял тот код zlib, что уже был — результат по скорости оказался неудовлетворительным.
Re[3]: Ищу простой быстрый алгоритм сжатия на С (не ++)
_RL>Как раз текущая реализация основана на zlib. _RL>Его исходники уже давно и успешно использовались в других проектах. Но для одного конкретного проекта понадобилось встроить сжатие данных. Взял тот код zlib, что уже был — результат по скорости оказался неудовлетворительным.
Для этого существуют системные требования. Пишите в документации, что машина с такой то конфигурацией поддерживает столько то одновременных подключений.
Я например сколько не экспериментировал, так и не добился существенного прироста в производительности и остановился на старом проверенном zlib, оптимальном по показателям скорость — уровень сжатия.
Re[4]: Ищу простой быстрый алгоритм сжатия на С (не ++)
Здравствуйте, bobik1, Вы писали: B>Для этого существуют системные требования. Пишите в документации, что машина с такой то конфигурацией поддерживает столько то одновременных подключений.
К сожалению, в данном случае это не пройдет. Есть два варианта — или скорость работы на текущих серверах удовлетворительна, или нет.
На данный момент ни zlib (около 12 МБ/сек), ни только что протестированный мной quickLZ (порядок тот же, около 12-14 МБ/сек) не удовлетворяют.
Будем искать дальше...
B>Я например сколько не экспериментировал, так и не добился существенного прироста в производительности и остановился на старом проверенном zlib, оптимальном по показателям скорость — уровень сжатия.
В моем случае степень сжатия не так важна — данные текстово-цифровые и весьма разреженные. Но вот по скорости достойных вариантов пока не нашел, смотрю по разным ссылкам.
Re: Ищу простой быстрый алгоритм сжатия на С (не ++)
а ты как тестируешь? что пакуешь?
конкретные циферки от этого сильно зависят.
я тут проверил архиватор AIN (написан на C/ASM).
дал ему файл с текстом "quick brown fox jumps over a lazy dog" размером один гигабайд пожевать.
он выплюнул 4-метровый архив через 40 сек. (25 MB/s).
Re[5]: Ищу простой быстрый алгоритм сжатия на С (не ++)
_RL>К сожалению, в данном случае это не пройдет. Есть два варианта — или скорость работы на текущих серверах удовлетворительна, или нет. _RL>На данный момент ни zlib (около 12 МБ/сек), ни только что протестированный мной quickLZ (порядок тот же, около 12-14 МБ/сек) не удовлетворяют. _RL>Будем искать дальше...
_RL>В моем случае степень сжатия не так важна — данные текстово-цифровые и весьма разреженные. Но вот по скорости достойных вариантов пока не нашел, смотрю по разным ссылкам.
Для какого уровня сжатия вы тестировали zlib? скорость сжатия меняется в разы при изменении уровня сжатия.
Re[5]: Ищу простой быстрый алгоритм сжатия на С (не ++)
_RL>В моем случае степень сжатия не так важна — данные текстово-цифровые и весьма разреженные. Но вот по скорости достойных вариантов пока не нашел, смотрю по разным ссылкам.
Возможно вам будет лучше написать кастомный алгоритм сжатия именно для ваших данных, он может оказаться в разы быстрее и лучше сжимать чем алгоритмы общего назначения.
Re: Ищу простой быстрый алгоритм сжатия на С (не ++)
Здравствуйте, _RL_, Вы писали:
_RL>Кто-нибудь видел такие библиотеки/алгоритмы?
все же рекомендую вам осилить zlib еще разок
покрутите настройки (уровни сжатия), по дефолту там уровень 6 вроде, максимальный уровень 9
аккуратно свой код проверьте, чтобы убедиться, что именно zlib тормозит, а не ваша обвязка
если он не подходит, то вам уже надо более четко сформулировать какого формата данные и под этот формат искать архиватор
для видео — это кодеки, для музыки — другие кодеки, для текстов — это конкретные архиваторы
еще можете архиватор Булата поюзать http://www.freearc.org/ (все-таки реклама реально зомбирует, булат, почисти подпись )
Re: Ищу простой быстрый алгоритм сжатия на С (не ++)
Здравствуйте, uzhas, Вы писали:
U>все же рекомендую вам осилить zlib еще разок U>покрутите настройки (уровни сжатия), по дефолту там уровень 6 вроде, максимальный уровень 9 U>аккуратно свой код проверьте, чтобы убедиться, что именно zlib тормозит, а не ваша обвязка U>еще можете архиватор Булата поюзать http://www.freearc.org/ (все-таки реклама реально зомбирует, булат, почисти подпись )
Zlib крутил по всякому, ставил все варианты, даже 1 уровень... Допускаю, что он был собран изначально не слишком качественно, это у нас другой коллега собирал, еще лет 5 назад. Он там подкручивал чего-то, адаптировал...
U>если он не подходит, то вам уже надо более четко сформулировать какого формата данные и под этот формат искать архиватор U>для видео — это кодеки, для музыки — другие кодеки, для текстов — это конкретные архиваторы
Данные — из базы данных, какие обычно там данные и лежат — строки, числа, даты и т.п.
Бывают сильно разреженные таблицы, бывают плотные. Как обычно.
Re[2]: Ищу простой быстрый алгоритм сжатия на С (не ++)
Какая реализация! Столько указателей и magic numbers. Чую уязвимости есть.
И все таки я за zlib. Проверенное временем решение, правда и там по безопасности критические вещи всплывали.
Make flame.politics Great Again!
Re[2]: Ищу простой быстрый алгоритм сжатия на С (не ++)
Здравствуйте, _RL_, Вы писали:
_RL>Здравствуйте, bobik1, Вы писали: B>>Для этого существуют системные требования. Пишите в документации, что машина с такой то конфигурацией поддерживает столько то одновременных подключений.
_RL>К сожалению, в данном случае это не пройдет. Есть два варианта — или скорость работы на текущих серверах удовлетворительна, или нет. _RL>На данный момент ни zlib (около 12 МБ/сек), ни только что протестированный мной quickLZ (порядок тот же, около 12-14 МБ/сек) не удовлетворяют. _RL>Будем искать дальше...
Что-то маленькая скорость получается. Может проблема уже не в копрессоре, а например в неправильном выделении памяти через стандартный heap?
Re[6]: Ищу простой быстрый алгоритм сжатия на С (не ++)
Здравствуйте, Kluev, Вы писали: K>Что-то маленькая скорость получается. Может проблема уже не в копрессоре, а например в неправильном выделении памяти через стандартный heap?
Чорд. Неправильная методика тестирования при параллельном выполнении была
Текущее положение такое:
MiniLZO ~40 мбайт/сек
QuickLZ ~55 мбайт/сек.
Соответственно, пока остановлюсь на последнем варианте. С нового года попробую потестировать другие.
Спасибо всем!!!
Re[2]: Ищу простой быстрый алгоритм сжатия на С (не ++)
Здравствуйте, Kerbadun, Вы писали:
K>>http://www.oberhumer.com/opensource/lzo/
K>Если не ошибаюсь, на современных компьютерах оно работает быстрее, чем memcpy.
Несколько сомнительно.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re[4]: Ищу простой быстрый алгоритм сжатия на С (не ++)
Не уверен на 100% насчет именно этого алгоритма, но данные были получены экспериментально и довольно легко объяснимы: общее количество памяти, которое нужно прочитать/записать у memcpy больше, а процессор работает очень быстро и не вносит большого вклада, то есть все упирается в скорость памяти. Закономерно получается быстрее.
Я конечно, тоже сначала офигел, когда увидел цифры ("Э-э, погодите, memcpy медленнее?! Но оно же просто копирует!").
Когда он умрет, его мозг заспиртуют в стакане
Re[5]: Ищу простой быстрый алгоритм сжатия на С (не ++)
Здравствуйте, Kerbadun, Вы писали:
K>>>>http://www.oberhumer.com/opensource/lzo/ K>>>Если не ошибаюсь, на современных компьютерах оно работает быстрее, чем memcpy. CC>>Несколько сомнительно.
K>Не уверен на 100% насчет именно этого алгоритма, но данные были получены экспериментально и довольно легко объяснимы: общее количество памяти, которое нужно прочитать/записать у memcpy больше
Считать как минимум столько же.
Записать да, меньше.
Но обработка она всё равно не настолько бесплатная.
K>Я конечно, тоже сначала офигел, когда увидел цифры ("Э-э, погодите, memcpy медленнее?! Но оно же просто копирует!").
У них на сайте:
Here are some original timings done on an Intel Pentium 133. Multiply by a constant factor for modern machines.
Здравствуйте, Kerbadun, Вы писали:
K>>>>http://www.oberhumer.com/opensource/lzo/ K>>>Если не ошибаюсь, на современных компьютерах оно работает быстрее, чем memcpy. CC>>Несколько сомнительно.
K>Не уверен на 100% насчет именно этого алгоритма, но данные были получены экспериментально и довольно легко объяснимы: общее количество памяти, которое нужно прочитать/записать у memcpy больше, а процессор работает очень быстро и не вносит большого вклада, то есть все упирается в скорость памяти. Закономерно получается быстрее.
Вики про него говорит:
On modern architectures, decompression is very fast; in non-trivial cases able to exceed the speed of a straight memory-to-memory copy due to the reduced memory-reads.
Насчёт существенного буста скорости на минимизации чтения для non-trivial cases для LZ несколько сомнительно.
Похоже больше на то, что сжатый текст весь сидит в кэше, cache miss при распаковке не происходит и потому доставание из словаря дёшево на чтении.
Надо тест.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re: Ищу простой быстрый алгоритм сжатия на С (не ++)
)
