This assignment was to implement a self-contained memory system with a varying amount of heap space, and compare its performance to the default implementations of malloc and free. The assignment also specified that the memory system must use a Next Fit allocation model.
The main ways that I achieved decent performance were by taking advantage of header parallelism, and a forked search algorithm during coalescing.
By header parallelism, I mean that the Free and Used block headers each had identical data. This meant that I could use casting to treat any block header as Free or Used as I needed. Or if a permanent change was required, I could simply flip the flag inside the header from Free to Used (or vice versa). This meant that the only time a constructor would be called was when splitting a Free block during allocation. When deallocating a Used block, no constructors were required at all.
For my search algorithm, I took advantage of the mandatory Next Fit policy when coalescing, beginning each search at the NextFit pointer when trying to place a newly Free block back into the Free List. From there, I checked the newly Free block’s address against NextFit’s address, then forked in the appropriate direction depending on whether it was above or below. As NextFit was more likely to be in the middle of the list, this brought the time complexity of the search down closer to O(logN), as opposed to the linear time of O(N) expected of iterating through a double-linked list.
Test Results
Sean Foreman Game Development 