CS 107: Computer Organization and Systems is the closest thing Stanford has to a “weed-out” class for the increasingly popular Computer Science (CS) major. Going into the class, I heard mixed reports from upperclassmen. Some said that 107 (the class is so infamous we drop the preceding “CS”) was so time intensive and difficult that it ruined their quarter and their GPA. Many said that even after spending 30-40 hours a week on the class, they had to retake it. Others said it was the best class they’ve taken at Stanford – the class that took them from novice programmers to hardened coders. When I enrolled in the course, I stuck to one of my maxims, “Hope for the best, prepare for the worst.”
As implied by the title, 107 delves deeper into the workings of a computer, flirting with the boundary between CS and Electrical Engineering. In short, I think it’s a class that’s intended to help students really understand how our computers take binary bits “01010101” and turn them into the Microsoft Word program I’m currently typing in. We code in the C language, which is the barebones version of the widely-used C++ language, because it maps efficiently to the machine instructions that are more easily read by the computer. The class that precedes 107, CS106B, is taught in C++ and the switch to C is quite drastic because all of the tools and data structures are no longer readily available. Almost every tool must be built from scratch, forcing us to understand it inside and out.
One of the most important concepts we learn is that of the stack and heap memory. The stack is a temporary memory storage system that is used for local functions and computations. For example, if we wanted to write a program that added two integers, we would place those integers on the stack and just add them. The heap, on the other hand, is for dynamic memory used across multiple functions. A program that keeps a sorted list of names, gives you tools to manipulate those names, and allows external programs to reference the list, would definitely need to use the heap. We learn that using the stack is very fast, while the heap allows for maximum accessibility.
After using the heap allocator extensively for our other homework assignments, our final assignment was the notorious Heap Allocator project. This behemoth of a project asked us to implement our own heap allocator using direct manipulation of the memory. Not only did our code need to work with great precision, it was tested for Utilization (efficient usage of memory) and Throughput (speed). This assignment gives us the option to work in partners, so I decided to partner up with Krister, a Stanford Law student who found that law school just wasn’t what he had imagined. He finagled his way into the Masters in CS program, under the condition that he take all the undergraduate level classes first. We met randomly in 107 lab, a required weekly session that helped us get a hang of the concepts taught in lecture that week.
Many partners find the project to be a source of argument, but Krister and I had a chemistry that was essential to our success. We were given two weeks, the first week being the Thanksgiving break while Krister was home in Washington and I was home in the Bay Area. So we agreed to work via Skype, and I would be the designated coder – though I physically typed everything, we talked over each line and agonized over the little bugs in our code. The beauty of coding together is that we often pick up on different mistakes, and thus complement each other in our ability to fix our code. I imagine that’s what it feels like to write programs with fellow software engineers at a tech firm – you work together in deciding an algorithm, and both search for mistakes or ways to improve the code. The “Aha!” moments were so precious, and each time we felt a little closer to our destination.
One problem in particular took us more than two hours to solve. We had created a function that attempted to combine free blocks – memory that had not been designated to hold anything, and there were four scenarios to consider: when a block is surrounded by reserved blocks, when a block is only preceded by a free block, when a block is only followed by a free block, and when both neighboring blocks were free. This system caught every possible iteration, or so we thought, and yet we were still running into errors that brought us back to this piece of code. After two and a half hours of agonizing over each character, Krister noticed that the line that checked for the final case was missing two “!”s. The difference was as subtle as this:
Our incorrect code: if (nextBlockIsFree && previousBlockIsFree) {…
Correct code: if (!nextBlockIsFree && !previousBlockIsFree) {…
In our hundreds of lines of code, these two exclamation points held us up for almost three hours! So is the meticulous nature of programming, requiring caution in each step. Making the mistakes is easy, finding them can be hard, and then fixing them can be impossible. We were advised by 107 survivors to try and get a simple algorithm working before trying anything fancy. We started with the Doubly Linked List strategy, hoping that we could get it working within the week, then transition to a more complicated Segregated Free List strategy. The first week was trial by fire, and we ended the week slightly behind our goal – and I started to worry, because I knew students who never got their program to work; submitting a non-functional program could result in no better than a C on the assignment.
We were provided a way to check the utilization and throughput of our program, and the full-credit benchmarks were 65% / 80% respectively. On Monday of the second week, four days before the due date, we finally got our doubly linked list to work, and had a meager 15% / 7%. Our friends reported numbers between forty and sixty, and we were flabbergasted! Once we got the basic structure working, we worked on a few major optimizations – ways to maximize our stats. On Tuesday, we felt that we had improved the program significantly, but our numbers were still stuck at 35% / 21% and I began to freak out. It just didn’t make sense!
That night, my next door neighbor Maneesh came over to talk about the project and asked if we had switched the compiler flags. I said, “Huh? Compiler flags?” My partner and I had been oblivious to the compiler’s ability to streamline the process by which our code turned into machine instruction. Changing the flag literally meant changing 1 character – the compiler flag changed from “-O0” to “-O2”. And just like that, our numbers shot up to 60% / 70%! At that point, we had a difficult choice to make. Did we switch to the segregated free list strategy with three days left? Or did we stick to this implementation that many said would be impossible to optimize enough?
We chose to buckle down and commit to the strategy we had initially started with. We wanted to prove people wrong. We spent the next days trying myriad optimizations, many of them incredibly clever. We were able to increase our numbers to 78% / 87%, and we suspect that with a couple more days we could have increased them. Our implementation was a lot simpler than most of the others, and yet still performed very well. The sigh of relief we shared when we hit “submit” was indescribable. We both felt proud of our heap allocator, our baby, a result of 42.5 hours of hard work and all of the material we had learned throughout the quarter. We ended up getting an A- on the assignment, due to some little edge cases we hadn’t accounted for. But I’m still happy about it. We built from scratch a fundamental component of 99% of programs, we built a strong friendship, and we survived the consuming yet rewarding class that is 107.
Leave A Comment