Optimized fetch of random values using cache

[TanukiSharp]

I would like to propose a good optimization for a few code change.

Here the sample code I used to benchmark the gain:

const crypto = require('crypto');

const RANDOM_BATCH_SIZE = 256;
let randomIndex;
let randomBytes;
const getNextRandomValue = () => {
    if (randomIndex === undefined || randomIndex >= randomBytes.length) {
        randomIndex = 0;
        randomBytes = crypto.randomBytes(RANDOM_BATCH_SIZE);
    }

    const result = randomBytes[randomIndex];
    randomIndex += 1;

    return result;
};

const iterations = 1000000;

const func1 = () => {
    for (let i = 0; i < iterations; i += 1) {
        crypto.randomBytes(1);
    }
};

const func2 = () => {
    for (let i = 0; i < iterations; i += 1) {
        getNextRandomValue();
    }
};

const startTime = Date.now();
func1();
//func2();
const endTime = Date.now();

console.log(`Took ${endTime - startTime} ms for ${iterations} iterations.`);

With the optimization, the code (func2) runs about 67 times faster.

And hereafter is another benchmark code to find the best RANDOM_BATCH_SIZE:

const crypto = require('crypto');

let RANDOM_BATCH_SIZE = 32;
let randomIndex;
let randomBytes;
const getNextRandomValue = () => {
    if (randomIndex === undefined || randomIndex >= randomBytes.length) {
        randomIndex = 0;
        randomBytes = crypto.randomBytes(RANDOM_BATCH_SIZE);
    }

    const result = randomBytes[randomIndex];
    randomIndex += 1;

    return result;
};

const iterations = 1000000;

const runFunc = (funcToRun, funcName, numberOfTimes) => {
    let totalDuration = 0;

    for (let i = 0; i < numberOfTimes; i += 1) {
        const startTime = Date.now();
        funcToRun();
        const endTime = Date.now();
        totalDuration += endTime - startTime;
    }

    return totalDuration / numberOfTimes;
};

const func1 = () => {
    for (let i = 0; i < iterations; i += 1) {
        crypto.randomBytes(1);
    }
};

const func2 = () => {
    for (let i = 0; i < iterations; i += 1) {
        getNextRandomValue();
    }
};

let baseDuration = runFunc(func1, 'func1', 10);

console.log(`Average base duration: ${baseDuration} ms for ${iterations} iterations.`);

for (let size = 32; size <= 1024; size += 32) {
    RANDOM_BATCH_SIZE = size;
    const duration = runFunc(func2, 'func2', 50);
    console.log(`Batch size ${size}: ${duration} ms for ${iterations} iterations. ` +
        `[x${Math.round(baseDuration / duration)}]`);
}

Running this gave me the following result:

Average base duration: 2633.5 ms for 1000000 iterations.
Batch size 32: 103.81 ms for 1000000 iterations. [x25]
Batch size 64: 64.16 ms for 1000000 iterations. [x41]
Batch size 96: 55.34 ms for 1000000 iterations. [x48]
Batch size 128: 46.56 ms for 1000000 iterations. [x57]
Batch size 160: 43.51 ms for 1000000 iterations. [x61]
Batch size 192: 39.29 ms for 1000000 iterations. [x67]
Batch size 224: 37.57 ms for 1000000 iterations. [x70]
Batch size 256: 35.75 ms for 1000000 iterations. [x74]
Batch size 288: 34.87 ms for 1000000 iterations. [x76]
Batch size 320: 33.13 ms for 1000000 iterations. [x79]
Batch size 352: 33.98 ms for 1000000 iterations. [x78]
Batch size 384: 33.96 ms for 1000000 iterations. [x78]
Batch size 416: 32.03 ms for 1000000 iterations. [x82]
Batch size 448: 31.35 ms for 1000000 iterations. [x84]
Batch size 480: 31.27 ms for 1000000 iterations. [x84]
Batch size 512: 33.13 ms for 1000000 iterations. [x79]
Batch size 544: 31.28 ms for 1000000 iterations. [x84]
Batch size 576: 30.15 ms for 1000000 iterations. [x87]
Batch size 608: 31.52 ms for 1000000 iterations. [x84]
Batch size 640: 31.39 ms for 1000000 iterations. [x84]
Batch size 672: 29.36 ms for 1000000 iterations. [x90]
Batch size 704: 28.89 ms for 1000000 iterations. [x91]
Batch size 736: 29.06 ms for 1000000 iterations. [x91]
Batch size 768: 30.55 ms for 1000000 iterations. [x86]
Batch size 800: 27.78 ms for 1000000 iterations. [x95]
Batch size 832: 28.05 ms for 1000000 iterations. [x94]
Batch size 864: 28.88 ms for 1000000 iterations. [x91]
Batch size 896: 27.51 ms for 1000000 iterations. [x96]
Batch size 928: 28.62 ms for 1000000 iterations. [x92]
Batch size 960: 27.68 ms for 1000000 iterations. [x95]
Batch size 992: 28.68 ms for 1000000 iterations. [x92]
Batch size 1024: 29.13 ms for 1000000 iterations. [x90]

We can see that beyond 256, the gain still gets bigger but isn't really significant to justify allocating more memory. Maybe this can be made configurable.

Note that with the values I obtained, it can run up to 96 times faster.

Please don't tell me that passwords are generally not generated million times (I get that) so performance does not matter (I wouldn't get that).

Thank you for your consideration.

[brendanashworth]

@TanukiSharp this is great, thank you! I've merged it in https://github.com/brendanashworth/generate-password/commit/ea642553c5ba327989f36d0b0f2d4e80ff25b45a and am releasing a patch release with the change. Cheers 🍻

[TanukiSharp]

Waow that was fast, awesome, thank you :)