5.2.4 Monitorando o Desempenho da Máquina

A simulação é útil não apenas para verificar a correção de um projeto de máquina proposto, mas também para medir o desempenho da máquina. Por exemplo, podemos instalar em nosso programa de simulação um "medidor" que mede o número de operações de pilha usadas em uma computação. Para fazer isso, modificamos nossa pilha simulada para manter o controle do número de vezes que registradores são salvos na pilha e a profundidade máxima alcançada pela pilha, e adicionamos uma mensagem à interface da pilha que imprime as estatísticas, como mostrado abaixo. Também adicionamos uma operação ao modelo de máquina básico para imprimir as estatísticas da pilha, inicializando the_ops em make_new_machine para:

list(list("initialize_stack",
          () => stack("initialize")),
     list("print_stack_statistics",
          () => stack("print_statistics")));

Aqui está a nova versão de make_stack:

Exemplo de Código

1function make_stack() {
2  let stack = null;
3  let number_pushes = 0;
4  let max_depth = 0;
5  let current_depth = 0;
6  function push(x) {
7      stack = pair(x, stack);
8      number_pushes = number_pushes + 1;
9      current_depth = current_depth + 1;
10      max_depth = math_max(current_depth, max_depth);
11      return "done";
12  }
13  function pop() {
14      if (is_null(stack)) {
15          error("empty stack -- pop");
16      } else {
17          const top = head(stack);
18          stack = tail(stack);
19          current_depth = current_depth - 1;
20          return top;
21      }
22  }
23  function initialize() {
24      stack = null;
25      number_pushes = 0;
26      max_depth = 0;
27      current_depth = 0;
28      return "done";
29  }
30  function print_statistics() {
31      display("total pushes = " + stringify(number_pushes));
32      display("maximum depth = " + stringify(max_depth));
33  }
34  function dispatch(message) {
35      return message === "push"
36             ? push
37             : message === "pop"
38             ? pop()
39             : message === "initialize"
40             ? initialize()
41             : message === "print_statistics"
42             ? print_statistics()
43             : error(message, "unknown request -- stack");
44  }
45  return dispatch;
46}

function make_stack() { let stack = null; let number_pushes = 0; let max_depth = 0; let current_depth = 0; function push(x) { stack = pair(x, stack); number_pushes = number_pushes + 1; current_depth = current_depth + 1; max_depth = math_max(current_depth, max_depth); return "done"; } function pop() { if (is_null(stack)) { error("empty stack -- pop"); } else { const top = head(stack); stack = tail(stack); current_depth = current_depth - 1; return top; } } function initialize() { stack = null; number_pushes = 0; max_depth = 0; current_depth = 0; return "done"; } function print_statistics() { display("total pushes = " + stringify(number_pushes)); display("maximum depth = " + stringify(max_depth)); } function dispatch(message) { return message === "push" ? push : message === "pop" ? pop() : message === "initialize" ? initialize() : message === "print_statistics" ? print_statistics() : error(message, "unknown request -- stack"); } return dispatch; }

Código editável · Ctrl+Enter executa · Esc solta o foco

Os exercícios 5.13 a 5.18 descrevem outros recursos úteis de monitoramento e depuração que podem ser adicionados ao simulador de máquina de registradores.

Exercício 5.13

Meça o número de pushes e a profundidade máxima de pilha necessária para calcular n! para vários valores pequenos de n usando a máquina fatorial mostrada na Figura 5.11. A partir de seus dados, determine fórmulas em termos de n para o número total de operações push e a profundidade máxima de pilha usada no cálculo de n! para qualquer n > 1. Observe que cada uma dessas é uma função linear de n e é, portanto, determinada por duas constantes. Para obter as estatísticas impressas, você terá que aumentar a máquina fatorial com instruções para inicializar a pilha e imprimir as estatísticas. Você pode querer também modificar a máquina para que ela leia repetidamente um valor para n, calcule o fatorial e imprima o resultado (como fizemos para a máquina MDC na figura 5.4), para que você não tenha que invocar repetidamente get_register_contents, set_register_contents e start.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Instrumentando a máquina (com perform(op("initialize_stack")) no início e perform(op("print_stack_statistics")) antes de done) e medindo:

n	pushes	profundidade máxima
2	2	2
3	4	4
4	6	6
5	8	8

As fórmulas, para $n > 1$: pushes $= 2(n-1)$ e profundidade máxima $= 2(n-1)$ — a cada nível recursivo antes da base, a máquina salva continue e n (2 pushes), e nada é consumido até a volta, então o pico coincide com o total. As "duas constantes" pedidas: coeficiente 2 e deslocamento −2.

Para o laço de leitura contínua, envolva o controlador em read/imprime como a máquina de MDC da figura 5.4: rótulo inicial que faz assign("n", op("read")), corpo do fatorial, perform(op("print"), reg("val")) e go_to de volta.

Resolvi o exercício 5.13

Exercício 5.14

Adicione contagem de instruções à simulação de máquina de registradores. Ou seja, faça o modelo de máquina manter o controle do número de instruções executadas. Estenda a interface do modelo de máquina para aceitar uma nova mensagem que imprima o valor da contagem de instruções e redefine a contagem para zero.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Um contador no modelo da máquina, incrementado dentro de execute:

// em make_new_machine:
let instruction_count = 0;
function execute() {
    const insts = get_contents(pc);
    if (is_null(insts)) { return "done"; }
    instruction_count = instruction_count + 1;
    instruction_execution_fun(head(insts))();
    return execute();
}
// no dispatch:
: message === "instruction-count"
? () => { const n = instruction_count;
          instruction_count = 0;
          display(n);
          return n; }

O ponto único de passagem (execute) faz a contagem valer para qualquer máquina simulada, sem tocar no montador.

Resolvi o exercício 5.14

Exercício 5.15

Aumente o simulador para fornecer rastreamento de instruções. Ou seja, antes de cada instrução ser executada, o simulador deve imprimir a instrução. Faça o modelo de máquina aceitar mensagens trace_on e trace_off para ativar e desativar o rastreamento.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Uma flag no modelo e uma impressão condicional no mesmo execute:

let tracing = false;
function execute() {
    const insts = get_contents(pc);
    if (is_null(insts)) { return "done"; }
    if (tracing) {
        display(instruction_text(head(insts)));
    }
    …
}
// no dispatch: "trace_on" liga, "trace_off" desliga

O montador já guarda o texto de cada instrução (instruction_text) exatamente para diagnósticos assim — a instrução impressa é a fonte, não a função de execução.

Resolvi o exercício 5.15

Exercício 5.16

Estenda o rastreamento de instruções do exercício 5.15 de modo que antes de imprimir uma instrução, o simulador imprima quaisquer rótulos que precedem imediatamente essa instrução na sequência do controlador. Tenha cuidado para fazer isso de uma maneira que não interfira com a contagem de instruções (exercício 5.14). Você terá que fazer o simulador reter a informação de rótulo necessária.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

O montador precisa reter os rótulos junto às instruções: em extract_labels, quando um rótulo é encontrado, anote-o na próxima instrução (a instrução ganha um campo de rótulos que a precedem — pode haver mais de um):

// instrução vira: pair(texto, pair(rótulos_precedentes, fun_execução))

No execute com rastreamento, imprima primeiro os rótulos da instrução corrente, depois o texto dela. Como os rótulos não são instruções, o contador do exercício 5.14 não é tocado — imprimir rótulos não passa pelo incremento. O cuidado pedido pelo enunciado é só esse: manter a impressão fora do caminho da contagem.

Resolvi o exercício 5.16

Exercício 5.17

Modifique a função make_register da seção 5.2.1 de modo que os registradores possam ser rastreados. Registradores devem aceitar mensagens que ativam e desativam o rastreamento. Quando um registrador é rastreado, atribuir um valor ao registrador deve imprimir o nome do registrador, o conteúdo antigo do registrador e o novo conteúdo sendo atribuído. Estenda a interface ao modelo de máquina para permitir que você ative e desative o rastreamento para registradores de máquina designados.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

No próprio make_register:

function make_register(name) {
    let contents = "*unassigned*";
    let tracing = false;
    function dispatch(message) {
        return message === "get"
               ? contents
               : message === "set"
               ? value => {
                     if (tracing) {
                         display(name);
                         display("  antigo: " + stringify(contents));
                         display("  novo:   " + stringify(value));
                     }
                     contents = value;
                 }
               : message === "trace_on" ? () => { tracing = true; }
               : message === "trace_off" ? () => { tracing = false; }
               : error(message, "unknown request -- register");
    }
    return dispatch;
}

e no modelo da máquina, mensagens trace_register_on/off que localizam o registrador pelo nome (via get_register) e repassam. Toda atribuição — venha de assign, restore ou inicialização — passa por "set", então o rastreamento cobre tudo por construção.

Resolvi o exercício 5.17

Exercício 5.18

Alyssa P. Hacker quer um recurso de breakpoint no simulador para ajudá-la a depurar seus projetos de máquina. Você foi contratado para instalar este recurso para ela. Ela quer poder especificar um lugar na sequência do controlador onde o simulador irá parar e permitir que ela examine o estado da máquina. Você deve implementar uma função:

set_breakpoint(machine, label, n)

que define um breakpoint logo antes da n-ésima instrução após o rótulo dado. Por exemplo,

set_breakpoint(gcd_machine, "test_b", 4)

instala um breakpoint em gcd_machine logo antes da atribuição ao registrador a. Quando o simulador alcança o breakpoint, ele deve imprimir o rótulo e o deslocamento do breakpoint e parar de executar instruções. Alyssa pode então usar get_register_contents e set_register_contents para manipular o estado da máquina simulada. Ela deve então poder continuar a execução dizendo:

proceed_machine(machine)

Ela deve também poder remover um breakpoint específico por meio de:

cancel_breakpoint(machine, label, n)

ou remover todos os breakpoints por meio de:

cancel_all_breakpoints(machine)

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Breakpoints são pares (rótulo, deslocamento) guardados no modelo; a verificação vive no execute:

set_breakpoint(machine, label, n)     // pára antes da n-ésima instrução após label
proceed_machine(machine)              // continua do ponto parado
cancel_breakpoint(machine, label, n)
cancel_all_breakpoints(machine)

Implementação: com os rótulos retidos nas instruções (exercício 5.16), o montador consegue anotar em cada instrução sua posição "rótulo + deslocamento"; execute compara a posição da instrução corrente com a lista de breakpoints e, havendo casamento, retorna sem executá-la (deixando pc como está) após imprimir o estado. proceed_machine executa a instrução corrente uma vez "por fora" e retoma o execute normal; os cancel_* só editam a lista.

Parar antes de executar e manter pc intacto é o que permite a Alyssa inspecionar registradores com get_register_contents e retomar sem perder nada — o simulador inteiro continua sendo uma função pura de seu estado.

Resolvi o exercício 5.18