Add initial POC

finchie

Dec 15, 2023, 6:48 AM

BCGZCHJBLMJWKXOX3H6WROCXQ2OOHN6GYO2YIHOADIKHMSAMFKVAC

Dependencies

[2] 3UGBOW4I

Change contents

file addition: timings.html (----------)

[2.1]

<!DOCTYPE html>
<html lang="en">

<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Cargo timings experiments</title>
<style>
span {
display: flex;
text-align: center;
}

.crate {
display: flex;
flex-direction: column;
flex-grow: 1;
}

.container {
flex-grow: 1;
margin: 5px;
}

.row,
.column {
display: flex;
}

.row {
flex-direction: row;
/* writing-mode: sideways-lr;
text-orientation: upright; */
}

.column {
flex-direction: column;
/* writing-mode: vertical-lr;
text-orientation: mixed; */
}

#heatmap {
height: 30rem;
width: 38rem;
}
</style>
</head>

<body>
<div id="heatmap" class="row"></div>
<script src="layout.js"></script>
</body>

</html>
file addition: layout.js (----------)

[2.1]

const UNIT_DATA = [
{
"i": 0,
"name": "proc-macro2",
"version": "1.0.70",
"mode": "todo",
"target": " build script",
"start": 0.07,
"duration": 0.53,
"rmeta_time": null,
"unlocked_units": [
24
],
"unlocked_rmeta_units": []
},
{
"i": 1,
"name": "unicode-ident",
"version": "1.0.12",
"mode": "todo",
"target": "",
"start": 0.07,
"duration": 0.22,
"rmeta_time": 0.1,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 2,
"name": "serde",
"version": "1.0.193",
"mode": "todo",
"target": " build script",
"start": 0.07,
"duration": 0.48,
"rmeta_time": null,
"unlocked_units": [
23
],
"unlocked_rmeta_units": []
},
{
"i": 3,
"name": "utf8parse",
"version": "0.2.1",
"mode": "todo",
"target": "",
"start": 0.07,
"duration": 0.43,
"rmeta_time": 0.08,
"unlocked_units": [],
"unlocked_rmeta_units": [
10
]
},
{
"i": 4,
"name": "thiserror",
"version": "1.0.50",
"mode": "todo",
"target": " build script",
"start": 0.07,
"duration": 0.45,
"rmeta_time": null,
"unlocked_units": [
21
],
"unlocked_rmeta_units": []
},
{
"i": 5,
"name": "anstyle-query",
"version": "1.0.1",
"mode": "todo",
"target": "",
"start": 0.07,
"duration": 0.16,
"rmeta_time": 0.07,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 6,
"name": "anstyle",
"version": "1.0.4",
"mode": "todo",
"target": "",
"start": 0.07,
"duration": 0.66,
"rmeta_time": 0.6,
"unlocked_units": [],
"unlocked_rmeta_units": [
27
]
},
{
"i": 7,
"name": "camino",
"version": "1.1.6",
"mode": "todo",
"target": " build script",
"start": 0.07,
"duration": 0.54,
"rmeta_time": null,
"unlocked_units": [
25
],
"unlocked_rmeta_units": []
},
{
"i": 8,
"name": "colorchoice",
"version": "1.0.0",
"mode": "todo",
"target": "",
"start": 0.1,
"duration": 0.35,
"rmeta_time": 0.1,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 9,
"name": "semver",
"version": "1.0.20",
"mode": "todo",
"target": " build script",
"start": 0.13,
"duration": 0.42,
"rmeta_time": null,
"unlocked_units": [
22
],
"unlocked_rmeta_units": []
},
{
"i": 10,
"name": "anstyle-parse",
"version": "0.2.3",
"mode": "todo",
"target": "",
"start": 0.16,
"duration": 0.51,
"rmeta_time": 0.43,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 11,
"name": "serde_json",
"version": "1.0.108",
"mode": "todo",
"target": " build script",
"start": 0.2,
"duration": 0.32,
"rmeta_time": null,
"unlocked_units": [
20
],
"unlocked_rmeta_units": []
},
{
"i": 12,
"name": "strsim",
"version": "0.10.0",
"mode": "todo",
"target": "",
"start": 0.24,
"duration": 0.77,
"rmeta_time": 0.5,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 13,
"name": "itoa",
"version": "1.0.9",
"mode": "todo",
"target": "",
"start": 0.28,
"duration": 0.31,
"rmeta_time": 0.19,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 14,
"name": "equivalent",
"version": "1.0.1",
"mode": "todo",
"target": "",
"start": 0.3,
"duration": 0.31,
"rmeta_time": 0.04,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 15,
"name": "anyhow",
"version": "1.0.75",
"mode": "todo",
"target": " build script",
"start": 0.42,
"duration": 0.47,
"rmeta_time": null,
"unlocked_units": [
28
],
"unlocked_rmeta_units": []
},
{
"i": 16,
"name": "ryu",
"version": "1.0.15",
"mode": "todo",
"target": "",
"start": 0.45,
"duration": 0.55,
"rmeta_time": 0.43,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 17,
"name": "clap_lex",
"version": "0.6.0",
"mode": "todo",
"target": "",
"start": 0.48,
"duration": 0.44,
"rmeta_time": 0.28,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 18,
"name": "hashbrown",
"version": "0.14.3",
"mode": "todo",
"target": "",
"start": 0.48,
"duration": 0.87,
"rmeta_time": 0.81,
"unlocked_units": [],
"unlocked_rmeta_units": [
32
]
},
{
"i": 19,
"name": "fixedbitset",
"version": "0.4.2",
"mode": "todo",
"target": "",
"start": 0.5,
"duration": 0.38,
"rmeta_time": 0.3,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 20,
"name": "serde_json",
"version": "1.0.108",
"mode": "run-custom-build",
"target": " build script (run)",
"start": 0.52,
"duration": 0.01,
"rmeta_time": null,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 21,
"name": "thiserror",
"version": "1.0.50",
"mode": "run-custom-build",
"target": " build script (run)",
"start": 0.52,
"duration": 0.14,
"rmeta_time": null,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 22,
"name": "semver",
"version": "1.0.20",
"mode": "run-custom-build",
"target": " build script (run)",
"start": 0.55,
"duration": 0.02,
"rmeta_time": null,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 23,
"name": "serde",
"version": "1.0.193",
"mode": "run-custom-build",
"target": " build script (run)",
"start": 0.55,
"duration": 0.03,
"rmeta_time": null,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 24,
"name": "proc-macro2",
"version": "1.0.70",
"mode": "run-custom-build",
"target": " build script (run)",
"start": 0.6,
"duration": 0.02,
"rmeta_time": null,
"unlocked_units": [
26
],
"unlocked_rmeta_units": []
},
{
"i": 25,
"name": "camino",
"version": "1.1.6",
"mode": "run-custom-build",
"target": " build script (run)",
"start": 0.61,
"duration": 0.02,
"rmeta_time": null,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 26,
"name": "proc-macro2",
"version": "1.0.70",
"mode": "todo",
"target": "",
"start": 0.63,
"duration": 0.8,
"rmeta_time": 0.56,
"unlocked_units": [],
"unlocked_rmeta_units": [
31
]
},
{
"i": 27,
"name": "anstream",
"version": "0.6.4",
"mode": "todo",
"target": "",
"start": 0.68,
"duration": 0.46,
"rmeta_time": 0.39,
"unlocked_units": [],
"unlocked_rmeta_units": [
29
]
},
{
"i": 28,
"name": "anyhow",
"version": "1.0.75",
"mode": "run-custom-build",
"target": " build script (run)",
"start": 0.89,
"duration": 0.19,
"rmeta_time": null,
"unlocked_units": [
30
],
"unlocked_rmeta_units": []
},
{
"i": 29,
"name": "clap_builder",
"version": "4.4.11",
"mode": "todo",
"target": "",
"start": 1.07,
"duration": 3.31,
"rmeta_time": 2.41,
"unlocked_units": [],
"unlocked_rmeta_units": [
35
]
},
{
"i": 30,
"name": "anyhow",
"version": "1.0.75",
"mode": "todo",
"target": "",
"start": 1.08,
"duration": 0.44,
"rmeta_time": 0.31,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 31,
"name": "quote",
"version": "1.0.33",
"mode": "todo",
"target": "",
"start": 1.2,
"duration": 0.42,
"rmeta_time": 0.27,
"unlocked_units": [],
"unlocked_rmeta_units": [
33
]
},
{
"i": 32,
"name": "indexmap",
"version": "2.1.0",
"mode": "todo",
"target": "",
"start": 1.3,
"duration": 0.76,
"rmeta_time": 0.64,
"unlocked_units": [],
"unlocked_rmeta_units": [
34
]
},
{
"i": 33,
"name": "syn",
"version": "2.0.39",
"mode": "todo",
"target": "",
"start": 1.48,
"duration": 2.29,
"rmeta_time": 1.75,
"unlocked_units": [
37,
36
],
"unlocked_rmeta_units": []
},
{
"i": 34,
"name": "petgraph",
"version": "0.6.4",
"mode": "todo",
"target": "",
"start": 1.97,
"duration": 1.1,
"rmeta_time": 1.05,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 35,
"name": "clap",
"version": "4.4.11",
"mode": "todo",
"target": "",
"start": 3.48,
"duration": 0.08,
"rmeta_time": 0.07,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 36,
"name": "serde_derive",
"version": "1.0.193",
"mode": "todo",
"target": "",
"start": 3.77,
"duration": 2.21,
"rmeta_time": null,
"unlocked_units": [
39
],
"unlocked_rmeta_units": []
},
{
"i": 37,
"name": "thiserror-impl",
"version": "1.0.50",
"mode": "todo",
"target": "",
"start": 3.77,
"duration": 1.11,
"rmeta_time": null,
"unlocked_units": [
38
],
"unlocked_rmeta_units": []
},
{
"i": 38,
"name": "thiserror",
"version": "1.0.50",
"mode": "todo",
"target": "",
"start": 4.88,
"duration": 0.04,
"rmeta_time": 0.03,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 39,
"name": "serde",
"version": "1.0.193",
"mode": "todo",
"target": "",
"start": 5.98,
"duration": 1.52,
"rmeta_time": 1.42,
"unlocked_units": [],
"unlocked_rmeta_units": [
42,
41,
40,
43
]
},
{
"i": 40,
"name": "semver",
"version": "1.0.20",
"mode": "todo",
"target": "",
"start": 7.4,
"duration": 0.3,
"rmeta_time": 0.24,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 41,
"name": "serde_json",
"version": "1.0.108",
"mode": "todo",
"target": "",
"start": 7.4,
"duration": 0.82,
"rmeta_time": 0.66,
"unlocked_units": [],
"unlocked_rmeta_units": [
44
]
},
{
"i": 42,
"name": "camino",
"version": "1.1.6",
"mode": "todo",
"target": "",
"start": 7.4,
"duration": 0.43,
"rmeta_time": 0.33,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 43,
"name": "cargo-platform",
"version": "0.1.5",
"mode": "todo",
"target": "",
"start": 7.4,
"duration": 0.26,
"rmeta_time": 0.17,
"unlocked_units": [],
"unlocked_rmeta_units": []
},
{
"i": 44,
"name": "cargo_metadata",
"version": "0.18.1",
"mode": "todo",
"target": "",
"start": 8.06,
"duration": 0.88,
"rmeta_time": 0.59,
"unlocked_units": [
45
],
"unlocked_rmeta_units": []
},
{
"i": 45,
"name": "cargo-depgraph",
"version": "1.6.0",
"mode": "todo",
"target": " bin \"cargo-depgraph\"",
"start": 8.94,
"duration": 0.61,
"rmeta_time": null,
"unlocked_units": [],
"unlocked_rmeta_units": []
}
];

const EDGES = {0: [1, 2, 3, 4], 2: [5, 6, 7, 8, 9, 10], 3: [11], 4: [12, 13], 6: [8], 9: [14, 15, 8], 11: [17, 18], 13: [20, 21]};
const NODES = ["cargo-depgraph",
"anyhow",
"cargo_metadata",
"clap",
"petgraph",
"camino",
"cargo-platform",
"semver",
"serde",
"serde_json",
"thiserror",
"clap_builder",
"fixedbitset",
"indexmap",
"itoa",
"ryu",
"anstream",
"anstyle",
"clap_lex",
"strsim",
"equivalent",
"hashbrown",
"anstyle-parse",
"anstyle-query",
"colorchoice",
"utf8parse"];

class Crate {
constructor(name) {
this.name = name;

for (const [index, node] of NODES.entries()) {
if (node == name) {
this.node_index = index;
break;
}
}
console.assert(this.node_index !== undefined);

let unit_indexes = [];
for (const [index, element] of UNIT_DATA.entries()) {
if (element.name === name) {
unit_indexes.push(index);
}
}

let dependencies = [];
if (EDGES[this.node_index] !== undefined) {
for (const dependency of EDGES[this.node_index]) {
dependencies.push(new Crate(NODES[dependency]));
}
}

let total_unlocked = 0;
for (const index of unit_indexes) {
total_unlocked += UNIT_DATA[index].unlocked_units.length;
total_unlocked += UNIT_DATA[index].unlocked_rmeta_units.length;
}

this.total_unlocked = total_unlocked;
this.unit_indexes = unit_indexes;
this.dependencies = dependencies;
}

sum_duration() {
let total = 0;
for (const index of this.unit_indexes) {
total += UNIT_DATA[index].duration;
}

return total;
}

total_sum_duration() {
let total = this.sum_duration();
for (const child of this.dependencies) {
total += child.total_sum_duration();
}

return total;
}
}

let max_unlocked = 0;
for (const node of NODES) {
const crate = new Crate(node);
max_unlocked = Math.max(max_unlocked, crate.total_unlocked)
}

function max_sum(items) {
let largest = 0;
for (const item of items) {
largest = Math.max(largest, item.total_sum_duration());
}

console.assert(largest > 0);
return largest;
}

function largest_in(items) {
let largest = [undefined, 0];
for (const [index, item] of items.entries()) {
total_duration = item.total_sum_duration();
if (total_duration > largest[1]) {
largest = [index, total_duration];
}
}

console.assert(largest[0] !== undefined);
return largest[0];
}

function running_sum(items) {
let sum = 0;

for (const item of items) {
sum += item.total_sum_duration();
}

return sum;
}

// From https://stackoverflow.com/questions/12875486/what-is-the-algorithm-to-create-colors-for-a-heatmap
function heatMapColorforValue(value){
var h = (1.0 - value) * 60
return "hsl(" + h + ", 100%, 50%)";
}

function recurse(list, parent) {
for (const item of list) {
const child = document.createElement("div");
child.classList.add(item.name);
child.classList.add("crate");

const container = document.createElement("div");
container.classList.add("container")

const text = document.createElement("span");
text.innerHTML = item.name;
child.appendChild(text);

if (parent.classList.contains("column")) {
container.classList.add("row");
} else {
container.classList.add("column");
}

// container.style.flexGrow = item.total_sum_duration();
child.style.backgroundColor = heatMapColorforValue(item.total_unlocked / max_unlocked);
child.appendChild(container);
parent.appendChild(child);

if (item.dependencies.length > 0) {
split(item.dependencies, container);
} else {
// not sure yet
}

}
}

// Algorithm from "Treemapping via balanced partitioning" paper (algorithm 2: variance-minimizing solution for balanced partition)
function split(list, parent) {
let height = running_sum(list) / 2;

let l_1 = [];
let l_2 = list.map((item) => new Crate(item.name));
let x = largest_in(l_2);

while (Math.abs(running_sum(l_1) - height) > Math.abs(running_sum(l_1.concat([l_2[x]])) - height)) {
l_1.push(l_2[x]);
l_2.splice(x, 1);

x = largest_in(l_2);
}

console.log(l_1, l_2);
recurse(l_1, parent);
recurse(l_2, parent);
}

const heatmap = document.getElementById("heatmap");
// const ctx = heatmap.getContext("2d");

// for (const item of UNIT_DATA) {
// ctx.beginPath();
// ctx.arc(item.duration * 100, (item.unlocked_units,length + item.unlocked_rmeta_units.length) * 100, 5, 0, 2 * Math.PI);
// ctx.stroke();
// }

const root = new Crate("cargo-depgraph");

split(root.dependencies, heatmap)
file addition: .ignore (----------)

[2.1]

.git
.DS_Store