5.2.6 · 기계 계측

기계는 컨트롤러가 수행한 일을 직접 보고할 수 있다.

명시적인 레지스터 기계 실행기는 결과와 마지막 스택 상태를 보존하면서 가져온 명령 수와 전체 push 수와 최대 스택 깊이를 셀 수 있습니다.

생각해 볼 질문

마지막 레지스터 값만으로는 알 수 없는 어떤 일을 컨트롤러 수준 계수기가 보여 줄까요?

명시적인 규약으로 가져온 모든 명령 세기
전체 save 수와 현재 스택 깊이 구분하기
restore 뒤에도 최대 스택 깊이 보존하기
같은 factorial 컨트롤러의 기본 경로와 재귀 경로 비교하기
컨트롤러 계측값과 실제 시간·하드웨어 프로파일링 구분하기

컨트롤러는 모든 실행에서 동일한 유한 재귀 factorial 기계입니다. 명시적인 레지스터 벡터는 n, val, continue, flag, pc를 담습니다. 별도의 리스트가 스택을 나타냅니다. 실행기는 halt를 포함해 명령을 가져오는 즉시 instruction-count를 증가시킵니다. push!는 total-pushes를 증가시키고 현재 리스트 길이로 max-depth를 갱신하며, pop!은 활성 스택을 줄이지만 누적된 push 횟수를 지우지는 않습니다.

n이 1일 때 분기는 기본 대입으로 바로 건너뛰어 스택 사용 없이 다섯 개의 명령을 가져온 뒤 halt에 도달합니다. n이 3일 때 컨트롤러는 두 재귀 수준에서 continue와 n을 저장하므로, 네 번의 push를 수행하고 깊이 4에 도달하며 27개의 명령을 가져온 뒤 값 6과 빈 스택으로 정지합니다. 이 수치들은 정확히 이 컨트롤러와 입력값과 계측 규약을 설명하며, 실행기가 가져온 명령 수와 스택 사용량을 명시적인 측정 데이터로 보고합니다.

SICP 코드UTF-8 3,860 / 1,048,576바이트

(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))을 반환합니다.

실행 추적에서 볼 점

halt를 포함해 각 벡터 가져오기 직후의 instruction-count를 따라가세요. 각 save를 push 증가 및 잠재적인 max-depth 갱신과 비교한 뒤, restore가 total-pushes를 줄이지 않고 현재 스택을 단축하는 모습을 관찰하세요. 기본 경로는 명령 11로 바로 건너뛰지만, 재귀 수준이 하나씩 늘어날 때마다 두 번의 save와 이후 두 번의 restore가 추가됩니다.

직접 해보기

프로그램을 수정하고 결과를 비교해 보세요.

실행하지 않고 입력값 3에 대한 보고 결과를 예측하세요. 그런 다음 halt가 포함되지 않도록 계측 규약을 바꾸고 정확히 어떤 필드가 바뀌는지 설명하세요.

힌트 보기

입력값 3은 두 재귀 수준을 만듭니다. 각 수준은 continue와 n을 push합니다. halt를 제외하면 가져온 명령 수에서만 1이 빠집니다.

이 수업 완료하기

이 장의 총 23개 수업 중 0개 완료0%