Posts

TSC is a register that increments on every CPU tick. RDTSC is the assembly instruction that reads TSC into EDX:EAX. RDTSCP is the assembly instruction that reads TSC into EDX:EAX and also reads the processor ID (IA32_TSC_AUX) into ECX. Equivalent to doing RDTSC + RDPID in a single instruction. Benchmarking a critical session of code is as simple as start = rdtsc() // get current counter value .... beep boop, executing code .... cycles = rdtsc() - start // theoretically the number of cycles Sadly, reality has a surprising amount of detail. ...

An optimization of free() using boundary tags Last week, I was concerned about the performance of the coalescing algorithm. In particular - could I be smarter about coalescing by trading off memory for time? Memory is “cheap”, so I’m happy to store some extra bytes that facilitate the coalescing process. As a reminder, the two embedded data structures in the heap: struct FreeBlockHeader { size_t size; // size of free space FreeBlockHeader* next; // location of next free block }; struct AllocBlockHeader { size_t size; // size of allocated space }; The coalescing algorithm works by continuously comparing the head of the free list with every other node in the free list - until no more coalescing is possible. ...

In v0, we made the simplifying assumption that all the data we work with are fixed-size blocks. Now, we’re going to relax the assumption: data can now be requested in any size. Our simplifying assumptions meant that we didn’t have to track how much free space is available; we could just iterate over the blocks until we found one that was marked as empty. The problem with variable sizes is that now, we need to do some bookkeeping. When we request memory, our memory allocator needs to know: ...

For the next couple weeks, we’re going to write a memory allocator. I’m dumb, so I need to start from dead-simple problem constraints and work my way up to increasingly complex constraints. As such, we’ll write this allocator in stages. What is the memory allocation problem? Every process gets allocated memory - but some memory demands are more dynamic than others. This means that the programmer must bear responsibility over memory allocation. ...