Data representation 3: Layout and dynamic allocation

Examples from last time

Understanding stringify: call-by-value and copies

#include <cassert>

int f(int a) {
    a = 2;          // changes local variable, not caller’s version
}

int main() {
    int a = 3;
    f(a);
    assert(a == 3);
}

Call-by-value and performance

#include <vector>
#include <cstdio>

unsigned long vector_sum(std::vector<unsigned long> vector) {
    unsigned long sum = 0;
    for (auto value : vector) {
        sum += value;
    }
    return sum;
}

int main() {
    std::vector<unsigned long> v;
    for (unsigned long i = 0; i != 10'000'000; ++i) {
        v.push_back(i);
    }
    printf("%zu\n", vector_sum(v));
}

Explicit references

#include <vector>
#include <cstdio>

unsigned long vector_sum(std::vector<unsigned long>& vector) {
    unsigned long sum = 0;
    for (auto value : vector) {
        sum += value;
    }
    return sum;
}

int main() {
    std::vector<unsigned long> v;
    for (unsigned long i = 0; i != 10'000'000; ++i) {
        v.push_back(i);
    }
    printf("%zu\n", vector_sum(v));
}

Other programming languages

dx

Sorting integers: an example of the value of “working memory”

$ cd cs61-lectures/datarep3
$ make
$ ./intgen | python3 intsort.py
0
1
2
3
4
5
6
7
8
9

How call-by-value affects stringify and returning local variables

Fixing stringify

intsort.py

datarep3/intsort.py
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:
    sys.stdout.write("{}\n".format(v))

intsort.cc

datarep3/intsort.cc
#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) {
            ++it;
        }
        ls.insert(it, val);
    }

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

intsort.cc mark 2

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

What happened????

Here are some results from several runs of ./intgen -n 100000 | time ./intsort > /dev/null (on my desktop in Docker):

Data structure Elapsed times
std::list 27.48 sec 27.45 sec 27.42 sec
std::vector 0.73 sec 0.73 sec 0.75 sec

An investigation

Analysis

Insertion order

Data structure Insertion order Elapsed times
std::list -r (random) 27.48 sec 27.45 sec 27.42 sec
std::vector -r 0.73 sec 0.73 sec 0.75 sec
std::list -u (increasing) 7.43 sec 7.43 sec 7.36 sec
std::vector -u 1.16 sec 1.14 sec 1.15 sec
std::list -d (decreasing) 0.01 sec 0.01 sec 0.01 sec
std::vector -d 0.35 sec 0.33 sec 0.34 sec