Skip to content

Instantly share code, notes, and snippets.

@jerch

jerch/index.html

Created August 8, 2018 09:12
Show Gist options
  • Save jerch/ad0d03ab606713799bd5bfbc2f6beb27 to your computer and use it in GitHub Desktop.
Save jerch/ad0d03ab606713799bd5bfbc2f6beb27 to your computer and use it in GitHub Desktop.
Download ZIP
Untitled benchmark (https://jsbench.github.io/#ad0d03ab606713799bd5bfbc2f6beb27) #jsbench #jsperf
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"/>
<title>Untitled benchmark</title>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/1.0.0/benchmark.min.js"></script>
<script src="./suite.js"></script>
</head>
<body>
<h1>Open the console to view the results</h1>
<h2><code>cmd + alt + j</code> or <code>ctrl + alt + j</code></h2>
</body>
</html>
Raw
suite.js
"use strict";
(function (factory) {
if (typeof Benchmark !== "undefined") {
factory(Benchmark);
} else {
factory(require("benchmark"));
}
})(function (Benchmark) {
var suite = new Benchmark.Suite;
Benchmark.prototype.setup = function () {
var PoolAllocatorU32 = /** @class */ (function () {
function PoolAllocatorU32(initialSlots, maxSlots, slotSize) {
this.initialSlots = initialSlots;
this.maxSlots = maxSlots;
this.slotSize = slotSize;
// adjust slotSize to multiple of 4 (must be at least 4 bytes to hold list address)
this.entrySize = slotSize;
// check for address overflow
if ((initialSlots + 1) * this.entrySize > 0xFFFFFFFF)
throw new Error('initial address space exceeds 2^32');
if ((maxSlots + 1) * this.entrySize > 0xFFFFFFFF)
throw new Error('max address space exceeds 2^32');
// create storage, reserve first slot as NULL
this.HEAP = new Uint32Array(this.entrySize * (this.initialSlots + 1));
// insert free list pointers
// last slot gets NULL pointer
// head points to first slot at entrySize
for (var i = this.entrySize; i < this.HEAP.length; i += this.entrySize)
this.HEAP[i] = i + this.entrySize;
this.HEAP[this.HEAP.length - this.entrySize] = 0;
this.head = this.entrySize;
this.numSlots = this.initialSlots;
}
PoolAllocatorU32.prototype.alloc = function () {
if (!this.head) {
// out of memory, try to resize
var newSlots = this.numSlots * 2;
if (newSlots > this.maxSlots)
newSlots = this.maxSlots;
if (newSlots === this.numSlots)
throw new Error('out of memory');
// alloc new storage and copy values over
var HEAP = new Uint32Array(this.entrySize * (newSlots + 1));
for (var i = 0; i < this.HEAP.length; ++i)
HEAP[i] = this.HEAP[i];
HEAP[HEAP.length - this.entrySize] = 0;
for (var i = this.HEAP.length; i < HEAP.length; i += this.entrySize)
HEAP[i] = i + this.entrySize;
HEAP[HEAP.length - this.entrySize] = 0;
this.head = this.HEAP.length;
this.numSlots = newSlots;
this.HEAP = HEAP;
}
var idx = this.head;
this.head = this.HEAP[idx];
return idx;
};
PoolAllocatorU32.prototype.free = function (idx) {
this.HEAP[idx] = this.head;
this.head = idx;
};
return PoolAllocatorU32;
}());
var nullptr = 0;
var LLRB = /** @class */ (function () {
function LLRB(initialSlots, maxSlots) {
//this.memory = new PoolAllocator(initialSlots, maxSlots, 20);
//this.M = this.memory.HEAP32;
this.memory = new PoolAllocatorU32(initialSlots, maxSlots, 5);
this.M = this.memory.HEAP;
this.alloc = this.memory.alloc.bind(this.memory);
this.bottom = nullptr;
this.root = this.bottom;
}
//alloc() {
// return this.memory.alloc() >> 2;
//}
LLRB.prototype.compare = function (a, b) {
return a < b ? -1 : a > b ? 1 : 0;
};
LLRB.prototype.find = function (key) {
var M = this.M;
var n = this.root;
while (n !== this.bottom) {
var c = this.compare(key, M[n + 0 /* KEY */]);
if (c === 0)
return n;
n = c < 0 ? M[n + 3 /* LEFT */] : M[n + 4 /* RIGHT */];
}
return nullptr;
};
LLRB.prototype.insert = function (key, value) {
this.root = this._insert(this.root, key, value, this.M);
this.M[this.root + 2 /* RED */] = 0;
};
LLRB.prototype.removeMin = function () {
if (this.root === this.bottom)
return;
var M = this.M;
var root_left = M[this.root + 3 /* LEFT */];
var root_right = M[this.root + 4 /* RIGHT */];
if (!M[root_left + 2 /* RED */] && !M[root_right + 2 /* RED */])
M[this.root + 2 /* RED */] = 1;
this.root = this._removeMin(this.root, M);
M[this.root + 2 /* RED */] = 0;
};
LLRB.prototype.remove = function (key) {
if (!this.find(key))
return;
var M = this.M;
if (!M[M[this.root + 3 /* LEFT */] + 2 /* RED */] && !M[M[this.root + 4 /* RIGHT */] + 2 /* RED */])
M[this.root + 2 /* RED */] = 1;
this.root = this._remove(this.root, key, M);
M[this.root + 2 /* RED */] = 0;
};
LLRB.prototype._insert = function (h, key, value, M) {
if (h === this.bottom) {
var idx = this.alloc();
this.M = this.memory.HEAP;
M = this.M;
M[idx + 0 /* KEY */] = key;
M[idx + 1 /* VALUE */] = value;
M[idx + 2 /* RED */] = 1;
M[idx + 3 /* LEFT */] = this.bottom;
M[idx + 4 /* RIGHT */] = this.bottom;
return idx;
}
var c = this.compare(key, M[h + 0 /* KEY */]);
if (c < 0)
this.M[h + 3 /* LEFT */] = this._insert(M[h + 3 /* LEFT */], key, value, M);
else if (c > 0)
this.M[h + 4 /* RIGHT */] = this._insert(M[h + 4 /* RIGHT */], key, value, M);
else
this.M[h + 1 /* VALUE */] = value;
M = this.M;
if (M[M[h + 4 /* RIGHT */] + 2 /* RED */] && !M[M[h + 3 /* LEFT */] + 2 /* RED */])
h = this._rotateLeft(h, M);
if (M[M[h + 3 /* LEFT */] + 2 /* RED */] && M[M[M[h + 3 /* LEFT */] + 3 /* LEFT */] + 2 /* RED */])
h = this._rotateRight(h, M);
if (M[M[h + 3 /* LEFT */] + 2 /* RED */] && M[M[h + 4 /* RIGHT */] + 2 /* RED */])
this._flipColors(h, M);
return h;
};
LLRB.prototype._remove = function (h, key, M) {
if (this.compare(key, M[h + 0 /* KEY */]) < 0) {
var left = M[h + 3 /* LEFT */];
if (!M[left + 2 /* RED */] && !M[M[left + 3 /* LEFT */] + 2 /* RED */])
h = this._moveRedLeft(h, M);
M[h + 3 /* LEFT */] = this._remove(M[h + 3 /* LEFT */], key, M);
}
else {
if (M[M[h + 3 /* LEFT */] + 2 /* RED */])
h = this._rotateRight(h, M);
if (this.compare(key, M[h + 0 /* KEY */]) === 0 && (M[h + 4 /* RIGHT */] === this.bottom))
return this.bottom;
var right = M[h + 4 /* RIGHT */];
if (!M[right + 2 /* RED */] && !M[M[right + 3 /* LEFT */] + 2 /* RED */])
h = this._moveRedRight(h, M);
if (this.compare(key, M[h + 0 /* KEY */]) === 0) {
var x = this._min(M[h + 4 /* RIGHT */], M);
M[h + 0 /* KEY */] = M[x + 0 /* KEY */];
M[h + 1 /* VALUE */] = M[x + 1 /* VALUE */];
M[h + 4 /* RIGHT */] = this._removeMin(M[h + 4 /* RIGHT */], M);
}
else
M[h + 4 /* RIGHT */] = this._remove(M[h + 4 /* RIGHT */], key, M);
}
return this._balance(h, M);
};
LLRB.prototype._min = function (h, M) {
if (M[h + 3 /* LEFT */] === this.bottom)
return h;
return this._min(M[h + 3 /* LEFT */], M);
};
LLRB.prototype._removeMin = function (h, M) {
var left = M[h + 3 /* LEFT */];
if (left === this.bottom)
return this.bottom;
if (!M[left + 2 /* RED */] && !M[M[left + 3 /* LEFT */] + 2 /* RED */])
h = this._moveRedLeft(h, M);
M[h + 3 /* LEFT */] = this._removeMin(left, M);
return this._balance(h, M);
};
LLRB.prototype._balance = function (h, M) {
if (M[M[h + 4 /* RIGHT */] + 2 /* RED */])
h = this._rotateLeft(h, M);
var left = M[h + 3 /* LEFT */];
if (M[left + 2 /* RED */] && M[M[left + 3 /* LEFT */] + 2 /* RED */])
h = this._rotateRight(h, M);
if (M[M[h + 3 /* LEFT */] + 2 /* RED */] && M[M[h + 4 /* RIGHT */] + 2 /* RED */])
this._flipColors(h, M);
return h;
};
LLRB.prototype._moveRedLeft = function (h, M) {
this._flipColors(h, M);
var right = M[h + 4 /* RIGHT */];
if (M[M[right + 3 /* LEFT */] + 2 /* RED */]) {
M[h + 4 /* RIGHT */] = this._rotateRight(right, M);
h = this._rotateLeft(h, M);
}
return h;
};
LLRB.prototype._moveRedRight = function (h, M) {
this._flipColors(h, M);
if (M[M[M[h + 3 /* LEFT */] + 3 /* LEFT */] + 2 /* RED */])
h = this._rotateRight(h, M);
return h;
};
LLRB.prototype._rotateRight = function (h, M) {
var x = M[h + 3 /* LEFT */];
M[h + 3 /* LEFT */] = M[x + 4 /* RIGHT */];
M[x + 4 /* RIGHT */] = h;
M[x + 2 /* RED */] = M[h + 2 /* RED */];
M[h + 2 /* RED */] = 1;
return x;
};
LLRB.prototype._rotateLeft = function (h, M) {
var x = M[h + 4 /* RIGHT */];
M[h + 4 /* RIGHT */] = M[x + 3 /* LEFT */];
M[x + 3 /* LEFT */] = h;
M[x + 2 /* RED */] = M[h + 2 /* RED */];
M[h + 2 /* RED */] = 1;
return x;
};
LLRB.prototype._flipColors = function (h, M) {
M[h + 2 /* RED */] ^= 1;
M[M[h + 3 /* LEFT */] + 2 /* RED */] ^= 1;
M[M[h + 4 /* RIGHT */] + 2 /* RED */] ^= 1;
};
return LLRB;
}());
function insert(num, data) {
for (let i=0; i<data.length; ++i) {
if (!data[i]) {
data[i] = num;
return i;
}
if (data[i] === num) return i;
}
}
function filler(from, to, data) {
for (let i=from; i<to; ++i) insert(i, data);
}
function fillerllrb(from, to, data) {
for (let i=from; i<to; ++i) data.insert(i);
}
let b100 = new Uint32Array(1000000);
filler(1, 100, b100);
let b1000 = new Uint32Array(1000000);
filler(1, 1000, b1000);
let b10000 = new Uint32Array(1000000);
filler(1, 10000, b10000);
let llrb = new LLRB(1000000, 1000000);
fillerllrb(1, 100000, llrb);
};
Benchmark.prototype.teardown = function () {
b100.fill(0);
filler(1, 100, b100);
b1000.fill(0);
filler(1, 1000, b1000);
b10000.fill(0);
filler(1, 10000, b10000);
llrb = new LLRB(1000000, 1000000);
fillerllrb(1, 100000, llrb);
};
suite.add("filler(10000, 10100, b100);", function () {
filler(10000, 10100, b100);
});
suite.add("filler(10000, 10100, b1000);", function () {
filler(10000, 10100, b1000);
});
suite.add("filler(10000, 10100, b10000);", function () {
filler(10000, 10100, b10000);
});
suite.add("fillerllrb(100000, 100100, llrb);", function () {
fillerllrb(100000, 100100, llrb);
});
suite.on("cycle", function (evt) {
console.log(" - " + evt.target);
});
suite.on("complete", function (evt) {
console.log(new Array(30).join("-"));
var results = evt.currentTarget.sort(function (a, b) {
return b.hz - a.hz;
});
results.forEach(function (item) {
console.log((idx + 1) + ". " + item);
});
});
console.log("Untitled benchmark");
console.log(new Array(30).join("-"));
suite.run();
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment