Дмитрий Радищев (dibr) wrote,
Дмитрий Радищев
dibr

lazy life


     Disclaimer: описанное ниже - не чисто техническое, но и литературное произведение. Поэтому технической строгости не требуйте - что-то "в реальности" может быть не реализовано или реализовано по другому. Но хочется верить, что всё описанное - как минимум реализуемо :-)

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

       (c) ibash

     Вообще, у компьютерщиков постоянно так. Чтобы программу с одной стороны не переписывать заново (и не сильно утруждать себя лишними мыслями при написании), а с другой стороны - чтобы оно работало "ещё быстрее", есть два стандартных способа: использовать "ленивое (отложенное) что-то" (самый известный пример - "отложенная запись" в дисковом кеше), или наоборот - "упреждающее что-то" (упреждающее чтение в нём же). В первом случае, когда нужно совершить какое-то действие, программе сообщают "да сделано уже, сделано" (а сделают потом, когда время будет, или когда реально понадобится), во втором - наоборот, делают какое-то действие заранее, на всякий случай - авось понадобится. Кстати, хороший пример второго подхода - упреждающее выполнение операций процессором. Процессор запускает на выполнение операции, для которых ещё не получены операнды, в надежде что когда операцию фактически начнут выполнять - операнд уже приедет - и это работает! Правда, операции иногда приходится выполнять по нескольку раз, пока не приедет операнд :-) Кстати, интересная статья, почитайте.
     Когда-то давно на тему "отложенного чего-то" я прикалывался, мол, если есть отложенная запись - давайте сделаем отложенное (не "упреждающее", а именно отложенное) чтение. Скажем программе, что то что она хотела прочитать - прочиталось, а прочитаем как-нибудь потом. Тогда я думал, что это прикол. Сейчас понял - это вполне реально: мы просто пометим (в менеджере виртуальной памяти) эти страницы памяти как "лежащие во-он там на диске", и как только приложение полезет с ними реально работать - произойдёт экспешн, управление будет передано куда-надо, и мы быстренько дочитаем их на ходу, прозрачно для приложения :-) При том что приложение не факт что сразу полезет работать со считанным, и тем более не факт что использует всё считанное - может и правда получиться ускорение. Правда, такое вроде бы нигде не реализовано, ограничились memory mapped files, что близко по смыслу, но не так смешно по названию :-)

     А теперь вот - "ленивые вычисления".
     Идея-то простая. Программист сказал - "посчитай мне, сколько будет логарифм тангенса пи на четыре, и положи в переменную Икс", программа сказала "ага". Программист сказал - "ну и что же у нас оказалось в Икс?", программа - "ой, ё... счас посчитаю" - и считает :-) Реализовано может быть по разному - через "встроенные свойства языка", через те же экспешны, через какие-нибудь особые объекты с автоматически активирующимся методом "а теперь подсчитать уже в самом деле" при обращении к каким-то его частям, или ещё как-нибудь.
     Польза номер раз - если программист попросил заполнить массив логарифмами тангенсов углов от 0 до 2*пи с шагом 0.001*пи, а потом пользуется всего десятком элементов, заранее неизвестно каких - то остальные элементы считать в общем-то необязательно. То же самое реализуется "кешированием результатов вычислений", но отложенные вычисления будут прозрачнее с точки зрения программиста, а в данном случае - скорее всего ещё и быстрее.
     Польза номер два интереснее. Скажем, наша программа имеет два массива - с электрическим и с магнитным полем. И рассчитывает, по кругу, одно из другого - моделирует, тсзть, эволюцию полей во времени. Для расчета электрического поля - магнитное должно быть полностью подсчитано (все используемые значения должны быть из одного "момента виртуального времени"), в программе это, ясное дело, реализуется тем что считается один массив, потом второй, потом опять первый, второй... Распараллелить это можно - считаем один массив, а в соседнем потоке, с небольшим оставанием по индексу элемента - считаем второй. Но сразу же возникнет геморрой с синхронизацией, чтобы второй поток не забежал вперёд и не стал использовать "ещё не посчитанные" (старые) данные первого массива... в-общем, "типичный физик", пишущий программу сам, про синхронизацию знающий что это когда "где-то в системе то-ли семафоры ставят, то-ли стрелки переводят", и искренне верящий что spinlock, malloc и maalox - однокоренные слова, с таким точно не справится.
     А теперь давайте так. "А вычисли-ка мне первый массив" - "А легко!". "А теперь второй, но при вычислении понадобятся данные из первого" - и при (фактическом) вычислении второго массива, при первом же обращении к элементам первого массива, начнётся вычисление элементов первого масива. Идущее, ясное дело, "с упреждением" - пока не досчитан нужный элемент, не разблокируется вычисление для второго массива, но которые вычисления можно, что характерно, пустить параллельным потоком. А значит в результате мы совершенно на халяву, то есть даром, сделали из однопоточной программы - двухпоточную, не изменив её "логику" с точки зрения программиста.
     Но это ещё не всё. Обсчёт массивов ведь повторяется в цикле, 1-2-1-2-1-2, и так 10000 раз. Если у нас будет возможность делать вложенные ленивые вычисления нужной глубины - то фактический расчет можно будет откладывать на N шагов. И, скажем, на 8-ядерном компьютере, делая вложенные "ленивые вычисления", и форсируя фактический обсчёт каждые 8 шагов, мы автоматом нагрузим все восемь ядер. При этом алгоритм на вид останется совершенно линейным, без каких-то признаков распараллеленности.
     А если не форсировать обсчёт ручками, то фактический обсчёт произойдёт только тогда, когда данные понадобятся в явном виде - например, чтобы сохранить их в файл. Лишь бы памяти хватило, всю лабуду связанную с "отложенностью" хранить.

     Но с другой стороны - зачем так себя ограничивать? Оба модных нынче направления, и объектно-озабоченное, считающее что "всё - объект", и дофигаразрядное, считающее что http://google.com, не говоря уже о каких-то там локальных файлах, должно просто маппиться куда-то в адресное пространство, не делают принципиального различия между "файлом" и "областью памяти": "память / диск, мальчик / девочка - какая разница"? Это либо "объект", либо "один фиг имеет адрес".
     А значит, и в файл в принципе можно сохранить "ленивые" данные. Просто, ну, пометить их, что если в самом деле понадобятся - то их можно подсчитать, вон и программа есть. Получится специальный, "ленивый", файл - точнее, "ленивая" область в файле.

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

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

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

     Самое смешное - именно это (спонтанная декогеренция) является одной из основных проблем создания квантовых компьютеров. То есть, если бы никто не требовал показать, что эти компьютеры там внутри себя считают - их давно бы создали, но консервативному человечеству якобы нужно поглазеть на какой-то "результат"... :-)
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 38 comments