Почему Кнут использует этот неуклюжий декремент?

Ответ 1

Предварительное замечание: при грамотном программировании в стиле Кнута (то есть при чтении программ 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 ′ (часть главы 1):

Timing. […] Время выполнения программы зависит не только от тактовой частоты, но также от количества функциональных блоков, которые могут быть активны одновременно, и степени, в которой они передаются по конвейеру; это зависит от методов, используемых для предварительной выборки команд перед их выполнением; это зависит от размера оперативной памяти, которая используется для иллюзии 2 ⁶⁴ виртуальных байтов; и это зависит от размеров и стратегий размещения кэшей и других буферов и т.д. и т.д.

В практических целях время выполнения программы MMIX часто можно оценить удовлетворительно, назначив фиксированную стоимость каждой операции на основе приблизительного времени выполнения, которое будет получено на высокопроизводительной машине с большим объемом основной памяти; так вот что мы будем делать. Предполагается, что каждая операция принимает целое число υ, где υ (произносится как "oops") - это единица, которая представляет время тактового цикла в конвейерной реализации. Хотя значение υ уменьшается по мере совершенствования технологии, мы всегда следим за последними достижениями, потому что измеряем время в единицах υ, а не в наносекундах. Время выполнения в наших оценках также будет зависеть от количества ссылок на память или мемов, которые использует программа; это количество инструкций по загрузке и хранению. Например, мы будем предполагать, что каждая инструкция LDO (load octa) стоит µ + υ, где µ - средняя стоимость ссылки на память. Общее время выполнения программы может быть указано, скажем, как 35µ + 1000υ, что означает "35 мемов плюс 1000 упс". Отношение µ/υ неуклонно растет на протяжении многих лет; никто не знает наверняка, будет ли эта тенденция продолжаться, но опыт показал, что µ и v заслуживают рассмотрения независимо.

И он, конечно, понимает отличие от реальности:

Даже при том, что мы часто будем использовать предположения Таблицы 1 для оценок времени выполнения, мы должны помнить, что фактическое время выполнения может быть весьма чувствительным к порядку инструкций. Например, целочисленное деление может стоить только одного цикла, если мы сможем найти 60 других вещей, которые нужно сделать между временем, когда мы выполняем команду, и временем, когда нам нужен результат. Некоторым инструкциям LDB (загрузочный байт) может потребоваться ссылаться на память только один раз, если они ссылаются на один и тот же октабайт. Тем не менее, результат команды загрузки обычно не готов к использованию в следующей сразу инструкции. Опыт показывает, что некоторые алгоритмы хорошо работают с кеш-памятью, а другие нет; следовательно, µ не является на самом деле постоянным. Даже расположение инструкций в памяти может оказать существенное влияние на производительность, потому что некоторые инструкции могут быть получены вместе с другими. […] Только мета-симулятор можно доверять, чтобы предоставлять достоверную информацию о реальном поведении программ на практике; но такие результаты могут быть трудно интерпретировать, потому что бесконечно много конфигураций возможно. Вот почему мы часто прибегаем к гораздо более простым оценкам таблицы 1.

Наконец, мы можем использовать Godbolt Compiler Explorer, чтобы посмотреть на код, сгенерированный типичным компилятором для этого кода. (В идеале мы посмотрим на инструкции MMIX, но, поскольку мы не можем этого сделать, давайте согласимся с настройками по умолчанию, которые кажутся x68-64 gcc 8.2.) Я удалил все o и 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; два мема поступают из нагрузки, а хранилище --; не из двух хранилищ. )

Ответ 2

Кажется, что вся эта практика основана на ошибочной идее/модели того, как работает C, что существует некоторое соответствие между работой, выполняемой абстрактной машиной, и фактической программой, которая была выполнена (то есть ошибкой "C является переносимым ассемблером"). Я не думаю, что мы можем ответить намного больше о том, почему появляется именно этот фрагмент кода, за исключением того, что он оказался необычной идиомой для подсчета нагрузок и сохранения на абстрактной машине как отдельного.