Written by Julie Zelenski
Below is our plan for the quarter. Topics may occasionally be shuffled around and we will keep this syllabus updated to reflect the current schedule. Exam dates are set at quarter start and will not change.
In the readings listed below, B&O is Computer Systems (Bryant and O'Hallaron), K&R is The C Programming Language (Kernighan and Ritchie), and EssentialC is a PDF available at http://cslibrary.stanford.edu/101. A digital copy of K&R is available to Stanford students via Safari Books Online. Code from lecture will be posted to the class directory in /afs/ir/class/cs107/samples/lectN where N is the lecture number.
SCPD posts lecture recordings a few hours after live capture at myvideosu.stanford.edu.
| Topics | Reading/Handouts | |
|---|---|---|
| Week 1 | ||
| Lecture 1 (Mon): Welcome Join us for an overview of what to expect in CS107. We'll go through course logistics, learning goals, a tour of some surprising realities about modern systems Slides |
Course overview handout B&O Ch 1 (skim chapter for quick overview of what is meant by systems and preview of topics to come) Systems programmers and zombies (a must-read about the adventure ahead!!) |
|
| No lab during first week (optional unix help sessions listed on calendar) | UNIX quick study guide by CS107 alumna Allison Yuen | |
| Lecture 2 (Fri): Transitioning to C A whirlwind tour of C for C++ programmers using the unix environment. Slides |
Brush up on C syntax, data types, operators, control structure, function calls. K&R Ch 1, 2, 3 (skip sections on arrays until next lecture) or EssentialC sections 1, 2, 4 |
|
| Week 2 | ||
| Lecture 3 (Mon): C pointers & arrays Now it's time for the tricky parts of C, including use of * and &, arrays and pointers, pointer arithmetic, and the dynamic allocation functions malloc/realloc/free. Slides |
K&R Ch 1.6, 5.1-5.5 or Essential C section 3 on mechanics of pointers and arrays. Pay special attention to the relationship between arrays and pointers and how pointers/arrays are passed as parameters. Oddly enough, K & R doesn't have much to say about using malloc/free (although section 8.7 talks about how to implement malloc!); for this, I recommend a careful read of section 6 of Essential C. | |
| Lab 1: C programming under Unix Hands-on practice with C-strings and unix development tools |
K&R (1.9, 5.5, Appendix B3) or Essential C section 3 for C-strings and string.h library functions. C-strings are primitive compared to Java/C++ strings, take note of the manual efforts required for correct use and pitfalls to avoid. Peruse our Mercurial and gdb tool guides. | |
| Lecture 4 (Fri): More on pointers Follow-up on C-strings after this week's lab, trying to tease out the minute differences between arrays/pointers (while reinforcing ways they are the same), and compare/contrast stack and heap allocation. One tricky issue to work through is passing pointers themselves by reference. Slides |
K&R 5.6-5.9 (skim parts on multi-d arrays) | |
| Week 3 | ||
Lecture 5 (Mon): void*, function pointers Pointer typecasts, untyped void* pointers, and how used for generic behavior. Function pointers and use as client callbacks. Writing generic functions, being a client of generic functions.Slides |
K&R 5.11 (function pointers). There isn't much new reading for void*, be prepared for further application of mechanics of pointers, arrays, and pointer arithmetic to manipulating pointers of indeterminate type. |
|
| Lab 2: C memory Examining pointers/arrays, using/writing C generics, using tools to understand and debug memory |
Our Valgrind and gdb tool guides | |
| Lecture 6 (Fri): Pointer wrap, bits, bytes, and bitwise operators Resolve any open issues on void* and review rules for wise use of memory. Callback functions (function pointers). Then if any time remains, we drop down to examine bits and bytes and introduce the C bitwise operators.Slides |
K&R 2.9 and B&O 2.1 on bit ops and data representation (skip 2.1.7 on boolean rings). | |
| Week 4 | ||
| Lecture 7 (Mon): Data representation, integer types Integer-family types (chars/short/long/pointers). ASCII character set. Two's complement representation and properties of integer arithmetic. Unsigned vs signed types. Operations on mixed types. Truncation and sign extension. Slides |
For integers, B&O Ch 2.2-2.3 (skim the formal proofs, but important to take away solid working knowledge of two's complement and behaviors of integer operations). This is important reading to have done before lecture/lab! | |
| Lab 3: Bits and bytes Hands-on practice with bits and integers |
||
| Lecture 8 (Fri): Floating point IEEE floating point representation. Understanding the features/limitations of the floating point number line. Rounding, exceptions. Slides |
B&O 2.4 on floats. (skim formal proofs, strive for reasonable understanding of floating point representation and its limitations). You'll get much more from lecture/lab if you have done this reading beforehand! | |
| Week 5 | ||
| Lecture 9 (Mon): Intro to x86-64 assembly, data movement Representation of pointers, structs, instructions. Introduce assembly/machine language and find out what's happening underneath the hood of the C compiler. The x86-64 instruction set architecture and its almighty mov instruction. Addressing modes, data layout, and access to variables of various types.Slides GCC Explorer (start) GCC Explorer (addressing modes) GCC Explorer (suffixes and types) |
B&O 3.1-3.3 for background info on assembly. Very carefully read B&O 3.4 on addressing modes and data transfer. The multitude of addressing modes is one of the things that puts the first C in CISC. Our handy x86-64 Guide |
|
| Lab 4: Floats Hands-on float dissection |
||
| Lecture 10 (Fri): ALU ops, control We're on to the arithmetic/logical ops and implementation of control structures (if-else and for/while loops). We'll be tracing through much assembly code in these lectures. By having done the reading before lecture, you'll be in a better position to follow along without getting lost :-) GCC Explorer (start) GCC Explorer (ALU) GCC Explorer (Control) |
B&O Ch 3.4 on data layout and access, 3.5 on ALU ops, 3.6 on control structures. There is a lot of detail in these sections, especially when absorbing the assembly, but resist the temptation to skim. It is key to get a solid foundation on these basics which requires following the assembly closely and working the self-test exercises to be sure you have it down. | |
| Week 6 | ||
| Lecture 11 (Mon): Function calls, runtime stack Implementing function calls: asm instructions push/pop/call/return, how rsp is managed, linux C calling conventions, parameter passing rules, and management of stack housekeeping.Slides |
B&O 3.7 | |
| Lab 5: Assembly x86-64 in all its glory |
Our x86-64 guide | |
| MIDTERM EXAM Friday May 6th in-class No alternate/makeup exams |
||
| Week 7 | ||
| Lecture 12 (Mon): Asm wrap Use asm understanding to explore stack features: why recursion works, why locals are cheap, how variable arguments work, consequences of various stack misuses (uninitialized locals, returning pointer to local, overrun/underrun on stack variables, and so on). Caller/callee-saved registers, how stack fits into address space, and binary encoding of machine instructions, and we're ready to wrap up asm. |
||
| Lab 6: Dissecting the runtime stack One of my favorites of all the labs-- lots of fun explorations with the stack! |
||
| Lecture 13 (Fri): Build process The step-by-step process of how C code becomes an executable. Preprocessor, compiler, assembler, linker, loader, what each tool does and how they fit together. Symbol resolution, relocation. Basics about libraries: static, dynamic, shared. |
B&O Ch 7 (skip 7.12 on PIC) | |
| Week 8 | ||
| Lecture 14 (Mon): Managing the heap How the heap fits into the address space. Design decisions for implementing malloc/realloc/free. Performance tradeoffs (throughput, utilization). Compare/contrast stack versus heap allocation. Slides |
B&O Ch. 9.9-9.11 covers heap allocation implementation, garbage collectors, and memory misuses. There is a lot of very detailed code in 9.9.12 It's ok to skim this code for now (if you are sure to understand the underlying principles) but you will eventually be assigned the job of writing a heap allocator and will want to be intimately familiar with this code at that point, so making the investment now will pay off later. :-) | |
| Lab 7: Build process Compilation steps, tools for examining executables |
man pages for nm and readelf |
|
| Lecture 15 (Fri): Code optimization What optimizing compilers do and don't do. Explore transformations such as constant folding, common subexpression elimination, strength reduction, code motion, loop hoisting. Quick overview of instruction-level parallelism, superscalar execution, and pipelining. Timing tools and profilers to measure code performance. |
B&O 5.1-5.6 and 5.13-5.15, skim 5.7-5.11. (read 5.12 for next lecture) | |
| Week 9 | ||
| Lecture 16 (Mon): Memory hierarchy, locality, caching Understanding storage hierarchy (registers -> caches -> memory -> files) and how properties change as you move downward (fast/small/expensive => large/slow/cheap). Temporal and spatial locality of reference and its effect on performance. Caches and writing cache-friendly code. Measuring memory performance using callgrind with cache simulation. Slides |
B&O 5.12, 6.1-6.3 and 6.5-6.7, skim 6.4. The reading gets fairly dense, most important to get big picture. | |
| Lab 8: Code and memory optimization Experiments in optimization, profiling using callgrind |
Our callgrind guide | |
| Lecture 17 (Fri): Wrap Wrap up course themes, preview courses/opportunities post-107, and try to reach closure on any loose ends. Bring questions if you have them! |
||
| Week 10 | ||
| Memorial Day (Mon): No lecture | ||
| Week 11 | ||
| FINAL EXAM exam info page Wednesday June 8th, 12:15-3:15pm No alternate/makeup exams |
||