5.2.6 · Инструментирование машины

Учет работы контроллера регистровой машины

Исполнитель регистровой машины считает извлеченные команды, число помещений в стек и его максимальную глубину, сохраняя результат контроллера.

Вопрос для размышления

Что могут показать счетчики уровня контроллера из того, чего не показывают одни лишь конечные значения регистров?

Подсчет каждой извлеченной команды по единому явному соглашению
Подсчет общего числа операций save без их смешивания с текущей глубиной стека
Отслеживание максимальной глубины стека при развертывании стека операциями restore
Сравнение базового и рекурсивного путей одного и того же контроллера factorial
Отличие измерений контроллера от астрономического времени и аппаратного профилирования

Для каждого запуска используется один и тот же конечный контроллер рекурсивной машины factorial. Его явный вектор регистров содержит n, val, continue, flag и pc. Отдельный список представляет стек. Исполнитель увеличивает instruction-count сразу после извлечения команды, включая команду halt. push! увеличивает total-pushes и обновляет max-depth на основе текущей длины списка, а pop! укорачивает активный стек, но не стирает накопленное количество помещений в стек.

При n, равном 1, ветвление переходит непосредственно к базовому присваиванию и достигает halt после пяти извлеченных команд без использования стека. При n, равном 3, контроллер сохраняет continue и n на двух уровнях рекурсии, выполняя четыре операции push, достигает глубины 4 и извлекает 27 команд перед остановкой со значением 6 и пустым стеком. Эти числа описывают именно этот контроллер, входные данные и соглашение о подсчете. Они не отражают затраченное время, процессорные инструкции, затраты на выделение памяти или универсальный профилировщик.

Код SICP3,860 из 1,048,576 байт UTF-8

(begin
  (define controller
    (vector
      '(test base? n)
      '(branch 11)
      '(save continue)
      '(save n)
      '(assign n sub1 n)
      '(assign continue constant 7)
      '(goto 0)
      '(restore n)
      '(restore continue)
      '(assign val multiply n val)
      '(goto-register continue)
      '(assign val constant 1)
      '(goto-register continue)
      '(halt)))
  (define (register-index name)
    (cond ((eq? name 'n) 0)
          ((eq? name 'val) 1)
          ((eq? name 'continue) 2)
          ((eq? name 'flag) 3)
          ((eq? name 'pc) 4)))
  (define (run-factorial start)
    (let ((registers (vector start 0 13 #f 0))
          (stack '())
          (instruction-count 0)
          (total-pushes 0)
          (max-depth 0))
      (define (get-register name)
        (vector-ref registers (register-index name)))
      (define (set-register! name value)
        (vector-set! registers (register-index name) value))
      (define (advance!)
        (set-register! 'pc (+ (get-register 'pc) 1)))
      (define (push! value)
        (set! stack (cons value stack))
        (set! total-pushes (+ total-pushes 1))
        (set! max-depth (max max-depth (length stack))))
      (define (pop!)
        (let ((value (car stack)))
          (set! stack (cdr stack))
          value))
      (define (assign-value instruction)
        (let ((operation (caddr instruction)))
          (cond ((eq? operation 'constant)
                 (cadddr instruction))
                ((eq? operation 'sub1)
                 (- (get-register (cadddr instruction)) 1))
                ((eq? operation 'multiply)
                 (* (get-register (cadddr instruction))
                    (get-register (list-ref instruction 4)))))))
      (define (execute remaining-steps)
        (if (= remaining-steps 0)
            'step-limit
            (let* ((instruction
                    (vector-ref controller (get-register 'pc)))
                   (operation (car instruction)))
              (set! instruction-count (+ instruction-count 1))
              (cond
                ((eq? operation 'halt)
                 (list (get-register 'val)
                       instruction-count
                       total-pushes
                       max-depth
                       (length stack)))
                ((eq? operation 'test)
                 (set-register!
                   'flag
                   (= (get-register (caddr instruction)) 1))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'branch)
                 (set-register!
                   'pc
                   (if (get-register 'flag)
                       (cadr instruction)
                       (+ (get-register 'pc) 1)))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'save)
                 (push! (get-register (cadr instruction)))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'restore)
                 (set-register! (cadr instruction) (pop!))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'assign)
                 (set-register! (cadr instruction)
                                (assign-value instruction))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto)
                 (set-register! 'pc (cadr instruction))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto-register)
                 (set-register! 'pc
                                (get-register (cadr instruction)))
                 (execute (- remaining-steps 1)))))))
      (execute 200)))
  ; value, fetched instructions, pushes, max depth, final depth
  (run-factorial 3))

(begin
  (define controller
    (vector
      '(test base? n)
      '(branch 11)
      '(save continue)
      '(save n)
      '(assign n sub1 n)
      '(assign continue constant 7)
      '(goto 0)
      '(restore n)
      '(restore continue)
      '(assign val multiply n val)
      '(goto-register continue)
      '(assign val constant 1)
      '(goto-register continue)
      '(halt)))
  (define (register-index name)
    (cond ((eq? name 'n) 0)
          ((eq? name 'val) 1)
          ((eq? name 'continue) 2)
          ((eq? name 'flag) 3)
          ((eq? name 'pc) 4)))
  (define (run-factorial start)
    (let ((registers (vector start 0 13 #f 0))
          (stack '())
          (instruction-count 0)
          (total-pushes 0)
          (max-depth 0))
      (define (get-register name)
        (vector-ref registers (register-index name)))
      (define (set-register! name value)
        (vector-set! registers (register-index name) value))
      (define (advance!)
        (set-register! 'pc (+ (get-register 'pc) 1)))
      (define (push! value)
        (set! stack (cons value stack))
        (set! total-pushes (+ total-pushes 1))
        (set! max-depth (max max-depth (length stack))))
      (define (pop!)
        (let ((value (car stack)))
          (set! stack (cdr stack))
          value))
      (define (assign-value instruction)
        (let ((operation (caddr instruction)))
          (cond ((eq? operation 'constant)
                 (cadddr instruction))
                ((eq? operation 'sub1)
                 (- (get-register (cadddr instruction)) 1))
                ((eq? operation 'multiply)
                 (* (get-register (cadddr instruction))
                    (get-register (list-ref instruction 4)))))))
      (define (execute remaining-steps)
        (if (= remaining-steps 0)
            'step-limit
            (let* ((instruction
                    (vector-ref controller (get-register 'pc)))
                   (operation (car instruction)))
              (set! instruction-count (+ instruction-count 1))
              (cond
                ((eq? operation 'halt)
                 (list (get-register 'val)
                       instruction-count
                       total-pushes
                       max-depth
                       (length stack)))
                ((eq? operation 'test)
                 (set-register!
                   'flag
                   (= (get-register (caddr instruction)) 1))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'branch)
                 (set-register!
                   'pc
                   (if (get-register 'flag)
                       (cadr instruction)
                       (+ (get-register 'pc) 1)))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'save)
                 (push! (get-register (cadr instruction)))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'restore)
                 (set-register! (cadr instruction) (pop!))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'assign)
                 (set-register! (cadr instruction)
                                (assign-value instruction))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto)
                 (set-register! 'pc (cadr instruction))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto-register)
                 (set-register! 'pc
                                (get-register (cadr instruction)))
                 (execute (- remaining-steps 1)))))))
      (execute 200)))
  ; value, fetched instructions, pushes, max depth, final depth
  (run-factorial 3))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Первая программа возвращает (6 27 4 4 0). Вторая возвращает ((1 1 5 0 0) (2 2 16 2 2) (4 24 38 6 6)).

На что обратить внимание в трассе

Следите за instruction-count сразу после каждого извлечения из вектора, включая команду halt. Сопоставляйте каждый save с увеличением счетчика push и возможным обновлением max-depth, затем наблюдайте, как restore укорачивает текущий стек, не уменьшая total-pushes. Базовый путь переходит непосредственно к команде 11, тогда как каждый дополнительный уровень рекурсии добавляет два save и затем два restore.

Попробуйте сами

Измените программу и сравните результат.

Предскажите отчет для входного значения 3 без запуска программы. Затем измените соглашение о подсчете так, чтобы halt не учитывалась, и объясните, какое именно поле изменится.

Показать подсказку

Входное значение 3 создает два уровня рекурсии. Каждый уровень помещает в стек continue и n. Исключение halt вычитает единицу только из числа извлеченных команд.

Завершить этот урок

В этой главе пройдено 0 из 23 урока0%