This week, I worked on implementing the malloc lab from the CS:APP3e Lab Assignments. The main topics I focused on were system calls, data segments, memory fragmentation, and sbrk/mmap.
I had already gone over most of these concepts in a previous post, so this time was more about translating that understanding into an actual implementation. There are several ways to implement malloc, including Implicit Free List, Explicit Free List, Segregated List, and Buddy System.
On top of that, there are different strategies for finding free space, such as First Fit, Next Fit, and Best Fit. I mainly implemented Implicit + First Fit and Explicit + First Fit, and extended it to Implicit + Next Fit as well. The other approaches turned out to be more difficult than expected, so I didn’t get to explore them as much.
The biggest thing I realized while working on this was how important it is to design things in a very detailed and precise way. Without proper comments, it’s easy to lose track of your own assumptions in long code. For example, I often got confused about whether a “size” referred to the payload size or the total block size, or whether a macro expected a header pointer or a payload pointer. These kinds of inconsistencies kept creeping in, so I tried to be much more explicit with naming and definitions. It also made me think that in a team setting, these definitions would definitely need to be documented and shared.
I also feel like I’m slowly getting used to reading large codebases. Writing and using my own macros helped me understand why they are so heavily used in bigger projects, and I’m starting to get a better sense of how to approach reading them.
For the AI team project, we worked on integrating a B+ Tree into the mini SQL system we built earlier to improve the performance of range queries. The focus there was more on understanding the structure and purpose of B+ Trees rather than just implementing them.
This time, I also tried a different approach to studying. Instead of going through the code line by line from the beginning, I focused on understanding the overall flow first. I asked AI to generate markdown explanations for each stage, and then used those as a guide to explore the code in a more top-down, question-driven way. It turned out to be quite effective, so I’m planning to keep using this approach.
I’m still figuring out the best way to read large codebases.