Сначала написал это сообщение как ответ на вот это заяление:
http://rsdn.ru/forum/Message.aspx?mid=1454333&only=1

Автор: Pavel Dvorkin
Дата: 25.10.05

И поверь,оптимизировать чтение из файла путем замены двух сопутствующих операторов я тоже не призываю. а вот когда некие умники начинают из файла по одному байту читать — это уже другой разговор.

Но потом решил, что слишком много написал, и эта история может оказаться интересна не только Pavl-у Dvorkin-у (его все равно этим не проймешь), а в столь глубокой подветке ее никто не заметит. Может быть эта история остановит хоть часть последователей гордых борцов за производительность бьющих себя пяткой в грудь и гордящихся своим мировозрением.

Так вот...

PD>И поверь,оптимизировать чтение из файла путем замены двух сопутствующих операторов я тоже не призываю. а вот когда некие умники начинают из файла по одному байту читать — это уже другой разговор.

От как раз на эту тему могу рассказать призабавнейшую историю из своего опыта.

Когда я только учился программировать передо мной была поставлена задача написать замену Norton Guide. Norton Guide — эта такая ДОСовская резидентная программка которую можно было активизировать поверх других текстовых ДОСовских приложений и почитать тот или иной мануал. Если не ошибаюсь к Клиперу хэлп на нем был сделан. Так вот я создал вместо него некий прообраз современного HTML-браузера, но в текстовом интерфейсе. Как и в Norton Guide, в отличии от современных браузеров, я хранил информацию в едином файле. Естественно подготавливать такой файл напрямую было невозможно. Так что на вход я получал обычные текстовые файлы размеченные специальным образом, а на выходе выдавал этот самый файл в котором запаковывалась вся информация из этих файлов.

Делал это специальный компилятор.

Писал все это дело я на С.

Первая версия этого компилятора была создана мной очень просто. Я просто читал по одному символу из входного потока, анализировал (благо грамматика была LL(1), вот только я тогда этого не знал ) его и формировал выходной поток и записывал его (уже более большими кусками) на диск в тот самый выходной файл. Потом делался второй проход в котором разрешались ссылки, но это уже детали. Главно, что в обоих проходах я как раз читал файл посимвольно.

Отлаживался я на довольно коротких файлах, так что проблем с производительностью не видел.
Конечным продуктом пользовался мой отец, который лабал на этом деле некую справочную систему по бухучету и т.п. Естественно через некоторое время отец дошел до объемов когда компилятор начал работать очень медленно. И хотя я к тому времени разработал технологию инкрементальной разработки (когда куски справочной системы отлаживаются по отдельности, а потом сливаются воедино), но все же хотелось сделать все настолько быстро насколько это было возможно.

Так вот это был первый, в моей жизни, случай оптимизации.

Как раз в это время у меня на столе появился 386 SX, аж с 4 метрами памяти на борту. Естественно я сразу же водрузил на него Windows 3.1 и выклянчил покупку С++-компилятора Семантик С++ (бывший Zortech C++, но с IDE под Windows). В поставке Семантик С++ была Win32S. Если кто не в курсе, это такой хитрый хак для 16-битного Вынь 3.1 позволяющий писать, отлаживать и выполнять почти полноценные 32-битные приложения. "Почти" потому как все вызовы 32-битного АПИ транслировались в аналогичные 16-битные вызовы, а многих функций из Вынь32 в Вынь16 попросту не было. Ну, например не было функций работы с многопоточностью. Ну, да это не важно. Возвращаемся к нашим баранам...

Почти одновременно с покупкой Семантика я докупил к машине еще 4 метра памяти и у меня ее стало аж 8 мегобайтищь! По тем временам огромная память!!! Заполучив в свое распоряжение это богатство я смекнул, что читать файлы по одному символу не эффективно!!! Вывод этот я сделал так же как Pavel Dvorkin, то есть чисто из своего чутья, которого у меня надо признать тогда было в избытке, но оно было еще круче чем чутье легендарного Pavl-а Dvorkin-а.

Так вот сделав вывод что читать по символу не эффективно я стал думать как же читать большими блоками и каков должен быть размер этих блоков. На первом проходе все было просто. Исходные файлы не превышали 32 килобайта, так что я читал их одним залпом и особых проблем не испытывал. Но вот на втором проходе я имел уже многомегабайтный файл заведомо не влезавший даже в огромнейщие 8 метров (а может это было 4, но да не важно ).

Напомню, что программировать я тогда по сути не умел. Это были первые потуги. Причем у меня не было никакой начальной базы. Зато был невероятный задор и желание свернуть горы (эх так и хочется поныть на тему какое замечательное время было тогда... ).

Так вот я принял "самое разумное решение" — я выделил буфер максимального размера и стал считывать в него (на втором проходе) часть этого самого огромного файла. Задача второго прохода (я уже ее почти не помню, но по сути...) была разрешение ссылок. Ну, на пером проходе появлялись ссылки на файлы которые читались только в последствии. Как точно я изворачивался не помню, но общий смысл был в том, что я вставлял некую заглушку которую заменял во втором проходе на конкретную ссылку.

Так вот чтобы распознать эту заглушку нужно было считывать файл последовательно и анализировать символы. Некая последовательность символов говорила, что это ссылка. Далее нужно было прочесть заглушку, найти соответствующую ей ссылку и вставить эту ссылку в выходной файл (а может в тот же, уже не помню, но не суть...).

Когда я читал символы последовательно, проблем в распознавании этой последовательности предшествующей ссылке не было. Я читал один символ... Если это был некий Х, то читал следующий, и если это был У, то было ясно, что передо мной ссылка и нужно действовать.

Похожим образом же я поступил и в буферизированной программе. Но я уже проверял подстроку а не отдельные символы. Так ведь было эффективнее! Программа получилась значительно сложнее исходной, так как приходилось подчитывать и записывать буферы, а потом проходиться по ним. За то после прогона этой версии компилятора на рабочем файле я был поражен! Она работала в разы быстрее исходной! Я был счастлив. И счастье длилось до тех пор пока отец не обнаружил, что некоторые ссылки в готовом файле по просу не работают.

Я начал искать ошибку...
Напомню, я только начинал программировать и это была моя 3-я программа в жизни (первые две — это сама резидентная программа и первая версия компилятора).

Так вот я тупо смотрел в код и не видел места с ошибкой. Через неделю потения (в прямом и переносном смысле) я таки понял в чем дело. Дело было в том, что иногда, причем очень редко, спецсимволы попадали на край блока. Казалось бы — "вот проблема?!". Но для начинающего программиста это оказалось очень не просто. Я протупил над решением еще кучу времени.

Первым моим решением было — сэмулировать getch() которым я читал данные в первом варианте компилятора. Но я тут же сделал очередное гениальное предположение в котором нисколько не сомневался. Звучало оно так — на возню с передачей символов и анализ по одному символу я убью кучу времени и моя программа станет не эффективна!

Поясню... В первой версии компилятора я проверял подстроку предшествующую заглушке посимвольно. Находя очередной символ я поднимал флаги до тех пор пока не был уверен, что передо мною именно ссылка (через много лет я узнал, что это называется ДКА, но тогда я даже подумать не мог что изобрел столь мудреную вещь ). Во-второй же версии компилятора я воспользовался преимуществом буфера и стал проверять подстроку, изученной мною к тому времени, функций strncmp()! По всем умным книжкам и моему чутью (ну, и наглец я был тогда!!! Программировал без году неделю, а уже было чутьё! Ну, да у некоторых оно не просыпается и к преклонному возрасту) использование этой могучей функции должно было существенно ускорить работу программы. Кстати, функция эта действительно быстрее чем посимвольные проверки так как она была реализована на ассемблере, а компиляторов в то время умом не отличались.

В общем, я уже не помню как я решил эту проблему, но точно помню что решил довольно эффективно (с моей тогдашней точки зрения, которая тогда была полностью аналогична сегодняшней точке зрения ну вы сами знаете кого ). Если не ошибаюсь я просто стал проверять не оканчивается ли блок на тот самый заветный символ начала гиперссылки поднимая специальный флаг который проверялся на следующем шаге итерации. Думаю, не надо объяснять, что такое решение еще больше усложнило алгоритм?! Естественно, что на такие выкрутасы начинающий упорный оптимизатор убил еще не мало времени.

Но игра стола свеч!!! Скорость была потрясающая. Все конечно относительно, но по сравнению с первой версией компилятора эта версия просто летала! Ура!!! Первая победа оптимизатора! Я был счастлив... я пел и ликовал... ровно до тех пор пока мне не рассказали про Smartdrv. Если кто не в курсе — это такой драйвер в ДОС который кэшировал доступ к жесткому диску и ускорял тем самым операции с ним.

Когда я включил смардрайв, запустил старую версию компилятора, засек время и сравнил его с временем работы нового компилятора — я был поражен. Нет, это не то слово! Я был дико ошеломлен, поражен, подавлен, удивлен и растерян!!! Я хотел плакать! Столько усилий коту под хвост. А ведь если не считать того что у нового компилятора была модная GUI-шная морда лица, то других преимуществ у него не было.

Зато код нового компилятора был ужасен! Причем ужасен на столько, что даже не опытный прграммист по сути еще не знакомый даже с принципами структурного программирования смог оценить НАСКОЛЬКО УЖАСЕН этот код!!!

Естественной реакцией было — не верю! Я где-то ошибся в измерениях!!!...

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

Сейчас, то я понимаю, что время не было убито зря. Это был бесценный опыт который не раз в последствии остановил меня от опрометчивых поступков и заставил относиться к своим предположениям более скептически. Теперь я понимаю, что даже самые маловероятные вещи могут повлиять на результат, а всякое предположение может быть неверным или практически не верным. Практически не верным значит то, что, например, чтение большим буфером и отказ от посимвольного анализа должны, да нет просто обязаны, дать повышение производительности, но на сколько? Ведь это повышение может оказаться несоизмеримо с основными затратами приложения.

Так в чем еж была моя ошибка? Думаю, почти все уже поняли в чем. Я недооценил того что основное время мои компиляторы тратили на чтение (и запись) данных с диска. По сравнению с этим разница между strncmp и банальными сравнениями была мизерной. К тому же проверял я 2-3 символа и strncmp банально не мог показать своей прыти. Зато накладные расходы на вызов функции присутствовали. Правда они присутствовали и в пресловутом getch() вызываемом при считывании каждого символа. Но опять же эти затраты мизер по сравнению с чтением данных с диска.

Когда данные читались с диска действительно по байтно чтение одного символа выливалось в ужасно затратные операции вроде передвижение головок винчестера и считывание информации с дорожки. Смартдрайв же привел к тому, что все эти накладные расходы исчезли. Функция getch() в большинстве случаев просто обращалась к буферу в памяти. Это было очень быстро. Ведь в ДОС все было в одном адресном пространстве и обращение к драйверу было не более чем банальным вызовом метода. А учитывая, что драйверы писались на ассемблере и то что параметры ДОС-овских вызовов передавались через регистры процессора скорость была даже выше чем в моей программе.

С тех времен прошло уже 12 лет (если не ошибаюсь). И мне казалось что уже все знают, что посимвольное чтение из файла — это совершенно не смертельно. Но вот появляется еще один перформанс-варьер который не был столь прозорлив чтобы наступить на эти грабли 12 лет назад, и делает смелые заявления

Автор: Pavel Dvorkin
Дата: 25.10.05

.