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, не говоря уже о каких-то там локальных файлах, должно просто маппиться куда-то в адресное пространство, не делают принципиального различия между "файлом" и "областью памяти": "память / диск, мальчик / девочка - какая разница"? Это либо "объект", либо "один фиг имеет адрес".
     А значит, и в файл в принципе можно сохранить "ленивые" данные. Просто, ну, пометить их, что если в самом деле понадобятся - то их можно подсчитать, вон и программа есть. Получится специальный, "ленивый", файл - точнее, "ленивая" область в файле.

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

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

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

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