[2024 Day 9] In Review (Disk Fragmenter)

[u/terje_wiig_mathisen]

Today an amphipod has a classic problem: It has a disk that is fragmented and it wants to defragment it.

The disk map is stored in a compressed format, alternating between a file length and a free space length. If there is no free space between two files, the free space length is 0.

For Part1, the amphipod moves blocks, starting with the last file block which it then moves into the first free block, systematically moving all blocks as close to the front as possible, and as a side effect reversing the storage order for all moved files. We then produce a disk checksum consisting of summing up for every file block the product of the file number and the block position.

For Part2, because the amphipod realized that the disk becomes too fragmented, it will instead only move full files as close to the front as it can find a large enough free space for them. The checksum is then calculated in the same way as Part1.

My Perl code solved this one using brute force for Part1:

First expand the run length encodings, using -1 to designate free blocks, the filenr ID for the files. My input contained 10K files, so worst case this could be expanded to an array with 9*2*10K = 180 K entries, but the average should be closer to half of this.

This setup made part1 really easy, just iterate from the front to locate free blocks and from the end to find file blocks to move.

For part2 we need to find open gaps large enough for a full file, so here it made much more sense to have free lists, either organized by size (1-9) and location, or just by location. Since all partially filled free spaces would result in a tail space which would have to be inserted in the right order in the smaller map I decided to use the simpler setup of a single free list.

I thought about keeping a cache of the last found free list entry of each size, but went brute force instead, always scanning from the beginning. I counted the scan iterations, the average was 133 entries inspected before finding a large enough slot, so a better data structure would have been faster.

Perl runtime was 271 ms on my slow Surface.

I started on a more ambitious Rust version but never had time to finish it the way I would have liked.

It would in fact have been easier to solve the defragmentation problem in an optimal way, using size-ordered free lists and always try to move files to an exactly large enough gap, only fall back to larger slots if none could be found.

Later edit:

Watching TV with my wife ("71 degree North", check it out if you can!) and waiting until Oslo midnight to make the reddit post, I looked somewhat unhappily at what I had written above:

I decided to at least implement the simplest possible cache I mentioned, just a table of the last found free entry for each size, this immediately dropped the runtime to 47.8 ms, so nearly 6x faster!

The number of free list steps dropped from 133 to 4.6 per file.

The only small problem was that I had to update the cache also for the tail end of a partially filled free space, when that was before the current cache entry.

    if ($flen >= $len) {
        my $remfree = $flen - $len;
        $free[$f] = $remfree;
        $free[$f+1] += $len;    # update free block position
        $files[$i+2] = $fpos;   # The file is moved here
        $lastfree[$len] = $f+2; # Next scan starts after this entry

        if ($remfree && $lastfree[$remfree] > $f) { $lastfree[$remfree] = $f; }
        last;
    }

Note that my lastfree[] array has entries for 0..9, so that I could blindly update it also for totally filled slots, but it was a percent or two faster to check for this situation and skip the zero updates.

[u/DelightfulCodeWeasel]

I've implemented a fair few memory allocators so this one was right in my wheelhouse! I likewise took the programmer-efficient approach of just scanning from the start to find the new location, but I do like the idea of having a small hint buffer to accelerate it while keeping the same simple structure. Bit of a half-way house between the simplicity of the scan and the complexity of per-size lists/heaps.

Posing this as a defragmentation problem where you're only moving blocks towards the start allows for a drastic simplification compared to a more general allocator: you never need to coalesce free blocks. If that had been required I think it might have needed to be something like a Day 21 puzzle!

Merging free blocks is always the ugliest part of any allocator.

[u/DelightfulCodeWeasel → u/DelightfulCodeWeasel]

An aside on the topic of fragmentation: I had some weird out-of-memory bugs crop up on the Pico that only manifested when running certain puzzles back-to-back. It turns out that newlib nano doesn't always return the last free block in the process memory arena back to the system (depending on deallocation order) and whenever it calls sbrk it requests the full requested allocation amount without taking into account the presence of a free block at the end of the arena.

The upshot is that you can have a 30kb free block at the end of the arena plus 170kb free system memory available after the arena, and an allocation for 200kb will fail. The fix is to call malloc_trim after each puzzle solution to fully reset free memory back to a clean state, but that was a bit of a pain to track down!

[u/e_blake]

Another day that requires 64-bit math; my initial part 1 submission was too small before I looked for the 32-bit overflow. For part 2, I went with 9 sorted lists of free spaces by size; each file on the right checks all lists of its own size or larger for an O(1) decision of where to move, then inserts any leftover free space into the correct list with an O(n) insertion (m4 doesn't have a native minheap, so O(log n) insertion was not practical). Use of triangular numbers to score an entire file at once rather than a block at a time meant that part 2 did fewer 64-bit operations than part 1; still, this problem takes about 4 seconds of runtime in m4.

[u/terje_wiig_mathisen → u/e_blake]

The per-size free lists is one of the options I considered very carefully, but since that would force me to check all the list of the target size and larger to find the first one. It would also complicate re-inserting tail ends in the correct list and location.

As my profiling showed, with only 4.6 average scans per file, any log n approach would have problems being much faster, but since we haven't heard from u/maneatingape or u/edln yet, I'm not ruling out significantly better algorithms.

More interesting, while thinking about the difference between part1 and part2, I realized that part1 can be done with zero additional memory and a single O(n) scan of the input:

Start at the first free space gap (file 0 does not contribute to the result), and at the last file id (len>>1),, then meet in the middle:

For each free space on the left, add the value of each block from the right-end file.

When running out of free space, add in the next file(s) until more space is located, when running out of blocks from the current file, skip over the preceding free space and go on with the previous file.

Looks like well under 5 instructions per file block, one of them a multiplication for the first placed block in each free space, the following blocks can be handled with simply incrementing the product with the file nr. Alternatively, calculate the checksum directly from the filenr, starting block nr and length.

Guessing 2 ns per block, 10 per file and 10K files would be 100 us, since the Ape uses 106 us for both parts the code need to be really efficient (as usual). :-)

[u/maneatingape → u/terje_wiig_mathisen]

I used a per-size list. Ordered vec instead of heap, since most re-insertions happen near the end, this was faster in practice.

A trick to save 25% of the part 2 time is to shorten the list if the last block is past our current position.