Doing this lab was one of my more memorable experiences at CMU. It was tons of fun, but barely getting any sleep for 3 days because I put the assignment off was less fun.
I put in some horrible last minute hacks to optimize for the autograder and raise my grade, like doing a pseudo-bubble sort. Every time I coalesced two adjacent free blocks, I would compare the adjacent nodes in the linked list and swap them if they weren't sorted. That raised my allocation efficiency a tiny bit for certain test vectors- just high enough to bump my grade up a couple points. :)
I also put it off to the last minute. I had a pernicious bug in my coalescing code that was hard to debug. After one failed rewrite and only a few hours left, I resorted to taking the book's array version and optimizing it for utilization. My throughput was shit but I was able squeeze past their minimum score and squeak a C. My semester, the grading was pretty tough, only 6 or so people over 90. In other semesters, I know at least that many get 100.
I just finished taking 213 last week. It's one of those courses that is quite difficult, but still rewarding. Even though it was quite hard to score an A on some assignments (like this one), I still felt that the grading scheme was "fair" and reflective of my actual understanding relative to other students.
I ended up getting a B on malloc, and the morning after I finished I woke up with a clever idea for an optimization that would significantly decrease utilization and probably get me the A. If only I had started a day earlier!
We did this lab at the University of Utah because the Systems class is taught out of the same textbook. I also loved this lab. If I remember correctly we had a leaderboard, and it was fun competing with everyone else.
Most of the labs for this textbook were great: writing a shell, implementing common math functions by bit twiddling, buffer overflows, disassembling the bomb with the debugger, etc. It was a great class. Definitely not easy, but a lot of fun.
IIRC when I took 213 (Fall '07) a some folks somehow figured out bit of what the autograder branchmark was, and so added tricks like odd if statements to allocate extra memory for very specific sizes (which therefore, when freed and coalesced, allowed enough space for some following large allocation).
Seems like their new benchmarks might limit that sort of behavior
Can someone post a PDF (or something similar) of CMU's redesigned malloc lab?
Purdue's malloc lab [0] was much simpler: you get the algorithm, the data structures you're supposed to use, and the method signatures. It has to be thread safe. But there were no performance requirements. Consequently, it's something like a 10-20 hour lab.
In 2000 at least (when I took it) you could see a real-time leaderboard with the performance scores of classmates, so even after you earned an A, you could compete for the fastest implementation.
>Because we are running on 64-bit machines, your allocator must be coded accordingly, with one exception: the size of the heap will never be greater than or equal to 232 bytes. This does not imply anything about the location of the heap, but there is a neat optimization that can be done using this information. However, be very, very careful if you decide to take advantage of this fact. There are certain invalid optimizations that will pass all the driver checks because of the limited range of functionality we can check in a reasonable amount of time, so we will be manually looking over your code for these violations.
I’m curious about these optimizations and the issues that arise, any pointers on more reading?
I might be wrong but the heap size being at most 232 bytes means that heap blocks can be represented by two bytes: one byte for the start offset, and one byte for its length.
Every CS student at Georgia Tech does this as their final Computer Organization assignment. One of the most memorable and instructive experiences of my undergrad, thus far.
This is one of the best assignments I worked on at CMU. Putting in 20 hours of coding to actually get the passing malloc was not the most fun part. It was spending additional 40 hours to beat others at the leaderboard :) Gamification at it's best.
Bomb lab was my other favourite, where else do you get to read and make sense of assembly language programming.
Cool! On a related note, having recently cracked open my old k&r c programming language book, I was reminded they cover a fairly complete implementation of malloc as a case study.
Well, as a CS student in a not so highly ranked university, it's not surprising that grads from top CS schools end up in Google, Microsoft Research, etc. They know how stuff work much deeper than others. Of course this is not a generalization. There are some crazy dudes in other universities or even not in university at all.
I don't doubt that this is true at times, but what do you think they teach in mid-tier schools? They use the same textbooks and curricula that other schools do. For example, most of the schools within driving distance of Austin use UT's courses at least as a guide for course design. They're not just handing CS students a box of crayons and hoping for the best.
I have a cs degree from a good private university but with a not so great cs program. I didn't learn anything more than the basics of c++ programming, as I felt that it would be best to do the bare minimum. Looking back, I truly wish I had taken courses that really challenged me, as I'm finding that I use my background more and more these days.
Yes, people claim 'all CS degrees teach the same stuff and a degree from any place is the same' and I think they're crazy. Look at what a top university actually teaches, and then look at a mid-tier university and it's not even remotely the same league at all.
I think some people genuinely think there's some kind of national or even internationally agreed syllabus.
Someone was trying to tell me a first from Luton was the same as a first from Cambridge because they were the same degree course and the same grade. They're mad.
Yeah, they generally tend to be gameplay/engine specific. Much in the same way that you wouldn't want to use an open world(heavy emphasis on streaming, instancing) for a fighting game(no frame drops ever, 60 fps) and vice-versa.
Usually they get broken down into a couple discreet subsystem:
1. Particle systems - Pooled, fixed size.
2. Per-level/region entity pooling - Tuned based on encounter.
3. Strings, etc - Usually preallocated to avoid fragmentation.
4. Ring/command buffers - Again, fixed size and mostly preallocated. Generally used for rendering and job systems.
There's a couple other case I'm missing and as always a lot of this is also biased not only towards avoiding allocation but also arranging data in memory in such a way that it's friendly to your L1/L2 cache(things accessed sequentially laid out in memory sequentially, SoA/AoS and all that good stuff).
There's a lot of really impressive engineering that goes into things like allocation, in-place loading, seek-free loading(less so now with caching to HDD) and the like.
This also makes a fantastic interview question. I would never expect someone to finish but can lead to a great discussion on the types of problems they've seen in the wild with respect to allocation and how to they approach an ambiguous problem(purpose build allocators will always be better).
Ah, the legendary and beloved malloc lab. I am really glad they are working to keep this one visible and modernized.
I know a lot of schools do this, but if you've never had to write your own allocator, I cannot recommend it enough as an exercise!
Implementing a general-purpose malloc from scratch and attempting to beat cstdlib's malloc goes down as one of the top 3 most invaluable programming projects in the CS curriculum at my school. (The others being an OS kernel and a register allocator.) I do not do low-level programming in real life--at all--but I think every computer scientist and software engineer should have an understanding of all that has to go on to support shinier layers.
Former 213 TA here. This was by far the most enjoyable lab in the course - Bomb lab is a close second but this provides a more significant ‘levelling up’ experience.
The actual lab is currently offered split into 2 checkpoints with the 1st checkpoint having somewhat lower perf/efficiency thresholds. While dealing with non-small C code is one of the good parts of the lab, I felt the major takeaway for me was the improvement in my pointer bug fixing skills.
Hi there, I'm assuming TA means Teaching Assistant. I'm a CS teacher on a small polytechnic university and I'm looking for ways to transition some of my current courses from lecture-based with labs to project-based like this one seems to be.
Could you expand a little bit on your experience? Like, was all the course divided in 3-4 week-long projects, was there theoretical classes, how were the students graded (i.e., did they have exams as well, homework, etc.)? What were the other projects?
I TAed at Virginia Tech for a computer systems course (in 2010) that was based on the CMU course. It used the book, and the projects were also based off of the CMU projects. You can look at the past seven years of what they did here: http://courses.cs.vt.edu/~cs3214/
Given the rigour in the remainder of the exercise, this surprises me. Figuring out when to call munmap can be a significant part of what makes a heap implementation 'high performance'
Also, I wonder how common allocators like dl as well as hoard and its other concurrency aware counterparts would perform on this assignment.
The textbook is excellent and the course staff is almost always great at providing reasonable guidance. The earlier labs also do an excellent job of ramping up so that the increase in difficulty doesn't seem extreme. And being around dozens of other students in the same boat helps a lot, as well.
Several of the labs have a somewhat incremental process where you start out with an acceptable implementation and optimize in steps.
^ can second this. I TA'd the version of this at my uni (exact copy of the cmu course). Before this, we had students implement linked-list hashmaps which exposed students to working with void's.
not quite as intimidating, but the tests on this assignment are pretty harsh compared to previous assignments.
I finished 4th year CS in Aus, and I'd only needed to touch a compiler twice in those 4 years.
The US courses tend to be a lot more academic focused, teaching you actual CS. Whereas a lot of other places try and give you things they expect you'll need in a work place, which tends to be experience with Java, MySQL, Python, and web.
That's too bad, as none of those "things you'll need in the work place" sound like they belong in upper year computer science, and, at least in my experience, it was those upper year courses that made the degree worthwhile / distinguished it from community college level curriculum.
Neat, I am an IT major, but I am a sucker for CS, programming and security. Been looking for a projects to help my understanding of how things work. (maybe improve marketability also)
Thank you for giving me a new project,
-A random university student.
Project you can follow that link Unix comprehension, security and programming:
-implementing malloc (C)
-implementing nm and otools (C) (basics options only)
-implementing a ftp server (a fork for each new connection) or a basic IRC-like server (maybe using ring buffers, and only non-blocking I/O if you want to write in C)
-implementing ping then traceroute (in C obviously) (and nmap if you really want to push it).
In security, do small and easy challenges, like nebula (less than a day if you already know your stuff, i'd think maybe ~3 if you don't) and protonstar (i already knew some of the exploits and it still took me 4 days). Don't do those challenges alone, find a friend to help you: a second brain can think of new solutions and allow you to explain what you want to do (and just by explaining you'll get closer to find why it doesn't work, or why it does). The other challenges are not worth it if you just want to get how basic security work imo. At my school we then had to program some stuff like ptrace or strace (i don't remember which), it's pretty helpfull too, and it help a lot understanding gdb. Ah, and prior to the challenges, we rewrote a small part of the libc (strlen, strlcat and stuff like this) in assembly, and it was pretty helpfull (decompilers are fine, but its easier if you know a bit about assembly, at least with protonstar). If you want to do it, chose like 5 easy functions then 5 function which might use rep string operations, and implement them, it'll take you ~2 days (most of those will be research and reflexion, and you can do that during classes, like most of the security stuff actually).
I'll repeat myself, but if you're not crazy about security, i really advice you to work on this with a friend, security is boring when you're stuck (and really interesting when you're not)
Can anyone who has tried doing this outside of university recommend some good benchmarks, or resources for setting up a personal lab testing environment for this? I want to give this a shot and didn't get to do it in university.
We used this same project when I was GMU. I definitely enjoyed this project and some of the other projects we had in the same class such as implementing a TLB and page table and the "binary bomb" project.
For assignments such as this which primitives are the student expected to use? mmap & munmap?
Or are they given a flat chunk of memory? Or a chunk of memory that can grow on one end?
CS50 is an intro level course that has a lot of people who've never programmed before in it. It seems like this course is for CS majors. But probably neither is that comprehensive. It's good to know this low-level stuff, but you need to know much more to be a productive programmer nowadays since there are few jobs where you're just going to be writing systems code.
I put in some horrible last minute hacks to optimize for the autograder and raise my grade, like doing a pseudo-bubble sort. Every time I coalesced two adjacent free blocks, I would compare the adjacent nodes in the linked list and swap them if they weren't sorted. That raised my allocation efficiency a tiny bit for certain test vectors- just high enough to bump my grade up a couple points. :)