Hacker News Reader

Comment by kevindong | Hacker News Reader

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.

[0]: https://www.cs.purdue.edu/homes/grr/cs252/lab1-malloc-new-he...

View on HN

Here's an old link: https://www.cs.cmu.edu/afs/cs/academic/class/15213-f10/www/l...

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.

It's 2 to the 32nd power, not 232 :-)

Oh well, that makes more sense than 232.

But then again, it lets you fit the bookkeping data into a single 64bit word (32bit pointer + 32bit size).

Reply on news.ycombinator.com