summaryrefslogtreecommitdiffstats
path: root/docs/tests/hnbigset-benchmark.html
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 05:47:55 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 05:47:55 +0000
commit31d6ff6f931696850c348007241195ab3b2eddc7 (patch)
tree615cb1c57ce9f6611bad93326b9105098f379609 /docs/tests/hnbigset-benchmark.html
parentInitial commit. (diff)
downloadublock-origin-31d6ff6f931696850c348007241195ab3b2eddc7.tar.xz
ublock-origin-31d6ff6f931696850c348007241195ab3b2eddc7.zip
Adding upstream version 1.55.0+dfsg.upstream/1.55.0+dfsg
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'docs/tests/hnbigset-benchmark.html')
-rw-r--r--docs/tests/hnbigset-benchmark.html268
1 files changed, 268 insertions, 0 deletions
diff --git a/docs/tests/hnbigset-benchmark.html b/docs/tests/hnbigset-benchmark.html
new file mode 100644
index 0000000..6816f4f
--- /dev/null
+++ b/docs/tests/hnbigset-benchmark.html
@@ -0,0 +1,268 @@
+<!DOCTYPE html>
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
+<meta name="viewport" content="width=device-width, initial-scale=1">
+</head>
+<body style="font: 14px sans-serif">
+<h1>Benchmark of hostname-lookup from small to large set:<br>Set, HNTrie</h1>
+<p><a href="./.">Back</a></p>
+<p>&nbsp;</p>
+<p><button id="createBenchmark">Creation</button> <button id="lookupBenchmark">Lookup</button></p>
+<div id="results-0" style="white-space:pre;font-family:mono"></div>
+<div id="results-1" style="white-space:pre;font-family:mono"></div>
+<div id="results-2" style="white-space:pre;font-family:mono"></div>
+<div id="results-3" style="white-space:pre;font-family:mono"></div>
+<div id="results-4" style="white-space:pre;font-family:mono"></div>
+<div id="results-5" style="white-space:pre;font-family:mono"></div>
+<div id="results-6" style="white-space:pre;font-family:mono"></div>
+
+<script src="https://rawcdn.githack.com/gorhill/uBlock/1b6fea16da81d1df3e2efd5a31894f71ea04dbb1/src/js/hntrie.js"></script>
+<!-- <script src="../../src/js/hntrie.js"></script> -->
+<script src="hostname-pool.js"></script>
+
+<script src="https://cdn.jsdelivr.net/lodash/4.17.2/lodash.min.js"></script>
+<script src="https://cdn.jsdelivr.net/platform.js/1.3.3/platform.js"></script>
+<script src="https://cdn.jsdelivr.net/benchmarkjs/2.1.2/benchmark.js"></script>
+<script>
+const randomHostname = function() {
+ return hostnamePool[Math.floor(Math.random() * hostnamePool.length)];
+};
+
+const randomNeedle = function() {
+ let needle = randomHostname();
+ const pos = needle.lastIndexOf('.');
+ if ( pos !== -1 ) {
+ needle = Math.random().toString(36).slice(2) + needle.slice(pos);
+ }
+ if ( Math.random() < 0.5 ) {
+ needle = Math.random().toString(36).slice(2, 6) + '.' + needle;
+ }
+ return needle;
+};
+
+// Create hostname dictionary of all sizes (from 2 to 1024 at most)
+const hostnameLists = (function() {
+ const dicts = [];
+ let n = hostnamePool.length;
+ while ( n > 1 ) {
+ const dict = [];
+ for ( let i = 0; i < n; i++ ) {
+ dict.push(randomHostname());
+ }
+ dicts.unshift(dict);
+ n = n >>> 2;
+ }
+ return dicts;
+})();
+
+/******************************************************************************/
+
+var setBasedDictCreate = function(hostnames) {
+ return new Set(hostnames);
+};
+
+var setBasedDictTest = function(haystack, needle) {
+ for (;;) {
+ if ( haystack.has(needle) ) { return true; }
+ const pos = needle.indexOf('.');
+ if ( pos === -1 ) { break; }
+ needle = needle.slice(pos + 1);
+ }
+ return false;
+};
+
+/******************************************************************************/
+
+const hnBigTrieJS = new HNTrieContainer();
+const hnBigTrieWASM = new HNTrieContainer();
+
+const trieBasedDictCreateJS = function(hostnames) {
+ return hnBigTrieJS.fromIterable(hostnames, 'addJS');
+}
+
+const trieBasedDictTest = function(haystack, needle) {
+ return haystack.matchesJS(needle);
+};
+
+const trieBasedDictCreateWASM = function(hostnames) {
+ return hnBigTrieWASM.fromIterable(hostnames, 'addWASM');
+}
+
+const trieBasedDictTestWASM = function(haystack, needle) {
+ return haystack.matchesWASM(needle);
+};
+
+/******************************************************************************/
+
+const gBenchmarks = [ null ];
+let gWhich;
+
+/******************************************************************************/
+
+function stdout(which, text) {
+ if ( which > 0 ) {
+ which = ((which - 1) % 3) + 1;
+ }
+ var r = document.querySelector('#results-' + which);
+ if ( text === '' ) {
+ r.innerHTML = '';
+ } else {
+ r.innerHTML += text;
+ }
+}
+
+function doBenchmark(which) {
+ stdout(0, '');
+ stdout(0, 'Benchmarking, the higher ops/sec the better.\n');
+ stdout(0, Benchmark.platform.toString() + '.');
+ stdout(0, '\n\n');
+ stdout(1, '');
+ stdout(2, '');
+ stdout(3, '');
+ gWhich = which;
+ gBenchmarks[gWhich].run({ 'async': true });
+}
+
+function nextBenchmark() {
+ stdout(gWhich, 'Done.\n\n');
+ gWhich += 1;
+ var bms = gBenchmarks[gWhich];
+ if ( bms ) {
+ bms.run({ 'async': true });
+ }
+}
+
+function exitBenchmark() {
+ stdout(gWhich, 'Done.\n\n');
+}
+
+/******************************************************************************/
+
+function initBenchmarks() {
+ gBenchmarks.push((function() {
+ let dicts = [];
+ let bigTrieDictsSerialized;
+
+ const createDict = function(fn) {
+ const out = [];
+ for ( let i = 0; i < hostnameLists.length; i++ ) {
+ out[i] = fn(hostnameLists[i]);
+ }
+ return out;
+ };
+
+ var bms = new Benchmark.Suite();
+ bms.add(' - Set-based', function() {
+ dicts = createDict(setBasedDictCreate);
+ }).add(' - Trie-based JS (3rd-gen)', function() {
+ hnBigTrieJS.reset();
+ dicts = createDict(trieBasedDictCreateJS);
+ });
+ if ( hnBigTrieWASM.addWASM !== null ) {
+ bms.add(' - Trie-based WASM (3rd-gen)', function() {
+ hnBigTrieWASM.reset();
+ dicts = createDict(trieBasedDictCreateWASM);
+ });
+ }
+ bms.add(' - Trie-based unserialized (3rd-gen)', function() {
+ hnBigTrieJS.reset();
+ hnBigTrieJS.unserialize(bigTrieDictsSerialized);
+ }).on('start', function() {
+ hnBigTrieJS.reset();
+ createDict(trieBasedDictCreateJS);
+ bigTrieDictsSerialized = hnBigTrieJS.serialize();
+ stdout(gWhich, '');
+ stdout(gWhich, 'Create dictionaries\n');
+ }).on('cycle', function(event) {
+ stdout(gWhich, String(event.target) + '\n');
+ }).on('complete', function() {
+ dicts = [];
+ bigTrieDictsSerialized = undefined;
+ exitBenchmark();
+ });
+
+ return bms;
+ })());
+
+ const lookupCount = 100;
+
+ gBenchmarks.push((function() {
+ const bms = new Benchmark.Suite();
+ const needles = [];
+
+ let setDicts = [];
+ let bigTrieDicts = [];
+ let results;
+
+ const lookupDict = function(dicts, fn) {
+ for ( let i = 0; i < needles.length; i++ ) {
+ const needle = needles[i];
+ for ( const dict of dicts ) {
+ results[i] = fn(dict, needle);
+ }
+ }
+ };
+
+ bms.add(' - Set-based', function() {
+ lookupDict(setDicts, setBasedDictTest);
+ }).add(' - Trie-based JS (3rd-gen)', function() {
+ lookupDict(bigTrieDicts, trieBasedDictTest);
+ });
+ if ( hnBigTrieWASM.matchesWASM !== null ) {
+ bms.add(' - Trie-based WASM (3rd-gen)', function() {
+ lookupDict(bigTrieDicts, trieBasedDictTestWASM);
+ })
+ }
+ bms.on('start', function() {
+ for ( let i = 0; i < lookupCount; i++ ) {
+ needles[i] = randomNeedle();
+ }
+ setDicts = [];
+ bigTrieDicts = [];
+ results = [];
+ hnBigTrieJS.reset();
+ for ( const hostnameList of hostnameLists ) {
+ setDicts.push(setBasedDictCreate(hostnameList));
+ bigTrieDicts.push(trieBasedDictCreateJS(hostnameList));
+ }
+ hnBigTrieJS.optimize();
+ stdout(gWhich, '');
+ stdout(
+ gWhich,
+ 'Test ' + lookupCount +
+ ' needles against ' + setDicts.length +
+ ' dictionaries with size between ' + hostnameLists[0].length +
+ ' and ' + hostnameLists[hostnameLists.length-1].length +
+ ' hostnames\n'
+ );
+ }).on('cycle', function(event) {
+ stdout(gWhich, String(event.target) + '\n');
+ }).on('complete', ( ) => {
+ setDicts = bigTrieDicts = results = [];
+ hnBigTrieJS.reset();
+ exitBenchmark();
+ });
+
+ return bms;
+ })());
+}
+
+/******************************************************************************/
+
+Promise.all([
+ hnBigTrieJS.readyToUse(),
+ hnBigTrieWASM.readyToUse()
+]).then(( ) => {
+ initBenchmarks();
+});
+
+document.getElementById('createBenchmark').onclick = function() {
+ doBenchmark(1);
+};
+document.getElementById('lookupBenchmark').onclick = function() {
+ doBenchmark(2);
+};
+</script>
+</body>
+</html>
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-12 19:54:31 +0000