Generating diagram of memory allocations over time

script.js

// See this post: https://coder-mike.com/blog/2022/05/27/single-threading-is-more-memory-efficient/

const width = 1000;
const height = 600;
const spacePadding = 1;
const timePadding = 1;
const grid = 10;
const taskCount = 4;

const allocations = simulateRandomAllocations({
  tMin: 0,
  tMax: (width * 2) / grid,
  allocCount: 150,
  meanSize: 20 / grid,
  meanDuration: 40 / grid,
  timePadding,
  spacePadding,
})

console.dir(allocations);

renderAllocationsToSvg(allocations)

function renderAllocationsToSvg(allocations) {
  const svg = document.createElementNS('http://www.w3.org/2000/svg', 'svg');
  svg.setAttribute('fill', 'white');
  svg.setAttribute('viewBox', `${width} 0 ${width} ${height}`);

  colors = {
    '0': '#722',
    '1': '#272',
    '2': '#227'
  }

  for (const { start, duration, address, size, allocId } of allocations) {
    const taskId = Math.floor(Math.random() * Object.keys(colors).length);
    const color = colors[taskId];

    const outer = document.createElementNS('http://www.w3.org/2000/svg', 'rect');
    outer.setAttribute('data-allocId', allocId);
    outer.setAttribute('x', start * grid);
    outer.setAttribute('width', (duration) * grid);
    outer.setAttribute('y', height - (address + size) * grid);
    outer.setAttribute('height', size * grid);
    outer.setAttribute('opacity', 0.2 );
    outer.setAttribute('fill', color);
    outer.setAttribute('rx', grid / 2);
    outer.setAttribute('ry', grid / 2);
    svg.appendChild(outer);

    const inner = document.createElementNS('http://www.w3.org/2000/svg', 'rect');
    inner.setAttribute('data-allocId', allocId);
    inner.setAttribute('x', start * grid + grid/2);
    inner.setAttribute('width', (duration - timePadding) * grid);
    inner.setAttribute('y', height - (address + size - spacePadding) * grid - grid/2);
    inner.setAttribute('height', (size - spacePadding) * grid);
    inner.setAttribute('fill', color);
    svg.appendChild(inner);
  }

  return document.body.appendChild(svg);
}

function simulateRandomAllocations({ tMin, tMax, allocCount, meanSize, meanDuration, spacePadding, timePadding }) {
  const allocations = [];

  let allocId = 0;
  while (allocations.length < allocCount) {
    // Size follows an exponential distribution
    let size = -meanSize * Math.log(Math.random())
    let start = tMin + Math.random() * (tMax - tMin)
    // Let's try a duration with an exponential distribution as well
    let duration = -meanDuration * Math.log(Math.random())

    size = Math.ceil(size)
    duration = Math.ceil(duration)
    start = Math.ceil(start)

    size += spacePadding;
    duration += timePadding;

    const end = start + duration;
    const allocation = { start, end, size, allocId, duration };
    allocations.push(allocation);
    allocId++;
  }

  findAddressesForAllocations(allocations, spacePadding);

  return allocations;
}

function findAddressesForAllocations(allocations) {
  const events = [];
  for (const allocation of allocations) {
    events.push({ action: 'malloc', time: allocation.start, allocation });
    events.push({ action: 'free', time: allocation.end, allocation });
  }
  events.sort((a, b) => {
    if (a.time < b.time) { return -1 }
    if (a.time > b.time) { return 1 }
    // Free before malloc, just because it's visually cleaner
    if (a.action === 'malloc' && b.action === 'free') { return 1 }
    if (a.action === 'free' && b.action === 'malloc') { return -1 }
    return 0;
  });

  console.dir({events})

  const allocationsNow = []; // Ordered by address
  for (const { action, allocation } of events) {
    switch (action) {
      case 'malloc': malloc(allocationsNow, allocation); break;
      case 'free': free(allocationsNow, allocation); break;
    }
  }

  function malloc(allocationsNow, newAllocation) {
    let cursorAddress = 0;
    for (let i = 0; i < allocationsNow.length; i++) {
      const allocation = allocationsNow[i];
      const spaceBefore = allocation.address - cursorAddress;
      const enoughSpace = spaceBefore >= newAllocation.size;
      if (enoughSpace) {
        newAllocation.address = cursorAddress;
        allocationsNow.splice(i, 0, newAllocation);
        return;
      }
      cursorAddress = allocation.address + allocation.size;
    }
    // Otherwise, use space at end
    newAllocation.address = cursorAddress;
    allocationsNow.push(newAllocation);
  }

  function free(allocationsNow, allocation) {
    const index = allocationsNow.indexOf(allocation);
    console.assert(index >= 0);
    allocationsNow.splice(index, 1);
  }
}