I made i18next up to 5x faster with two includes() checks

Two includes() checks made i18next up to 5x faster on long text. This post shows that fix and two more.

A regular expression is a good tool, but it is not free. Each call scans the input, and a bad pattern can scan the same characters many times.

Three of my performance PRs had the same idea: do a cheap check before the expensive regex work. Maintainers merged all three. This post shows each change, the numbers, and the rule you can use in your own code.

1. i18next: check the prefix before you run the regex

i18next (35M npm downloads a week) runs its interpolation regex and its nesting regex on every translated text. The regexes look for {{name}} and $t(key).

Most texts have neither. "Save", "Cancel" and "Welcome back" contain no {{ and no $t(. But i18next ran both regexes on them anyway, and each scan read the full text to find nothing.

Every match of these regexes starts with a fixed prefix. So a text without the prefix cannot match. A plain includes() call answers that question, and it is much cheaper than a regex scan:

// Interpolator.interpolate()
// no placeholder at all: neither regexp can match
if (isString(str) && !str.includes(this.prefixText)) return str;

// Interpolator.nest()
// nothing to nest (the common case)
if (isString(str) && !str.includes(this.nestingPrefixText)) return str;

prefixText is {{ by default, and nestingPrefixText is $t(. Both follow the user's options, so a custom prefix such as %{ also works.

The long text gets the biggest gain, because the regex scan was most of the work. The output does not change. Old and new code gave the same results on 1,000,000 random resources, options and calls.

PR: i18next #2469.

2. regexp2: check ASCII before the Unicode tables

regexp2 is a .NET-style regex engine for Go. The \w and \b tokens call IsWordChar for each character. That function looked up 4 Unicode category tables by name, on every call:

// before
return unicode.In(r,
    unicode.Categories["L"], unicode.Categories["Mn"],
    unicode.Categories["Nd"], unicode.Categories["Pc"]) || r == '\u200D' || r == '\u200C'

Two things were slow. First, unicode.Categories["L"] is a map lookup, 4 times per character. Second, most text in logs, code and config files is ASCII. In ASCII, these 4 categories are only letters, digits and _. The change checks ASCII first, and uses the table variables directly for the other runes:

// after
if r < utf8.RuneSelf {
    // In ASCII, L, Mn, Nd and Pc are these runes only.
    return 'a' <= r && r <= 'z' || 'A' <= r && r <= 'Z' || '0' <= r && r <= '9' || r == '_'
}
return unicode.In(r, unicode.L, unicode.Mn, unicode.Nd, unicode.Pc) || r == '\u200D' || r == '\u200C'

Non-ASCII text also got 33 to 37% faster in my test, because the map lookups are gone for all runes. I checked the result for every rune.

PR: regexp2 #142.

3. colord: let the common case match first

colord (25M npm downloads a week) parses CSS colors such as rgba(255, 128, 0, 0.5). Each number in its regexes used this pattern:

/(?:\d*\.\d+|\d+)/   // before

Most numbers in CSS colors are integers, such as 255. For an integer, the first branch reads all the digits, finds no ., and gives the digits back one by one. Then the second branch reads the same digits again.

The new pattern accepts the same strings (.5, 5, 5.5), but an integer matches in one pass:

/(?:\d+(?:\.\d+)?|\.\d+)/   // after

The gain is smaller here, but it costs nothing. colord also has a test that rejects 1 MB malformed strings in linear time. The new pattern passes it, and it is about 2x faster on some of those cases.

PR: colord #173.

The rule

All three changes do the same thing: they find the cheapest question that settles the common case, and ask it first.

• A fixed prefix? Check it with includes() or strings.Contains() before you run the regex.
• Mostly ASCII input? Handle ASCII with a range check before you go to the Unicode tables.
• Alternatives in a pattern? Put the branch that matches the common input first, and make sure it does not backtrack.

When does this not help? If almost every input contains the prefix, the extra check is only extra work. Measure with your real inputs before you add it.

The full benchmarks are in each PR. More PRs: g4lb.