Настроение сейчас - гранатное (а, сами расшифруете, что я имел в виду...)

11 января 2009 г. Воскресенье. 18:34.
Что там сегодня, день прозрения? Ага, я заметил! Он у меня даже вчера начался!
Вчера взялся за дискретку. Сначала реализовывал вычисление функции Аккермана для пар параметров. Вроде бы и нечего делать, вроде бы и код короткий, а вот через каждые несколько минут приходят идеи, как можно оптимизировать это вычисление, и сидишь всё дальше и дольше… Некоторые идеи оказались успешными, одна же поразила меня так, что я пару часов не мог прийти в себя.
А дело было вот в чём. Функция Аккермана – дважды рекурсивна, то есть использует себя в качестве параметра. Мне пришло в голову, что стоит использовать ранее полученные результаты (загруженные в таблицу типа TStringGrid), не вычисляя их снова. С этой целью мной в функцию был внесён условный оператор, разделивший её на две ветки – "или ты считаешь, или смотришь в таблицу"…
Какой, по вашему предположению, последовал результат?..

Я был поражён!
Общая производительность программы снизилась в 1,7 раз!
Отчего это могло произойти?
Ну…
Я считаю так:
1. Ветка, отвечающая за использование результата с таблицы, я думаю, использовалась редко, поэтому полагать, что функция StrToInt() работала дольше, чем завершение вычисления, можно, но необязательно.
2. Разумеется, сравнение строк – ячейки таблицы с пустой строкой '' , тем более в дважды рекурсивной функции, должно было замедлить выполнение, но настолько ли?
3. Видимо, (пока что это только моё предположение; ответ я могу найти или прийти к нему самостоятельно, но не сейчас), блок функции, содержащей условный оператор, делящий её на две части, препятствует эффективной оптимизации кода компилятором. Возможно, выбор одного из двух путей при каждом вызове препятствует возникновению одновременно выполняющихся фрагментов кода (если такие, разумеется, есть). Жаль, конечно, что я пока что не знаю ассемблера, и вынужден лишь строить предположения.
Ну ладно, это было вчера…
А сегодня мне с утра пораньше стукнула в голову мысль, которая меня донимала и раньше, но я почему-то отмахивался.
Мы ведь по теории информации и кодирования архиватор пишем. Ну… пишу, в общем-то, только я… со всей группы… а может, и, со всего потока. Потому как все забили – вслед за лектором Андреем Николаевичем Стрюком, который совершенно не появлялся на парах.
За что он будет ставить зачёт, сказать сложно… наши шутят, что он и на зачёт не придёт… или что никто назло ему не придёт… неважно!
Итак, что же предлагал Стрюк? Он предлагал нам написать архиватор, реализующий один из алгоритмов сжатия – или статистический (Хаффмана или арифметического кодирования), или же словарный (LZ77, LZSS, LZ78), а также применяющий защиту от потерь данных (сохранение контрольной суммы CRC) и защиту паролем от несанкционированного доступа. Из этого мой архиватор знает только сжатие :( , потому как я всё не наберусь отваги почитать про CRC и защиту паролем. Нет лектора – нет охоты…
Так вот, реализацию сжатия алгоритмом Хаффмана я реализовал ещё в начале октября. Отладки совершенно не потребовалось – до сих пор я не встретился ещё ни с одним глюком в своём архиваторе. Как я уже говорил, CRC и паролирование я так и не сделал, но регулярно (по приколу) сажусь за его оптимизацию. Чего я там только не делал – и сортировку "пузырьком" на быструю заменил, и поиск перебором – на бинарный, и много других мелочей… Но, как оказалось, главный предмет оптимизации остался нетронут.
Дело в том, что с диска я читал по 1 байту. Тогда, в начале октября, я разыскал Стрюка и задал волновавший меня вопрос – важно ли читать байты файла блоками? Андрей Николаевич сослался на 128-байтовый буфер компиляторов Borland Delphi и Turbo Pascal, а также на факт кэширования записи – как программного (на уровне драйвера), так и аппаратного (на уровне микропроцессора жёсткого диска), чем успокоил меня. Больше у меня желания буферизовать чтение/запись не было :)
Конечно, меня смущал и повергал в краски стыда и смутных сомнений "Файловый монитор" Марка Русановича. На фоне разных приложений, в том числе WinAmp, который спокойно производит чтение приблизительно двух блоков в секунду размером в несколько килобайт, мой архиватор каждую секунду гордо посылал системе десятки тысяч запросов по одному байту :)) Мало-помалу, я всё более убеждался в том, что такое обращение недопустимо.
И вот… говорили, сегодня день прозрения?.. да, есть такое… меня с утра посетила стойкая идея буферизовать чтение/запись. Надо сказать, внедрение поблочного чтения/записи в алгоритм сжатия я произвёл подозрительно быстро, а вот аналогичные действия в алгоритме распаковки вызвали затруднения. Впрочем, они были скоро решены. Добившись полного исчезновения в модулях Compress и Decompress вызовов таких процедур и функций, как Read(), Write() и Eof() – вместо них стали вызываться мои подпрограммы, работающие поблочно, я приступил к тестированию.
Скажу честно! Ненавижу тестирование! Оно меня напрягает и выводит из себя. Никогда не умел и не умею находить ошибки в каких-либо программах – своих или чужих. Мне проще избежать ошибки, чем найти её. Поэтому обычно, испытывая потребность в тестировании свое программы, я обращаюсь к Жушману (сейчас) или Марцеву (раньше), которые шустро вылавливают в ней все баги.
Так вот, в ходе тестирования внезапно оказалось, что не всё так просто.
Дело в том, что с диска я намеревался читать блоки постоянного размера – по 64 КБ. Именно по 64 КБ, потому как при уменьшении этого размера, я полагаю, будет наблюдаться снижение производительности, а при увеличении – наш дорогой Windows будет его перебивать на блоки по 64 КБ :))). Я было так прикололся – стал читать блоками по 640 КБ; смотрю в Файловый монитор – и меня начинает потихоньку распирать от увиденной картины: после каждой однократной записи на диск блока размером 640 КБ Windows генерирует девять внутренних сообщений, перемещающих с потока $ReplaceAttribute2 в конец результирующего файла… блоки по 64 КБ ! Что лишний раз заставляет остановиться именно на этом размере блока.
Так вот. Кроме поблочного чтения/записи, у меня также производится поблочное сжатие/распаковка. А я с утра, не особо соображая, спутал одни блоки с другими, и у меня размер блока чтения/записи приравнялся к размеру блока сжатия/распаковки. Как показало тестирование, такое уравнение недопустимо, поэтому я остановился в раздумьях. Бросить всё как есть, оставив производительность архиватора зависимой от размера блока сжатия, или же разъединить буферизацию на два независимых уровня?
Разъединение оказалось несложным, и чтение стало производиться таким сложным образом. Данные поблочно читаются с файла в буфер чтения и, поблочно копируясь с буфера чтения, кодируются.
Проблема вот в чём. Даже невооружённым глазом видно, что программа делает глупость – она теряет в производительности на переходе с одного уровня буферизации на другой. Дело в том, что блоки сжатия я формирую, читая с буфера чтения по 1 байту! Ну, моя процедура, заменяющая Read(), возвращает с буфера только 1 байт! Иначе её реализация была бы посложнее.
Почему же я не копирую области памяти напрямую – с одного буфера в другой? Да потому, что у меня нет никаких гарантий на то, что нужный мне размер блока полностью считан в буфер чтения!
Из этого вижу лишь два выхода. Первый – начинать загрузку блока сжатия всегда с начала буфера чтения.
Понятно, что в этом случае буфер и блок сжатия станут эквивалентны, и мы вернёмся к ситуации, описанной на полстраницы выше.
Второй – избегать дробления блоков в буфере чтения. В таком случае, буфер, очевидно, должен иметь размер, кратный размеру блока сжатия, то есть, SetLength(BR, (65536 div BSize)*BSize) – установка размера, равного наибольшему целому числу, кратному размеру блока и не превышающего лимит в 65536.
Но сегодня я уже не стал этим заниматься. Просто так не хочется ломать автономность написанных процедур утром процедур! Использующиеся в них переменные и массивы нигде более не модифицируются… пока что… что упрощает понимание их работы. Когда же мне придётся извне влиять на ход их работы, эта понятность будет разрушена. А как мне иначе известить буфер о том, что я только что особым образом скопировал из него столько-то байт? :)
Кстати, введение буферизации ускорило распаковку более чем в 2 раза, а сжатие – почти в 10 раз!
Да, ещё! Понял я сегодня наконец, как реализованы строки в Delphi. Оказывается, строки, а также динамические массивы в Delphi являют собой, как и в C, всего-навсего указатели. Поэтому функция sizeof(), в случае передачи ей статического массива, вернёт его размер в байтах, а в случае передачи динамического массива, будет всегда равна размеру указателя (4 байта). Для определения же длины массива в Delphi используется функция length(). Помню, я поначалу смутился – в Turbo Pascal мне никогда не приходило в голову передавать функции length() что-либо, отличное от строки. Проверка показала, что в Turbo Pascal это было действительно недопустимо :)
Вот такой, я, значится, фигнёй маялся весь день.
Ща отдохну, про Винни почитаю, и продолжу.
P.S. (Расшифровка к настроению.) Щас сижу, гранат поедаю. Прикольный фрукт! (Если не фрукт – неважно.) На цвет, запах и вкус – натуральная роза! Не хватало опьянеть вконец!
P.P.S. Что-то медленно я мыслю: 9.5 слов в минуту!