Visualizing Computation/Memory Evolution Diagrams

Memory layout diagrams and memory evolution diagrams depict the contents of a linear address space, either at a single moment in time, or as they change with time.

History and Known Uses

Memory layout/evolution diagrams are typically used in descriptions of language systems (compilers and interpreters). They are frequently seen in undergraduate courses on programming language concepts, computer hardware, or compiler design, for example during discussions of stack allocation of memory for function calls or layout of data in memory for records or arrays.

Memory Layout Diagrams date back at least to the Green Dragon Book(Aho & Ullman 1977), which shows many MLD's for stack frame layout (in Chapter 10); Memory Evolution Diagrams have been used more recently to illustrate use and re-use of memory in a way that produces diagrams that can be understood later by students reviewing their lecture notes.

What is Being Visualized

Memory layout diagrams and memory evolution diagrams each provide information about the organization of values within computer memory, indicating the value contained within each of a number of memory cells. The former show a snapshot of the contents of memory at a given instant; the latter show the development through time of the contents.

As indicated below, various different uses of memory may be illustrated, for example stack frame layout, data structure organization, heap (free storage) layout, etc.

Depending on the need, the diagram may show an abstract layout with labels but no values, or a memory image for a specific execution of a specific program including specific values in each memory cell. Stylistic variations include whether labels are written beside or in a given memory cell.

Visualization Techniques

Memory layout diagrams

A memory layout diagram can be simply a collection of rectangles, typically stacked vertically, with each rectangle corresponding to a given memory cell or group of cells. Depending on emphasis, a layout diagram may show all cells or only some of them, and it may show each byte or each word of memory. For example, to illustrate the use of stack frames for function parameters using this example C++ program for raising a number to a power

bool even(int i) { // return True iff i is an even number
    return i % 2 == 0;
}

double power(double base, int exp) {
    if (exp == 1)
        return base;
    else if (even(exp)) {
        double base_to_half_exp = power(base, exp/2);
        return base_to_half_exp * base_to_half_exp;
    }
    else
        return base * power(base, exp-1);
}

#include <iostream>

int main() {
    std::cout << power(2, 10) << std::endl;
}

we might draw one box for each word (and a large box for a double word), producing a diagram like the following for (for example) the point at which we are checking to see if 4 is even during the computation of power(2, 10) --- carefully formatted and hand-drawn images might look like this (the potentially confusing cross-outs and erasures in the hand-drawn image are the motivation for the Memory Evolution Diagrams below):

The above examples show specific values for a specific execution of the program; the diagrams in Chapter 10 of the green dragon book show a more abstract view of the same topic.

Memory layout diagrams are frequently used to discuss options for data structure layout in memory. For example, Chapter 7.3 of Scott's Programming Language Pragmatics shows several ways of laying out in memory a structure almost identical to the one below (with an example MLD, based on the assumption that each field is word-aligned and a "bool" value will be stored in one byte of memory). Note that Scott's diagrams are more abstract than the one shown here, as they do not include specific values for all fields.

                                       
struct element {   // similar to Ex. 7.35 of Scott's "Programming Language Pragmatics" (3rd ed).
  char   name[2];
  int    atomic_number;
  double atomic_weight;
  bool   metallic;
};

struct element aluminum = {{'A', 'l'}, 13, 26.98, true };

Memory evolution diagrams

A memory evolution diagram is a systematic way of capturing memory use over time. It can be thought of as a series of layout diagrams for different times, aligned next to each other, for example progressing from left to right with time. Typically a large range of values that have not changed are not copied, so that one looks back to the left when no value is shown for a certain cell. Contrast the diagram below with the hand-drawn image above --- the MED, even if drawn by hand, provides a much more comprehensible image of what has happened. (Note also that the MED here shows more information than the MLD above, in that it includes frame pointer and stack pointer information, and an additional function call; adding these to the picture above makes the difference in clarity even more pronounced.)