  This paper presents a trace-based simulation methodology for constructing
representations of workload-allocator interaction. We use two-dimensional
rectangular bin packing (2DBP) as our foundation. Classical 2DBP algorithms
minimize their products' makespan, but virtual memory systems employing demand
paging deem such a criterion inappropriate. We view an allocator's placement
decisions as a solution to a 2DBP instance, optimizing some unknown criterion
particular to that allocator's policy. Our end product is a compact data
structure that fits e.g. the simulation of 80 million requests in a 350 MiB
file. By design, it is concerned with events residing entirely in virtual
memory; no information on memory accesses, indexing costs or any other factor
is kept.
  We bootstrap our contribution's significance by exploring its relationship to
maximum resident set size (RSS). Our baseline is the assumption that less
fragmentation amounts to smaller peak RSS. We thus define a fragmentation
metric in the 2DBP substrate and compute it for 28 workloads linked to 4 modern
allocators. We also measure peak RSS for the 112 resulting pairs. Our metric
exhibits a strong monotonic relationship (Spearman coefficient $\rho>0.65$) in
half of those cases: allocators achieving better 2DBP placements yield
$9\%$-$30\%$ smaller peak RSS, with the trends remaining consistent across two
different machines.
  Considering our representation's minimalism, the presented empirical evidence
is a robust indicator of its potency. If workload-allocator interplay in the
virtual address space suffices to evaluate a novel fragmentation definition,
numerous other useful applications of our tool can be studied. Both augmenting
2DBP and exploring alternative computations on it provide ample fertile ground
for future research.
