Let's optimize JavaScript - password generator (2.15x faster)

Keff - Aug 26 '21 - - Dev Community

I was searching through Github explore, when I found a password generator (omgopass), that supposedly was quite a lot faster that other alternatives. 600 times faster than password-generator.

This is the benchmark omgopass shows:

Original omgopass Benchmark

After seeing this I remembered I did a password generator a couple weeks back, and did not perform any benchmarks, so I decided to test my approach with this other libraries.

To my surprise it did fairly well, scoring second place in the same benchmark as shown above. Quite good for not even trying.

 Benchmark with my pass generator (passGenny):

Benchmark with passGenny

Considerations

This benchmark is not a reflection of the quality of the library or the skills of the developers, to really be sure a load more tests and benchmarks should be done.

Also, features vary from one library to the other, ones are readable, ones are not. Some use crypto for random, some not.

With that being said,

 Let's make passGenny faster

I decided to give it a go, and try optimizing it, let's see the original code:

class PasswordGenerator {
    static upperCaseChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split('');
    static lowerCaseChars = 'abcdefghijklmnopqrstuvwxyz'.split('');
    static symbolsChars = '<>[]{}=?()&%$#@!¡?¿*_-.:;,'.split('');
    static numbersString = '0123456789'.split('');

    constructor(options = {}) {
        this.options = {
            uppercase: true,
            lowercase: true,
            symbols: false,
            numbers: true,
            readable: false,
            length: 12,
            ...options,
        };
    }

    updateOptions(newOptions = {}) {
        this.options = {
            ...this.options,
            ...newOptions,
        };
    }

    random(min = 0, max = 10) {
        return Math.floor(
            Math.random() * (max - min) + min
        );
    }

    _getCharactersForOptions() {
        const combinedCaracters = [];

        if (this.options.lowercase)
            combinedCaracters.push(...PasswordGenerator.lowerCaseChars);
        if (this.options.uppercase)
            combinedCaracters.push(...PasswordGenerator.upperCaseChars);
        if (this.options.symbols)
            combinedCaracters.push(...PasswordGenerator.symbolsChars);
        if (this.options.numbers)
            combinedCaracters.push(...PasswordGenerator.numbersString);

        return combinedCaracters;
    }

    generate() {
        let combinedCaracters = this._getCharactersForOptions();
        let password = '';

        for (let c = 0; c < this.options.length; c++) {
            password += combinedCaracters[this.random(0, combinedCaracters.length)];
        }

        return password;
    }
}
Enter fullscreen mode Exit fullscreen mode

What this class does is, from a set of options, it will generate passwords. It does this by combining all characters allowed (by the options) into a single array, then we iterate over the length of the password (defined by options), and get a random character from that array.

Simple enough right? Now, I think we could optimize this quite a bit, shall we?

Optimization 1

Okay, the first thing I noticed is, in _getCharactersForOptions, I'm using arrays to hold the valid characters. Using the spread operator to append them into the combinedCaracters array.

This is kinda redundant as we could be using string all the way through. And concatenating a string is way cheaper that combining arrays.

Let's see what we could change.

First we need to change how we store the characters, we don't need to split them:

class PasswordGenerator {
    static upperCaseChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    static lowerCaseChars = 'abcdefghijklmnopqrstuvwxyz';
    static symbolsChars = '<>[]{}=?()&%$#@!¡?¿*_-.:;,';
    static numbersString = '0123456789';
    // ... more code
}
Enter fullscreen mode Exit fullscreen mode

Great, now let's modify the _getCharactersForOptions method:

class PasswordGenerator {
    _getCharactersForOptions() {
        let combinedCaracters = '';

        if (this.options.lowercase)
            combinedCaracters += PasswordGeneratorFast1.lowerCaseChars;
        if (this.options.uppercase)
            combinedCaracters += PasswordGeneratorFast1.upperCaseChars;
        if (this.options.symbols)
            combinedCaracters += PasswordGeneratorFast1.symbolsChars;
        if (this.options.numbers)
            combinedCaracters += PasswordGeneratorFast1.numbersString;

        return combinedCaracters;
    }
}
Enter fullscreen mode Exit fullscreen mode

Notice how we now return a string, instead of an array.

Let's see how this does in the benchmark

Benchmark with passGenny with one level of optimization

Damn, I did not expect that big of a change, it almost doubled.

As you can see, in this particular case, strings perform a lot better than arrays.

BUT WAIT

I think I can optimize this even more, you might have noticed, that the result of _getCharactersForOptions will always be the same with the same options. Meaning we don't need to concatenate the string on each password, we only need to generate them if the options change.

We could approach this in a couple of ways, using memoization (possibly better), creating a proxy around the object or the simple approach I will show you next.

Optimization 2

What I will do is, make options private and force people to change options using updateOptions method. This will allow me to mark if options have changed.

Let's see the complete example, and I will break it down afterwards:

class PasswordGeneratorFast2 {
    static upperCaseChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    static lowerCaseChars = 'abcdefghijklmnopqrstuvwxyz';
    static symbolsChars = '<>[]{}=?()&%$#@!¡?¿*_-.:;,';
    static numbersString = '0123456789';

    constructor(options = {}, randomFn) {
        this._options = {
            uppercase: true,
            lowercase: true,
            symbols: false,
            numbers: true,
            readable: false,
            length: 12,
            ...options,
        };
        this._random = randomFn || mathRandom;
        this._combinedCharacters = '';
        this._optionsChanged = true;
        this._getCharactersForOptions();
    }

    updateOptions(newOptions = {}) {
        this._options = {
            ...this._options,
            ...newOptions,
        };
        this._optionsChanged = true;
    }

    generate() {
        const combinedCaracters = this._getCharactersForOptions();
        const length = combinedCaracters.length;
        let password = '';

        for (let c = 0; c < this._options.length; c++) {
            password = password.concat(combinedCaracters[this._random(0, length)]);
        }

        return password;
    }

    _getCharactersForOptions() {
        // If options have not changed, we can return the previoulsy combined characters
        if (!this._optionsChanged) return this._combinedCharacters;

        let combinedCaracters = '';

        if (this._options.lowercase)
            combinedCaracters += PasswordGeneratorFast1.lowerCaseChars;
        if (this._options.uppercase)
            combinedCaracters += PasswordGeneratorFast1.upperCaseChars;
        if (this._options.symbols)
            combinedCaracters += PasswordGeneratorFast1.symbolsChars;
        if (this._options.numbers)
            combinedCaracters += PasswordGeneratorFast1.numbersString;

        // Update and mark options as not changed
        this._combinedCharacters = combinedCaracters;
        this._optionsChanged = false;

        return this._combinedCharacters;
    }
}
Enter fullscreen mode Exit fullscreen mode
  1. We add _optionsChanged, indicates whether the options have changed since the last time _getCharactersForOptions was called.
  2. We store the last combined character in _combinedCharacters
  3. We modify _getCharactersForOptions, so that if options have not changed, we return the last generated _combinedCharacters
  4. We change password += with password.concat() (in my tests, it concat performed better that +=)

That's it, let's see how that did:

Benchmark with passGenny with two levels of optimization

Impressive if you ask me, we made passGenny more that twice as fast, scoring first by quite a bit of margin. If we phrase it as omgovich did, passGenny is 2,444 times faster than password-generator

What to take from this?

  • Keeping it simple can equate to performant
  • Don't use arrays if you don't need to
  • Check if operations are needed to be performed every time
  • If you need performance, sometimes the smaller things make the biggest difference

PD: I'm no performance expert, so I might be missing some important thing, please let me know If I missed something or I misinterpreted the results.

Have a great day!

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .