Предварительное замечание: при грамотном программировании в стиле Кнута (то есть при чтении программ WEB или CWEB) «настоящая» программа, задуманная Кнутом, не является ни «исходным» .w файлом, ни сгенерированным (запутанным) .c файл, но набрано (тканый) вывод.Исходный файл .w лучше всего рассматривать как средство его создания (и, конечно, также источник .c, который передается компилятору).(Если у вас нет под рукой cweave и TeX; я набрал некоторые из этих программ здесь ; эта программа DLX1 здесь .)
Так что в этомВ этом случае я бы описал местоположение в коде как модуль 25 DLX1 или подпрограмму «cover»:
В любом случае, чтобы вернуться кАктуальный вопрос: обратите внимание, что эта (DLX1) - одна из программ, написанных для Искусство компьютерного программирования .Поскольку сообщение о времени, затраченном программой на «секунды» или «минуты», становится бессмысленным из года в год, он сообщает, сколько времени заняла программа в количестве «мемов» плюс «упс», в которых преобладают «мемы», то естьколичество обращений к памяти до 64-битных слов (обычно).Таким образом, книга содержит утверждения типа «эта программа находит ответ на эту проблему за 3,5 гигабайма времени работы».Кроме того, операторы предназначены в основном для самой программы / алгоритма, а не для конкретного кода, сгенерированного конкретной версией компилятора для определенного оборудования.(В идеале, когда детали очень важны, он пишет программу в MMIX или MMIXAL и анализирует ее работу на оборудовании MMIX, но это редко.) Подсчет mems (о чем сообщается выше) является целью вставки o иoo инструкция в программу.Обратите внимание, что более важно получить это право для инструкций «внутреннего цикла», которые выполняются много раз, например, для всего, что в подпрограмме cover в этом случае.
Это подробно описано в разделе 1.3.1 ′ (часть Fascicle 1 ):
Время. […] Время выполнения программы зависит не только от тактовой частоты, но ио количестве функциональных блоков, которые могут быть активны одновременно, и о степени их конвейерности;это зависит от методов, используемых для предварительной выборки команд перед их выполнением;это зависит от размера оперативной памяти, которая используется для иллюзии 2 64 виртуальных байтов;и это зависит от размеров и стратегий размещения кэшей и других буферов и т. д. и т. д.
Для практических целей время выполнения программы MMIX часто можно оценить удовлетворительно, назначив фиксированную стоимостькаждая операция, основанная на приблизительном времени работы, которое будет получено на высокопроизводительной машине с большим объемом оперативной памяти;так вот что мы будем делать.Предполагается, что каждая операция принимает целое число υ, где υ (произносится как «oops») - это единица, которая представляет время тактового цикла в конвейерной реализации.Хотя значение υ уменьшается по мере совершенствования технологии, мы всегда следим за последними достижениями, потому что измеряем время в единицах υ, а не в наносекундах.Время выполнения в наших оценках также будет зависеть от количества ссылок на память или мемов, которые использует программа;это количество инструкций по загрузке и хранению.Например, мы будем считать, что каждая инструкция LDO (загрузка окта) стоит µ + υ, где µ - средняя стоимость ссылки на память.Общее время выполнения программы может быть представлено, скажем, как 35µ + 1000υ, что означает «35 мемов плюс 1000 упс». Отношение µ / υ неуклонно растет на протяжении многих лет;никто не знает наверняка, будет ли эта тенденция продолжаться, но опыт показал, что µ и v заслуживают того, чтобы их рассмотрели независимо.
И он, конечно, понимает отличие от реальности:
Несмотря на то, что мы часто будем использовать допущения Таблицы 1 дляМы должны помнить, что при оценке времени выполнения команды «место в штанах» фактическое время работы может быть весьма чувствительным к порядку выполнения инструкций.Например, целочисленное деление может стоить только одного цикла, если мы сможем найти 60 других вещей, которые нужно сделать между временем, когда мы выполняем команду, и временем, когда нам нужен результат.Некоторым инструкциям LDB (загрузочный байт) может потребоваться ссылаться на память только один раз, если они ссылаются на один и тот же октабайт.Тем не менее, результат команды загрузки обычно не готов к использованию в следующей сразу инструкции.Опыт показывает, что некоторые алгоритмы хорошо работают с кеш-памятью, а другие нет;следовательно, µ не является на самом деле постоянным.Даже расположение инструкций в памяти может оказать существенное влияние на производительность, потому что некоторые инструкции могут быть получены вместе с другими.[…] Только мета-симулятор можно доверять, чтобы предоставлять достоверную информацию о реальном поведении программы на практике;но такие результаты могут быть трудно интерпретировать, потому что бесконечно много конфигураций возможно.Вот почему мы часто прибегаем к гораздо более простым оценкам таблицы 1.
Наконец, мы можем использовать Godbolt's Compiler Explorer , чтобы посмотреть на код, сгенерированный типичным компилятором для этого кода.,(В идеале мы посмотрим на инструкции MMIX, но, поскольку мы не можем этого сделать, давайте согласимся с настройками по умолчанию, которые кажутся x68-64 gcc 8.2.) Я удалил все o s и oo s.
Для версии кода с:
/*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; два мема поступают от нагрузки и хранилища в --; не в двух хранилищах.)