История одной оптимизации
От: VladD2 Российская Империя www.nemerle.org
Дата: 26.10.05 23:58
Оценка: 127 (17) +3 -22
Сначала написал это сообщение как ответ на вот это заяление:
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
.
... << RSDN@Home 1.2.0 alpha rev. 618>>
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: История одной оптимизации
От: ansi Россия  
Дата: 27.10.05 00:18
Оценка: 1 (1) +1 :)
Почему-то мне кажется, что раньше, вместо розового слона, там была муха

В чем смысл всей этой сказки то?
Re: История одной оптимизации
От: McSeem2 США http://www.antigrain.com
Дата: 27.10.05 03:42
Оценка: 219 (21) +16 -1
Здравствуйте, VladD2, Вы писали:

VD>Сначала написал это сообщение как ответ на вот это заяление:

VD>http://rsdn.ru/forum/Message.aspx?mid=1454333&amp;only=1
Автор: Pavel Dvorkin
Дата: 25.10.05

VD>

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

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

Влад, это все хорошо конечно, спасибо за рассказ. Но как-то злобно очень. Типа "вы все п...сы, а я — Дартаньян". Ну почему ты так неуважительно отзываешься о Павле Дворкине? Он старше нас с тобой, между прочим. И гораздо опытнее. И то, что твое мнение не совпадает с его, ни в коем случае не значит, что ты прав, а он — нет. Выражаясь тюремной феней, ты пытаешься "зачморить" всех, кто с тобой не согласен. Не надо этого делать. Это очень некрасиво выгдлядит.

Я тоже писал резидентный help. Я его так и назвал — MaxHelp или MHelp. Занимал в памяти он 5K и работал очень шустро. Это был полноценный гипертекст, только без картинок. К нему прилагался компилятор, собирающий файлы из текстового вида. И этот компилятор тоже читал файлы по-символьно. Но через некую свою прослойку. Я очень быстро обнаружил, что fread по одной букве работает медленно. Далее я обнаружил, что вызов int21 для прямого посимвольного чтения — это еще раз в 100 медленнее. Каков выход? — читать блоками через int21, а выдавать по-байтно. Фактически, это эмуляция fread, но с гораздо меньшими накладными расходами. Буфера в 256 байт оказалось вполне достаточно. Это для компилятора. В самом резиденте надо было читать как вперед, так и назад. Ну что же, для этого делается всего-навсего двойной буфер — 512 байт и он "поддергивается" в нужные моменты функцией memmove. Все! Была обеспечена и скорость и O(1) памяти. Работало и на меговых файлах без какой-либо видимой задержки на 286/12MHz. Я потратил на отработку этой стратегии пару дней. Это является тривиальнейшей задачей. И "программизм" как таковой здесь вообще ни при чем. Здесь требуются инженерные навыки или даже просто "common sense" как говорят буржуи-пиндосы.

Так что ты хотел сказать-то этой историей? Продемонстрировать свое невежество? Думаю, что нет. Но тем не менее, у тебя это вполне получилось. Извини за резкие слова.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[2]: История одной оптимизации
От: Дарней Россия  
Дата: 27.10.05 04:15
Оценка: 5 (3) +2 -1 :))) :)))
Здравствуйте, McSeem2, Вы писали:

Не ко всем мудрость приходит со старостью. К некоторым старость приходит в одиночку. (С)
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re: История одной оптимизации
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 27.10.05 05:41
Оценка: 7 (1)
Здравствуйте, VladD2, Вы писали:

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


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


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

Жаль только, что твой рассказ был переполнен наскоками на Павла Дворкина, это очень сильно впечатление от всей истории подпортило.

А вот по поводу блочного и посимвольного чтения данных из файла лет 5-6 назад мне статья попалась (кажется в "Открытых системах"). Там метрики приводились для какого-то Unix-а. Так вот меня поразило, что во многих случаях блочное чтение не имеет преимуществ над посимвольным чтением. Учитывая, что сейчас файловые системы очень умные, решение о том, читать ли данные посимвольно или поблоково, лучше принимать с учетом конкретной ОС и железа.
... << RSDN@Home 1.1.4 stable rev. 510>>


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[2]: История одной оптимизации
От: Pavel Dvorkin Россия  
Дата: 27.10.05 06:07
Оценка:
Здравствуйте, eao197, Вы писали:


E>На самом деле это получилась интересная, увлекательная и поучительная история о том, как ошибка при проектировании программы повлияло на ее производительность и расширяемость. Имхо, если бы на момент написания своего компилятора ты имел ну чуть-чуть больший опыт, все, что тебе пришлось сделать -- это задействовать собственный вариант getch, который прятал бы от тебя работу с буфером прочитанных из файла данных.


Естественно. Мне с подобной деятельность пришлось столкнуться во времена незабвенной СМ-4 и Фортрана. Там вообще никаких строк в смысле ASCIIZ не было, а ввод/вывод был либо Фортрановский (о нем умолчу , либо можно было с диска читать прямо-таки сектора. Фортрановский ввод не годился , поэтому я читал сектора, из них брал то что надо, а функция чтения при необходимости подчитывала новый сектор. В общем, все это старо как мир.
А кстати, как fread-то работает ? Там ведь ввод буферизованный (кстати, понимаю, почему, но уж не совсем понимаю, зачем сейчас — Windows и так все кеширует). Т.е. читается в буфер где-то в, условно говоря, <stdio.h>, а оттуда возвращают порции, и если надо, делают новый запрос для перегрузки буфера.

E>А вот по поводу блочного и посимвольного чтения данных из файла лет 5-6 назад мне статья попалась (кажется в "Открытых системах"). Там метрики приводились для какого-то Unix-а. Так вот меня поразило, что во многих случаях блочное чтение не имеет преимуществ над посимвольным чтением. Учитывая, что сейчас файловые системы очень умные, решение о том, читать ли данные посимвольно или поблоково, лучше принимать с учетом конкретной ОС и железа.


ИМХО файловые системы здесь ни при чем. Они все равно посимвольно читать не будут . Чтение идет кластера или нескольких кластеров. То, что называется посимвольным чтением (из файла, конечно) , т.е. fgetc и т.п., есть в действительности чтение из буфера , который в "<stdio.h>", а он перегружается, как уже сказано. И время уходит здесь не на чтение, а просто на обращения к функциям — либо один вызов fread (на 1000 байт), либо 1000 fgetc (на один байт). А ОС об этих наших потугах и не узнает скорее всего, если только при этом чтении 1000 байт не придется подчитать новый кластер.
With best regards
Pavel Dvorkin
Re[2]: История одной оптимизации
От: McSeem2 США http://www.antigrain.com
Дата: 27.10.05 06:22
Оценка: +2
Здравствуйте, eao197, Вы писали:

E>А вот по поводу блочного и посимвольного чтения данных из файла лет 5-6 назад мне статья попалась (кажется в "Открытых системах"). Там метрики приводились для какого-то Unix-а. Так вот меня поразило, что во многих случаях блочное чтение не имеет преимуществ над посимвольным чтением. Учитывая, что сейчас файловые системы очень умные, решение о том, читать ли данные посимвольно или поблоково, лучше принимать с учетом конкретной ОС и железа.


Это все надо проверять. Но я точно знаю, что в MS-DOS вызов int21 был очень дорогим сам по себе. Разница же заключается в том, что полагаясь на эффективность системных вызовов, ты обязан верить, что это быстро. Но при определенных обстоятельствах нас может поджидать жестский облом. Если же придерживаться предположения, что системные вызовы в общем и целом дорогие (хотя в каких-то редких частных случаях это может быть и не так), эта прослойка с собственной буферизацией в 90% случаев ускорит чтение в 10 раз, а в 10% случаев — может замедлить на 10%. Вот, собственно и вся разница. Конечно же, сейчас нет ни малейшего смысла городить свою буферизацию. Просто потому, что CRT хорошо отработана на всех платформах и мы знаем это. Но когда это было неочевидно, самодельная буферизация имела смысл.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: История одной оптимизации
От: Gomes Россия http://irazin.ru
Дата: 27.10.05 06:49
Оценка: 6 (1) :)
Здравствуйте, VladD2, Вы писали:

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


Круто. А я на БК-1001 квадратики рисовал
Re: История одной оптимизации
От: vdimas Россия  
Дата: 27.10.05 06:54
Оценка:
Здравствуйте, VladD2, Вы писали:

[...]

Так вроде можно было управлять буфером FILE в С. По умолчанию он там, вроде, 256 байт был.
Re[2]: История одной оптимизации
От: Шахтер Интернет  
Дата: 27.10.05 07:51
Оценка: +3
Здравствуйте, eao197, Вы писали:

E>А вот по поводу блочного и посимвольного чтения данных из файла лет 5-6 назад мне статья попалась (кажется в "Открытых системах"). Там метрики приводились для какого-то Unix-а. Так вот меня поразило, что во многих случаях блочное чтение не имеет преимуществ над посимвольным чтением.


Насчет "какого-то Unix" а не знаю. Но в любой защищённой OC вызов системных функций дорог сам по себе.
И если ты будешь читать файл по байту ими, то это будет очень медленно. По любому необходима буферизация в адресном пространстве процесса.

E>Учитывая, что сейчас файловые системы очень умные, решение о том, читать ли данные посимвольно или поблоково, лучше принимать с учетом конкретной ОС и железа.


Реализация буферизации -- тривиальная задача. Тем более, что обычно для доступа к файлам используются уже готовые библиотки, где буферизация уже реализована. Так что буферизация доступа к файлу -- это тот случай, когда надо не думать, а действовать.
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re: История одной оптимизации
От: Lloyd Россия  
Дата: 27.10.05 08:21
Оценка: -1
Здравствуйте, VladD2, Вы писали:

Очень поучительная иллюстрация к тому, что по-байтово считывать из файла действительно не стиот.
... << RSDN@Home 1.1.4 stable rev. 510>>
Re[2]: История одной оптимизации
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 27.10.05 09:01
Оценка: 2 (1)
Здравствуйте, eao197, Вы писали:

E>А вот по поводу блочного и посимвольного чтения данных из файла лет 5-6 назад мне статья попалась (кажется в "Открытых системах"). Там метрики приводились для какого-то Unix-а. Так вот меня поразило, что во многих случаях блочное чтение не имеет преимуществ над посимвольным чтением. Учитывая, что сейчас файловые системы очень умные, решение о том, читать ли данные посимвольно или поблоково, лучше принимать с учетом конкретной ОС и железа.


Нашел эту статью: http://www.osp.ru/os/2001/03/063.htm

Как всегда, память меня подвела и речь шла не о том
Приношу извинения всем, кого ввел в заблуждение.

А вообще-то я имел ввиду, что getch из стандартной библиотеки не обязательно будет каждый раз обращаться к OS. Более вероятно (чем лучше библиотека), что getch берет данные из внутреннего буфера, а запрашивает OS только при его опустошении. Причем стандартная библиотека может знать об особенностях OS и ее файловой системы, поэтому подчитываться могут блоки оптимального размера (скажем, сразу класстер или сектор). А если мы сами начнем читать данные блоками и не угадаем с размером блока, то ручной буфферизированный ввод будет проигрывать getch.
... << RSDN@Home 1.1.4 stable rev. 510>>


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[3]: История одной оптимизации
От: Дарней Россия  
Дата: 27.10.05 10:56
Оценка:
Здравствуйте, eao197, Вы писали:

E>А вообще-то я имел ввиду, что getch из стандартной библиотеки не обязательно будет каждый раз обращаться к OS. Более вероятно (чем лучше библиотека), что getch берет данные из внутреннего буфера, а запрашивает OS только при его опустошении. Причем стандартная библиотека может знать об особенностях OS и ее файловой системы, поэтому подчитываться могут блоки оптимального размера (скажем, сразу класстер или сектор). А если мы сами начнем читать данные блоками и не угадаем с размером блока, то ручной буфферизированный ввод будет проигрывать getch.


К тому же это будет создавать дополнительный расход памяти.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[2]: История одной оптимизации
От: sch  
Дата: 27.10.05 11:48
Оценка: -1
> В чем смысл всей этой сказки то?
Сдается мне, что весь смысл этой сказки заключается в том, что нужн было использовать FILE * и fopen(), fread(), fgetc(), а не
open(), read()...
Posted via RSDN NNTP Server 1.9
Re[3]: История одной оптимизации
От: FR  
Дата: 27.10.05 15:07
Оценка: 1 (1) -1
Простенький тест

//------------------------------------------------------------------------------

#include <stdio.h>
#include <time.h>

//------------------------------------------------------------------------------

void Test(size_t size)
{
char *buf = new char[size];
double sum = 0.0;

clock_t t1 = clock();
if(FILE *file = fopen("test.txt", "rb"))
 {
 while(!feof(file))
  {
  size_t count = fread(buf, 1, size, file);
  for(int i = 0; i < count; ++i) sum += buf[i];
  }
  
 fclose(file);
 clock_t t2 = clock();
 printf("size = %d, time = %d, sum = %f\n", size, t2 - t1, sum); 
 }
 
delete [] buf; 
}

int main(int argc, char *argv[])
{
Test(1);
Test(1);
Test(1);

Test(1024);
Test(1024);
Test(1024);

return 0;
}

//------------------------------------------------------------------------------


у меня на 7mb файле выдает такие результаты:

size = 1, time = 2383, sum = 332666720.000000
size = 1, time = 2333, sum = 332666720.000000
size = 1, time = 2334, sum = 332666720.000000
size = 1024, time = 120, sum = 332666720.000000
size = 1024, time = 110, sum = 332666720.000000
size = 1024, time = 130, sum = 332666720.000000


разница в почти 20 раз фигня?
Re[4]: История одной оптимизации
От: McSeem2 США http://www.antigrain.com
Дата: 27.10.05 15:32
Оценка:
Для более адекватной оценки надо бы убрать вызов feof(file), тем более, что конец файла можно отловить по count из fread. Но не думаю, что результат будет кардинально другим. Вообще-то я удивлен такой большой разницей. Хотя приколы случаются. Помню как у нас около 30% времени отъедала isspace() на винде. Оказалось, что оно аж ядро вызывает! Понятно, что кодировки, locale и все такое, но нам тогда не требовалось ничего, кроме банального 7-битного ASCII.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: История одной оптимизации
От: gear nuke  
Дата: 27.10.05 19:36
Оценка: 1 (1)
Физически прочитать один байт из сектора невозможно, нужно считать весь сектор. Если глупый ДОС (хотя он имел полное право) ничего не буфирезировал, то 512 раз счтитывать один и тот же сектор... ИМХО, отличный пример, что нужно знать не только низкоуровневые вещи в софте, но и железо.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Re[5]: История одной оптимизации
От: FR  
Дата: 28.10.05 03:38
Оценка:
Здравствуйте, McSeem2, Вы писали:

MS>Для более адекватной оценки надо бы убрать вызов feof(file), тем более, что конец файла можно отловить по count из fread. Но не думаю, что результат будет кардинально другим. Вообще-то я удивлен такой большой разницей. Хотя приколы случаются. Помню как у нас около 30% времени отъедала isspace() на винде. Оказалось, что оно аж ядро вызывает! Понятно, что кодировки, locale и все такое, но нам тогда не требовалось ничего, кроме банального 7-битного ASCII.


Да бывает
А мораль такая если работаешь с большими объемами то проверять нужно обязательно, иначе можно нарватся на то что программа грузится минуты вместо секунд.
feof убирать пробовал реакции ноль.
Re[6]: История одной оптимизации
От: Дарней Россия  
Дата: 28.10.05 04:46
Оценка: 76 (2) +4
Здравствуйте, FR, Вы писали:

FR>Да бывает

FR>А мораль такая если работаешь с большими объемами то проверять нужно обязательно, иначе можно нарватся на то что программа грузится минуты вместо секунд.
FR>feof убирать пробовал реакции ноль.

в том то и мораль истории. Если уж ты берешься за оптимизацию, то проверять нужно всё и всегда — твои предположения "это работает быстро" и "это работает медленно" могут оказаться очень далеки от действительности.
А пытаться делать "оптимизацию всего и вся", как предлагают некоторые товарищи — это бессмыслица, и результаты ее будут никудышными, как и показал "разбор полетов"
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[7]: История одной оптимизации
От: FR  
Дата: 28.10.05 04:56
Оценка: -1
Здравствуйте, Дарней, Вы писали:


Д>в том то и мораль истории. Если уж ты берешься за оптимизацию, то проверять нужно всё и всегда — твои предположения "это работает быстро" и "это работает медленно" могут оказаться очень далеки от действительности.

Д>А пытаться делать "оптимизацию всего и вся", как предлагают некоторые товарищи — это бессмыслица, и результаты ее будут никудышными, как и показал "разбор полетов"

Так ведь и обратный посыл который тут активно пиарится, "не оптимизируй пока не припрет" тоже неверен. Часто когда припрет оказывается уже поздно.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.