Problem set 5: Stdio

In this problem set, you’ll gain experience with caching by writing your own buffered I/O library.

As with Problem Set 4, we’re staging your work in two parts.

Reminder: You may not use code or solutions from previous years.

Get the code

Start with the cs61-psets Git repository you used for Problem Set 4 and run git pull --no-rebase handout main to merge our code, which is in the pset5 subdirectory, with your previous work. If you have any “conflicts” from Problem Set 4, resolve them before continuing further. Run git push to save your work back to GitHub.

Goal

Our simple IO61 library performs I/O on files. You will find the code in the pset directory in the file io61.cc. Our version of IO61 is correct for all inputs, but otherwise pretty stupid: it uses byte-at-a-time system call I/O and thus runs slowly.

You will introduce caching to the io61_file abstraction and use your cache to speed up IO61 operations. We’re giving you tons of freedom to implement the cache as you like. You may use memory-mapped I/O, prefetching system calls like madvise or posix_fadvise, or multiple threads or processes (although none of these are required). But you may not use another buffered I/O library or caching I/O library.

Your library:

Performance tests should report blue or green results (which means “at least as good as stdio”) on all tests. An excellent pset will additionally achieve very high performance (say, 20x stdio) on some non-sequential tests.

All your code should fit in io61.cc.

Evaluation

The leaderboard, and your pset grade, will be based on your code’s correctness and on its performance. For performance, we compare your code with a version of IO61 that uses stdio, as well as to a high-performance staff solution.

We provide some test programs that use IO61. Our tests run these programs and check their output for correctness, and compare the time they take with the time taken by the same programs using our stdio version of IO61. The programs are:

Program Description
cat61 Copies a file one byte at a time, using io61_readc and io61_writec.
read61 Like cat61, but writes using stdio, so it tests only IO61 reads.
write61 Like cat61, but reads using stdio, so it tests only IO61 writes.
blockcat61 Copies a file one block at a time, using io61_read and io61_write. -b BLOCKSIZE sets the block size (default 4096). -R reads one byte at a time instead; -W writes one byte at a time instead.
varblockcat61 Like blockcat61, but chooses a random size for each block, up to -b BLOCKSIZE. One-byte blocks use io61_readc and io61_writec, so this mixes the two kinds of call.
reverse61 Reads a file one byte at a time in reverse, seeking before each byte, and writes the result sequentially.
reverseread61 Like reverse61, but writes using stdio, so it tests only IO61 reads.
reversewrite61 Reads a file sequentially using stdio, and writes it to the output in reverse, seeking before each byte. The result is the same as reverse61’s.
stridecat61 Reads a file in a strided pattern and writes the result sequentially. It reads -b BLOCKSIZE bytes (default 1) at offset 0, then the block at offset STRIDE, then 2 × STRIDE, and so forth; at the end of the file, it starts again with the first bytes not yet read. -t STRIDE sets the stride (default 1024).

All the programs read the file named on the command line, or standard input if none is given, and write to standard output or to the file named by -o OUTFILE. Other useful options include -s SIZE (copy at most SIZE bytes), -r SEED (set the random seed for varblockcat61), and -A LIMIT (limit the program’s memory to LIMIT bytes, on Linux only). Run a program with -h to list all its options.

The grading server will have more programs that access files in other ways, and tests that use our programs in different ways.

Although this pset is about performance, correctness matters most. A program that runs quickly but incorrectly is worse than a program that runs slowly but correctly.

Tests (Pset 5a)

In the first week, as you begin implementing your library, you should write tests for IO61 at the same time. We provide a test harness, io61_tester, to make this easier; each test you write will be a small C++ program that runs a command using our test programs and checks what happened. Read iotest.hh for its full interface. Here’s an example:

// Test: Reading a file backwards one byte at a time
#include "iotest.hh"
#include <algorithm>

int main(int argc, char* argv[]) {
    io61_tester t(argc, argv);
    // Create a 32 KiB input file containing lines of text
    t.text_file("in.txt", 32 << 10);
    t.run("reverse61 -o out.txt in.txt");
    // The output should be the input, reversed
    std::string expected = t.file_contents("in.txt");
    std::reverse(expected.begin(), expected.end());
    assert(t.file_contents("out.txt") == expected);
}

As with the shell tester from pset 4, an IO61 tester first sets up a test environment, then runs a shell command. Here, that shell command will run one or more IO61 programs. Then, it checks the results with assert and functions like t.file_contents(name), t.stdout(), and t.stderr(). The command runs in bash, so it can use pipes and redirections, and it can run the test programs by name. The harness also fails a test if the command exits with a nonzero status, crashes, causes a sanitizer error, runs longer than its time limit (10 seconds unless the test calls t.set_time_limit), or writes far more data than expected.

Performance tests call t.report_timing() after checking their results. This runs the command again with our stdio version of IO61, then with yours, and prints both times:

$ t/perf-003
perf-003: 0.1556s (16 MiB), stdio 4.5935s (13 MiB): 29.52x stdio

The ratio is red if your code is much slower than stdio, blue if it’s about the same, and green if it’s much faster. Timing varies from run to run; to time several runs of each version and report the median, set TRIALS, as in TRIALS=5 t/perf-003.

Tests live in the t/, tt/, and torture/ subdirectories, one test per file. (There are no tt/ or torture/ tests in the handout.) To build and run a test, use make check-NAME, as in make check-reverse-001; this finds the test in any of those directories. You can also run a built test directly, as in t/reverse-001. A test that passes prints nothing (unless it reports timing); a test that fails says why:

$ t/reverse-001
reverse-001: t/reverse-001.cc:13: int main(int, char**): Assertion `t.file_contents("out.txt") == expected' failed.
--- command
reverse61 -o out.txt in.txt
--- stdout (empty)
--- stderr (empty)
(Run with `-d DIR` to keep the command's files.)
Aborted

To run a test with our stdio version of IO61, set IO61=stdio:

$ IO61=stdio t/reverse-001
$

A good test is:

Name each test after the access pattern it tests, such as cat, block, reverse, or stride, and start the names of performance tests with perf, as in t/stride-mytest.cc or t/perf-mytest.cc. Then make check-stride will run your test along with any other stride tests.

Each test runs its command in its own directory, which is removed when the test exits. To see the command’s files after a test runs, give the test an existing directory to use instead, as in t/reverse-001 -d mydir.

How to write tests

Think about the ways a cache can go wrong, and design inputs and commands that would expose them. Some ideas:

Commonly-installed utility programs can help set up input or check output. For instance, head -c N copies the first N bytes of its input, cmp compares files, and wc -c counts bytes. Since tests are C++ programs, you can also compute expected output directly, as the example above does with std::reverse.

How to proceed

The main work of this assignment is implementing the cache. Phases 1–3 are part of pset 5a; Phases 4–6 are part of pset 5b.

Pset 5a turnin (11/10, 11:59pm EST):

  1. Post at least three tests publicly to Ed, each with a brief description of what it tests. Your tests should cover different features. At least one of these tests should be a performance test. After the deadline, we’ll collect everyone’s tests and post them together.
  2. Implement Phases 1–3 as far as possible.
  3. Commit your tests and your library to GitHub.

Roadmap

It’s easy in this problem set to design something too complex and get yourself stuck. Avoid that problem by tackling the simple cases first.

Here’s a recommended roadmap. You should commit your code after each phase.

Phase 1

First improve the performance of io61_read and io61_write by ensuring that these library calls actually read and write blocks of data, rather than bytes.

The blockcat61 test program reads and writes data in blocks—but do its system calls use blocks or bytes? Run strace -o strace.out ./blockcat61 blockcat61.cc. (That command line tells strace to write its output to strace.out, so examine strace.out with a command like less strace.out or through VS Code. If you’re having trouble running strace, make sure that you’re in Docker and that you've previously run the command make.)

When you fix this problem, your code should still pass the correctness tests. Your performance should have improved on block I/O tests relative to the handout code, though it will still be much slower than stdio on byte I/O. (Our solution goes from almost infinitely slow to about half stdio’s speed on blockcat61 -b 1024. Your later changes may reduce this advantage, but in exchange for better performance on other tests.)

Phase 2

Implement a single-slot cache buffer for sequential reads. This will hold bytes [N, N+B) of the file, where B is some largish number (try different numbers). Any read request that lies within that range of bytes can be satisfied without making a system call.

This will improve your performance on byte reads (for example, read61 and blockcat61 -R). Your code should still pass sequential correctness tests. (varblockcat61, which combines io61_readc with io61_read calls, might be a special challenge—think about why!)

The interaction between cache buffers and the io61_seek call, which is used in non-sequential access patterns, is fiddly to get right. You may want to temporarily ignore non-sequential access patterns in Phases 2 and 3. This will mean your code will temporarily produce incorrect results for non-sequential tests, such as tests that use reverse61 or stridecat61.

Phase 3

Extend your single-slot cache buffer to also support sequential writes.

This will improve your performance on byte I/O tests. If you do this well, you should now match or beat stdio’s performance on all sequential I/O tests!

Short writes. A write system call on a pipe might write only part of its data, or fail with a restartable error like EINTR or EAGAIN. Make sure your io61_flush function handles these cases by retrying.

Phase 4

Fix your code to handle seeks correctly (but not necessarily in a high-performance way).

This should make your code produce correct results for all tests, including reverse and strided tests, but it may underperform stdio on some non-sequential tests.

Phase 5

Change your code to continue handling seeks correctly, but with good performance for reverse61.

For ideas, try running strace on the stdio version, bin/stdio/reverse61. What does it look like stdio is doing?

A correct fix for this phase should make your code both roughly equal stdio’s performance and produce correct results on all tests.

Phase 6

Finally, make your code outperform stdio on some tests!

Perhaps a bigger cache buffer will outperform stdio; perhaps memory-mapped files will help. If you have worked through the previous phases, you will have ideas of your own.

Make sure you commit regularly as you experiment with different potential optimizations. Real I/O performance is never perfectly consistent. You may find that some optimization ideas don’t work as well as simpler code—that’s part of what we want you to learn! If you commit regularly, you will always be able to go back to a previous working version, and to use commands like git branch or git bisect to run performance comparisons.

Checking your work

Use make check to run the tests in t/ and torture/, stopping at the first failure. To run some of the tests, use make check-NAME, which runs every test in t/, tt/, and torture/ whose name starts with NAME. For example, make check-perf runs all the performance tests, and make check-reverse-001 runs just one test.

Torture tests (pset 5b)

For pset 5b, we’ll release our own torture tests. Run git pull --no-rebase handout main; make check-torture to merge the torture tests and run your library against them. Like your tests, they all pass with IO61=stdio.

Make targets and options

Your code must work correctly with sanitizers turned on (though it will not be very fast). Run make SAN=1 check to check for errors.

To compile without optimization (which might help you debug), run make O=0.

To disable assertions, use make NDEBUG=1 check.

It’s often instructive to check the system calls made by your code, and to compare them against stdio’s. Strace lets you do this in Linux (Docker or a Linux host.) You can run an IO61 program under strace directly; for instance, strace -o strace.out ./cat61 < input > output. You can also ask testers to trace the IO61 programs they call. For instance, t/cat-003 runs the command line cat in.txt | blockcat61 -b 1021 | cat > out.txt. To run the same test while tracing blockcat61, run STRACE=1 t/cat-003. (The strace output is placed in the main pset directory with name strace.out.) If a test’s command runs more than one IO61 program, use STRACE=2 instead, which gives each program its own trace file named after its process ID. A command like STRACE=1 IO61=stdio t/cat-003 will run the stdio version of the blockcat61 program and dump its strace in strace.out. (Remember that the first 60–200 lines of any strace are startup noise; look for sequences of reads and/or writes to find the actual application.)

On Docker, tests run in a directory under /tmp, since writing files to your pset directory is very slow there.

Hints and troubleshooting

Read our file descriptors notes if you are confused about file descriptor system calls.

You will likely need to change most of the functions in io61.cc.

Stdio is a well-written package! It is OK if you can’t always beat it, especially for sequential I/O.

Write your own tests! This will help you shake out bugs in your code, particularly correctness bugs. What diabolical things can you think of to try?

If a program using your library produces incorrect results, it can be hard to figure out whether the problem is with reads, writes, or both. For instance, perhaps your read cache is wrong, so the program is reading incorrect data; or perhaps the write cache is wrong, so the program is trying to write correct data, but the data passed through to the kernel via system calls is wrong. To distinguish these scenarios, you can use strace to check things like file positions. You can also use the read61, write61, reverseread61, and reversewrite61 programs, which use stdio for half their work. The read variants use IO61 for reading and stdio for writing, whereas the write variants use IO61 for writing and stdio for reading. If cat61 and write61 produce bad results but read61 on the same workload produces correct results, you can be pretty sure the problem is with writes.

You may make a couple assumptions:

CPU performance. Add assertions in your code, since they can help you check correctness. However, assertions do take time to check, which could leave your code at a disadvantage relative to stdio. We will check the performance of your code with assertions disabled by running make NDEBUG=1 check.

If your code is slow, consider (1) the system calls it makes and (2) its CPU performance. For system calls, use strace to check: is a mistake in your code accidentally causing expensive system calls, such as many read calls that read one byte each? For CPU performance, consider whether there are functions that can avoid some extra work. It might pay off to have specialized io61_readc and io61_writec calls, for example.

Turnin

You will turn in your code by pushing your git repository to github.com and updating the grading server with your repository.

Please flag the commit on the grading server that you'd like to be graded.

Don’t forget to fill out README.md and AUTHORS.md.

This pset was originally created for CS61.