Skip to content

Instantly share code, notes, and snippets.

@coder-mike
Created May 29, 2022
Embed
What would you like to do?
Generating diagram of memory allocations over time
// 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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment