Skip to content

Instantly share code, notes, and snippets.

@lukekarrys
Last active December 7, 2019 18:25
Show Gist options
  • Save lukekarrys/29862f1162560f6b53263884b238bbba to your computer and use it in GitHub Desktop.
Save lukekarrys/29862f1162560f6b53263884b238bbba to your computer and use it in GitHub Desktop.
Playing around with random keys, collisions, and slow lookups
node_modules/
const assert = require("assert");
const {
toPairs,
toArray,
countBy,
times,
random,
snakeCase
} = require("lodash");
const {
KEY_LENGTH,
ITERATIONS,
MAX_RETRIES,
DELAY_LOOKUP_MIN,
DELAY_LOOKUP_MAX,
CHAR_SET
} = process.argv.slice(2).reduce(
(acc, k, i, list) => {
if (i % 2 > 0) return acc;
const key = snakeCase(k.slice(2)).toUpperCase();
const value = list[i + 1];
acc[key] = /^\d+$/.test(value) ? Number(value) : value;
return acc;
},
{
KEY_LENGTH: 4,
ITERATIONS: 923521,
MAX_RETRIES: Infinity,
DELAY_LOOKUP_MIN: 0,
DELAY_LOOKUP_MAX: 1,
// Less ambiguous character set (no o, 0, 1, l, i, etc)
CHAR_SET: "abcdefghjkmnpqrstuvwxyz23456789"
}
);
assert.ok(
ITERATIONS <= Math.pow(CHAR_SET.length, KEY_LENGTH),
"Iterations is too big for the max of char set and key length"
);
const hrtimeN = hrtime => hrtime[0] * 1e9 + hrtime[1];
const hrtimeM = hrtime => hrtimeN(hrtime) / 1e6;
const hrtimeS = hrtime => hrtimeM(hrtime) / 1e3;
const sleep = time => {
const stop = process.hrtime();
while (hrtimeM(process.hrtime(stop)) < time) {}
return true;
};
const generateKey = (length = KEY_LENGTH) =>
times(length, () => CHAR_SET.charAt(random(0, CHAR_SET.length - 1))).join("");
class DelayMap extends Map {
has(key) {
if (DELAY_LOOKUP_MAX) {
sleep(random(DELAY_LOOKUP_MIN || 0, DELAY_LOOKUP_MAX));
}
return super.has(key);
}
}
const keys = new DelayMap();
const tryGenerateKey = () => {
let key = null;
let tries = 0;
do {
tries++;
key = generateKey();
if (!keys.has(key)) {
return { key, tries };
}
if (tries >= MAX_RETRIES) {
assert.fail(`Exceeded max retries ${MAX_RETRIES}`);
}
} while (true);
};
const start = process.hrtime();
for (let i = 0; i < ITERATIONS; i++) {
const startKey = process.hrtime();
const { key, tries } = tryGenerateKey();
keys.set(key, tries);
const endKey = process.hrtime(startKey);
console.log(key, tries, keys.size, `${hrtimeM(endKey)}ms`);
}
assert.equal(keys.size, ITERATIONS);
const end = process.hrtime(start);
const countByTries = toPairs(countBy(toArray(keys.values())))
.map(v => v.join(" "))
.join("\n");
console.log("-".repeat(40));
console.log(countByTries);
console.log(`${hrtimeS(end)}s`);
{
"name": "key-collisions",
"version": "1.0.0",
"lockfileVersion": 1,
"requires": true,
"dependencies": {
"lodash": {
"version": "4.17.15",
"resolved": "https://registry.npmjs.org/lodash/-/lodash-4.17.15.tgz",
"integrity": "sha512-8xOcRHvCjnocdS5cpwXQXVzmmh5e5+saE2QGoeQmbKmRS6J3VQppPOIt0MnmE+4xlZoumy0GPG0D0MVIQbNA1A=="
}
}
}
{
"name": "key-collisions",
"version": "1.0.0",
"dependencies": {
"lodash": "^4.17.15"
},
"keywords": [],
"license": "ISC",
"main": "index.js",
"private": true
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment