w7d3: Current issues with compacting

The free list is stored as an unsorted single-linked list to save a) space (minimum block size) and b) time (insertion).  Used blocks are linked to from the header list, also unsorted.
There are two ways of doing compacting: sliding and arbitrary.

Arbitrary compacting: blocks are moved at random to free spaces. Order of blocks is not preserved.
Sliding compacting: blocks are pushed together (moved by offset) to the free space. Order of blocks is preserved.

Preserving blocks gives better cache locality on the premise that related objects are often allocated together in time.

Optimally, preserving blocks is the better idea. However, there are two constraints that makes this hard:

1. Memory is allocated from the top of the heap and no other location.
2. Compacting is allowed to take time, but it needs to be incremental so it can run in a given time slice.

(1) makes a perfect match for arbitrary compacting, where the top-most object (if unlocked) is moved to the bottom of the heap, freeing memory. However:

Issues with allocating objects at top of heap
Any object that is locked will effectively limit how much heap is available. Ponder the following allocation (_ = free, O = unlocked, X = locked)::


    [_______OOOO__OOOO_XOOX_______]

In this situation, there will never be any larger block available than what's left at the right side of the X, regardless of how well-compacted the rest of the heap is.  Therefore, simply increasing the top pointer is not a good idea. All available memory needs to be utilized, regardless of compacting option.

Greedy sliding, to free up as much memory as possible::


    1. [_______OOOO__OOOO_XOOX_______]
    2. [_________OOOOOOOO_XOOX_______]
    3. [__________OOOOOOOOXOOX_______]

When choosing between segments 1 and 2 (3 is locked between Xs), pick the one that causes the largest continuous block of free memory after move, i.e. move block 1 to the right.  Disregard any block with one or more X:s in them. Wiht a slightly different layout, it looks like this::


    1. [_______OOOO__OOOO___OO__X____]: g1 left
    2. [_________OOOOOOOO___OO__X____]: g3 left
    3. [_________OOOOOOOOOO_____X____]: done.

This all requires sorted list of used blocks and free blocks to find largest continuous areas not dispersed with locked blocks.  Insertion can be done sorted, for O(log N) in malloc()/free(), or they can be sorted in compact() and re-sorted on each entry. On each subsequent compact step, the list would have to be sorted, but it would also always be semi-sorted.  Thus, an algorithm can be picked that has best performance when the list is already in near-order.

Start at bottom also problematic
It's not certain, however, that we will have an ideal situation, in fact, the first objects tend to live longer, i.e.:

    1. [X______OOOO__OOOO___OO__X____]: g1 left

which means we cannot allocate from start.  Instead, have to allocate in free blocks. What blocks to choose? Just the first one and split it up into smaller blocks? Would it, possibly, be a better idea to look at the free block that is the closest size of the requested block?  Searching for block inside an unordered list, however, is O(n). That is too slow.  So, keep a 2^k array (2^k ... heap_size) of linked lists where blocks of *at least* the size would be linked in. Possibly sorted by order (binary tree? red-black? what techniques are there?).

Then, finding a suiting block would be heap[log2(size)], grab the first block, split up between used and free, relink list, done.  Similar to the buddy allocator.  However, since there will be a split in any event, why even bother about looking at the smallest block? Might as well just any block. No.  The block would have to fit. That's why they would have to be stored in the 2^k array, but internal order of each list doesn't matter.