mirror of
https://github.com/hanzoai/datastore.git
synced 2026-09-26 13:55:07 +00:00
466 lines
20 KiB
HTML
466 lines
20 KiB
HTML
<!DOCTYPE html>
|
|
<html>
|
|
<head>
|
|
<meta charset="UTF-8">
|
|
<title>Merge Selector Lab</title>
|
|
<link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.5.2/css/bootstrap.min.css">
|
|
<script src="https://d3js.org/d3.v7.min.js"></script>
|
|
</head>
|
|
<body>
|
|
<div class="container-fluid">
|
|
<form id="param-form" class="p-3">
|
|
<div class="row">
|
|
<div class="form-group col-md-4">
|
|
<label for="insertPartSize">Initial part size:</label>
|
|
<input type="text" class="form-control form-control-sm" id="insertPartSize" value="10MB">
|
|
</div>
|
|
<div class="form-group col-md-4">
|
|
<label for="parts">Initial parts count:</label>
|
|
<input type="text" class="form-control form-control-sm" id="parts" value="logrange(4,100000,1.1)">
|
|
</div>
|
|
<div class="form-group col-md-4">
|
|
<label for="poolSize">Workers in merge pool:</label>
|
|
<input type="text" class="form-control form-control-sm" id="poolSize" value="100">
|
|
</div>
|
|
</div>
|
|
<div class="row">
|
|
<div class="form-group col-md-4">
|
|
<label for="maxSourceParts">Max parts to merge:</label>
|
|
<input type="text" class="form-control form-control-sm" id="maxSourceParts" value="1000000">
|
|
</div>
|
|
<div class="form-group col-md-4">
|
|
<label for="maxPartSize">Average final part size:</label>
|
|
<input type="text" class="form-control form-control-sm" id="maxPartSize" placeholder="Unlimited">
|
|
</div>
|
|
<div class="form-group col-md-4">
|
|
<label for="layers">Layers:</label>
|
|
<input type="text" class="form-control form-control-sm" id="layers" value="range(2,10,1)">
|
|
</div>
|
|
</div>
|
|
<div class="row">
|
|
<div class="form-group col-md-6">
|
|
<label for="method">Method:</label>
|
|
<select class="form-control form-control-sm" id="method">
|
|
<!-- will be populated dynamically -->
|
|
</select>
|
|
</div>
|
|
<div class="form-group col-md-6">
|
|
<label for="solver">Solver:</label>
|
|
<select class="form-control form-control-sm" id="solver">
|
|
<!-- will be populated dynamically -->
|
|
</select>
|
|
</div>
|
|
<div class="form-group col-md-6">
|
|
<label for="x-axis">X Axis:</label>
|
|
<select class="form-control form-control-sm" id="x-axis">
|
|
<!-- will be populated dynamically -->
|
|
</select>
|
|
</div>
|
|
<div class="form-group col-md-6">
|
|
<label for="y-axis">Y Axis:</label>
|
|
<select class="form-control form-control-sm" id="y-axis">
|
|
<!-- will be populated dynamically -->
|
|
</select>
|
|
</div>
|
|
</div>
|
|
<div class="row">
|
|
</div>
|
|
<div class="row mt-3">
|
|
<div class="col">
|
|
<button type="button" class="btn btn-primary" id="solveButton">Solve</button>
|
|
</div>
|
|
</div>
|
|
</form>
|
|
</div>
|
|
|
|
<script type="module">
|
|
import { Chart } from './Chart.js';
|
|
import { MergeTree } from './MergeTree.js';
|
|
import { SimulationContainer } from './SimulationContainer.js';
|
|
import { sequenceInserter } from './sequenceInserter.js';
|
|
import { floatLayerMerges } from './floatLayerMerges.js';
|
|
import { mergeModel } from './mergeModel.js';
|
|
import { projectedGradientDescent, nesterovAcceleratedPGD, subgradientMethod } from './gradientDescent.js';
|
|
import { ModelSolver } from './ModelSolver.js';
|
|
import { fetchText, delayMs, parseHumanReadableSize } from './util.js';
|
|
|
|
function parseArray(expression) {
|
|
if (!expression)
|
|
return [null];
|
|
|
|
// Helper function to parse a range expression
|
|
const parseRange = (rangeString) => {
|
|
if (!rangeString.startsWith("range(") || !rangeString.endsWith(")"))
|
|
return null;
|
|
|
|
const content = rangeString.slice(6, -1); // Remove "range(" and ")"
|
|
const parts = content.split(",").map(part => part.trim());
|
|
|
|
if (parts.length !== 3)
|
|
return null;
|
|
|
|
const [startStr, endStr, stepStr] = parts;
|
|
const start = parseHumanReadableSize(startStr);
|
|
const end = parseHumanReadableSize(endStr);
|
|
const step = parseHumanReadableSize(stepStr);
|
|
|
|
if (step <= 0)
|
|
return null;
|
|
|
|
const range = [];
|
|
for (let i = start; i <= end; i += step)
|
|
range.push(i);
|
|
return range;
|
|
};
|
|
|
|
// Helper function to parse a range expression
|
|
const parseLogRange = (rangeString) => {
|
|
if (!rangeString.startsWith("logrange(") || !rangeString.endsWith(")"))
|
|
return null;
|
|
|
|
const content = rangeString.slice(9, -1); // Remove "logrange(" and ")"
|
|
const parts = content.split(",").map(part => part.trim());
|
|
|
|
if (parts.length !== 3)
|
|
return null;
|
|
|
|
const [startStr, endStr, stepStr] = parts;
|
|
const start = parseHumanReadableSize(startStr);
|
|
const end = parseHumanReadableSize(endStr);
|
|
const step = parseHumanReadableSize(stepStr);
|
|
|
|
if (step <= 1)
|
|
return null;
|
|
|
|
const range = [];
|
|
for (let i = start; i <= end; i *= step)
|
|
range.push(i);
|
|
return range;
|
|
};
|
|
|
|
if (expression.startsWith("range")) {
|
|
const result = parseRange(expression);
|
|
if (result !== null)
|
|
return result;
|
|
} else if (expression.startsWith("logrange")) {
|
|
const result = parseLogRange(expression);
|
|
if (result !== null)
|
|
return result;
|
|
} else {
|
|
return [parseHumanReadableSize(expression)];
|
|
}
|
|
}
|
|
|
|
// Fetches a JSON and returns ModelSolver
|
|
async function loadSolver(solverName) {
|
|
let solver = new ModelSolver(mergeModel);
|
|
let jsonData = await fetchText(`solvers/${solverName}.json`);
|
|
solver.deserializeData(jsonData);
|
|
return solver;
|
|
}
|
|
|
|
const methods = {
|
|
"Subgradient Method": subgradientMethod,
|
|
"Projected GD": projectedGradientDescent,
|
|
"Accelerated PGD": nesterovAcceleratedPGD,
|
|
"None": null,
|
|
};
|
|
|
|
const solvers = {
|
|
"None": null,
|
|
"BLI-x4": await loadSolver("solver-64KB_256GB_32768_x4_x4"),
|
|
"BLI-x1": await loadSolver("solver-64KB_256GB_32768"),
|
|
};
|
|
|
|
const xAxes = {
|
|
"log(Parts)": "log(parts)",
|
|
"log(Workers)": "log(workers)",
|
|
"Parts": "parts",
|
|
"Workers": "workers",
|
|
};
|
|
|
|
const yAxes = {
|
|
"log(Base)": "log(base)",
|
|
"log(Merges)": "log(merges)",
|
|
"log(Alpha)": "log(alpha)",
|
|
"log(PartTimeIntegral)": "log(cost)",
|
|
"log(Density)": "log(density)",
|
|
"Base": "base",
|
|
"Merges": "merges",
|
|
"Alpha": "alpha",
|
|
"PartTimeIntegral": "cost",
|
|
"Density": "density",
|
|
};
|
|
|
|
// Populate methods dropdown
|
|
const methodSelect = document.getElementById('method');
|
|
for (const [name] of Object.entries(methods)) {
|
|
const option = document.createElement('option');
|
|
option.value = name;
|
|
option.textContent = name;
|
|
methodSelect.appendChild(option);
|
|
}
|
|
|
|
// Populate solvers dropdown
|
|
const solverSelect = document.getElementById('solver');
|
|
for (const [name] of Object.entries(solvers)) {
|
|
const option = document.createElement('option');
|
|
option.value = name;
|
|
option.textContent = name;
|
|
solverSelect.appendChild(option);
|
|
}
|
|
|
|
// Populate xAxes dropdown
|
|
const xAxesSelect = document.getElementById('x-axis');
|
|
for (const [name] of Object.entries(xAxes)) {
|
|
const option = document.createElement('option');
|
|
option.value = name;
|
|
option.textContent = name;
|
|
xAxesSelect.appendChild(option);
|
|
}
|
|
|
|
// Populate yAxes dropdown
|
|
const yAxesSelect = document.getElementById('y-axis');
|
|
for (const [name] of Object.entries(yAxes)) {
|
|
const option = document.createElement('option');
|
|
option.value = name;
|
|
option.textContent = name;
|
|
yAxesSelect.appendChild(option);
|
|
}
|
|
|
|
function selectMethod() {
|
|
const selectedMethodName = document.getElementById('method').value;
|
|
return methods[selectedMethodName];
|
|
}
|
|
|
|
function selectSolver() {
|
|
const selectedSolverName = document.getElementById('solver').value;
|
|
return solvers[selectedSolverName];
|
|
}
|
|
|
|
function selectXAxis() {
|
|
const selectedXAxisName = document.getElementById('x-axis').value;
|
|
return xAxes[selectedXAxisName];
|
|
}
|
|
|
|
function selectYAxis() {
|
|
const selectedYAxisName = document.getElementById('y-axis').value;
|
|
return yAxes[selectedYAxisName];
|
|
}
|
|
|
|
function readParams() {
|
|
let params = {
|
|
insertPartSizeArray: parseArray(document.getElementById('insertPartSize').value),
|
|
partsArray: parseArray(document.getElementById('parts').value),
|
|
workersArray: parseArray(document.getElementById('poolSize').value),
|
|
layersArray: parseArray(document.getElementById('layers').value),
|
|
maxSourcePartsArray: parseArray(document.getElementById('maxSourceParts').value),
|
|
maxPartSizeArray: parseArray(document.getElementById('maxPartSize').value),
|
|
selectedMethod: selectMethod(),
|
|
selectedSolver: selectSolver(),
|
|
xAxis: selectXAxis(),
|
|
yAxis: selectYAxis(),
|
|
};
|
|
console.log("PARAMS", params);
|
|
return params;
|
|
}
|
|
|
|
document.getElementById('solveButton').addEventListener('click', async () => {
|
|
const solveButton = document.getElementById('solveButton');
|
|
solveButton.textContent = '⏳';
|
|
solveButton.disabled = true;
|
|
|
|
const {
|
|
insertPartSizeArray,
|
|
partsArray,
|
|
workersArray,
|
|
layersArray,
|
|
maxSourcePartsArray,
|
|
maxPartSizeArray,
|
|
selectedMethod,
|
|
selectedSolver,
|
|
xAxis,
|
|
yAxis
|
|
} = readParams();
|
|
|
|
const startTime = performance.now(); // Start timing
|
|
|
|
await delayMs(32);
|
|
|
|
function calculateBases(params, runner) {
|
|
if (runner instanceof ModelSolver) {
|
|
return runner.solve(params);
|
|
} else {
|
|
let solutions = [];
|
|
mergeModel(params,
|
|
runner, // GD method
|
|
function onOption(L, x, Fx) {
|
|
solutions[L - 1] = x[0];
|
|
}
|
|
);
|
|
return solutions;
|
|
}
|
|
}
|
|
|
|
// Setup chart and series
|
|
class SeriesManager {
|
|
constructor(title, xAxis, yAxis = 'log(base)') {
|
|
this.titleDiv = d3.select("body")
|
|
.append("div")
|
|
.attr("class", "container-fluid bg-primary text-white")
|
|
.append("div")
|
|
.attr("class", "p-3")
|
|
.text(title);
|
|
this.chartDiv = d3.select("body")
|
|
.append("div");
|
|
this.chart = new Chart(
|
|
this.chartDiv,
|
|
xAxis,
|
|
yAxis,
|
|
`This chart shows solutions. One point = one solution`
|
|
);
|
|
this.xAxis = xAxis;
|
|
this.yAxis = yAxis;
|
|
this.series = {};
|
|
this.ignore = new Set();
|
|
|
|
this.x = this.#getKey(xAxis);
|
|
this.y = this.#getKey(yAxis);
|
|
}
|
|
|
|
#getValue(pt, key) {
|
|
if (key in pt) {
|
|
return pt[key];
|
|
} else if (key.startsWith("log(") && key.endsWith(")")) {
|
|
return Math.log(this.#getValue(pt, key.slice(4, -1)));
|
|
} else if (key.startsWith("exp(") && key.endsWith(")")) {
|
|
return Math.exp(this.#getValue(pt, key.slice(4, -1)));
|
|
}
|
|
}
|
|
|
|
#getKey(key) {
|
|
if (key.startsWith("log(") && key.endsWith(")")) {
|
|
return this.#getKey(key.slice(4, -1));
|
|
} else if (key.startsWith("exp(") && key.endsWith(")")) {
|
|
return this.#getKey(key.slice(4, -1));
|
|
} else {
|
|
return key;
|
|
}
|
|
}
|
|
|
|
#getName(pt) {
|
|
return Object.keys(pt)
|
|
.filter(d => d !== this.x && d !== this.y)
|
|
.sort()
|
|
.map(d => (typeof pt[d] === "string" ? pt[d] : `${d}=${pt[d]}`))
|
|
.join(',');
|
|
}
|
|
|
|
addPoint(point) {
|
|
const pt = {};
|
|
for (const key in point) {
|
|
if (!this.ignore.has(key)) {
|
|
pt[key] = point[key];
|
|
}
|
|
}
|
|
|
|
const name = this.#getName(pt);
|
|
if (!(name in this.series)) {
|
|
this.series[name] = this.chart.addSeries(name);
|
|
}
|
|
this.series[name].addPoint({
|
|
x: this.#getValue(pt, this.xAxis),
|
|
y: this.#getValue(pt, this.yAxis)
|
|
});
|
|
}
|
|
|
|
ignoreKey(key) {
|
|
if (key != this.x && key != this.y)
|
|
this.ignore.add(key);
|
|
}
|
|
}
|
|
|
|
const paramText = {
|
|
b: document.getElementById('insertPartSize').value,
|
|
n: document.getElementById('parts').value,
|
|
N: document.getElementById('poolSize').value,
|
|
L: document.getElementById('layers').value,
|
|
nMax: document.getElementById('maxSourceParts').value,
|
|
B: document.getElementById('maxPartSize').value,
|
|
};
|
|
const title = Object.keys(paramText)
|
|
.sort()
|
|
.filter(d => paramText[d] !== '')
|
|
.map(d => `${d}: ${paramText[d]}`)
|
|
.join('║');
|
|
|
|
const series = new SeriesManager(title, xAxis, yAxis);
|
|
|
|
let runners = {};
|
|
if (selectedMethod)
|
|
runners.GD = selectedMethod;
|
|
if (selectedSolver)
|
|
runners.BLI = selectedSolver;
|
|
|
|
series.ignoreKey('base');
|
|
series.ignoreKey('merges');
|
|
series.ignoreKey('alpha');
|
|
series.ignoreKey('cost');
|
|
series.ignoreKey('density');
|
|
if (insertPartSizeArray.length == 1)
|
|
series.ignoreKey('insertPartSize');
|
|
if (maxSourcePartsArray.length == 1)
|
|
series.ignoreKey('maxSourceParts');
|
|
if (maxPartSizeArray.length == 1)
|
|
series.ignoreKey('maxPartSize');
|
|
if (workersArray.length == 1)
|
|
series.ignoreKey('workers');
|
|
if (partsArray.length == 1)
|
|
series.ignoreKey('parts');
|
|
if (layersArray.length == 1)
|
|
series.ignoreKey('L');
|
|
|
|
for (const insertPartSize of insertPartSizeArray) {
|
|
for (const maxSourceParts of maxSourcePartsArray) {
|
|
for (const maxPartSize of maxPartSizeArray) {
|
|
for (const workers of workersArray) {
|
|
for (const parts of partsArray) {
|
|
for (const [runnerName, runner] of Object.entries(runners)) {
|
|
const params = {
|
|
_runner: runnerName,
|
|
insertPartSize,
|
|
parts,
|
|
workers,
|
|
maxSourceParts,
|
|
maxPartSize,
|
|
};
|
|
const xs = calculateBases(params, runner);
|
|
const bases = xs.map((x) => Math.exp(x));
|
|
for (const L of layersArray) {
|
|
if ((L - 1) in xs) {
|
|
const base = bases[L - 1];
|
|
const entropy = xs[L - 1];
|
|
const merges = parts / base;
|
|
const alpha = Math.max(1, merges / workers);
|
|
const cost = 0.5 * ((alpha + 1) * base + alpha - 1); // we assume B = 1 and merge speed = 1
|
|
const density = cost / entropy; // cost per utility (here utility = entropy due to B = 1)
|
|
series.addPoint({...params, L, base, merges, alpha, cost, density});
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
const endTime = performance.now(); // End timing
|
|
console.log(`Solve time: ${(endTime - startTime).toFixed(2)} ms`); // Log time
|
|
|
|
solveButton.textContent = 'Solve';
|
|
solveButton.disabled = false;
|
|
});
|
|
</script>
|
|
</body>
|
|
</html>
|