This is not the current version of the class.

Data representation 1: Introduction


This course investigates how systems software works: what makes programs work fast or slow, and how properties of the machines we program impact the programs we write. We discuss both general ideas and specific tools, and take an experimental approach.

Textbook readings

Class outline

  1. Data representation
    • How do computers represent different kinds of information?
    • How do data representation choices impact performance and correctness?
  2. Assembly & machine programming
    • What kind of language is understood by computer processors?
    • How is code you write translated to code a processor runs?
  3. Kernel programming
    • How do hardware and software defend against bugs and attacks?
    • How are operating systems interfaces implemented?
  4. Storage & caching
    • What kinds of computer data storage are available, and how do they perform?
    • How can we improve the performance of a system that stores data?
  5. Process management
    • How can programs on the same computer cooperate and interact?
    • What kinds of operating systems interfaces are useful?
  6. Concurrency
    • How can a single program safely use multiple processors?
    • How can multiple computers safely interact over a network?

Your work

Your grade


Discussion, collaboration, and the exchange of ideas are essential to doing academic work, and to engineering. You are encouraged to consult with your classmates as you work on problem sets. You are welcome to discuss general strategies for solutions as well as specific bugs and code structure questions, and to use Internet resources for general information.

However, the work you turn in must be your own—the result of your own efforts. You should understand your code well enough that you could replicate your solution from scratch, without collaboration.

In addition, you must cite any books, articles, online resources, and so forth that helped you with your work, using appropriate citation practices; and you must list the names of students with whom you have collaborated on problem sets and briefly describe how you collaborated. (You do not need to list course staff.)

Our programming language

We use the C++ programming language in this class.

C++ is a boring, old, and unsafe programming language, but boring languages are underrated. C++ offers several important advantages for this class, including ubiquitous availability, good tooling, the ability to demonstrate impactful errors, and a good standard library of data structures.

Pset 0 links to several C++ tutorials and references, and to a textbook.


A simple program

#include <cstdio>

int main() {
    int x = 0;
    fprintf(stdout, "%d\n", x);

    x = x + 1;
    fprintf(stdout, "%d\n", x);

An equivalent program

#include <cstdio>

int main() {
    fprintf(stdout, "%d\n", 0);

    fprintf(stdout, "%d\n", 1);

Derpsy doodle

#include <cstdio>

int main() {
    fprintf(stdout, "%d\n", 0);

    0 = 0 + 1;
    fprintf(stdout, "%d\n", 0);

Primitive types, values, and objects

Where’s x?

M1 Mac board


Computer addresses

Finding x

#include <cstdio>

int main() {
    int x = 0;
    fprintf(stdout, "%d %p\n", x, &x);

    x = x + 1;
    fprintf(stdout, "%d %p\n", x, &x);

Finding x with hexdump

#include <cstdio>
#include "hexdump.hh"

int main() {
    int x = 0;
    fprintf(stdout, "%d\n", x);

    x = x + 1;
    fprintf(stdout, "%d\n", x);

A performance mystery

Sorting integers

$ cd cs61-lectures/datarep1
$ make
$ ./intgen | python3

import sys

ls = []
for line in sys.stdin:
    val = int(line)
    i = 0
    while i < len(ls) and ls[i] < val:
        i += 1
    ls.insert(i, val)

for v in ls:


  1. Does this work?
  2. How would you test it?
  3. How fast is it?

#include <cstdio>
#include <cassert>
#include <list>
#include <vector>
#include "hexdump.hh"

int main() {
    std::list<int> ls;

    // read integers from stdin, storing them in sorted order
    int val;
    while (fscanf(stdin, "%d", &val) == 1) {
        auto it = ls.begin();
        while (it != ls.end() && *it < val) {
        ls.insert(it, val);

    // print integers in sorted order
    for (auto v : ls) {
        fprintf(stdout, "%d\n", v);
} mark 2

-    std::list<int> ls;
+    std::vector<int> ls;

What happened????