Предварительное замечание: при грамотном программировании в стиле Кнута (т. е. при чтении программ WEB или CWEB) «настоящая» программа в понимании Кнута — это не «исходный» .w файл и не сгенерированный (запутанный) .c файл, а набранный (тканый) выход. Исходный файл .w лучше всего рассматривать как средство для его создания (и, конечно, также исходный код .c, который передается компилятору). (Если у вас нет под рукой cweave и TeX, я набрал некоторые из этих программ здесь; эта программа DLX1 находится здесь.)
Так что в этом случае я бы описал место в коде как модуль 25 DLX1 или подпрограмму «крышка»:
В любом случае, возвращаясь к основному вопросу: обратите внимание, что это (DLX1) — одна из программ, написанных для The Art of Computer Programming. Поскольку отчет о времени, затраченном программой на «секунды» или «минуты», из года в год становится бессмысленным, он сообщает, сколько времени заняла программа, в количестве «мемов» плюс «упс», в котором преобладают «мемы», т. е. количество обращений к памяти к 64-битным словам (обычно). Так вот в книге есть утверждения вроде «эта программа находит ответ на эту задачу за 3,5 гигабайта времени выполнения». Кроме того, утверждения предназначены в основном для самой программы/алгоритма, а не для конкретного кода, сгенерированного конкретной версией компилятора для определенного оборудования. (В идеале, когда детали очень важны, он пишет программу в MMIX или MMIXAL и анализирует ее работу на аппаратном обеспечении MMIX, но это случается редко.) Целью вставки инструкций o и oo является подсчет мемов (для отчета, как указано выше). в программу. Обратите внимание, что более важно сделать это правильно для инструкций «внутреннего цикла», которые выполняются много раз, например, все в подпрограмме cover в этом случае.
Это подробно описано в Разделе 1.3.1' (часть Faccicle 1):
Время. […] Время работы программы зависит не только от тактовой частоты, но и от количества функциональных блоков, которые могут быть активны одновременно, и степени их конвейеризации; это зависит от методов, используемых для предварительной выборки инструкций перед их выполнением; это зависит от размера оперативной памяти, которая используется для создания иллюзии 264 виртуальных байтов; и это зависит от размеров и стратегий распределения кешей и прочих буферов и т.д. и т.п.
Для практических целей время выполнения MMIX программы часто можно удовлетворительно оценить, назначив фиксированную стоимость каждой операции на основе приблизительного времени выполнения, которое было бы получено на высокопроизводительной машине с большим объемом оперативной памяти; так что мы будем делать. Предполагается, что каждая операция принимает целое число υ, где υ (произносится как «упс») — это единица измерения, представляющая время тактового цикла в конвейерной реализации. Хотя значение υ уменьшается по мере совершенствования технологии, мы всегда идем в ногу с последними достижениями, потому что мы измеряем время в единицах υ, а не в наносекундах. Время работы в наших оценках также будет зависеть от количества обращений к памяти или мемов, которые использует программа; это количество инструкций загрузки и сохранения. Например, мы предположим, что каждая инструкция LDO (загрузить окта) стоит µ + υ, где µ — средняя стоимость обращения к памяти. Общее время работы программы может быть выражено, скажем, как 35µ+ 1000υ, что означает «35 мемов плюс 1000 oops». Отношение µ/υ неуклонно растет в течение многих лет; никто точно не знает, сохранится ли эта тенденция, но опыт показал, что µ и υ заслуживают независимого рассмотрения.
И он, конечно, понимает отличие от реальности:
Несмотря на то, что мы будем часто использовать допущения из Таблицы 1 для ориентировочных оценок времени выполнения, мы должны помнить, что фактическое время выполнения может быть весьма чувствительным к порядку выполнения инструкций. Например, целочисленное деление может стоить всего один цикл, если мы сможем найти 60 других действий между моментом, когда мы выдаем команду, и временем, когда нам нужен результат. Некоторым инструкциям LDB (загрузка байта) может потребоваться обращение к памяти только один раз, если они ссылаются на один и тот же октабайт. Однако результат команды загрузки обычно не готов к использованию в следующей инструкции. Опыт показал, что одни алгоритмы хорошо работают с кэш-памятью, а другие нет; поэтому µ на самом деле не является постоянной величиной. Даже расположение инструкций в памяти может существенно повлиять на производительность, потому что одни инструкции могут быть получены вместе с другими. […] Только мета-симулятору можно доверять, чтобы он давал достоверную информацию о фактическом поведении программы на практике; но такие результаты может быть трудно интерпретировать, потому что возможно бесконечно много конфигураций. Вот почему мы часто прибегаем к гораздо более простым оценкам таблицы 1.
Наконец, мы можем использовать Compiler Explorer от Godbolt, чтобы просмотреть код, сгенерированный типичным компилятором для этого кода. (В идеале мы бы посмотрели на инструкции MMIX, но, поскольку мы не можем этого сделать, давайте остановимся на значении по умолчанию, которое выглядит как x68-64 gcc 8.2.) Я удалил все os и oos.
Для версии кода с:
/*o*/ t = nd[cc].len - 1;
/*o*/ nd[cc].len = t;
сгенерированный код для первой строки:
movsx rax, r13d
sal rax, 4
add rax, OFFSET FLAT:nd+8
mov eax, DWORD PTR [rax]
lea r14d, [rax-1]
а для второй строки:
movsx rax, r13d
sal rax, 4
add rax, OFFSET FLAT:nd+8
mov DWORD PTR [rax], r14d
Для версии кода с:
/*o ?*/ nd[cc].len --;
сгенерированный код:
movsx rax, r13d
sal rax, 4
add rax, OFFSET FLAT:nd+8
mov eax, DWORD PTR [rax]
lea edx, [rax-1]
movsx rax, r13d
sal rax, 4
add rax, OFFSET FLAT:nd+8
mov DWORD PTR [rax], edx
что, как вы можете видеть (даже не зная много о сборке x86-64), является просто конкатенацией кода, сгенерированного в первом случае (за исключением использования регистра edx вместо r14d), так что это не так, как если бы запись декремента в одной строке сохранил вам все мемы. В частности, было бы не корректно считать его за один, особенно в чем-то вроде cover, который в этом алгоритме вызывается огромное количество раз (пляшущие звенья для точного покрытия).
Таким образом, версия, написанная Кнутом, верна, поскольку ее целью является подсчет количества мемов. Он также может написать oo,nd[cc].len--; (считая два мема), как вы заметили, но, возможно, в этом случае на первый взгляд это может показаться ошибкой. (Кстати, в вашем примере в вопросе oo,nd[k].len--,nd[k].aux=i-1; два мема происходят из загрузки и хранилища в --, а не из двух хранилищ.)
person
ShreevatsaR
schedule
30.12.2018
o,t,nd,cc,aux. Это непостижимо. - person Boann schedule 01.01.2019