Blocklist experiments

blocklist.js

var ip = require('ip');

console.time("load");
var list = require("./bt_level1.js").map(function(block) {
	try {
		block.start = ip.toLong(block.start);
		block.end = ip.toLong(block.end);
	} catch(e) {
		console.log(e, block);
		process.exit(0);
	}
	return block;
});
console.timeEnd("load");
console.log("entries: " + list.length);

function BlockTree(start, end, reason) {
	this.block = { start: start, end: end, reason: reason };
	this.max = end;
	this.depth = 1;
	this.left = null;
	this.right = null;
}

BlockTree.prototype.balance = function() {
	var ldepth = this.left ? this.left.depth : 0;
	var rdepth = this.right ? this.right.depth : 0;

	if (ldepth > rdepth + 1) {
		var lldepth = this.left.left ? this.left.left.depth : 0;
		var lrdepth = this.left.right ? this.left.right.depth : 0;
		if (lldepth < lrdepth) this.left.rotateRR();
		this.rotateLL();
	} else if (ldepth + 1 < rdepth) {
		var rrdepth = this.right.right ? this.right.right.depth : 0;
		var rldepth = this.right.left ? this.right.left.depth : 0;
		if (rldepth > rrdepth) this.right.rotateLL();
		this.rotateRR();
	}
}

BlockTree.prototype.rotateLL = function() {
	var _block = this.block;
	var _right = this.right;

	this.block = this.left.block;
	this.right = this.left;
	this.left = this.left.left;

	this.right.left = this.right.right;
	this.right.right = _right;
	this.right.block = _block;

	this.right.update();
	this.update();
};

BlockTree.prototype.rotateRR = function() {
	var _block = this.block;
	var _left = this.left;

	this.block = this.right.block;
	this.end = this.right.end;
	this.left = this.right;
	this.right = this.right.right;

	this.left.right = this.left.left;
	this.left.left = _left;
	this.left.block = _block;

	this.left.update();
	this.update();
};

BlockTree.prototype.update = function() {
	this.depth = 1;
	if (this.left) this.depth = this.left.depth + 1;
	if (this.right && this.depth <= this.right.depth) this.depth = this.right.depth + 1;
	this.max = Math.max(this.block.end, this.left ? this.left.max : 0, this.right ? this.right.max : 0);
};

BlockTree.prototype.add = function(start, end, reason)  {
	var d = start - this.block.start;
	var update = false;

	if (d == 0 && this.block.end < end) {
		this.block.end = end;
		this.block.reason = reason;
		update = true;
	} else if (d < 0) {
		if (this.left) {
			update = this.left.add(start, end, reason);
			if (update) this.balance();
		} else {
			this.left = new BlockTree(start, end, reason);
			update = true;
		}
	} else if (d > 0) {
		if (this.right) {
			update = this.right.add(start, end, reason);
			if (update) this.balance();
		} else {
			this.right = new BlockTree(start, end, reason);
			update = true;
		}
	}

	if (update) this.update();
	return update;
};

BlockTree.prototype.search = function(addr) {
	var node = this;
	while (node && !(addr >= node.block.start && addr <= node.block.end)) {
		if (node.left && node.left.max >= addr) node = node.left;
		else node = node.right;
	}
	return node ? node.block : null;
}

// #### BIN ####
function bin_lookup(addr) {
	var min = 0;
	var max = list.length - 1;
	while(min <= max) {
		var mid = Math.floor((min + max) / 2);
		var range = list[mid];
		if(range.start <= addr && range.end >= addr) return range;
		else if(range.start > addr) max = mid - 1;
		else min = mid + 1;
	}
	return null;
}

// #### INSERT ####

console.time("insert");

var tree = new BlockTree(list[0].start, list[0].end, list[0].reason);

for(var i = 1, l = list.length; i < l; ++i) {
	tree.add(list[i].start, list[i].end, list[i].reason);
}

console.timeEnd("insert");

var miss = [];
var hit = [];
var miss_bin = [];
var hit_bin = [];

while(miss.length < 500000 || hit.length < 500000) {
	var ip = Math.round(Math.random()*range+min);

	var start = process.hrtime();
	var block = tree.search(ip);
	var diff = process.hrtime(start);
	var time = (diff[0] * 1e9 + diff[1]) / 1000;

	(block ? hit : miss).push(time);

	start = process.hrtime();
	var block2 = bin_lookup(ip);
	diff = process.hrtime(start);
	time = (diff[0] * 1e9 + diff[1]) / 1000;

	(block2 ? hit_bin : miss_bin).push(time);

	/*if(!!block2 !== !!block) {
		console.log("Lookup error:", ip);
		console.log("Tree:", block);
		console.log("Binary:", block2);
		return;
	}*/
}

function round(n) {
	var str = String(Math.round(n * 1000) / 1000);
	if (str.length > 6) return str.slice(0, 6 - str.length);
	return str;
}

function compute_data(set, drop_pct) {
	set.sort();

	var len = set.length;

	if(drop_pct) {
		var drop = len * drop_pct;
		set = set.slice(drop, -drop);
		len = set.length;
	}

	var min = Infinity;
	var max = -Infinity;
	var sum = 0;

	for(var i = 0; i < len; ++i) {
		var n = set[i];
		if(n < min) min = n;
		if(n > max) max = n;
		sum += n;
	}

	var avg = sum / len;

	var mid = (len - 1) / 2;
	var mean = (set[Math.floor(mid)] + set[Math.ceil(mid)]) / 2;

	var dev = 0;

	for(var i = 0; i < len; ++i) {
		var n = set[i] - avg;
		dev += n * n;
	}

	var std_dev = Math.sqrt(dev / (len - 1));

	return [len, round(min), round(avg), round(mean), round(max), round(std_dev)];
}

console.log("\n(time unit is μs)");

console.log("\nFull tree data:");
var miss_data = compute_data(miss, 0);
var hit_data = compute_data(hit, 0);

console.log("\tCount\tMin\tAvg\tMedian\tMax\tσ");
console.log("Miss:\t"
			+ miss_data[0] + "\t"
			+ miss_data[1] + "\t"
			+ miss_data[2] + "\t"
			+ miss_data[3] + "\t"
			+ miss_data[4] + "\t"
		    + miss_data[5]);

console.log("Hit:\t"
			+ hit_data[0] + "\t"
			+ hit_data[1] + "\t"
			+ hit_data[2] + "\t"
			+ hit_data[3] + "\t"
			+ hit_data[4] + "\t"
		    + hit_data[5]);

console.log("\nFull binary search:");
var miss_bin_data = compute_data(miss_bin, 0);
var hit_bin_data = compute_data(hit_bin, 0);

console.log("\tCount\tMin\tAvg\tMedian\tMax\tσ");
console.log("Miss:\t"
			+ miss_bin_data[0] + "\t"
			+ miss_bin_data[1] + "\t"
			+ miss_bin_data[2] + "\t"
			+ miss_bin_data[3] + "\t"
			+ miss_bin_data[4] + "\t"
		    + miss_bin_data[5]);

console.log("Hit:\t"
			+ hit_bin_data[0] + "\t"
			+ hit_bin_data[1] + "\t"
			+ hit_bin_data[2] + "\t"
			+ hit_bin_data[3] + "\t"
			+ hit_bin_data[4] + "\t"
		    + hit_bin_data[5]);

console.log("\n90% tree data:");
var miss_data = compute_data(miss, 0.05);
var hit_data = compute_data(hit, 0.05);

console.log("\tCount\tMin\tAvg\tMedian\tMax\tσ");
console.log("Miss:\t"
			+ miss_data[0] + "\t"
			+ miss_data[1] + "\t"
			+ miss_data[2] + "\t"
			+ miss_data[3] + "\t"
			+ miss_data[4] + "\t"
		    + miss_data[5]);

console.log("Hit:\t"
			+ hit_data[0] + "\t"
			+ hit_data[1] + "\t"
			+ hit_data[2] + "\t"
			+ hit_data[3] + "\t"
			+ hit_data[4] + "\t"
		    + hit_data[5]);

console.log("\n90% binary search:");
var miss_bin_data = compute_data(miss_bin, 0.05);
var hit_bin_data = compute_data(hit_bin, 0.05);

console.log("\tCount\tMin\tAvg\tMedian\tMax\tσ");
console.log("Miss:\t"
			+ miss_bin_data[0] + "\t"
			+ miss_bin_data[1] + "\t"
			+ miss_bin_data[2] + "\t"
			+ miss_bin_data[3] + "\t"
			+ miss_bin_data[4] + "\t"
		    + miss_bin_data[5]);

console.log("Hit:\t"
			+ hit_bin_data[0] + "\t"
			+ hit_bin_data[1] + "\t"
			+ hit_bin_data[2] + "\t"
			+ hit_bin_data[3] + "\t"
			+ hit_bin_data[4] + "\t"
		    + hit_bin_data[5]);

return;

module.exports = function(blocklist) {
	var tree = null;
	var that = {};

	that.add = function(start, end, reason) {
		if (!start) return;
		if (typeof start === 'object') {
			end = start.end;
			reason = start.reason;
			start = start.start;
		}

		if (typeof start !== 'number') start = ip.toLong(start);

		if (!end) end = start;
		if (typeof end !== 'number') end = ip.toLong(end);

		if (start < 0 || end > 4294967295 || end < start) throw new Error("Invalid block range");

		if (tree) tree.add(start, end, reason);
		else tree = new BlockTree(start, end, reason);
	}

	that.search = function(addr) {
		if (!tree) return null;
		if (typeof addr !== 'number') addr = ip.toLong(addr);
		return tree.search(addr);
	}

	if (Array.isArray(blocklist)) {
		blocklist.forEach(function(block) {
			that.add(block);
		});
	}

	return that;
};