Об эффективности программ
От: Pavel Dvorkin Россия  
Дата: 05.10.05 11:35
Оценка: 653 (89) +13 -3 :)
Собрался наконец написать. Минусов мне за эти тезисы поставят, это уж точно. Ну
что же — к счастью, я уже не в том возрасте, когда падение или рост рейтинга
могут серьезно повлиять на самочувствие.

Итак...

Когда компьютеры были большими, память у них была маленькой и
быстродействие тоже. И поэтому гуру от этих ЭВМ ничего, кроме ассемблера
(автокода, по-тогдашнему) и не признавали. А на нас, всяких там алгольщиков или
фортранщиков, смотрели свысока — писать , мол, эффективные программы не умеют,
только зря машинное время расходуют. Мы, конечно, с ними на словах не
соглашались и всякие аргументы приводили, но в глубине души их правоту, пожалуй,
признавали.
И действительно, как было не признать! Пока программа небольшая и в память
помещается — ладно, живите и радуйтесь! Ну а как побольше стала ? Тут-то и
придется признать свое бессилие. А гуру, им что, всегда что-нибудь придумают.
Кто-нибудь из нынешнего поколения слышал про "самоубийство программ" ? Нет, это
не стирание EXE-файла во время его работы. Это когда программа во время своей
работы использует память, занятую своими командами (которые уже отработали и
больше не потребуются) под свои данные. Вряд ли кому-нибудь придется этим сейчас
заниматься, и слава богу. А вот когда у Вас всего 18 Кбайт, то и таким не
пренебрегали.
Потом компьютеры стали больше. И в размерах (один мой знакомый, рост у
него 1.80, любит рассказывать, как он в процессор некоторой машины входил не
наклоняясь , но все же и память с быстродействием тоже росли. Вспоминаю
сейчас ЕС-1022. Памяти там было уже 512 Кбайт, правда, сотню из них занимала ОС.
Остальные 400 делились между 3-4 одновременно работавшими программами разных
пользователей. Так что на тех, кто заказывал больше 200 Кбайт, на ВЦ смотрели
довольно косо — за наш счет ведь! И правильно смотрели — нечего тут жировать!
Компилятор с Фортрана на 96 КБайтах работал, c PL/1 — даже на 64 Кбайтах (до сих
пор не знаю, почему — PL/1 сложнее Фортрана), линкеру тоже 96 Кбайт хватало, а
тебе так 200 надо ? Иди-ка, батенька, да перепиши свою программу как следует. До
сих пор помню, как потратил несколько часов, пытаясь написать вычисление
произведения трех матриц без промежуточной матрицы (было это на заре моей
карьеры, а я ведь химик .И студента своего, который без надобности
транспонировал матрицу, заведя еще одну, так отругал, что он долго это помнил :-
)
В общем, если говорить серьезнее, эффективность у нас была всегда на
первом плане. Не как-нибудь написать, а наиболее эффективным способом,
не любой алгоритм использовать, а лучший для этого случая. На этом мы
прочно стояли.
Поймите меня правильно. Это вовсе не значит, что мы оптимизировали
все и вся. Код, который работает 0.1 сек и занимает 100 байт, никто
не оптимизировал. И то, что оптимизировать нужно самые внутренние
циклы, мы прекрасно знали. Не об этом речь. А о том, что при написании
программ была определенная культура, требовавшая памятью не сорить
без надобности, первый попавшийся алгоритм не применять, а искать хороший,
ну и т.д.
Потом компьютеры стали меньше. И по размерам, и по быстродействию и
памяти тоже. Не потому, что большие исчезли, а потому, что малые
появились. Их так и называли — мини-ЭВМ. СМ-4, к примеру. Памяти у нее
было поменьше, быстродействие похуже, чем у той же ЕС-1022, зато у нее
было неоспоримое преимущество — она была моя! Никакого тебе ВЦ с десятком
конкурентов, никаких "Правил работы на ВЦ ... института", правила такие,
какие я хочу. Все это не могло не радовать, но все же уменьшение
памяти и быстродействия огорчало и тем более заставляло бороться
за эффективность. Первая моя серьезная работа на СМ-4 — адаптировать к
ней программу, которая на ЕС занимала 220 Кбайт, а здесь их всего 256.
Когда я понял, как ее в свободные 200 уложить — выяснилось, что понял
я неправильно, и для кода я могу рассчитывать только на 64 Кбайта, а
остальную память только под данные можно использовать. Вот тут-то я
и покрутился. Вы никогда не делали оверлейные структуры 9-го уровня ?
Даже не знаете, что это такое ? Ну и прекрасно, и не надо вам знать
Потом машины стали совсем маленькими, а быстродействие и память
уменьшились до неприличия. Проще говоря, пересел я на Ямаху-1. Память 64 Кбайта,
частота 2MHz, флоппи-диск — живи и радуйся! В общем, 8-битная машина. И вот на
этой машине я увидел чудо.
Чудо называлось Turbo Pascal 1.0. Сказать, что он меня поразил — не то
слово. И не меня только. Все, кто до этого Ямаху не видел (а их в Омск
очень немного попало тогда) и кому я о нем говорил, отвечали мне одинаково-
такого не может быть!
В 64 Кбайтах размещались
MSX-DOS, точнее , ее резидентная часть — несколько Кбайт
сам компилятор Turbo Pascal. Сидел резидентно в памяти.
редактор текста Turbo Pascal, вполне приличный по тому времени.
исходный текст программы, набранный в этом редакторе.
рабочая программа (машинные команды). Да-да, я не оговорился.В обычном
режиме компиляции программа размещалась в ОП и на диск не записывалась. И
не думайте, что это какой-то паршивый интерпретатор был, нет, самый
настоящий компилятор. Чуть позже (я уже в университете работал) был
у нас класс "Ямаха-2", память там была уже 128 Кбайт, а дисков на рабочих
станциях не было. Так вот. половину из этих 128 Кбайт мы отводили
под электронный диск, туда в начале занятия записывали Turbo Pascal,
а в конце с него переписывали на машину преподавателя .pas файлы студента.
Остановимся на минуту и вдумаемся. Итак, все это помещалось в 64 Кбайта.
Можно было, значит, написать это так, чтобы помещалось. Если, конечно,
эффективно написать. И работало это с вполне по тем временам приличной
скоростью. Не хуже, чем на СМ-4, кстати сказать. Даже лучше.
А потом компьютеры, хоть и не меньше и не больше по размерам стали, начали
резко увеличивать свою память и быстродействие. Сейчас любят вспоминать
пророчество Б.Гейтса — дескать, 256 Кбайт всем хватит. Ну, во-первых,
не думаю, что они имел в виду, что это навсегда. Во-вторых, никто,
в т.ч. Гейтс, в то время не понимал, что на свет явился не расширенный
калькулятор для научных лабораторий, а нечто такое, что перевернет
мир. А 256 Кбайт по тем временам — очень даже много. Настолько много,
что для большинства тогдашних задач это даже и не требовалось. Впрочем,
довольно скоро от этих 256 к 640 перебрались, на этом значении, правда,
надолго застряли.
Вот тут первые шаги в сторону пренебрежения оптимальностью уже и начались.
Действительно, на машине 600 Кбайт свободно, машина однопрограммная,
конкурентов нет, зачем мне пытаться программу в 100 Кбайт уложить ,если можно
все 500 спокойно использовать. Впрочем, память памятью, а есть еще и
быстродействие. Оно было еще очень маленьким, так что хотя бы в этом
плане писать все же приходилось эффективно, выжимать из машины все, что можно.
Так что писать старались все же эффективно, хотя десятком, а то и сотней
лишних Кбайт уже не мелочились.
Что было дальше — все знают. Память и быстродействие росли, эффективность
падала так же быстро, как те росли. Выяснилось, что и 1 Мбайта мало для
программы, предыдущая версия которой вполне 256 К было достаточно, да что там
1Мбайта, и 2 мало, и 16 мало, подайте 32, нет, 32 тоже мало, без 64 не
обойдемся.
Вот вам 2 классических примера.
Конечно, Object Pascal не Turbo Pascal, а Delphi 7 не Turbo Pascal 1.0.
Но, положа руку на сердце — неужели язык в 1000 раз усложнился ? Ну в 5-10
раз сложнее стал, не спорю (я имею в виду в плане написания собственно
компилятора, а не IDE, отладчика и т.д.). А раз так, то для компиляции
консольных приложений компилятор командной строки-то уж должен в 640 Кбайт
уложиться ? Дудки вам, а не 640 Кбайт. В 640 Кбайт сейчас умеют только "Hello,
World" укладывать! Пока несколько десятков Мбайт не будет, и не подходите.
Другой пример — сама Windows. Я прекрасно понимаю, что Windows NT 4 и
Windows XP — не совсем одно и то же. Но та на 8 Мбайтах работала, а эта от
128 нос воротит, подавай ей 256. А ядро, вообще говоря, претерпело не такие
уж большие изменения.
Почему же так произошло? На мой взгляд, просто потому, что требованию
эффективности просто перестали уделять нужное внимание. Если памяти много —
чего ее жалеть, зачем экономить? Какой смысл бороться за то, чтобы твоя
программа занимала 8 Мбайт, если можно взять 64 ? Даже, пожалуй, наоборот-
увидят, что твоя программа меньше памяти занимает, чем у конкурента — ну
и решат, что та более крутая
Разумеется, эффективности внимание перестали уделять не везде. Для тех
программ, которые и сейчас работают на пределе возможностей машины, за
эффективность по-прежнему борются, да еще как, иначе ведь работать вообще
не будет. Ну а там, где для предела далеко — чего это мы будем лишний
десяток Мбайт экономить ? Пусть пользователь память докупит, она нынче
дешевая!
Вспоминаю один случай из своей практики. Вел я тогда кружок в средней
школе,хорошие ребята попались, большинство из них потом наш матфак закончили. В
DOS на Turbo Pascal, лет 10 назад это было. И вот дал я одниу мальчику
упражнение, сделал он его, показал мне, посмотрел я , похвалил и добавил :"А
теперь, Илья, выкинь отсюда этот массив. Он здесь совсем не нужен, и без него
даже лучше получится". До сих пор помню тот взгляд, которым он меня одарил
Если кто-то думает, что моей целью было 200 байт сэкономить — ничего Вы
из моих рассуждений не поняли. Моей целью было научить его грамотно писать
программы, делать как следует, а не так, как получится. Не реализовать первую
пришедшую в голову идею, а подумать, нельзя ли здесь лучше сделать! Потому что
если я сейчас это пропущу — он и дальше будет так же делать, тройные циклы
писать там, где двойных хватит и лишние массивы без надобности заводить.
Меня тут некоторые уже обвиняли в "наездах" на C# и .Net. Вообще-то
я такое понятие "наезд" — не признаю. Если к любимой системе программирования,
компилятору и т.д. подходить с позиций "В России нет еще пока команды лучше
Спартака" — тогда, конечно, всякая критика левого крайнего Спартака есть явный
наезд . Если же подходить к этому вопросу объективно, скажем, с позиций
человека, который вообще ни за одну команду не болеет или болеет за Реал-Мадрид,
то сравнение левого крайнего Спартака и левого крайнего ЦСКА есть дело вполне
разумное, и если вывод будет не в пользу спартаковца — ничего страшного тут нет,
что же поделаешь... Другого левого крайнего искать надо, а может, стоит из
ЦСКА его переманить .
Так что в том. что примеры я буду приводить именно из области .Net — не
есть наезд на нее. Просто ИМХО она наиболее ярким образом характеризует то, о
чем я пишу.
Вот простой пример. Ставя свои эксперименты, обнаружил я , что в
библиотеке .Net не имеется способа получить список файлов каталога без того,
чтобы не прочитать его полностью.

http://www.rsdn.ru/Forum/Message.aspx?mid=1398903&only=1
Автор: Pavel Dvorkin
Дата: 23.09.05


Чтобы не было неясностей — класс DirectoryInfo как он есть, не позволяет.
То, что можно самому написать, с использованием InterOp — я это и до
постинга вполне понимал.
Мне это показалось странным, и я решил вопрос в форуме задать. В общем,
объяснили мне то, что я и так знал, и подтвердили , что без InterOp это
не делается, а с ним — великолепно.

Поясню, в чем проблема здесь. С помощью Win32 функций можно записи
о файлах по одной получать. Времени на чтение всего каталога это
никак не уменьшит, это вообще не от моей программы, а от драйвера
ФС зависит, а вот памяти мне в Win32 почти совсем не надо — одна
структура WIN32_FIND_DATA на все файлы, хоть 100 их будет, хоть
миллион. А класс DirectoryInfo предлагает считать весь каталог
в оперативную память (массив FileInfo), а потом уж из него брать.

Проверил я этот DirectoryInfo на имеющемся у меня каталоге в
100,000 файлов. Работало это все 1 минуту (неудивительно, и Win32 программа
не меньше бы потребовала, FAR, к примеру, именно столько и требует)
и заняло по Task Manager 57 Мбайт.

Ну ладно, я не вчера родился, и как это на Win32 делается — еще лет 10
назад знал Так что такое решение, приведись мне это в реальной программе
писать, меня вряд ли бы устроило, и что-нибудь бы придумал или вопрос бы задал.
А как же будут делать те, кто школу более или менее эффективного (в этом
плане, только в этом плане!) программирования в Win32 не прошел, а сразу за .Net
взялся ?
Вот ведь что мне Sinclair советует

http://www.rsdn.ru/Forum/Message.aspx?mid=1404835&only=1
Автор: Sinclair
Дата: 27.09.05


Цитирую

> То, что ты умеешь делать на плюсах, в рамках дотнета ты делать не сможешь.

Некоторые концепции могут быть переиспользованы, но в целом легче изучать
дотнет с нуля.

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

http://www.rsdn.ru/Forum/Message.aspx?mid=1403668&only=1
Автор: VladD2
Дата: 27.09.05


>А производительность и не должна быть на первом месте. Она должна быть

достаточной. А на первом месте должны быть удобство и простота.

Я не против удобства и простоты. Я за. А вот что такое "достаточной" —
извольте объяснить. Если машина однопрограммная — тогда, конечно, достаточно —
если помещается в память и достаточно быстро работает. А в многопрограммной
коммунальной квартире стоит еще и о других подумать. Потому как память хоть и
большая, но не резиновая. И процессор пока что только один, как правило.

Или вот другой пример — с умножением матриц

http://www.rsdn.ru/Forum/Message.aspx?mid=1410674&only=1
Автор: Pavel Dvorkin
Дата: 30.09.05


Я не касаюсь сейчас вопроса, можно ли это было оптимизировать. В дискуссии на
эту тему

http://www.rsdn.ru/Forum/Message.aspx?mid=1408480&only=1
Автор: Pavel Dvorkin
Дата: 29.09.05


был предложен не один способ это сделать, да я и сам предложил с самого начала
свой — как ни плохо .Net я знаю, а все же догадаться несложно было. Мой вопрос в
другом — кто именно этот вариант алгоритма так реализовал, что он вместо
чего-то похожего на n^3 показывает временную зависимость, напоминающую утренние
прыжки моего кота, когда он есть просит ? . Чтобы с увеличением размера
матрицы на 100 время уменьшалось, а при увеличении еще на 200 — увеличивалось в
10 раз —
такого в моей практике еще не было! Не знаю, кто тут виноват, не знаю, кто
эту исполняющую систему писал, но об эффективности здесь говорить не приходится.

Другой пример на эту же тему. Клонирование объектов (deep copy). Рихтер
для этого советует простой способ — сериализовать в memory stream, а потом
десериализовать. Просто ? Да. Изящно ? Да. Только при этом как-то забывают,
что вместо одной операции копирования мы здесь имеем две, и вместо двух
наборов байт (source и destination) имеем три — source, intermediate и
destination.
Правда, Рихтер тут же отмечает, что эта операция может оказаться слишком
дорогой,да и не всегда возможной. Рихтер, безусловно, понимает, когда ее можно
применять, а когда не стоит. Понимают ли это все разработчики под .Net ? Боюсь,
что нет. Так что будут они этот способ использовать, не слишком задумываясь,
скорее всего. Сериализуют двумерную матрицу размером в несколько Мбайт, и все
дела

Кстати, и о самой сериализации. Нет слов — реализовано в .Net красиво. Помечаешь
атрибутом, и все! Только вот не стоит забывать, что бесплатный сэр бывает только
в мышеловках. Конечно, приятно, что за тебя все сделают — reflection, чтение
значений, запись, проход по все ссылкам и опять reflection, чтение значений,
запись. А между тем грамотно написанный код в той же MFC, использующий
сериализацию, сделает в принципе то же самое без того, чтобы изучать
структуру класса(ов) и тратить на это время и память.


В в результате такого отношения — "что нам десяток Мбайт жалеть, что
нам с того, что это здесь на 100 мсек дольше выполняться будет", получается то,
о чем хорошо сказал Cyberax

http://www.rsdn.ru/Forum/Message.aspx?mid=1409923&only=1
Автор: Cyberax
Дата: 29.09.05


>Чего-то я начинаю в этой истине сомневаться. Слишком часто все "не

тормозит" (или не жрет памяти) в отдельности, но работает со скоростью
улитки (или жрет гигибайты) в целом.

>Причем наблюдается это, в основном, у современного софта — та же ICQ без

зазрения совести сжирает 20 метров памяти. Какой-нибудь WinAmp еще 20
метров. Вот так и не остается памяти для чего-нибудь полезного....

Хороший, кстати, пример — ICQ. Написана она не на .Net ИМХО (давно
ее не держу, у меня Trillian, ему 7.5 Мбайт хватает . По существу — текстовый редактор плюс модуль связи с winsock. Все остальные возможности его используются
один раз в неделю, если не в месяц. Я ничего против них не имею, но
сидели бы они на диске в виде DLL и раз в неделю загружались! Так нет,
20 Мб вынь да положь! Интересно, под что?
Если бы ICQ был в DOS времена (кстати, был?), то быть бы ему
там TSR размером в 30-40 Кбайт максимум, и писать в нем свои SMS можно было
бы так же, или почти так же, как сейчас, разве что в текстовом
режиме. Да, ладно, бог с ней. с DOS. Сколько места занимали первые
версии ICQ (жаль, не сохранил я тот клиент, с которым начинал лет
8 назад), и сколько сейчас? Памяти много, чего ее жалеть!

Мне тут VladD2 упрек такой кинул — дескать, писать надо , не
слишком думая об эффективности, а потом узкие места можно оптимизировать.
Теоретически — совершенно безупречное рассуждение. А практически — это
верно, если Вы заранее какой-то целью задаетесь — по памяти не более...
или по времени не медленнее ... Если нет — никто и не будет оптимизировать,
потому как совершенно непонятно, что и зачем. Работает каждый модуль раз в
5 дольше , чем можно было бы, памяти кушает раз в 5 больше, чем надо было
бы — что тут оптимизировать? Так и должно быть, все нормально сделали!

В результате получаем некую самодвижущуюся повозку размером с аэроплан,
ставим на нее ракетный двигатель, запускаем — едет! Едет ведь! Со скоростью
60 км/час. Ну вот это и есть настоящий аэроплан, в серию его и пусть
по дорогам ездит. А когда этим разработчикам объясняешь, что аэроплан
должен не ездить, а летать, и не 60, а 900 км/ч давать, а если Вы автомобиль
делали, то он и при двигателе внутреннего сгорания должен эти 60 (а то и 120)
давать, да и размерами должен быть раз в 20 меньше — удивляются, чего, мол,
привязался! Ездят же на нем, чего тебе надо!

А теперь перехожу к главному, что меня беспокоит.

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

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

И вот тогда этот неэффективный стиль программирования даст себя знать!
Сейчас можно просто рассуждать — чего я буду 20 Мбайт экономить, если
пользователь без проблем 256 может докупить ? А вот когда опять в жестких
лимитах работать придется — окажется, что некоторые программы, которые вполне
могли бы быть написаны, написаны не будут, или же будут написаны лет через 10
после того момента, когда они могли бы появиться! Потому что эффективно
работать большинство не умеет. Привычки у них такие — что нам стоит лишних
десяток Мбайт взять!

Не согласны ? OK, кто из вас взялся бы написать "Turbo Pascal 1.0"
образца 2005 года? Который будет работать в такой маленькой памяти — 512 Мбайт
и на таком медленном процессоре с частотой всего 3 GHz ? Боюсь, что Вы
потребуете для этого 16 Gb памяти и не менее 30 GHz . Вы же прекрасно знаете,
какие ресурсы для чего требуются, поэтому оцените их для этой задачи и получите
16 Gb и 30 GHz, А где их взять? Впрочем, нет, не потребуете. Вы даже задачу
такую не поставите — Вам она и в голову не придет: Боюсь, что мы даже и не
узнаем, что могло бы быть написанным, если бы это эффективно делалось...

Ну и к чему автор призывает, спросите Вы ? К поголовному возврату на
ассемблер
и к 64 Кбайтам ? К отказу от того пути, по которому сейчас пошло развитие ?

Я не настолько наивен, чтобы к этому призывать. Просто одно скажу :

Пишите свои программы эффективно, господа! По крайней мере настолько, насколько
это возможно!
With best regards
Pavel Dvorkin
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.