Visualize Heap Fragmentation with ASCII Art Colors

Topic Overview

See the Heap Holes

Repeated allocate/free patterns of different sizes leave unusable gaps between live blocks. Visualizing free holes explains why long-running servers restart or switch to pool allocators even when total bytes look fine.

ASCII Visualization Idea

Map each heap byte to a character: . free, # allocated, | boundary. After a fragmentation script, long runs of . between # clusters show external fragmentation.

cCopy
Loading…

• External fragmentation: free bytes exist but not contiguously
• Internal fragmentation: allocator rounds up request size
• Compaction is rare in malloc; embedders use pools instead
• Log allocation order to reproduce worst cases

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will simulate a simple heap and print colored ASCII maps after a fragmentation workload. This exercise requires identifying a hole that blocks a large allocation request.

Your Task

External fragmentation is when plenty of memory is free but no single hole is big enough. Build a heap allocator over a fixed arena of 16-byte units, with first-fit, best-fit and worst-fit placement, draw the heap as an ASCII map, and measure fragmentation. Watch a request fail while the total free space would have been enough.

Input

cCopy
Loading…

Rules

• A request needs ceil(BYTES / 16) contiguous units. Holes are maximal runs of free units in address order, and free neighbours merge automatically.
• first: the lowest hole that fits. best: the smallest hole that fits. worst: the largest hole. Ties go to the lowest address.
• Each successful malloc gets the next symbol from A..Z then a..z (cycling), which is drawn in its units. Free units are ..
• A request with no hole large enough prints FAILED, need N contiguous units, M free in total and counts as a failure.
• External fragmentation = (total free − largest hole) / total free, rounded half up to 1 decimal (0 when nothing is free).
• Errors: malloc NAME: rejected (BYTES < 1, a live duplicate name, or 128 blocks), free NAME: invalid free, heap: 1..1024 units, and policy: first, best or worst.

Output

cCopy
Loading…

The map shows 32 units per row, prefixed by the row's byte offset in 5 columns. The last row may be shorter.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Derive holes from the unit map every time. Then coalescing is automatic and can never go stale.
2. Implement the three policies as one scan with different selection rules, so their results can be compared on the same trace.

Hidden tests cover best-fit and worst-fit choosing different holes on the same trace, several failures despite enough total space, a heap that is not a multiple of 32 units, symbols cycling past Z, and invalid commands.