Implementing Malloc: Students and Systems Programming [pdf]
cs.cmu.edu
cs.cmu.edu
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 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!
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.
Seems like their new benchmarks might limit that sort of behavior
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.
[0]: https://www.cs.purdue.edu/homes/grr/cs252/lab1-malloc-new-he...
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.
I’m curious about these optimizations and the issues that arise, any pointers on more reading?
But then again, it lets you fit the bookkeping data into a single 64bit word (32bit pointer + 32bit size).
And pfft, "upper level my ass", some people take 2110 their second semester.
Bomb lab was my other favourite, where else do you get to read and make sense of assembly language programming.
Computer Systems: A Programmer's Perspective
http://www.cs.cmu.edu/afs/cs/academic/class/15213-s16/www/sc...
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.
Even in managed languages you see extensive use of pooling to achieve the same effect.
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.
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.
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.
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?
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.
Several of the labs have a somewhat incremental process where you start out with an acceptable implementation and optimize in steps.
not quite as intimidating, but the tests on this assignment are pretty harsh compared to previous assignments.
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.
Thank you for giving me a new project, -A random university student.
-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)
Source: I did this lab a month ago at CMU :)
At technical school, using MS-DOS, we used a chunk of memory static dimensioned at compile time.
A couple of years later at the university, on UNIX systems, brk().