CS371p Spring 2021, 8 Mar–14 Mar

OOP Blog Post #7

What did you do this past week?

It was quite a busy week for me. I foolishly decided to do most of the project as soon as it was published, and took longer than necessary to realize that deallocation requests didn’t refer to the allocated blocks in the order that they were allocated in, but rather their order inside the allocator. There was quite a lot of other work that I put off due to this, including a problem set for Algorithms that included a LeetCode hard problem (the proof alone took me an entire day). Thankfully, I managed to get everything turned in on time.

What’s in your way?

I still have a few things due over the weekend before I can enjoy Spring Break.

What will you do next week?

I want to work on some personal projects, catch up on grading, bake, and apply to internships.

If you read it, what did you think of the Liskov Substitution Principle?

As I was reading the chapter, I found myself predicting the solutions to many of the problems raised by the bad examples presented. It seems like common sense that ISA relationships in the context of object-oriented design would be based on behavior — after all, the main motivation for having abstract base classes, as I understand them, is to provide a common interface for behavior, implemented as virtual or abstract methods. If a derived class deviates from this interface, then it shouldn’t extend that interface. The Liskov Substitution Principle seems like a formalization of this idea, and it has value in assigning a concrete name to this concept, and allows programmers to check their work more easily. The chapter also contained valuable insight about how the principle connects with the Open-Closed Principle; the two are almost isomorphic.

What was your experience of heap arrays, allocators, and digits iterator?

I love heaps. There’s a lot of variety in how heaps are implemented, from block-finding strategies, data structures used, and overall structure. dlmalloc is probably my favorite combination of various heap optimizations —it combines best-fit and next-fit, binning, and uses bitwise tries for nearly constant time malloc and free that has a reasonable balance of speed, cache efficiency, and fragmentation. I implemented it previously for CS429 and CS439, but there are other implementations that have advantages in other areas, like tcmalloc, which is supposedly very good for multi-threaded code, as well as buddy and slab allocators that are suitable for kernels. Of course, given that the implementation of heaps plays with raw memory and tends to require a lot of casting, debugging them can be a pain.

For this project, since we’re limited to first-fit, we can actually reduce the amount of metadata we need for each block. If we defer coalescing until the next time we iterate over the allocator, we only need to know the next block, not the previous, allowing us to save 4 bytes, or use it for a magic number to catch memory corruption. We would then coalesce not when we free, but when we iterate — if the current block is free, we can then merge it with all subsequent free blocks. Even though this is a linear-time operation, so is iteration, so we don’t lose any asymptotic performance.

The concept of allocators in C++ is really interesting and gives us a lot of freedom in terms of memory management. It allows code that might have specific memory requirements to still be able to take advantage of the standard library.

The digits iterator was a fun and interesting demonstration of an iterator that differed from the usual iterator over a container of values.

What made you happy this week?

I’m participating in UTCTF with a few other people. It’s my first time doing a CTF, so I’ve mostly been very confused. Many of the problems and concepts are completely new to me, and I’ve been learning a lot trying to crack some of them open. I haven’t been very successful, but it’s still pretty fun!

What’s your pick-of-the-week or tip-of-the-week?

One of my favorite resources about heaps is this link. It contains a lot of very useful information about practical optimizations for a heap implementation, much of which are used by dlmalloc, which was created by the author.