5.2.4 Monitoring Machine Performance - SICP Comparison Edition

Simulation is useful not only for verifying the correctness of a proposed machine design but also for measuring the machine's performance. For example, we can install in our simulation program a meter that measures the number of stack operations used in a computation. To do this, we modify our simulated stack to keep track of the number of times registers are saved on the stack and the maximum depth reached by the stack, and add a message to the stack's interface that prints the statistics, as shown below. We also add an operation to the basic machine model to print the stack statistics, by initializing the-ops the_ops in make-new-machine make_new_machine to

Original	Python
`(list (list 'initialize-stack (lambda () (stack 'initialize))) (list 'print-stack-statistics (lambda () (stack 'print-statistics))))`	`llist(llist("initialize_stack", lambda: stack("initialize")), llist("print_stack_statistics", lambda: stack("print_statistics")))`

Here is the new version of make-stack: make_stack:

Original

Python

(define (make-stack) (let ((s '()) (number-pushes 0) (max-depth 0) (current-depth 0)) (define (push x) (set! s (cons x s)) (set! number-pushes (+ 1 number-pushes)) (set! current-depth (+ 1 current-depth)) (set! max-depth (max current-depth max-depth))) (define (pop) (if (null? s) (error "Empty stack - - POP") (let ((top (car s))) (set! s (cdr s)) (set! current-depth (- current-depth 1)) top))) (define (initialize) (set! s '()) (set! number-pushes 0) (set! max-depth 0) (set! current-depth 0) 'done) (define (print-statistics) (newline) (display (list 'total-pushes '= number-pushes 'maximum-depth '= max-depth))) (define (dispatch message) (cond ((eq? message 'push) push) ((eq? message 'pop) (pop)) ((eq? message 'initialize) (initialize)) ((eq? message 'print-statistics) (print-statistics)) (else (error "Unknown request - - STACK" message)))) dispatch))

def make_stack(): stack = None number_pushes = 0 max_depth = 0 current_depth = 0 def push(x): nonlocal stack, number_pushes, current_depth, max_depth stack = pair(x, stack) number_pushes = number_pushes + 1 current_depth = current_depth + 1 max_depth = math_max(current_depth, max_depth) return "done" def pop(): nonlocal stack, current_depth if is_null(stack): error("empty stack -- pop") else: top = head(stack) stack = tail(stack) current_depth = current_depth - 1 return top def initialize(): nonlocal stack, number_pushes, max_depth, current_depth stack = None number_pushes = 0 max_depth = 0 current_depth = 0 return "done" def print_statistics(): display("total pushes = " + stringify(number_pushes)) display("maximum depth = " + stringify(max_depth)) def dispatch(message): return (push if message == "push" else pop() if message == "pop" else initialize() if message == "initialize" else print_statistics() if message == "print_statistics" else error("unknown request -- stack", message)) return dispatch

Exercises 5.14 through 5.18 describe other useful monitoring and debugging features that can be added to the register-machine simulator.

Exercise 5.13 Measure the number of pushes and the maximum stack depth required to compute $n!$ for various small values of $n$ using the factorial machine shown in figure 5.13. From your data determine formulas in terms of $n$ for the total number of push operations and the maximum stack depth used in computing $n!$ for any $n > 1$. Note that each of these is a linear function of $n$ and is thus determined by two constants. In order to get the statistics printed, you will have to augment the factorial machine with instructions to initialize the stack and print the statistics. You may want to also modify the machine so that it repeatedly reads a value for $n$, computes the factorial, and prints the result (as we did for the GCD machine in figure 5.5), so that you will not have to repeatedly invoke get-register-contents, get_register_contents, set-register-contents!, set_register_contents, and start. start.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 5.14 Add instruction counting to the register machine simulation. That is, have the machine model keep track of the number of instructions executed. Extend the machine model's interface to accept a new message that prints the value of the instruction count and resets the count to zero.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 5.15 Augment the simulator to provide for instruction tracing. That is, before each instruction is executed, the simulator should print the text of the instruction. Make the machine model accept trace-on trace_on and trace-off trace_off messages to turn tracing on and off.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 5.16 Extend the instruction tracing of exercise 5.15 so that before printing an instruction, the simulator prints any labels that immediately precede that instruction in the controller sequence. Be careful to do this in a way that does not interfere with instruction counting (exercise 5.14). You will have to make the simulator retain the necessary label information.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 5.17 Modify the make-register make_register procedure function of section 5.2.1 so that registers can be traced. Registers should accept messages that turn tracing on and off. When a register is traced, assigning a value to the register should print the name of the register, the old contents of the register, and the new contents being assigned. Extend the interface to the machine model to permit you to turn tracing on and off for designated machine registers.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 5.18 Alyssa P. Hacker wants a breakpoint feature in the simulator to help her debug her machine designs. You have been hired to install this feature for her. She wants to be able to specify a place in the controller sequence where the simulator will stop and allow her to examine the state of the machine. You are to implement a procedure function

Original	Python
`(set-breakpoint $machine$ $label$ $n$)`	`set_breakpoint($machine$, $label$, $n$)`

that sets a breakpoint just before the $n$th instruction after the given label. For example,

Original	Python
`(set-breakpoint gcd-machine 'test-b 4)`	`set_breakpoint(gcd_machine, "test_b", 4)`

installs a breakpoint in gcd-machine gcd_machine just before the assignment to register a. When the simulator reaches the breakpoint it should print the label and the offset of the breakpoint and stop executing instructions. Alyssa can then use get-register-contents get_register_contents and set-register-contents! set_register_contents to manipulate the state of the simulated machine. She should then be able to continue execution by saying

Original	Python
`(proceed-machine $machine$)`	`proceed_machine($machine$)`

She should also be able to remove a specific breakpoint by means of

Original	Python
`(cancel-breakpoint $machine$ $label$ $n$)`	`cancel_breakpoint($machine$, $label$, $n$)`

or to remove all breakpoints by means of

Original	Python
`(cancel-all-breakpoints $machine$)`	`cancel_all_breakpoints($machine$)`

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.