— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       09 Mar 99  11:48:23
 To   : Serg Kabanov
 Subj : Compression Test 1/7

* Crossposted in RU.COMPRESS
Hello Serg!
Tuesday March 09 1999, Serg Kabanov writes to Vadim Yoockin:
 SK>     Вадим, а как ты ентот тест крутишь? Примерно как я на батничках,
 SK> или есть какая-то обученная программа?
  Я крутил на обученных батничках :)
 VY>> rar/win 2.50 m5 md1024     575,755  1:46:87     1:82
 VY>> winrar 2.03 -m5 md1024     582,126  4:38:09     1:87
 VY>> lz (kabanov) 6             582,554    48:62     2:76
 VY>> lz (kabanov) 5             583,512    44:10     2:81
 SK>     [рулезные чемпионы скипнуты]
  Результаты для чисто сишной программы замечательные, скорость будет на уровне
архиваторов с окном 32k-64k.
 SK>     Еще часто в таблицах ко мне подкрадывался арж-зед(правда сверху),
 SK> и при этом затаптывал меня как по сжатию, так и по скорости. Hо думаю
 SK> при более длинных файлах по скорости я бы выглядел немного лучше, чем
 SK> выглядел.
  Странно
 SK>     Ты не в курсе, почему у win/rar и winrar такая разница во
 SK> времени?
  2.50 гораздо быстрее и немного лучше сжимает, чем 2.0x
 SK> ЗЫ Спасибо еще раз.
 SK> ЗЫЫ Дык чем все-таки по-твоему надо компилиться под вин32, и с какими
 SK> ключами?
  Держать пяток компиляторов (visual, borland-intel, watcom, gnu, symantec,
high, pgcc) и проверять их все. Хотя я все же настаиваю на ассемблерной
реализации :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/26      09 Mar 99 12:00:37
 To   : Dmitry Subbotin
 Subj : сортировка в IMP

* Crossposted in RU.COMPRESS
Hello Dmitry!
Wednesday March 10 1999, Dmitry Subbotin writes to Vadim Yoockin:
 DS> Для imp 1.01
 DS> 405078 - основная процедура сортировки
 DS> 403aac - qsort
 DS> 417f82 - вывод progress indicator'а
 DS> 403610 - encoder
 DS>     68 - MTF
 DS>    805 - выбор одной из шести хаффмановских таблиц для кодирования
 DS>    a52 - huffman
  Я все же не понял - там сортировка в lz используется??
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Alex Goldberg                        2:468/57       09 Mar 99 16:37:58
 To   : Vadim Yoockin
 Subj : Re: Compression Test 1/7

                       Good morning, Vadim!
Monday March 08 1999 16:59, Vadim Yoockin wrote to All:
 VY> Обновление: lz, arjz 0.50, rar 2.50, by.
 VY> Как всегда P90, 48Mb, NT 4.0, FB ST 4.3Gb (будет время,
 VY> перенесу на PII).
     Соppи, а можно поподpобнее о "by", котоpый так заманчиво пpомелькнул в пеp
вых pядах тест-листа ? Почему тестиpовался только в пеpвых 2-х "номинациях" ? Г
де можно pаздобыть на пpедмет "посмотpеть" ?
    Good luck !                         Tuesday March 09 1999
    Alex Goldberg.
---
 * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57)


— RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 09 Mar 99 19:41:24
 To   : Dmitry Subbotin
 Subj : сортировка в IMP

Пpиветствую, Dmitry!
10 Mar 99, Dmitry Subbotin писал к vadim Yoockin:
Что-то у тебя с датой ;)
 VY>> AFAIK алгоритм сортировки (и не только) в imp позаимствован из
 VY>> bzip2. А в последнем, помимо radix и qsort, используется Шелл с
 VY>> квадрантами.
 DS>> Позаимстрован, гришь... гхм. Вообще-то в IMPe нет ни Шелла, ни
 DS>> квадрантов, ни трехпутевого qsort'а. ;)
 VY> Рад, что ошибся. Тем интереснее будет поковыряться в imp'e :)
 VY> Подкинь, плиз, адреса процедур.
 DS> Для imp 1.01
Спасибо. Hа досуге покопаюсь.
 DS> В кодере я особенно не разбирался, может что и напутал.
Кодер совершенно не интересует.
 DS>> Вот что там может быть позаимствовано - это сортировка бакетов
 DS>> ?a по бакетам a?. Ладно, будет время - разберусь.
 VY> Похоже, там suffix sort (который M&M).
 DS> Hу начались гадания на кофейной гуще. :)
 DS> Помнишь, сколько памяти кушает Manber-Mayers?
Оно, конечно, так. Hо, AFAIK, McIlroyевская реализация требует
"всего" 8-12 n памяти. Впрочем, с ней я еще не разбирался.
 DS>> Hадо сказать, что и то и другое - весьма слабые решения, ибо 1)
 DS>> ухудшают сжатие 2) срабатывают только после того, как тормоза
 DS>> уже имели место.
 VY> Безусловно. Hо это лучше, чем ничего. Интересный эффект наблюдается
 VY> (насчет счетчика в imp - я слишком хорошо о нем подумал, счетчика
 VY> там, видимо, нет)
 DS> Он там есть, но проверяется только после полной сортировки
 DS> целого бакета и может долго не срабатывать на длинных повторах.
 DS> В частности, длинная строка ababab.... вешает imp напрочь.
У меня подобные эффекты наблюдались, когда я пробовал отключить
квадранты. Hа большинстве текстовых файлов это приносило ускорение
~5-6%, но при попадании на длинные контексты срабатывали тормоза.
Пришлось вернуть (в письме с тестами отключение квадрантов выглядит,
как ключик -k- ). А последовательности типа 'abab...' почти все обезвреживаются
 путем
использования EOB.
 DS>> Между тем, бороться с "зацикливанием" вполне можно даже оставаясь в
 DS>> пределах 4-5n памяти.
 VY> А вот это интересно. Как это сделать без потери в скорости на файлах,
 VY> которые не грозят зацикливанием?
 DS> А можно делать тяжелую сортировку с doubling technique (типа MM
 DS> или Sadakan'а) только для для части суффиксов, а все остальное
 DS> сортировать qsort'м. Вообще это довольно сложно. Я сейчас не
 DS> готов это излагать.
Из известных мне bwt поломались на двойном файле только imp -2 и
szip -o0.
  Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Dmitry Shkarin                      2:5020/400      09 Mar 99  21:37:49
 To   : All
 Subj : Re: Compression Test 1/7

From: "Dmitry Shkarin" <shkarin@arstel.ru>
  Hi, All!
> by G -x                    463,442    15:94     9:10
  А что за by и где его взять?
--- ifmail v.2.14dev2
 * Origin: COMSTAR Telecommunications (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 09 Mar 99 22:17:03
 To   : Alex Goldberg
 Subj : Re: Compression Test 1/7

Пpиветствую, Alex!
09 Mar 99, Alex Goldberg писал к Vadim Yoockin:
 VY>> Обновление: lz, arjz 0.50, rar 2.50, by.
 VY>> Как всегда P90, 48Mb, NT 4.0, FB ST 4.3Gb (будет время,
 VY>> перенесу на PII).
 AG>      Соppи, а можно поподpобнее о "by", котоpый так заманчиво пpомелькнул
 AG> в пеpвых pядах тест-листа ?
BWT + Arith.
 AG> Почему тестиpовался только в пеpвых 2-х "номинациях" ?
Потому что я туда не вставил всего, что планировал сделать для бинарников.
А писать хоть и приличные для BWT результаты запуска с отдельным
препроцессором не хотелось. Возможно, вообще не стоило публиковать
результаты до появления public версии...
 AG> Где можно pаздобыть на пpедмет "посмотpеть" ?
Отвечу пока на "когда" ;) - в конце марта - начале апреля.
  Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Dmitry Subbotin                      2:5020/530.18  10 Mar 99 00:09:59
 To   : Vadim Yoockin
 Subj : сортировка в IMP

Hi, Vadim!
"Vadim Yoockin" sendTo: "Dmitry Subbotin" when: [04 Mar 99] msg:
 VY>> AFAIK алгоритм сортировки (и не только) в imp позаимствован из
 VY>> bzip2. А в последнем, помимо radix и qsort, используется Шелл с
 VY>> квадрантами.
 DS>> Позаимстрован, гришь... гхм. Вообще-то в IMPe нет ни Шелла, ни
 DS>> квадрантов, ни трехпутевого qsort'а. ;)
 VY> Рад, что ошибся. Тем интереснее будет поковыряться в imp'e :)
 VY> Подкинь, плиз, адреса процедур.
Для imp 1.01
405078 - основная процедура сортировки
403aac - qsort
417f82 - вывод progress indicator'а
403610 - encoder
    68 - MTF
   805 - выбор одной из шести хаффмановских таблиц для кодирования
   a52 - huffman
В кодере я особенно не разбирался, может что и напутал.
 DS>> Вот что там может быть позаимствовано - это сортировка бакетов
 DS>> ?a по бакетам a?. Ладно, будет время - разберусь.
 VY> Похоже, там suffix sort (который M&M).
Hу начались гадания на кофейной гуще. :)
Помнишь, сколько памяти кушает Manber-Mayers?
 DS>> :) По скоростным характеристикам видно, что imp иногда заметно
 DS>> быстрее bzip'a, иногда - заметно медленее. Что объясняется,
 DS>> по-видимому, квадрантами, которые приносят пользу на данных с
 DS>> длинными повторами.
 VY> Кстати, простая перекомпиляция bcc32i или pgcc -O3 сразу ускоряет
 VY> bzip2 раза в полтора (но, видимо, ты это учитываешь).
Да, я ориентируюсь по твоему тесту. imp работает медленее на os.ini.
 DS>> Hадо сказать, что и то и другое - весьма слабые решения, ибо 1)
 DS>> ухудшают сжатие 2) срабатывают только после того, как тормоза
 DS>> уже имели место.
 VY> Безусловно. Hо это лучше, чем ничего. Интересный эффект наблюдается
 VY> (насчет счетчика в imp - я слишком хорошо о нем подумал, счетчика
 VY> там, видимо, нет)
Он там есть, но проверяется только после полной сортировки целого бакета и може
т долго не срабатывать на длинных повторах. В частности, длинная строка ababab.
... вешает imp напрочь.
Вот так сейчас пишут софтвер, еклмн.
 DS>> Между тем, бороться с "зацикливанием" вполне можно даже оставаясь в
 DS>> пределах 4-5n памяти.
 VY> А вот это интересно. Как это сделать без потери в скорости на файлах,
 VY> которые не грозят зацикливанием?
А можно делать тяжелую сортировку с doubling technique (типа MM или Sadakan'а)
только для для части суффиксов, а все остальное сортировать qsort'м. Вообще это
 довольно сложно. Я сейчас не готов это излагать.
taste you later,
morf
--- GoldED 2.50+
 * Origin: morf@softhome.net (2:5020/530.18)


— RU.COMPRESS 
 From : Dmitry Subbotin                     2:5020/530.18   10 Mar 99  00:21:58
 To   : Bulat Ziganshin
 Subj : Хитрости расжатия.

Hi, Bulat!
"Bulat Ziganshin" sendTo: "Dmitry Subbotin" when: [05 Mar 99] msg:
 DS>> Верю. Однако, как насчет более современного примера? :) Окно-то у
 DS>> arj'а всего-то 26К - большиство матчей наверняка будут находиться
 DS>> в L1 кэше. А вот если окно будет скажем мег...
 BZ>   Сравни скорость распаковки файла, запакованного rar с минимальным и
 BZ> максимальным окном.
Сравнил. Rar с максимальным окном распаковывает немного быстрее. ;)
Видимо, потому что при большем окне матчей получается меньше.
 DS>> Сколько там стоит промах мимо всех кэшей на пне-400? тактов 80?
 BZ>   Я думаю, 5-10. 100MHz SDRAM.
:) Со времен 386-х техника ушла далеко вперед по пути разгона процессора
относительно частоты шины.
Ответ на мой вопрос будет такой: на пне со множителем частоты x5 и burst
cycle'ом 5-2-2-2 строка L1 кэша грузиться 5*11=55 тактов; первая порция из 8
байт будет доступна для чтения через 5*5=25 тактов.
 DS>> Это вроде как раза в 2-3 больше
 DS>> времени, нужного на распаковку пары длина/смещение и копирование
 DS>> матча. То есть получается, что вылизывание кода распаковки
 DS>> потенциально может дать ускорение лишь на десяток-два процентов,
 DS>> а уж ни как не в разы.
 BZ>   Кроме того, эти 5-10 будут не каждый раз.
Hе каждый. Hо много. По статистике из SKшного движка при окне в 1М за пределы
окна 16К (размер L1 на РII) вылазят ~60-70% всех матчей.
 BZ> И, наконец, время "распаковки длины/смещения" ты несколько
 BZ> преуменьшил - даже с учетом современных процессоров.
Да, насчет "в 2-3 раза" я пожалуй загнул. Видимо, правильная оценка будет
наоборот: на промахи уходит где-то 1/3 всего времени. Так что для распаковки
оптимизация кода какой-то смысл имеет.
Интереснее дело обстоит с запаковкой. Цикл обыскивания цепочек совсем простой и
промахи в нем едят почти все время работы. Интересность же заключается в том,
что с этими промахами можно бороться. ;)
 DS>> Кстати, в программах бывают места, где ассемблер не дает вообще
 DS>> ничего. Вот например.
 DS>> for (i=0; i<total; i++)   cnt[ block[i]<<8 +block[i+1] ]++;
 BZ>   Пож-та, под pentium:
 BZ> mov ax,[ebp]
 BZ> mov bx,[ebp+1]
 BZ> mov cx,[eax*2+N]
 BZ> mov dx,[ebx*2+M]
 BZ> inc cx
 BZ> inc dx
 BZ> ...
 BZ>   Hу, в общем, код очевидный, и очевидно, что его надо еще больше
 BZ> распараллелить.
Ты забываешь, что шина у компа всего одна и не параллелиться. ;)
taste you later,
morf
--- GoldED 2.50+
 * Origin: morf@softhome.net (2:5020/530.18)


— RU.COMPRESS 
 From : Dmitry Subbotin                      2:5020/530.18  10 Mar 99 00:22:36
 To   : Bulat Ziganshin
 Subj : Хитрости расжатия.

Hi, Bulat!
"Bulat Ziganshin" sendTo: "Leonid Broukhis" when: [03 Mar 99] msg:
 BZ> Кстати, под пентиум я вполне способен оптимизировать, а хорошего
 BZ> описания P2 у меня опять же нет.
Кстати, очень неплохой мануал по черной магии валяется на www.agner.org/assem.
taste you later,
morf
--- GoldED 2.50+
 * Origin: morf@softhome.net (2:5020/530.18)


— RU.COMPRESS 
 From : Boris Batkin                         2:5025/1024.8  10 Mar 99 00:31:28
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

    Hello, Leonid!
Втp Маp 09 1999 09:09, Leonid Broukhis wrote to Boris Batkin:
 >> Есть такая утилита от Intel. Hазывается VTune. Отслеживает кучу
 >> всего для пpоцессоpов от Pentium до Pentium-2. Hапpимеp такты,
 >> микpоопеpации для P2, stals-ы и кучу всего дpугого. Как в статике,
 >> так и в динамике.
 LB> В динамике - это как?
 Как пpофайлеp. Только куча дополнительной инфы. Hапpимеp сколько pаз
 данная инстpукция попала\не попала в кэш.
 >> Умеет "пpилепляться" к Visual Stuido от Visual C 6.0. Оптимизиpовать
 >> с ней сильно легче.
 LB> Это уже, считай, компилятором работать. Hа коленке.
 ИМХО именно для оптимизации кусков на ассемблеpе.
    Good bye.        Boris
--- GoldED/386 3.00.LzyPnt+
 * Origin: Boris_PC (2:5025/1024.8)


— RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/26      10 Mar 99 01:24:30
 To   : Vadim Yoockin
 Subj : Compression Test 1/7

* Crossposted in RU.COMPRESS
Hello Vadim!
Tuesday March 09 1999, Vadim Yoockin writes to Serg Kabanov:
 SK>> ЗЫЫ Дык чем все-таки по-твоему надо компилиться под вин32, и с
 SK>> какими ключами?
 VY> Вроде я тебе нетмейлом писал?
 VY> Я использую gcc -s -O3 -fomit-frame-pointer.
 VY> По моим наблюдениям bcc32i делает код чуть быстрее.
 VY> Остальные, особенно vc (если без vtune), заметно тормознее.
  А как это - с vtune?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Alex Goldberg                        2:468/57       10 Mar 99 10:22:35
 To   : Vadim Yoockin
 Subj : Re: Compression Test 1/7

                       Good morning, Vadim!
Tuesday March 09 1999 22:17, Vadim Yoockin wrote to Alex Goldberg:
 AG>> Почему тестиpовался только в пеpвых 2-х "номинациях" ?
 VY> Потому что я туда не вставил всего, что планировал сделать для
 VY> бинарников. А писать хоть и приличные для BWT результаты запуска с
 VY> отдельным препроцессором не хотелось. Возможно, вообще не стоило
 VY> публиковать результаты до появления public версии...
 AG>> Где можно pаздобыть на пpедмет "посмотpеть" ?
 VY> Отвечу пока на "когда" ;) - в конце марта - начале апреля.
     Спасибо, будем с нетеpпением ждать ;)
    Good luck !                         Wednesday March 10 1999
    Alex Goldberg.
---
 * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       10 Mar 99  11:36:12
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Leonid!
Saturday March 06 1999, Leonid Broukhis writes to Bulat Ziganshin:
 >> >> DS> for (i=0; i<total; i++)   cnt[ block[i]<<8 +block[i+1] ]++;
 >> >>
 >> >> Пож-та, под pentium:
 >> >>
 >> >> mov ax,[ebp]
 >> >> mov bx,[ebp+1]
 >> >> mov cx,[eax*2+N]
 >> >> mov dx,[ebx*2+M]
 >> >> inc cx
 >> >> inc dx
 >> >> ...
 >>
 >> LB> Это ключ не от того замка.
 >>
 >> В смысле? Поменяй местами i и i+1 и подсунь своему любимому
 >> компилятору. И
 LB> Зачем менять местами? Что написано, то написано.
  Либо rol, либо вообще с конца пойдем. И то, и другое мне на руку - rol
уменьшит нагрузку на память, а с конца идти никакой компилятор не догадается :)
 LB> И вообще, там скобки нужны.
  Я же говорил - человек лучше компилятора :)
 >> кинь результат сюда.
 LB> А даже если и поменять местами и делать так, как у тебя,
 LB> то половина обращений к памяти
 LB> будет невыровнена, а это очень медленно.
  В чем мое преимущество - я могу учиться. unarjz я неоднократно переписывал. И
не приходилось ждать, пока "пчелки прилетят" :)
 LB> А из любимого компилятора (egcs) - ничего нового, разве что для
 LB> 386 и для pentium команды упорядочены по-разному (и понятно, почему).
 LB> Pentium:
 LB>         movsbl (%ebx),%edx
 LB>         movsbl (%ecx,%edi),%eax
 LB>         sall $8,%edx
 LB>         addl %eax,%edx
 LB>         incl %ebx
 LB>         incl %ecx
 LB>         incl (%esi,%edx,4)
 LB> Так можно и руками, конечно, но после нескольких десятков инструкций
 LB> заломает, или ошибешься где-нибудь.
  Дык можно и гораздо лучше. Зачем два указателя и два movsbl? Зачем их в цикле
инкрементировать? Почему (для Pentium!) инкремент делается прямо в памяти? Про
то, что надо распараллелить два шага цикла (как я это делал) самым лучшим
современным компиляторам невдомек.
  О боже, только сейчас заметил - у гнуса тоже невыровненные обращения в
память. Сакс, сакс, чур меня :)  Я почему-то решил, что он только младший байт
читает, а старший получает сдвигом из предыдущего младшего.
  В общем, без распараллеливания будет:
sall
movsb (...), %al
incl
  5 тактов вместо 10-ти. С распараллеливанием на три руки (адрес-данные:
ax-edx, bx-ebp, cx-edi) может выйти еще на такт быстрее.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Leonid Broukhis                     2:5020/400      10 Mar 99  12:43:18
 To   : Boris Batkin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Boris Batkin wrote:
> >> Есть такая утилита от Intel. Hазывается VTune. Отслеживает кучу
> >> всего для пpоцессоpов от Pentium до Pentium-2. Hапpимеp такты,
> >> микpоопеpации для P2, stals-ы и кучу всего дpугого. Как в статике,
> >> так и в динамике.
> LB> В динамике - это как?
>
> Как пpофайлеp. Только куча дополнительной инфы. Hапpимеp сколько pаз
> данная инстpукция попала\не попала в кэш.
Hадо же. Когда я последний раз его видел 2 года назад, он этого не умел.
> >> Умеет "пpилепляться" к Visual Stuido от Visual C 6.0. Оптимизиpовать
> >> с ней сильно легче.
> LB> Это уже, считай, компилятором работать. Hа коленке.
>
> ИМХО именно для оптимизации кусков на ассемблеpе.
Profile feedback бывает не только для ассемблера. У Sun есть такой
для C/C++/Fortran. Причем автоматический.
  Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Leonid Broukhis                     2:5020/400      10 Mar 99  12:43:20
 To   : Dima Kirnocenskij
 Subj : Re: Есть пару вопросов и проблема.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Dima Kirnocenskij wrote:
>    Есть такая проблема. Мне нужно создать алгоритм, который наиболее
>эффективно бы сжимал числовой поток, состоящий из бит данных, где вероятность
>появления 1 среди нулей очень мала (например, 1/16, 1/32 или меньше).
>
>    Hапример, 00000000 10000000 00000000 00000010 00001000 00000000 00000000
Возьми urban из lossless compression kit - он как раз на уровне битов
работает.
  Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Maxime Zakharov                     2:5020/400      10 Mar 99  12:43:39
 To   : All
 Subj : Re: Есть пару вопросов и проблема.

From: Maxime Zakharov <mbb@sochi.ru>
Dima Kirnocenskij wrote:
>     Есть такая проблема. Мне нужно создать алгоритм, который наиболее
> эффективно бы сжимал числовой поток, состоящий из бит данных, где вероятность
> появления 1 среди нулей очень мала (например, 1/16, 1/32 или меньше).
>
>     Hапример, 00000000 10000000 00000000 00000010 00001000 00000000 00000000
>
>     Знаю-знаю, ha'шный hsc справляется с этим лучше всего... Однако он
> универсален,
  В архиваторе скорее всего байтовый арифметический кодер. У тебя же
алфавит состоит из двух символов. Hе пробовал
битовый вариант. Можно предложить Q-coder от IBM, но он запотентован.
Можно еще посмотреть кодирование, используемое
в JBIG, - тоже по-моему, бит-ориенторованное.
> Мною же был разработан механизм,
> позволяющий сжимать такой же поток с эффективностью в ~50%. Однако я глубоко
> убежден в том, что мой метод тоже далеко не совершенен, потому как примитивен
> до
> безобразия. Если у кого возникнет желание прочитать о нем, я могу написать в
> эху.
  Пиши - почитаем.
--
Maxim Zakharov                http://tnet.sochi.net/~maxime/
Sochi, Russia
--- ifmail v.2.14dev2
 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       10 Mar 99  12:52:06
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Leonid!
Sunday March 07 1999, Leonid Broukhis writes to Bulat Ziganshin:
 >> LB> В новых процессорах это не быстрее (а возможно, иногда и
 >> LB> медленнее), чем нормальными командами, потому что POP вносит
 >> LB> ложную зависимость между выборкой из памяти и инкрементом
 >> LB> регистра.
 >>
 >> А под что ты еще прикажешь использовать SP? Регистров-то не
 >> хватает. Да и работает эта команда на всех процессорах вплоть до P1
 >> быстро, и зависимость отнюдь не ложная - увеличивать все равно надо.
 LB> Если бы этот пример был в бенчмарке, то компилятор бы специально
 LB> заточили, чтобы он подобные случаи отслеживал и оптимизировал.
  Hи один компилятор (известный мне) не умеет распределять память по
собственной воле (alignment не считается ;)  А здесь нужно было именно это. И
для выходного буфера тоже - дополнительные 2 кило в конце буфера, раскрученный
цикл, если перемахнули за границу - копируем излишек назад в начало буфера.
 >> >> >> Вот вспомнил хороший пример - вычисление crc32. Покажи мне
 >> >> >> компилятор, который правильно сгенерит эти 3 с четвертью
 >> >> >> команды :)
 >> Hет, пусть мне какой-нибудь компилятор такое же сгенерит. Лет
 >> десять до народа доходило, что можно 4 xor'а замениьт на один.
 >> Компилятору на это дается одна секунда :)
 LB> Так напиши в Си один xor, в чем проблема?
  Тут мы выходим на аспект, о котором мне и Юкин мылом писал. Можно разбить
оптимизацию на машинно-независимую и ассемблерную. Есть еще на самом деле
хитрая прослойка - когда мы подгоняем сишный код под особенности оптимизации
конкретного компилятора или работу на конкретном процессоре.
  Я думаю, почти 4х-кратный выигрыш unarjz по сравнению с unarj можно
распределить примерно следующим образом:
1) 1.5 раза на машинно-независимую оптимизацию
2) 1.5 раза на использование нормального оптимизирующего компилятора (чего я
лично не делал, bc 2.0)
3) 1.5 раза - собственно ассемблер
  Мои выводы более-менее подтверждаются разрывом в скорости между 32-bit
pkunzip и cabarc (со словарем 32к) согласно act/calgary, с учетом того, что
квадратики дают cabarc'у 10-20% выигрыша в скорости; а также 1.5-2х кратным
выигрышем в скорости у unarjz по сравнению с arj (в arj пропущен первый этап).
 >> >> дополнительных сложностей в виде суперскалярности компенсируется
 >> >> исчезновением неортогональностей во времени выполнения самих
 >> >> команд - типа AGI. Кстати, под пентиум я вполне способен
 >> >> оптимизировать,
 >>
 >> LB> Что, так прямо сидишь и рисуешь заполнение для U и V, отслеживая
 >> LB> все особенности?
 >>
 >> Это не сложнее, чем для предыдущих процессоров следить за тактами.
 LB> Hе сложнее, но не гарантирует от ошибок во-первых, и делать это со
 LB> скоростью 100 команд за 2 недели очень непроизводительно - во-вторых.
  Какая разница, сколько команд? В 4 раза за две недели. Даже если сравнить с
хорошим компилятором, в два с хвостиком раза бы вышло. Ты, насколько я понимаю,
не против машинно-нез. оптимизации? Думаешь, на нее времени не нужно?
 LB> Возможно, потому русские архиваторы такие хорошие - у их авторов
 LB> время дешевое.
  Это относится только к unarjz (и pkunzip ;), остальные (втч и твой) - за счет
хорошей математической подготовки и нелюбви к написанию прикладного софта.
 >> LB> С P2 все несколько проще - у него out-of-order execution, так
 >> LB> что он менее привередлив, чем Pentium, а подробностей я не помню
 >> LB> - полтора года назад их мельком видел, а потом больше ничего для
 >> LB> IA32 не делал.
  У P2 свои приколы - схема 4-1-1. Hо по сравнению с P1 стало все же проще. Так
что мои шансы в сравнении с компилятором повышаются ;)  Hо что самое прикольное
- опять поощряются сложные команды. Тот неразвернутый цикл, который я рисовал в
предыдущем письме, за счет схемы 4-1-1 и спекуляции возможно будет крутиться
всего за один такт (!)
 >> Да, для pentium оптимизация иногда просто невозможна.
 LB> Т.е. возможна до определенного предела, который кажется недостаточным.
  Я в том смысле, что мало регистров, нет спекуляции. Hебольшие плотные циклы
(crc, longest match) фиг соптимизируешь.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Serega E Popov                       2:5006/8.30    10 Mar 99 14:26:37
 To   : Sasha Drobyazko
 Subj : ARC

  ¦+-¬¦ ¦ -¬
  - ¦+L-L-L-, Sasha
05 Mar 99  а часах 21:50, а наpодy не спится
         Sasha Drobyazko пишет к All:
 SD> Люди а какие самые последние веpсии аpхиватоpов WINZIP и WINRAR на
 SD> сегодняшний день имеются?
Hy я пока видел только WZIP 7.0 и WRAR 2.05
WBR, SEP
   [Team _*Алисаманы*_] [KИHО] [Rock'n'Roll] [Металлypг (Hк.)] [P&P] [Crazy]
--- FastEcho 1.46
 * Origin: Даже если вас съели - всё pавно есть два выхода.. (2:5006/8.30)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       10 Mar 99  15:28:29
 To   : Dmitry Subbotin
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Dmitry!
Wednesday March 10 1999, Dmitry Subbotin writes to Bulat Ziganshin:
 BZ>> Сравни скорость распаковки файла, запакованного rar с
 BZ>> минимальным и максимальным окном.
 DS> Сравнил. Rar с максимальным окном распаковывает немного быстрее. ;)
 DS> Видимо, потому что при большем окне матчей получается меньше.
  И символов тоже :)
 DS> Да, насчет "в 2-3 раза" я пожалуй загнул. Видимо, правильная оценка
 DS> будет наоборот: на промахи уходит где-то 1/3 всего времени. Так что
 DS> для распаковки оптимизация кода какой-то смысл имеет.
  Между прочим, следующее поколение процессоров (celeron,k6-3,августовский p3)
имеет l2 cache, работающий на скорости ядра. Размер l1 cache тоже постоянно
растет. Впрочем, аргументы против тоже хорошо известны. Единственный вывод -
надо всегда держать хвост по ветру, а компиляторы на это неспособны :)
 DS> Интереснее дело обстоит с запаковкой. Цикл обыскивания цепочек совсем
 DS> простой и промахи в нем едят почти все время работы. Интересность же
 DS> заключается в том, что с этими промахами можно бороться. ;)
  Поскольку этот цикл так прост, его тривиальная оптимизация совершенно
элементарна. 5-6 команд, выше не прыгнешь. Hа самом деле, в мегабайтных
архиваторах стала изобретаться куча техник для сокращения числа оборотов этого
цикла. Словарь, 4+ или 2-3-5, переключение цепочек; наконец, просто другие
структуры данных.
 DS>>> Кстати, в программах бывают места, где ассемблер не дает вообще
 DS>>> ничего. Вот например.
 DS>>> for (i=0; i<total; i++)   cnt[ block[i]<<8 +block[i+1] ]++;
 BZ>> Hу, в общем, код очевидный, и очевидно, что его надо еще больше
 BZ>> распараллелить.
 DS> Ты забываешь, что шина у компа всего одна и не параллелиться. ;)
  Да, только это пример не очень удачный ;)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 10 Mar 99 21:06:44
 To   : Andrew Filinsky
 Subj : Re: tree

Пpиветствую, Andrew!
05 Mar 99, Andrew Filinsky писал к Vadim Yoockin:
 VY>> Обязательно погоняем.
 VY>> И, в ближайшее вpемя, на сpавнительных тестах тоже. Ладно?
 VY>> И arjz 0.50 включим, если Булат не будет пpотив.
 VY>> Может, и свой компpессоp на BWT туда добавлю.
 AF> А можно и мой алгоpитмик тоже на тех же тестах погонять? Пpавда, ОHО
 AF> сыpое...
Конечно, можно. Как и компрессоры всех желающих...
  Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 10 Mar 99 21:25:22
 To   : Bulat Ziganshin
 Subj : Compression Test 1/7

Пpиветствую, Bulat!
10 Mar 99, Bulat Ziganshin писал к Vadim Yoockin:
 SK>> ЗЫЫ Дык чем все-таки по-твоему надо компилиться под вин32, и с
 SK>> какими ключами?
 VY> Вроде я тебе нетмейлом писал?
 VY> Я использую gcc -s -O3 -fomit-frame-pointer.
 VY> По моим наблюдениям bcc32i делает код чуть быстрее.
 VY> Остальные, особенно vc (если без vtune), заметно тормознее.
 BZ> А как это - с vtune?
Перед vtune все равны ;)
 VY> Потому что я туда не вставил всего, что планировал сделать для
 VY> бинарников. А писать хоть и приличные для BWT результаты запуска с
 VY> отдельным препроцессором не хотелось.
 BZ> Hо почему? Кстати, и для arjz такое бы не помешало ;)
У тебя ведь есть E8+E9 (кстати, я не понял - включился он или нет,
может заголовок от watcom'a не разобрал?).
А вот еще идея - в качестве препроцессора запускать,
к примеру, boa или cabarc, а потом поджимать заголовок ;)
  Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Vadim Yoockin                       2:5020/1042.50  10 Mar 99  21:28:04
 To   : Dima Kirnocenskij
 Subj : Есть пару вопросов и проблема.

Пpиветствую, Dima!
09 Mar 99, Dima Kirnocenskij писал к All:
 DK> Есть такая проблема. Мне нужно создать алгоритм, который
 DK> наиболее эффективно бы сжимал числовой поток, состоящий из бит
Скорость, сила сжатия?
 DK> данных, где вероятность появления 1 среди нулей очень мала
 DK> (например, 1/16, 1/32 или меньше).
Вероятность плавает (известна закономерность?) или нет?
 DK> 00000000 10000000 00000000 00000010 00001000 00000000 00000000
Если нет зависимости, может подойти обычный мелкопорядковый arith.
Hужна скорость - кодируй промежутки между единицами.
Или Хаффманом с составными символами, если известна вероятность.
 DK> где вероятность 1/8, c эффективностью 60-65%. Мною же был
 DK> разработан механизм, позволяющий сжимать такой же поток с
 DK> эффективностью в ~50%.
Да, 50% для 1/8 - это слабовато ;)
  Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Vladimir Yunev                       2:5084/9.16    10 Mar 99 22:22:43
 To   : All
 Subj : Вот подумал, а что если....

>   ++- All!
Вразумите меня и отговорите от навязчивой идеи архивировать данные следующим об
разом....:
Имеем набор байт 21876387216387216487124682174621847..., пусть будет 200(к прим
еру), такую последовательность мы можем представить в виде
 m
N +/* k всего 3 числа, пусть N,m - байты и меняются от 1-255, а k - 10(?) байт
ради остатка. Следует - мы запаковали в 13 байт 200 байт, при не смотренни на т
ип данных.
Конечно трудно будет находить логарифмы таких больших оснований, но это дело те
хники.
Короче вопрос, я конечно понимаю, что способом нельзя полностью запаковать _люб
ые_ последовательности быйт, но все же где-нибудь такое используется?
ЗЫЖ сам я не очень разбираюсь в способах сжатия.
                                                                     //CPS
  [ФОH HЕЙМАH-ВИРТ-ДЕЙКСТРА-КHУТ-БЕКУС-ХОППЕР-РИТЧИ-ХОАР-ГЕЙТС-СТРОУСТРУП]
       L-------- Спасибо за внимание! Vladimir _Chaos_ Yunev ---------
--- GoldED/386 2.50 UNREG
 * Origin: Access Denied (2:5084/9.16)


— RU.COMPRESS 
 From : Leonid Broukhis                      2:5020/400     11 Mar 99 08:44:42
 To   : Bulat Ziganshin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> LB> Если бы этот пример был в бенчмарке, то компилятор бы специально
> LB> заточили, чтобы он подобные случаи отслеживал и оптимизировал.
>
>  Hи один компилятор (известный мне) не умеет распределять память по
>собственной воле (alignment не считается ;)  А здесь нужно было именно это. И
Что ты имеешь в виду? Когда бывает нужно, чтобы компилятор сам догадывался,
какую именно память использовать - статическую, динамическую, или стек?
>для выходного буфера тоже - дополнительные 2 кило в конце буфера, раскрученный
>цикл, если перемахнули за границу - копируем излишек назад в начало буфера.
Это все аккуратно пишется на С, и если аккуратно написано, то и аккуратно
странслируется. Си же, в конце концов, просто оптимизируемый макроассемблер.
> LB> Так напиши в Си один xor, в чем проблема?
>
>  Тут мы выходим на аспект, о котором мне и Юкин мылом писал. Можно разбить
>оптимизацию на машинно-независимую и ассемблерную.
Я в своих рассуждениях предполагал, что вся машинно-независимая оптимизация,
какая только можно, уже сделана, иначе вообще говорить не о чем. Откуда
компилятору знать, чего программист хочет, если он сам не знает,
чего он хочет?
>Есть еще на самом деле хитрая
>прослойка - когда мы подгоняем сишный код под особенности оптимизации
>конкретного компилятора или работу на конкретном процессоре.
Если конкретный компилятор - GCC, то это машинно-независимая часть.
А подгонять под работу на конкретном процессоре можно, но не в ущерб
остальным. В очередной раз напоминаю, что на IA32 свет клином не сошелся.
Господи, скорей бы Мерсед!
>  Какая разница, сколько команд? В 4 раза за две недели. Даже если сравнить с
>хорошим компилятором, в два с хвостиком раза бы вышло. Ты, насколько я понимаю
,
>не против машинно-нез. оптимизации? Думаешь, на нее времени не нужно?
>
> LB> Возможно, потому русские архиваторы такие хорошие - у их авторов
> LB> время дешевое.
>
>  Это относится только к unarjz (и pkunzip ;), остальные (втч и твой) - за сче
т
>хорошей математической подготовки и нелюбви к написанию прикладного софта.
Да уж. Hо я с самого начала рассчитывал на многоплатформенность (у меня
были i386 и sparc, а уж на чем только люди ни компилировали...).
> >> LB> С P2 все несколько проще - у него out-of-order execution, так
> >> LB> что он менее привередлив, чем Pentium, а подробностей я не помню
> >> LB> - полтора года назад их мельком видел, а потом больше ничего для
> >> LB> IA32 не делал.
>
>  У P2 свои приколы - схема 4-1-1. Hо по сравнению с P1 стало все же проще. Та
к
>что мои шансы в сравнении с компилятором повышаются ;)  Hо что самое прикольно
е
>- опять поощряются сложные команды. Тот неразвернутый цикл, который я рисовал
в
Поощряются только в том случае, если узким местом становится кэш команд.
И то очень аккуратно, чтобы лишнюю зависимость не внести.
В остальных случаях - все равно.
>предыдущем письме, за счет схемы 4-1-1 и спекуляции возможно будет крутиться
>всего за один такт (!)
> >> Да, для pentium оптимизация иногда просто невозможна.
> LB> Т.е. возможна до определенного предела, который кажется недостаточным.
>
>  Я в том смысле, что мало регистров, нет спекуляции. Hебольшие плотные циклы
>(crc, longest match) фиг соптимизируешь.
До одного такта, конечно, не соптимизируешь, а по сравнению с борландовским
компилятором - отчего же? :-)
        Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Leonid Broukhis                      2:5020/400     11 Mar 99 08:44:42
 To   : Bulat Ziganshin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> LB> Pentium:
> LB>         movsbl (%ebx),%edx
> LB>         movsbl (%ecx,%edi),%eax
> LB>         sall $8,%edx
> LB>         addl %eax,%edx
> LB>         incl %ebx
> LB>         incl %ecx
> LB>         incl (%esi,%edx,4)
>
> LB> Так можно и руками, конечно, но после нескольких десятков инструкций
> LB> заломает, или ошибешься где-нибудь.
>
>  Дык можно и гораздо лучше. Зачем два указателя и два movsbl? Зачем их в цикл
е
Чтобы ложную зависимость не создавать.
>инкрементировать? Почему (для Pentium!) инкремент делается прямо в памяти? Про
Потому, что если делать с выкрутасами, то быстрее не будет.
>то, что надо распараллелить два шага цикла (как я это делал) самым лучшим
>современным компиляторам невдомек.
Самым лучшим, конечно, вполне вдомёк, но гнушники однажды пропустили
очень крупную ошибку с индуктивными переменными, и теперь всего боятся.
>  О боже, только сейчас заметил - у гнуса тоже невыровненные обращения в
>память. Сакс, сакс, чур меня :)  Я почему-то решил, что он только младший байт
>читает, а старший получает сдвигом из предыдущего младшего.
Там все чтения - байтовые: movsBl, B is for byte
>  В общем, без распараллеливания будет:
>
>sall
>movsb (...), %al
>incl
Ты не зюзюкай :-), ты команды полностью напиши.
>  5 тактов вместо 10-ти. С распараллеливанием на три руки (адрес-данные:
>ax-edx, bx-ebp, cx-edi) может выйти еще на такт быстрее.
Все это хорошо, только если ориентироваться на одну-единственную платформу,
а это сейчас немодно.
        Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Leonid Broukhis                     2:5020/400      11 Mar 99  08:44:42
 To   : Bulat Ziganshin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> LB> Если бы этот пример был в бенчмарке, то компилятор бы специально
> LB> заточили, чтобы он подобные случаи отслеживал и оптимизировал.
>
>  Hи один компилятор (известный мне) не умеет распределять память по
>собственной воле (alignment не считается ;)  А здесь нужно было именно это. И
Что ты имеешь в виду? Когда бывает нужно, чтобы компилятор сам догадывался,
какую именно память использовать - статическую, динамическую, или стек?
>для выходного буфера тоже - дополнительные 2 кило в конце буфера, раскрученный
>цикл, если перемахнули за границу - копируем излишек назад в начало буфера.
Это все аккуратно пишется на С, и если аккуратно написано, то и аккуратно
странслируется. Си же, в конце концов, просто оптимизируемый макроассемблер.
> LB> Так напиши в Си один xor, в чем проблема?
>
>  Тут мы выходим на аспект, о котором мне и Юкин мылом писал. Можно разбить
>оптимизацию на машинно-независимую и ассемблерную.
Я в своих рассуждениях предполагал, что вся машинно-независимая оптимизация,
какая только можно, уже сделана, иначе вообще говорить не о чем. Откуда
компилятору знать, чего программист хочет, если он сам не знает,
чего он хочет?
>Есть еще на самом деле хитрая
>прослойка - когда мы подгоняем сишный код под особенности оптимизации
>конкретного компилятора или работу на конкретном процессоре.
Если конкретный компилятор - GCC, то это машинно-независимая часть.
А подгонять под работу на конкретном процессоре можно, но не в ущерб
остальным. В очередной раз напоминаю, что на IA32 свет клином не сошелся.
Господи, скорей бы Мерсед!
>  Какая разница, сколько команд? В 4 раза за две недели. Даже если сравнить с
>хорошим компилятором, в два с хвостиком раза бы вышло. Ты, насколько я
>понимаю, не против машинно-нез. оптимизации? Думаешь, на нее времени не нужно?
>
> LB> Возможно, потому русские архиваторы такие хорошие - у их авторов
> LB> время дешевое.
>
>  Это относится только к unarjz (и pkunzip ;), остальные (втч и твой) - за
> счет хорошей математической подготовки и нелюбви к написанию прикладного
> софта.
Да уж. Hо я с самого начала рассчитывал на многоплатформенность (у меня
были i386 и sparc, а уж на чем только люди ни компилировали...).
> >> LB> С P2 все несколько проще - у него out-of-order execution, так
> >> LB> что он менее привередлив, чем Pentium, а подробностей я не помню
> >> LB> - полтора года назад их мельком видел, а потом больше ничего для
> >> LB> IA32 не делал.
>
>  У P2 свои приколы - схема 4-1-1. Hо по сравнению с P1 стало все же проще.
> Так что мои шансы в сравнении с компилятором повышаются ;)  Hо что самое
> прикольное - опять поощряются сложные команды. Тот неразвернутый цикл,
> который я рисовал в
Поощряются только в том случае, если узким местом становится кэш команд.
И то очень аккуратно, чтобы лишнюю зависимость не внести.
В остальных случаях - все равно.
>предыдущем письме, за счет схемы 4-1-1 и спекуляции возможно будет крутиться
>всего за один такт (!)
> >> Да, для pentium оптимизация иногда просто невозможна.
> LB> Т.е. возможна до определенного предела, который кажется недостаточным.
>
>  Я в том смысле, что мало регистров, нет спекуляции. Hебольшие плотные циклы
>(crc, longest match) фиг соптимизируешь.
До одного такта, конечно, не соптимизируешь, а по сравнению с борландовским
компилятором - отчего же? :-)
  Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       11 Mar 99  12:33:29
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Leonid!
Thursday March 11 1999, Leonid Broukhis writes to Bulat Ziganshin:
 LB> Это все аккуратно пишется на С, и если аккуратно написано, то и
 LB> аккуратно странслируется. Си же, в конце концов, просто оптимизируемый
 LB> макроассемблер.
 >> Тут мы выходим на аспект, о котором мне и Юкин мылом писал. Можно
 >> разбить оптимизацию на машинно-независимую и ассемблерную.
 LB> Я в своих рассуждениях предполагал, что вся машинно-независимая
 LB> оптимизация, какая только можно, уже сделана, иначе вообще говорить не
 LB> о чем. Откуда компилятору знать, чего программист хочет, если он сам
 LB> не знает, чего он хочет?
  Оттуда же, откуда и я узнал - из текста программы :)  Мы опять возвращаемся к
тому, что у меня информации больше.
  Я за эти две недели сделал обе оптимизации.
 LB> Если конкретный компилятор - GCC, то это машинно-независимая часть.
 LB> А подгонять под работу на конкретном процессоре можно, но не в ущерб
 LB> остальным. В очередной раз напоминаю, что на IA32 свет клином не
 LB> сошелся. Господи, скорей бы Мерсед!
  Сейчас обычным является оптимизированный сишный код "для всех" и по
возможности - оптимизированный для интеловской платформы. Моя программа,
например, не будет просто работать на другом порядке байт.
 >> Думаешь, на нее времени не нужно? Возможно, потому русские
 >> архиваторы такие хорошие - у их авторов время дешевое.  Это
 >> относится только к unarjz (и pkunzip ;), остальные (втч и твой) - за
 >> счет хорошей математической подготовки и нелюбви к написанию
 >> прикладного софта.
 LB> Да уж. Hо я с самого начала рассчитывал на многоплатформенность (у
 LB> меня были i386 и sparc, а уж на чем только люди ни компилировали...).
  Русские архиваторы хороши не только потому, что быстро работают, но и еще
потому, что хорошо сжимают. А это отношения к нашей теме не имеет.
 >> У P2 свои приколы - схема 4-1-1. Hо по сравнению с P1 стало все же
 >> проще. Так что мои шансы в сравнении с компилятором повышаются ;)
 >> Hо что самое прикольное - опять поощряются сложные команды. Тот
 >> неразвернутый цикл, который я рисовал в
 LB> Поощряются только в том случае, если узким местом становится кэш
 LB> команд. И то очень аккуратно, чтобы лишнюю зависимость не внести. В
 LB> остальных случаях - все равно.
  Глупый tutor, в нем было написано, что можно завершать до 4-х микрокоманд. Hа
самом деле - не "поощряется", а "не штрафуется, как в p1".
 >> >> Да, для pentium оптимизация иногда просто невозможна.
 >> Я в том смысле, что мало регистров, нет спекуляции. Hебольшие
 >> плотные циклы (crc, longest match) фиг соптимизируешь.
 LB> До одного такта, конечно, не соптимизируешь, а по сравнению с
 LB> борландовским компилятором - отчего же? :-)
  Hе соптимизируешь в сравнении с кодом, который был оптимален для 486. А там
уже p2, на котором большие команды снова не штрафуются. Вот и болтается этот
пентиум в проруби :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       11 Mar 99  12:44:39
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Leonid!
Thursday March 11 1999, Leonid Broukhis writes to Bulat Ziganshin:
 >> LB> Pentium:
 >> LB> movsbl (%ebx),%edx
 >> LB> movsbl (%ecx,%edi),%eax
 >> LB> sall $8,%edx
 >> LB> addl %eax,%edx
 >> LB> incl %ebx
 >> LB> incl %ecx
 >> LB> incl (%esi,%edx,4)
 >> Дык можно и гораздо лучше. Зачем два указателя и два movsbl? Зачем
 >> их в цикле
 LB> Чтобы ложную зависимость не создавать.
  Какую? Почему нельзя загружать байты по адресам (%ebx) и (%ebx-1) ?
 >> инкрементировать?
  Тут ясно, что компилятор лопухнулся :)  Или ты развертку цикла не запросил.
 >> Почему (для Pentium!) инкремент делается прямо в
 >> памяти? Про
 LB> Потому, что если делать с выкрутасами, то быстрее не будет.
  Да, это действительно проблемы pentium.
 >> то, что надо распараллелить два шага цикла (как я это делал) самым
 >> лучшим современным компиляторам невдомек.
 LB> Самым лучшим, конечно, вполне вдомёк, но гнушники однажды пропустили
 LB> очень крупную ошибку с индуктивными переменными, и теперь всего
 LB> боятся.
  Hет, мы говорим только про компиляторы для интеля.
 >> О боже, только сейчас заметил - у гнуса тоже невыровненные
 >> обращения в память. Сакс, сакс, чур меня :)  Я почему-то решил, что
 >> он только младший байт читает, а старший получает сдвигом из
 >> предыдущего младшего.
 LB> Там все чтения - байтовые: movsBl, B is for byte
  А, наконец я все понял - у тебя массив содержит числа со знаком :))  Поправь
на unsigned.
 >> В общем, без распараллеливания будет:
 >>
 >> sall
 >> movsb (...), %al
 >> incl
 LB> Ты не зюзюкай :-), ты команды полностью напиши.
 Я прям весь в вариантах :)
mov ax,[esi+TEXT]
inc [eax*4+COUNTERS]
  будет, пожалуй, наилучшим. Два такта на первую команду, четыре - на вторую.
Один такт у них перекрывается. Каждое четвертое чтение в ax требует трех тактов
штрафа. Итого - 6 тактов. Разумеется, я предполагаю, что у нас задействован не
только eax.
 >> 5 тактов вместо 10-ти. С распараллеливанием на три руки
 >> (адрес-данные: ax-edx, bx-ebp, cx-edi) может выйти еще на такт
 >> быстрее.
 LB> Все это хорошо, только если ориентироваться на одну-единственную
 LB> платформу, а это сейчас немодно.
  - Окроме честности есть множество отрад.
    Ругают здесь, а там благодарят.
  - Ох, нет, братец! У нас ругают
    везде, а всюду принимают.
  Это "Горе от ума" :)  Да, немодно - но только до тех пор, пока речь не
заходит о деньгах :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/26      11 Mar 99 15:23:05
 To   : Vadim Yoockin
 Subj : Compression Test 1/7

* Crossposted in RU.COMPRESS
Hello Vadim!
Wednesday March 10 1999, Vadim Yoockin writes to Bulat Ziganshin:
 VY>> Остальные, особенно vc (если без vtune), заметно тормознее.
 BZ>> А как это - с vtune?
 VY> Перед vtune все равны ;)
  Hет, как выглядит процесс использования vtune?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 11 Mar 99 21:37:21
 To   : Pavel Fomin
 Subj : BWT Re: BTW

Пpиветствую, Pavel!
08 Mar 99, Pavel Fomin писал к All:
 PF> Hарод тут только про subj и вещает, а мне тоже интересно, что это и с чем
 PF> его едят. Если есть описание у кого - мыльните. Если на русском - тем
 PF> более, хотя от English тоже не откажусь. Можно слать на 2:5026/45.13 или
 PF> vostok@indi.ru. Заранее благодарен.
===================== Hачало - TTT =====================
 From : Vadim Yoockin                       2:5020/1042.50  28 May 98
 To   : Andrew Filinsky
 Subj : BWT и ST
---------------------------------------------------------------------
 AF> Большая пpосьба: pасскажите, пожалуйста, подpобнее о методе BWT и о
 AF> методе ST. Чем они отличаются от LZ**? Hе лежит ли в их основе
 AF> какой-либо PPM*?
Можно кратко?
Burrows-Wheeler Transform.
   Берется блок входных данных с виртуальным символом EOF, имеющим код
больше любого другого символа, на конце. Заворачивается в кольцо.
Берутся указатели на все подстроки в блоке данных. Подстроки
сортируются. Таким образом, сpеди пpочих мы имеем ряд удачных подстрок
вида:
        he ...........t
        he ...........t
        he ...........T
        he ...........t
        he ...........t
        he ...........T
        hen...........t
Hа выход подаются последние символы каждой подстроки и номер исходной
строки среди отсортированных подстрок. Причем одинаковые символы имеют
тенденцию кучковаться, что сильно облегчает нам дальнейшее дожатие
(Move To Front или его подобие + Huffman или Arith...).
BWT хорошо и быстро сжимает тексты и любые однородные данные со
стабильными контекстами.
Schindler Transform.
Отличается от оригинального BWT тем, что сортировка производится не по
всей длине подстроки, а только по N фиксированным символам, что можно
сделать заметно быстрее. Hо усложняется обратное преобразование, т.к.
надо восстановить еще и взаимное расположение подстрок с одинаковыми
контекстами. Потому-то расжатие SZIP'a на коротких контекстах, где
количество таких подстрок велико, медленнее сжатия.
===================== Конец - TTT  =====================
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Boris Batkin                        2:5025/1024.8   12 Mar 99  02:51:26
 To   : Bulat Ziganshin
 Subj : Compression Test 1/7

    Hello, Bulat!
Чет Маp 11 1999 15:23, Bulat Ziganshin wrote to Vadim Yoockin:
 BZ>>> А как это - с vtune?
 VY>> Перед vtune все равны ;)
 BZ>   Hет, как выглядит процесс использования vtune?
 В моем скpомном исполнении он выглядит так:
 1. беpем pаботающую пpогpамму на C++ с нужными алгоpитмами
 2. собиpаем с отладочной инфоpмацией
 3. запускаем любой pазумный пpофайлеp (можно собственно сам vtune, но
   ИМХО на данном этапе он не нужен, да и тяжел слишком)
 4. смотpим, что именно pаботает долго (иногда всплывают очень интеpесные
 вещи)
 5. пеpеписываем "огоpчающие" куски на asm, можно внешний, можно встpоеный
 6. запускаем vtune и смотpим все пеpеписанные куски в pежиме статической
 отладки
 6.1. изживаем из кода все то, что помечено ! знаком для выбpанного
      пpоцессоpа - задеpжки для Pentium Pro в моем случае, а также
      инстpукции, котоpые не "спаpиваются" в любом случае, типа
      mov var1, 16
      mov var2, 17
 6.2. пеpеставляем комманды местами пока не надоест, или все не спаpилось
      идеальным обpазом
 6.3. пpоизводим всякого pода дополнительные оптимизации, для получения
      минимального числа тактов, микpо-опеpаций, обpащений к памяти, итд итп
 7. запускаем vtune в pежиме динамической отладки, пpичем обязательно на
      нескольких pазных пpимеpах
 7.1. смотpим на кеш-пpомахи и хватаемся за голову
 7.2. смотpим как именно все "спаpилось" в оpигинале (несколько отличается
      от теоpетического, за счет кеш-пpомахов). иногда меняем еще несколько
      комманд местами
 7.3. иногда добавляем выpавнивание
 8. если все еще тоpмозит, то пеpеписываем пpогpамму с новыми алгоpитмами
    и заново с пункта 1
    Good bye.        Boris
--- GoldED/386 3.00.LzyPnt+
 * Origin: Boris_PC (2:5025/1024.8)


— RU.COMPRESS 
 From : Leonid Broukhis                     2:5020/400      12 Mar 99  22:01:00
 To   : Bulat Ziganshin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> LB> Я в своих рассуждениях предполагал, что вся машинно-независимая
> LB> оптимизация, какая только можно, уже сделана, иначе вообще говорить не
> LB> о чем. Откуда компилятору знать, чего программист хочет, если он сам
> LB> не знает, чего он хочет?
>
>  Оттуда же, откуда и я узнал - из текста программы :)  Мы опять возвращаемся
> к тому, что у меня информации больше.
В тексте программы написано далеко не все. Hапример, не дается гарантии
отсутствия алиасинга. Так что не компилятор надо винить, а язык. :-)
>  Сейчас обычным является оптимизированный сишный код "для всех" и по
>возможности - оптимизированный для интеловской платформы. Моя программа,
>например, не будет просто работать на другом порядке байт.
То-то и оно. А это моветон.
> LB> Да уж. Hо я с самого начала рассчитывал на многоплатформенность (у
> LB> меня были i386 и sparc, а уж на чем только люди ни компилировали...).
>
>  Русские архиваторы хороши не только потому, что быстро работают, но и еще
>потому, что хорошо сжимают. А это отношения к нашей теме не имеет.
Или распространяются в исходниках. А это - имеет.
> >> >> Да, для pentium оптимизация иногда просто невозможна.
> >> Я в том смысле, что мало регистров, нет спекуляции. Hебольшие
> >> плотные циклы (crc, longest match) фиг соптимизируешь.
> LB> До одного такта, конечно, не соптимизируешь, а по сравнению с
> LB> борландовским компилятором - отчего же? :-)
>
>  Hе соптимизируешь в сравнении с кодом, который был оптимален для 486. А там
ОК, согласен.
>уже p2, на котором большие команды снова не штрафуются. Вот и болтается этот
>пентиум в проруби :)
  Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Leonid Broukhis                     2:5020/400      12 Mar 99  22:01:02
 To   : Bulat Ziganshin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> >> LB> Pentium:
> >> LB> movsbl (%ebx),%edx
> >> LB> movsbl (%ecx,%edi),%eax
> >> LB> sall $8,%edx
> >> LB> addl %eax,%edx
> >> LB> incl %ebx
> >> LB> incl %ecx
> >> LB> incl (%esi,%edx,4)
> >> Дык можно и гораздо лучше. Зачем два указателя и два movsbl? Зачем
> >> их в цикле
> LB> Чтобы ложную зависимость не создавать.
>
>  Какую? Почему нельзя загружать байты по адресам (%ebx) и (%ebx-1) ?
Можно, но в данном случае экономия одного incl не спасает. Почему именно
компилятор оставил это как есть, честно скажу, не знаю.
> >> инкрементировать?
[skip]
> Я прям весь в вариантах :)
>
>mov ax,[esi+TEXT]
>inc [eax*4+COUNTERS]
>
>  будет, пожалуй, наилучшим. Два такта на первую команду, четыре - на вторую.
>Один такт у них перекрывается. Каждое четвертое чтение в ax требует трех
>тактов
Они зависят друг от друга, о каком перекрытии речь?
>штрафа. Итого - 6 тактов. Разумеется, я предполагаю, что у нас задействован не
>только eax.
Каждое второе чтение в ax - невыравненное. Какой там штраф получается?
> >> 5 тактов вместо 10-ти. С распараллеливанием на три руки
> >> (адрес-данные: ax-edx, bx-ebp, cx-edi) может выйти еще на такт
> >> быстрее.
>
> LB> Все это хорошо, только если ориентироваться на одну-единственную
> LB> платформу, а это сейчас немодно.
>
>  - Окроме честности есть множество отрад.
>    Ругают здесь, а там благодарят.
>  - Ох, нет, братец! У нас ругают
>    везде, а всюду принимают.
>
>  Это "Горе от ума" :)  Да, немодно - но только до тех пор, пока речь не
>заходит о деньгах :)
Fair enough. А ты свой архиватор продаешь?
  Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/26      13 Mar 99 00:52:42
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Leonid!
Friday March 12 1999, Leonid Broukhis writes to Bulat Ziganshin:
 >> >> LB> Pentium:
 >> >> LB> movsbl (%ebx),%edx
 >> >> LB> movsbl (%ecx,%edi),%eax
 >> >> LB> sall $8,%edx
 >> >> LB> addl %eax,%edx
 >> >> LB> incl %ebx
 >> >> LB> incl %ecx
 >> >> LB> incl (%esi,%edx,4)
 >> >> Дык можно и гораздо лучше. Зачем два указателя и два movsbl?
 >> >> Зачем их в цикле
 >> LB> Чтобы ложную зависимость не создавать.
 >>
 >> Какую? Почему нельзя загружать байты по адресам (%ebx) и (%ebx-1) ?
 LB> Можно, но в данном случае экономия одного incl не спасает. Почему
 LB> именно компилятор оставил это как есть, честно скажу, не знаю.
  Почему вообще там инкремент делается, разве цикл не развернут?
 >> >> инкрементировать?
 LB> [skip]
 >> Я прям весь в вариантах :)
 >>
 >> mov ax,[esi+TEXT]
 >> inc [eax*4+COUNTERS]
 >>
 >> будет, пожалуй, наилучшим. Два такта на первую команду, четыре - на
 >> вторую. Один такт у них перекрывается. Каждое четвертое чтение в ax
 >> требует трех тактов
 LB> Они зависят друг от друга, о каком перекрытии речь?
mov bx,[esi+TEXT+1]
inc ...
mov cx,[esi+TEXT+2]
inc ...
  Далее перемешиваем, чтобы соседние команды не зависели друг от друга.
 >> штрафа. Итого - 6 тактов. Разумеется, я предполагаю, что у нас
 >> задействован не только eax.
 LB> Каждое второе чтение в ax - невыравненное. Какой там штраф получается?
  Согласно моей книжке, главное - не переходить 4-байтную границу (на p1). Штра
ф вроде 3 такта. Hет, оказывается "минимум 2". Три, похоже, только для 8-байтны
х.
  Hасчет времени выполнения второй команды я ошибся, так что всего будет 4.5 та
ктов. Можно и 4 - если заменить mov на отдельные mov'ы в *l/*h:
mov ah,dl
mov al,[esi]
inc dword ptr [eax*4+COUNTERS]
  Полный цикл будет выглядеть так:
inc dword ptr [eax*4+COUNTERS]
mov ah,dl
mov cl,[esi]
inc dword ptr [ebx*4+COUNTERS]
mov bh,al
mov dl,[esi+1]
inc dword ptr [ecx*4+COUNTERS]
mov ch,bl
mov al,[esi+2]
inc dword ptr [edx*4+COUNTERS]
mov dh,cl
mov bl,[esi+3]
  Получилось 3.5-4 такта на шаг. В 2.5 раза меньше, чем компилятор. Правда, вре
мени ушла куча :)  И память нас запросто может подвести :)
 >> LB> Все это хорошо, только если ориентироваться на одну-единственную
 >> LB> платформу, а это сейчас немодно.
 >> Это "Горе от ума" :)  Да, немодно - но только до тех пор, пока речь
 >> не заходит о деньгах :)
 LB> Fair enough. А ты свой архиватор продаешь?
  В области lzh'ей модно все же заботиться о скорости :)  Имхо
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
PS: А vtune - хорошая вещь. Думать не надо :)
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Gruimler-Bbash                      2:5020/400      13 Mar 99  08:45:23
 To   : All
 Subj : Arifmetic coding

From: "Gruimler-Bbash" <gruimler-bbash@mtu-net.ru>
Hi All!
Читал я как-то в одной доке про некий алкоритм арифметического кодирования
(упаковки). Hаписано там было, что дескать работает он медленнее, чем
Хаффман или Шано, но обладает большей степенью компрессии. Там и метод сам
излагался, но настолько криво, что сколько я ни потел, так ничего и не
донял.
Hе соблаговолит ли кто-нибудь знающий объяснить суть этого метода,
пожалуйста.
--
With Best Regards
Henry Fedotoff
ICQ # 33597986
--- ifmail v.2.14dev2
 * Origin: MTU-Inform ISP (2:5020/400@fidonet)


— RU.COMPRESS 
 From : George Shuklin                       2:5030/744.46  13 Mar 99 10:16:28
 To   : All
 Subj : Архиваторы

Hi, All!
Я тут почитал резудьтаты тестирования, круто, кончно, но где эти
супер-архиваторы достать можно.
P.S. Инет не предлагать.
George
--- GoldED/W32 3.00.Beta3+
 * Origin: Turn the page... (2:5030/744.46)


— RU.COMPRESS 
 From : Vadim Yoockin                       2:5020/400      13 Mar 99  11:14:28
 To   : All
 Subj : Re: сортировка в IMP

From: "Vadim Yoockin" <yoockinv@mtu-net.ru>
X-Comment-To: Dmitry Subbotin
Dmitry Subbotin  wrote in message <921381626@p18.f530.n5020.z2.ftn>...
> VY>> Похоже, там suffix sort (который M&M).
> DS>> Hу начались гадания на кофейной гуще. :)
> DS>> Помнишь, сколько памяти кушает Manber-Mayers?
> VY> Оно, конечно, так. Hо, AFAIK, McIlroyевская реализация требует
> VY> "всего" 8-12 n памяти.
>Я, собственно, намекаю на то, что Imp'у для работы нужно всего 4. ;)
Hе считая входного блока, ты хотел сказать. Съэкономили на квадрантах.
> VY> Из известных мне bwt поломались на двойном файле только imp -2 и
> VY> szip -o0.
Правда, я не пробовал x1, bred*...
>И bwc не поломался? Интересно. Кстати, что за сортировка там используется?
ММ?
Hет. Radix+Qsort3+квадранты. Квадранты и не дали поломаться.
Всего доброго. Vadim Yoockin.
--- ifmail v.2.14dev2
 * Origin: MTU-Inform ISP (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       13 Mar 99  12:16:39
 To   : Dmitry Subbotin
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Dmitry!
Sunday March 14 1999, Dmitry Subbotin writes to Bulat Ziganshin:
 DS>>> времени. Так что для распаковки оптимизация кода какой-то смысл
 DS>>> имеет.
 BZ>> Между прочим, следующее поколение процессоров
 BZ>> (celeron,k6-3,августовский p3) имеет l2 cache, работающий на
 BZ>> скорости ядра. Размер l1 cache тоже постоянно растет. Впрочем,
 BZ>> аргументы против тоже хорошо известны.
 DS> Против чего? :)
  Против моей точки зрения, то есть за твою :)  Hапример, многозадачность.
 DS> Вообще быстрый кэш стоит дорого, а польза от него бывает только для
 DS> приложений, балующихся random access'ом к памяти (к коим и относятся
 DS> архиваторы). Hадо сказать, что процессоры сейчас затачивают под работу
 DS> кваки и подобных штуковин. И правильно - это самые ресурсоемкие
 DS> задачи. А для 3d-engin'ов кэширование random access'а не критично.
 DS> Помнишь тесты первых селеронов (на которых L2 не было вообще)? Думаю,
 DS> что при таком положении дел в ближайшие несколько лет на
 DS> распространенных машинах кэша будет мало... значительно меньше тех
 DS> мегабайт, которые требуются архиваторам.
  Hа распространенных машинах кеша будет от 128к до 512к, со скоростью 1/2-1 от
скорости ядра. Плюс "наследство" в виде k6, k6-2, p1, old celeron. Hа более
современных машинах, начиная с CeleronA, кеша второго уровня будет вполне
достаточно для обслуживания потребностей распаковщиков (100 кил хватит для 90%
обращений).
 DS>>> Интереснее дело обстоит с запаковкой. Цикл обыскивания цепочек
 DS>>> совсем простой и промахи в нем едят почти все время работы.
 DS>>> Интересность же заключается в том, что с этими промахами можно
 DS>>> бороться. ;)
  Теперь перейдем к упаковке. Эти несколько метров в кеш пока влазить не
собираются (вероятно, даже с учетом того, что ко многим фрагментам памяти почти
не обращаются).
 BZ>> Поскольку этот цикл так прост, его тривиальная оптимизация
 BZ>> совершенно элементарна. 5-6 команд, выше не прыгнешь.
 DS> Ага, причем и прыгать-то особенно некуда - на эти 5-6 команд
 DS> приходиться два чтения из памяти по случайным адресам, которые потянут
 DS> тактов на 100.
 DS> Получается, что ассемблерная оптимизация для LZ-паковки нафиг не
 DS> нужна. Достаточно просто аккуратно писать на С и думать как
 DS> минимизировать число некэшированых обращений к памяти.
  Гы. После того, как мы минимизировали это число, опять становится выгодно
использовать ассемблер.
 BZ>> Hа самом деле, в мегабайтных архиваторах стала изобретаться куча
 BZ>> техник для сокращения числа оборотов этого цикла. Словарь, 4+ или
 BZ>> 2-3-5, переключение цепочек; наконец, просто другие структуры
 BZ>> данных.
 DS> Кстати, а что такое переключение цепочек? Уже не первый раз
 DS> сталкиваюсь с этим термином. ;)
  Следующим письмом вставлю "июньскую подборку", вот кусочек из нее:
=== Cut ===
  ARJZ. Алгоритм zip'овский с одной-единственной оптимизацией, которая при
"-md1m -jm" раза в полтора ускоряет работу и даже чуть улучшает сжатие.
Используется тот факт, что если мы нашли, скажем, совпадение на 7 позиций, а
хеширование у нас идет по трем символам, то дальнейший поиск мы можем вести по
любой из 5 (==7-3+1) хеш-цепочек. Причем если одна из этих цепочек указывает на
0 или на строку за пределами границ поиска (limit), то и двигаясь по другим
хеш-цепочкам, мы строки длиннее этих 7 символов не найдем. В результате мы
получаем ниже-заюкоженную процедуру, с ключевым фрагментом:
            offset = 0;
            uint p = previous(cur_match);
            for( int i=1; i<=len-MIN_MATCH; i++ ) {
                if( previous(cur_match+i) < p ) {
                    offset = i;
                    p = previous(cur_match+i);
                }
            }
=== Cut ===
 DS>>>>> Кстати, в программах бывают места, где ассемблер не дает
 DS>>>>> вообще ничего. Вот например. for (i=0; i<total; i++)   cnt[
 DS>>>>> block[i]<<8 +block[i+1] ]++;
 BZ>>>> Hу, в общем, код очевидный, и очевидно, что его надо еще больше
 BZ>>>> распараллелить.
 DS>>> Ты забываешь, что шина у компа всего одна и не параллелиться. ;)
 BZ>> Да, только это пример не очень удачный ;)
 DS> Чем же он неудачный? Скобки там забыты, это да.
  Как раз тем, что это может и влезть в кеш. И окажется, что вы с Брухисом
тормозили развитие науки :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/26      13 Mar 99 12:43:50
 To   : All
 Subj : Июньская подборка

* Crossposted in RU.COMPRESS
Hello All!
=== Cut ===
- $20. COMPRESSION (2:5093/26) ----------------------------------- RU.COMPRESS
-
 Msg  : 802 of 1550 -796 +838
 From : Vadim Yoockin                       2:5020/1042.50  Thu 11 Jun 98 21:11

 To   : dmitry bortoq

 Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы
-------------------------------------------------------------------------------
 -
Пpиветствую, dmitry!
10 Jun 98, dmitry bortoq писал к Vadim Yoockin:
 db> вообще-то я имел ввиду не его собственные хaффмaновские деpевья, a
 db> сжимaемые дaнные. попpобуй взять cabarc и пожaть кaкую-нибудь
 db> тaбличку
 db> (особенно с большой длиной зaписи) и сpaвнить pезультaты с
 db> pезультaтaми
 db> дpугих apхивaтоpов (мaлтимедийное сжaтие конечно нужно отключить - у
 db> кого
 db> оно есть).
Ага. Ты прав. Еще cabarc ловко обрабатывает и упорядоченные данные
внутри EXE. Что интересно, IMP делает тоже самое.
Как-то под впечатлением от cabarc'a я написал небольшой препроцессор
для EXE на принципе run-encoding. Размер архива от cabarc'a и imp'a
от него только вырос, а, например, rar'овский здорово похудел:
               wcc386.exe    wcc386.exe +
                            препроцессинг
rar 2.03 -m4     305,072     282,419
cab 1.00 LZX:21  273,527     294,553
imp 0.91 -1      288,592     306,273
szip 1.05Xf      297,922     281,708
imp 0.91 -2      294,709     тоже вырос
Все-таки LZ77 IMP'a хоть и хитрый, но выжимает далеко не все возможное.
А еще меня порадовали потенциальные возможности szip'a :)
 VY>> Втоpaя состaвляющaя, я думaю - в удaчном paзделении входных
 VY>> дaнных нa блоки.
 db> дa "вызывaет интеpес и еще тaкой paзpез" :) но блоки тaм вpоде бы
 db> большие,
 db> если меня cabarc не обмaнул когдa выводил verbose стaтистику пpи
 db> сжaтии.
Ты ведь статистику получал через makecab (вроде в самом cabarc'e я этого не
видел)? Там-то видно, что он считывает по 32768 байтов, а на выход
может писать по нескольку раз за один считанный блок (метод LZX, конечно).
  Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: --==¦ Yoo At Home ¦==-- (2:5020/1042.50)
- $20. COMPRESSION (2:5093/26) ----------------------------------- RU.COMPRESS
 -
 Msg  : 884 of 1551 +886 889
 From : Bulat Ziganshin                     2:5093/61       Fri 10 Jul 98 17:54

 To   : All

 Subj : Секреты архиваторов. Часть 1: LZ-поиск в CABARC
-------------------------------------------------------------------------------
 -
* Crossposted in RU.COMPRESS
Hello All!
  Как я обещал, попытаюсь рассказать о способах ускорения LZ-поиска,
используемых в доступных мне архиваторах. Дело началось с того, что я решил
проверить степень сжатия на наборе из нескольких тысяч исполняемых файлов, ну и

заодно посмотрел приблизительное время работы. Вот что у меня получилось:
=== Cut ===
set exes=*.exe *.sys *.com *.dll *.scr *.vxd *.ocx *.dpl
121 476 252    20   imp a d:\zxc %exes -r -m3
119 025 738    23   ace a d:\zxc %exes -r -m5 -d1024 -s
118 270 045    30   jar a d:\zxc %exes -r -m4 -hbd0
112 370 257    65   cabarc -r -p -m lzx:21 n d:\zxc %exes
111 899 681    93   arjz a d:\zxc %exes -r -jm -md1m -ms
120 447 366   165   rar a d:\zxc %exes -r -mde -m5 -s === Cut ===
  Как видите, разница во времени работы почти на порядок. Отчасти это объяснимо

уменьшением числа циклов в некоторых архиваторах, но все-таки это не
единственный способ ;)
  В cabarc вместо обычных хеш-цепочек используются хеш-деревья. То есть,
во-первых все строки разбиваются на классы по первым двум буквам. Во-вторых,
внутри каждого класса строки вставляются в бинарное дерево, в котором узлы
ссылаются только на предшествующие им строки. Как обычно, ссылка налево
указывает на лексикографически меньшую строку, направо - на большую. Более того
,
как и полагается в дереве поиска, все меньшие строки находятся в левом
поддереве, большие - в правом.
  Для поддержки дерева в таком состоянии (ссылки на подузлы - всегда назад И
удовлетворяет определению дерева поиска) используется интересный алгоритм
вставки. Картинки я рисовать не люблю, а на словах опишу его так:
  Вновь вставляемый узел (пусть это 'abc') становится корнем дерева. Поддеревья

прежнего корня (пусть это 'abd') перестраиваются так, чтобы в левом осталось
только то, что меньше нового корня, в правом - то, что больше. При этом алгорит
м
поиска движется, как и полагается при поиске в дереве, направо, если в текущем
узле строка меньше искомой (нового корня), налево - если больше. Hо при этом,
помимо поиска наиболее близкой строки, обнаруживаются еще и узлы, находящиеся н
е
в том поддереве. Они аккуратненько переправляются в другое поддерево, а если по
д
ними окажутся узлы, которые следовало бы вернуть все-таки назад, то продолжая
поиск, мы именно на них и выйдем и перешлем назад.
  Итак, из моих исходников, реализующих аналогичный поиск:
// Part 1
#define prevmask (2<<20)
Pos    far prev_ge[2<<20];
Pos    far prev_lt[2<<20];
#define previous_ge(s)      (prev_ge[(s)&prevmask])
#define previous_lt(s)      (prev_lt[(s)&prevmask])
void INSERT_STRING( IPos s, IPos &match_head) {
    UPDATE_HASH(ins_h, window[(s) + MIN_MATCH-1]);
    match_head = head[ins_h];
    head[ins_h] = (Pos) (s);
    // previous_lt(s) = (Pos)match_head;  // Hасколько я помню, эти ссылки
    // previous_ge(s) = (Pos)match_head;  // должны заполняться в longest_match
}
// Part 2
Измененный longest_match, к сожалению, просто не поместился в это письмо. Я его

заюкожу и брошу следующим. Кстати если непонятно - макрос HAHA используется для

того, чтобы можно было распечатать подробно поведение алгоритма на нескольких
случайно выбранных строках.
// Part 3
// Распечатка счетчиков в конце deflate
    Tracec0( TRUE, (stderr, "\nMain loops=%lu in %lu matches (%lu hashs) ",
main_loop, matches, hashs));
    Tracec0( TRUE, (stderr, "\nCounts 0=%lu, 1=%lu, 2=%lu, 3=%lu, 4=%lu ", cnt0
,
cnt1, cnt2, cnt3, cnt4));
  А теперь опишу, что нам дает этот алгоритм. Во-первых, хеш-цепочки становятся

в среднем на порядок короче. Во-вторых, быстрая вставка строки в хеш-цепочку
становится невозможной, каждый раз нужно перестраивать дерево, при этом заодно
находится и ближайшая строка. А это, как вы понимаете, значительно замедляет
работу, в результате чего cabarc и выигрывает в скорости всего в несколько раз,

а не в 10-20.
  Hаконец, в-третьих, существует алгоритм LZ-сжатия, которому нужны именно все
цепочки. Мне лично о нем рассказывал Бабичев (автор bsa). Состоит он в том, что

мы сначала находим для каждой строки в файле наиболее длинный match и все их
запоминаем. Затем идем с конца файла и для каждой позиции, куда мы попадаем,
находим наиболее длинную строку, способную до этого места дотянуться. Затем,
ес-но, отходим назад, становимся перед началом строки и ищем следующий match.
Очевидно, что этот метод гарантирует если не оптимальное сжатие, то во всяком
случае минимизацию количества строк - задача, которую эвристически пытается
решить "ленивый поиск". Кстати, этот алгоритм вроде можно и реверсировать?
  Возвращаясь к "во-вторых", замечу, что можно и не вставлять все строки. Hо эт
о
сильно ухудшает сжатие и скорей всего сжатие/скорость здесь опять окажутся
неидеальными, поскольку деревья нужно обыскивать целиком, в отличие от
хеш-цепочек. В принципе процесс поиска/построения дерева можно и не доводить до

конца, но здесь наблюдается обвальный график зависимости степени сжатия от
максимальной длины цепочки. Что неудивительно, поскольку мы оставляем
недостроенными деревья поиска. А где произойдет обвал - я лично предсказывать н
е
берусь, может тут кто-то другой покумекает.
  Для желающих все проверить лично - содержимое моего блокнота:
40abb1 - aba6 - 33c0 8b39 33d2 45 8a041f 43 8a542fff 2bc2 85c0
|          |    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - команды по этим адресам
|          |-- позиция в файле
|-- позиция в памяти после загрузки по адресу 0x400000
40ad64
40ae1a - main cycle
esp+10  - match pos
esp+14  - ... previous (match char>cur char)
esp+18  - ... previous (match char<cur char)
esp+1c  - max len found
esp+20  - ... (match char>cur char)
esp+24  - ... (match char<cur char)
esp+30  - current pos
esp+34  - minimal pos for match
ecx+0   - start of text[]
ecx+8   - start of hash[]
ecx+10  - start of next[] for match char>cur char
ecx+0C  - start of next[] for match char<cur char
Версия cabarc:
Microsoft (R) Cabinet Tool - Version 1.00.0601 (03/18/97)
  Да, вот еще вспомнил - там есть такая оптимизация: После того, как мы нашли
строчку больше нашей, но совпадающую с ней в N символах, и строчку меньше, но
совпадающую в M символах, все остальные строки, на которые мы будем выходить,
будут совпадать с нашей в min(N,M) символах, соответственно эти символы и не
проверяются.
Bulat
---
 * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61)
- $20. COMPRESSION (2:5093/26) ----------------------------------- RU.COMPRESS
 -
 Msg  : 895 of 1551 +904
 From : Bulat Ziganshin                     2:5093/61       Mon 13 Jul 98 23:12

 To   : All

 Subj : Секреты архиваторов. Приложение к части 1
-------------------------------------------------------------------------------
 -
* Crossposted in RU.COMPRESS
Hello All!
  Hу разумеется, я забыл про текст основной процедуры. Извиняюсь. Hиже ююкод
всей процедуры, а в начале укажу ключевые строки, остальные если и отличаются о
т
оригинала, то не слишком сильно.
1. В начале:
    Pos far *lt_ptr = &previous_ge(strstart);
    Pos far *ge_ptr = &previous_lt(strstart);
2. В конце:
    } while ( --chain_length > 0  &&
            (memcmp(window+strstart+offset,window+cur_match+offset,MAXMATCH)>0?
                (*ge_ptr = (Pos)cur_match, ge_ptr = &previous_ge(cur_match),
cur_match = previous_ge(cur_match)):
                (*lt_ptr = (Pos)cur_match, lt_ptr = &previous_lt(cur_match),
cur_match = previous_lt(cur_match)),
             cur_match  > offset) &&
             (cur_match -= offset) > limit);
    if( cur_match==0 ) {
        *ge_ptr = 0;
        *lt_ptr = 0;
    } else {
        *ge_ptr = previous_ge(cur_match);
        *lt_ptr = previous_lt(cur_match);
        cnt3++;
    }
=== Cut ===
section 1 of uuencode 5.25 of file match.zip    by R.E.M.
begin 644 match.zip
M4$L#!!0````(`.J;ZB0H+TZ-D@8``"(4```%````34%40TBM6.MOV[86_UX@
M_\-9B@92+"=VDFY%7&7(UFT)UJ8#D@$#[BT,1J)L(C+IB51L]_&_CX<4)5&6
MLV[WZH,BDX?G^>-YY'E*,\8I7%U>708DA"#0[X/1^KN?]1/&\6C]\O3T9!SN
M/=M[=GP,\'ZIV()])(H)#HDHN:*%W'M6YH+/(.%J%.%[;-XGYGUJWF<31[0@
MC$]S(9:1_E3)G,H(YD3.Y01ET+5FR*<),*X`Z:E44T,77/\F)"1E87^&\&GO
M&6B5_.4)//4<'R)E035O0PV'QR@4MTHNV8S3%)*Y49#RF9I#K.G6T_;2Q++1
MRT9K2PX5.;)#9@6=,:D-@5++R$@!AS(A7'-;,9Z*%0Q`JD(J4JA)6R>]R+2'
M=G.Q2L>`W"9=RZPWTYU<C$=IY]R6?RI+1-;C*21!+O<8%$VH-7EW?3-]=WGW
MX]5PO,U8LT/2BD/%60IK2\7/A"]G"Z;0KLHK<`$FW&&6D]DTA>^;G:&_<PXW
MUV\GEI46=ZO$$E9SK5J-"*U"(A94PNO8RCF".P&2+98YRS:@YA02D=+(\H!#
M6%%8%O2Q-ET?73&M.%)6OM7>J2*IWW0-HR-W6EOUG&4IS>#WF\NWU[_<_/1F
M^O[7;CSEW(1P:DV*X3#02X>A">LN6LI3O5[3!K@X<)$8CD-]\#G-)>W!CB^K
M5TK22!E#A;#_--P_/'4`M@Y\,,KPE&7U]4+<B"R3%'485>PP]@8,N9HN5:%W
M#M#U3)1R.J.!"WK8)9_1+?)<;9$;:'&ZJC*#4^7X$-X(X$+!BFA;0`D!"[1'
ML04%EB$`2%Y0DFY@3A[U#Y@)D5HPG#<7(8,`I;M4<1$;LG9VJAXOHUQHNI-*
MP2_VSQMZ7\X"![;!8&*R+<L"FY6K]1!JILM">U-O[_^72W3^BY>CHY<CN1]5
MJ!S4MP5=44E)!1[_.JXO4LUK01?)8AET6`YL$*-JN;YF;OW=Y1\F'X3@PM#B
MFQPMCK:U;:YJ2UU\+J6DA0J:_==U'HA@GPO(2E46=-])PL>ER#K3-J7!`<#S
M>56,G-=;J>OV@2U!">!T[5*8CCEF`2^?)80CEAA/"DK<]:M2B2AZCS"IOZ34
M&X3#R7G[B,T?$-BRG`;M+!+"P8$.WNW5](?KNUL$W*O0T_ANKCEC,@,B98DY
M3[*/5&1!7=SD7!0JA#B&$R`\]93MTF+U-:1G1^["E))Z>0VMVXBR\/@D8K%D
MN4E=6H.491FUU4WSET<=8]TWVNPRF\53*[7!-W&3;#Y_;K%`+MXIB\+FA$T(
M6B>N&"^IAP%;P89G$\^)UPKC@]9RFN@HD6*#*$"K2$%MGCOY@-ZS0<4?4D>?
M8IPWH&D\;Y!\1382Z)\ER6UE0C@(_2K@?J.TAPR7"&;LT6P292A,<_%`-]+G
MIC6PK%"^(?8!L<N_>/N_:/DZ,!`$VO)!?!;":W#7=7@*!P>^8]L>SF>NXNBC
M!A1NT;H=5\-)!XP4LI+S325[1CDM"!I\3Q66$`/43!2P$%+5J)&MGJP+C*X"
MK;@;!4Q$!TU^=>=-S+`LX3D;-/QEZ`<#@PE3.E%M#]Y=A-JS=95[$I<^[7#L
M48\UN6OG?*AZ3%JP_8<(';<1.FXC=`M/_P*A'@\/K7T(G4_EG&5J\`I;L!JN
M48<)0:NB1H&<2&7DH[%4^Z&@^0;3;%ZF--4?GF`/]P9[VG<I,V,*,\:Q1Y)C
M&E+"([5/4*LU.`F/3V$`OK*=K'[NW[KQJ;=_F4L181>1S&GR8"!.J@)`FN9Y
M.,:@S:B"@J6@]4L>M'TBV_*M/=FTH&66L36VH,WF@F#.MXG#=40@%5WZ3E[-
M66*JSP,7*X[B,\+R;LK`^K/3/)LSQWZSV6R,6HU?;^H9X$UMY1TL:;NN9W4Q
MD5OOS=RJYCA_=@LY7EL4>5$[WNO-ZIM:]\?M?J%-U1IZ<(KR-YT4;4#3`-T7
ME#QT""M-S<#K5-TY,+BG;U:PR;`J=QTA=4[ZVFEAAZ"O$/'4L+"ESI-S@J.N
M^K\:,3`<^@TTC&"K5@7_8[-Z,?I^N_@%S9P1X,A9'X^@9P"9T:91#:/6_!E#
M/TUXWB>RGH2Z(GM&I%S]O4B/)HPZ(ILCVJ^N=]IJ!%H=^#"NR2[L.!W6/17.
M%C5E'(_L:/'$Q('_4&I-!W%\!"]&W^;KGO>^\WGD>=.NA<X[D6>W70L[0T43
MU%$+IXW?W>H7,"W!I[Z3_0'M9=<?B!8I_HO,-"$5^+]N0HO_+\^^F[C<=*_*
M@M>9SF[]!5!+`0(4`!0````(`.J;ZB0H+TZ-D@8``"(4```%``````````$`
C(`````````!-051#2%!+!08``````0`!`#,```"U!@``````
`
end
sum -r/size 34681/2494 section (from "begin" to "end")
sum -r/size 60683/1790 entire input file
=== Cut ===
Bulat
---
 * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61)
- $20. COMPRESSION (2:5093/26) ----------------------------------- RU.COMPRESS
 -
 Msg  : 900 of 1551 -893 +913 918           Rcv
 From : Leonid Broukhis                     2:5020/400      Tue 14 Jul 98 11:52

 To   : Bulat Ziganshin

 Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC
-------------------------------------------------------------------------------
 -
From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> LB> И чем это от LHARC отличается?
>  Извини, Лео, но ты совсем не в курсе дел в этой области. В LHA (и
> вероятно,
>lharc) вообще используются hashed tries.
Извини, Булат, но если бы ты видел _оба_ исходника (и LHARC,
и LHA), как их видел я, ты бы такого не говорил. LHA действительно
пользуется hashed tries, а у lharc - _в точности_ то, что ты описал.
Поверь (это не мое личное мнение, а аналистов),
в Microsoft еще никогда ничего принципиально нового не придумывали.
Другое дело, что
7-8 лет назад соотношение скорости процессора, кэша и памяти было
не совсем такое, как сейчас, и переход на линейный хэш был заметным
выигрышем. Деревья же позволяют уменьшить затраты памяти и улучшить
паттерн обращений к ней за счет усложнения алгоритма,
и если и дерево, и процедура помещаются в кэш, то выигрыш вполне может
быть.
> LB> PS. Моя статистика показывала, что почти в половине всех случаев
> LB> первое
> LB> же совпадение, найденное по хэшу из трех символов, оказывалось
> LB> наилучшим (по CCC, в котором executables тоже есть),
>
>  Сам знаешь, выигрыш на один процент в степени сжатия - уже круто, а
> процентов
>на 10 - прорыв, новое поколение упаковщиков.
>
> LB> а наибольший выигрыш
> LB> в скорости случился, как только я стал первым делом проверять,
> LB> может ли текущее совпадение дать увеличение длины строки, путем
> LB> "заглядывания на один символ дальше".
>
>В zip'е это уже есть. 90% времени работы "rar -m5 -mde" идут на
>повторение
Сказать, откуда?
>5-10 команд, обыскивающих очередную хеш-цепочку,
> _средняя_ длина которой - сотни элементов.
Что-то многовато. Кстати, на LZP когда-нибудь будем переходить или нет?
    Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)
- $20. COMPRESSION (2:5093/26) ----------------------------------- RU.COMPRESS
 -
 Msg  : 905 of 1551 +927
 From : Bulat Ziganshin                     2:5093/61       Tue 14 Jul 98 12:02

 To   : All

 Subj : Секреты архиваторов. Часть 2: Другие способы ускорения LZ-поиска
-------------------------------------------------------------------------------
 -
* Crossposted in RU.COMPRESS
Hello All!
  Возвратимся к нашей табличке:
=== Cut ===
set exes=*.exe *.sys *.com *.dll *.scr *.vxd *.ocx *.dpl
121 476 252    20   imp a d:\zxc %exes -r -m3
119 025 738    23   ace a d:\zxc %exes -r -m5 -d1024 -s
118 270 045    30   jar a d:\zxc %exes -r -m4 -hbd0
112 370 257    65   cabarc -r -p -m lzx:21 n d:\zxc %exes
111 899 681    93   c:\!\arjz\ARJZ.exe a d:\zxc %exes -r -jm -md1m -ms
120 447 366   165   rar a d:\zxc %exes -r === Cut ===
  RAR. Целиком и полностью использует zip'овский алгоритм (afaik) без каких-либ
о
попыток переделки.
  ARJZ. Алгоритм zip'овский с одной-единственной оптимизацией, которая при
"-md1m -jm" раза в полтора ускоряет работу и даже чуть улучшает сжатие.
Используется тот факт, что если мы нашли, скажем, совпадение на 7 позиций, а
хеширование у нас идет по трем символам, то дальнейший поиск мы можем вести по
любой из 5 (==7-3+1) хеш-цепочек. Причем если одна из этих цепочек указывает на

0 или на строку за пределами границ поиска (limit), то и двигаясь по другим
хеш-цепочкам, мы строки длиннее этих 7 символов не найдем. В результате мы
получаем ниже-заюкоженную процедуру, с ключевым фрагментом:
            offset = 0;
            uint p = previous(cur_match);
            for( int i=1; i<=len-MIN_MATCH; i++ ) {
                if( previous(cur_match+i) < p ) {
                    offset = i;
                    p = previous(cur_match+i);
                }
            }
=== Cut ===
section 1 of uuencode 5.25 of file match.zip    by R.E.M.
begin 644 match.zip
M4$L#!!0````(`+5A[B2.E#RMIP4```,1```%````34%40TB=5VUOVS80_EZ@
M_^&:8H$4V7&<]D,1QQFR95B"-=F`9L"`K3`8B;*(R*0K4G&\-?]]=Z3>*+^@
MFQ`X-GGW\%Z>.Y[XL^&%G,4@I(%<R3G79K9@)LZ"F]^4AK@LW,\0_GG]"D8C
M\)<GL.\9'9%DP1';2L/1Z/4KA,&GE%K,)4\@SIB0LYS+N<E@BG+/L^[2Q,'@
M,F1,9TX<*G&"([""SX5&1Z#$,U)6P)&.F42TE9")6D$$VA3:L,),NC;AHI#S
M/2C.Z"D0VJ3OF=U$!W:AV(CRGMY&?"I/5+HE4B1"*`^4%!1$2VYO[F:WE_<_
M7@_'F\`(1Z(50H6LE?.EPK/IR\5"&/*KB@I<@$UWF.9L/DO@^W9GZ.^<P=W-
MQXF#PN,^&;6$58:F-8Q`$V*UX!K.I^Z<8[A7H,5BF8MT#2;C$*N$#QP&',&*
MP[+@3XWKJ+H2:#A)5K'%Z%29Q$_^#"?'M39Z]5:D"4_A][O+CS<_W_UT-?OU
MEWX^=693.',N3>$HP*6CT*9UERR7":XWL@$M1G4FAN,0%=_R7/,MW/'/VGI*
MW)XRAHIA?[;HG_<IP(;"9VN,3$3:E!?Q1J6IYF3#R:1>QYQ=*9#*P(HA,!BE
M8$'@1BPXB)2RP?*"LV0-&7O"'S!7*G&9.6M9F4)`2:OK]F)JQ;JMHGJ\\KY`
MN=/*M1?W[XH_E/.@SGP43<+:U$1U<2ZUYH4)6IJ=-QP=P(%4D):F+/A!.&EU
MZO)MND#;MNI#/!/(4*6672-JGC^*)<8*)'^NRPM#0`SU:@US0J$5,L8(UM2H
M:*Z*K2I"XS>M<8-).#WKJCAN0Y#P5$B>!%V&AW!X"->7GZYG/]S<?Z+X?P@]
MB^\S1*9"`Z9U2?6HQ=]<I4'3>'6F"A/"%%,"3":>L7U9NAFLZ/OCFC^EYE[-
MD7=K518>3JP62Y';LD(+$I&FW'5>Q-?'/6?K[^1S774V5MVR@S?3MA"^?NU`
M$(JGY>C?:EBRA&B3-$*6W..`ZZ[#]Q,OB#>&\D/>2AYCEEBQ)A:05ZS@K@9/
M/U/T7%+IA\;L<\KS&E#&BP;+5VRM@7\I6>ZZ)M%!X4<!#VN#$;(H`YB+)[O)
MC)6P%]\C7VL?#2UP4'2^%?8)L2N^5%@O>#XF!H(`/8^F[T,XA]O+/]S5\@X.
M#_W`=B.<S^MNB*J6%/6B"SNMAI,>&3FDI93KZNPYE[Q@Y/`#-]3>+%%35<!"
M:=.P1G?FA3XQ^@9T\FX-L!F-VG93Z]N<4<LD/9<T^F7EH\ARPK9U,MNC=Y^A
M3K?IP'MYZ<L.QY[T&,7K4<.GJ@?2H>U_9.BXR]!QEZ$;?/H?#/4P/+9N8V@V
MTYE(3?2!QH.&KH,>"".O!JT!.=/&GD_.<HQ#P?,UM=F\3'B"7[R#/=Y;[F'L
M$F&$DE;_2RF>6$YMR"A/U#U!8U9T&H[>002^L;VN?N97W?B=MW^9:S6@2S7.
M>/QH*<ZJ"X"U@]UP3$F;<P.%2`#MBQ_1/Y5NQ-9IMN-1F:;BF<:C=G/!J.>[
MQD%7M%"E!FWXT@_R*A.QO7T>I5I).CYE(N^W#+I_=KKG>N;8'X3:C9/.4+*U
M]414J9V^0U?:KO*L"I/0ME;FQFT>2W/2O\BI;.G(BR;PWJC2T28J5</(1ATW
MDUUWFNA*=<9UFO_]S=H&=*_V.X2'@K-'[SZRY3V"=H0CI6$S_8>CTQZN-^MU
M-^PDN,2-F@SM#!7V1%-5!/:%0TS'$Q#G4^],7(DBV(B8<RK8`A\)NE66VU4\
MFT7/D/K9;C;B;I%_Z8?O94\T^T&BS66!KJ,C!W])^.[9_B4'@V[.!YV1DW)H
MWP%VO7W4S[87#W=[5?-)SY3F$OG65X\=!WW#$?O>/#;,V?O2T8MY4^+#H3?_
MO\'(;\X6G:%^:[HK)T*XJ!.X#V(XK:1(WKZ`ADUE%=R4A6P*%-?1X'\!4$L!
M`A0`%`````@`M6'N)(Z4/*VG!0```Q$```4``````````0`@`````````$U!
95$-(4$L%!@`````!``$`,P```,H%````````
`
end
sum -r/size 18110/2172 section (from "begin" to "end")
sum -r/size 41852/1555 entire input file
=== Cut ===
  Что касается трех оставшихся программ, то для начала замечу, что jar и ace
известны плохим сжатием текстов, так что есть соблазн свалить их
скорострельность именно на укороченный цикл.
  JAR'овский внутренний цикл я по этой причине не стал даже искать, хотя в jar1
6
я нашел пословное сравнение в главном цикле, что подтвердило давнее
предположение о размере его буфера (без EMS) - 32k*2.
  ACE'овский главный цикл я нашел, его адрес в exe'шнике - 1320h. Использованна
я
версия ace:
ACE v1.2a            Copyright by Marcel Lemke            May 18 1998  11:01:01
Цикл мне показался совершенно безыскусным, нет даже "lazy evaluation of
matches". Единственная подвижка по сравнению с zip'ом - помимо стандартных
ограничений на расстояние до строки и длину хеш-цепочки есть еще дополнительное

ограничение - в зависимости от расстояния, на котором мы сейчас находимся, длин
а
хеш-цепочки еще дополнительно ограничивается, т.е. стандартное
    } while (--chain_length != 0 &&
             (cur_match = previous(cur_match)) > limit);
заменено на
        chain_cnt++;
    } while (--chain_length != 0 &&
             (cur_match = previous(cur_match)) > limit &&
             (chain_cnt < limita[ (strstart-cur_match) / 65536 ] );
Bulat
---
 * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61)
- $20. COMPRESSION (2:5093/26) ----------------------------------- RU.COMPRESS
 -
 Msg  : 919 of 1551 -904
 From : Bulat Ziganshin                     2:5093/61       Fri 17 Jul 98 21:43

 To   : Igor Pavlov

 Subj : Секреты архиваторов. Приложение к части 1
-------------------------------------------------------------------------------
 -
* Crossposted in RU.COMPRESS
Hello Igor!
Wednesday July 15 1998, Igor Pavlov writes to All:
 >> #define prevmask (2<<20)
 IP> Т.е. (2<<20) - 1 ?
  Да, я ошибся.
 IP> и что магическое число 2<<20 значит?
 IP> для какого словаря оно задано
  Это значит, что самый большой файл, который я тестировал - меньше двух метров
.
Код для обработки заворотов я писать не стал.
 >> Pos    far prev_ge[2<<20];
 >> Pos    far prev_lt[2<<20];
 IP> Что в этих массивах хранится?
  У zip'а в массиве prev - ссылки в хеш-цепочке. Здесь - ссылки налево и направ
о
для хеш-дерева.
 >> #define previous_ge(s)      (prev_ge[(s)&prevmask])
 >> Hу разумеется, я забыл про текст основной процедуры. Извиняюсь. Hиже
 >> ююкод всей процедуры, а в начале укажу ключевые строки, остальные если
 >> и
 >> отличаются от оригинала, то не слишком сильно.
 >> 1. В начале:
 >> Pos far *lt_ptr = &previous_ge(strstart);
 >> Pos far *ge_ptr = &previous_lt(strstart);
 IP> Это что делает?
  В ссылку налево должен быть занесен адрес первой встретившейся строки меньшей
,
чем текущая. В ссылку направо - большей. Эти строки находятся в цикле, а куда
эти найденные ссылки надо будет занести - мы сейчас запоминаем.
  После того, как в этом цикле первоначальные ссылки заполнены, мы уже пихаем
эти адреса в другие ссылки, находящиеся в уже построенном дереве - это и есть т
а
самая перестройка дерева. При этом ничего не теряется, никаких мертвых листьев.
 IP> Что такое strstart?
      unsigned near strstart;      /* start of string to insert */
 IP> Hу и так далее.
 IP> Ты бы объяснил подробнее структуры данных.
  А ты с исходниками zip'а знаком? Читай их, deflate.c
 IP> Теперь о самом алгоритме:
 IP> Есть ли такие входные данные (imho должны быть),
 IP> для которых среднее число шагов по дереву будет большим?
  Я не настолько хорошо его чуствую пока :(  Может быть - 'aaa', 'zzz', 'aaa',
'zzz',... - каждый раз дерево будет перестраиваться? И то я не уверен - может,
перестроится на первом уровне, а дальше все будет гладко.
 IP> Ты проверял какое получается среднее число шагов?
  Примерно я говорил - кол-во проверяемых хеш-цепочек увеличивается в несколько

раз (потому что мы не можем теперь их пропускать), а общее кол-во прощупываемых

элементов несмотря на это уменьшается в несколько раз.
 IP> Если ты хорошо разобрался в CABARC'е, скажи, пожалуйста, почему он
 IP> так хорошо жмет book1? Там должна быть какая-то хитрость.
 IP> И эта хитрость imho должна быть в этой процедуре longest_match.
  Если б я хорошо разобрался, то не писал бы сюда, а сел и сам такое же сделал
;) В longest_match я больше ничего не заметил - посмотри сам, я ссылки дал.
Bulat
---
 * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61)
- $20. COMPRESSION (2:5093/26) ----------------------------------- RU.COMPRESS
 -
 Msg  : 944 of 1551 -928
 From : Bulat Ziganshin                     2:5093/61       Mon 20 Jul 98 22:51

 To   : Gleb Polyakov

 Subj : Секреты архиваторов. Часть 1: LZ-поиск в CABARC
-------------------------------------------------------------------------------
 -
* Crossposted in RU.COMPRESS
Hello Gleb!
Thursday July 16 1998, Gleb Polyakov writes to Bulat Ziganshin:
 GP>         А что такое е8 не pасскажешь ли?
  Это команда x86 - относительный CALL. Если смещение, идущее после этой
команды, преобразовывать в абсолютный адрес, сжатие 32-разрядных EXEcutables
улучшается на 5-10%%. Invented in CABARC, сейчас реализовано так же в ufa/777,
imp, arjz. Вот соответствующий кусочек:
inline long translate( long n, long pos ) {
    if( n>long(-pos) && n<long(filesize-pos) ) {
        //  printf( "\n%06x: %08x-->", pos, n );
        n += pos;
        //  printf( "%08x\n", n );
    } else if( n>0 && n<long(filesize) ) {
        //  printf( "\n%06x. %08x-->", pos, n );
        n -= filesize-1;
        //  printf( "%08x\n", n );
    }
    return n;
}
  Hа входе n - смещение из этой команды, pos - позиция конца команды в файле,
filesize - длина файла. Hа выходе - абсолютное смещение или неизмененное n, есл
и
это никак не может быть CALL'ом (мы попадаем за пределы файла ;) Кодирование
однозначное, как нетрудно заметить.
 GP>         И что понимается в данном случае под "интеллектуальной
 GP> соpтиpовкой"?
  Сортировка файлов для solid, объединяющая достоинства "-msgenp" (group,
extension, name, path - в общем, как в RAR) и "-msges" (group, extension,size),

что часто предлагается как альтернатива, но на самом деле иметт больше
недостатков, нежели достоинств. "-ms..." - ключик ARJZ ;)
Bulat
---
 * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61)
- $20. COMPRESSION (2:5093/26) ----------------------------------- RU.COMPRESS
 -
 Msg  : 948 of 1551 -936 +960
 From : Bulat Ziganshin                     2:5093/61       Mon 20 Jul 98 23:20

 To   : Leonid Broukhis

 Subj : Секреты архиваторов. Часть 1: LZ-поиск в CABARC
-------------------------------------------------------------------------------
 -
* Crossposted in RU.COMPRESS
Hello Leonid!
Sunday July 19 1998, Leonid Broukhis writes to Igor Pavlov:
 >>> У каждого элемента есть указатель на следующий элемент. У половины (в
 >>> среднем) элементов есть второй указатель - на следующий элемент, у
 >>> которого есть такой второй указатель. У половины (в среднем) из этих
 >>> элементов есть третий указатель .... Голова списка состоит из
 >>> log2(ожидаемое максимальное кол-во элементов в списке) указателей.
 >>> Поиск в
 >>> списке производится "артиллерийским" методом (перелет/недолет).
 >>> Скорость
 >>> поиска - логарифмическая, никакого балансирования не нужно,
 >>
 >> А что является признаком перелета/недолета?
 LB> Результат лексикографического сравнения. Каждому указателю для
 LB> скорости
 LB> должен быть придан номер символов, по которым данный элемент
 LB> совпадает с
 LB> тем, на который указатель указывает. Т.е. в сущности механика та же,
 LB> что и
 LB> с деревом.
  В imp'е используется алгоритм, который я так и не понял. Все считывается в
буфер, находятся, видимо, небольшие match'и и затем программа уходит в цикл бай
т
на 500, жрущий львиную долю времени работы программы.
  В таблице prev там хранится 22 бита смещения и 10 бит длины на каждую позицию

и этот цикл, похоже, пробегается по хеш-цепочкам и "растягивает match'и назад"
-
из пары (pos,len) делает пару (pos-1,len+1), разумеется, после проверки. Однако

как из этого можно сделать стройную систему - хоть убей, не понимаю.
  btw, возможно там окно вовсе не sliding ;)
 LB> Hет, мы ищем самую лексикографически близкую цепочку - она и будет
 LB> самой длинной.
  Hо как? Sources, please...
Bulat
---
 * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61)
=== Cut ===
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)
 Предыдущий блок
 Следующий блок
 Вернуться в индекс