Bad CucumberExpression creation performance about cucumber-expressions

[mpkorstanje]

I would welcome a pull request for this, but the cache(s) should not be static.

Consider extracting the code from the CucumberExpression constructor to a CucumberExpressionFactory. This factory could then be instantiated in the ExpressionFactory with a cache instance. This means that once the ExpressionFactory goes out of scope, and no more expressions are created, the cache will be garbage collected.

Note that the RegularExpression also create a TreeRegex. The same optimization may be useful there.

Please also update the documentation for the TreeRegex and GroupBuilder to note that they should be thread-safe.

[mpkorstanje]

Ah. Please disregard my previous comment.

The ExpressionFactory is instantiated with a ParameterTypeRegistry which contains scenario specific state. While we could share the cache inside a Runner, I need to think about this. At some point it becomes easier to remove cucumber-java8 and then refactor cucumber-core instead.

[jkronegg]

I don't see the issue with ParameterTypeRegistry : the proposed solution only cache things that are "really constant" (i.e. that are not impacted by cucumber-java8).

I don't think the static cache will cause a real memory usage issue because on my project with ~150 stepdefs and ~400 test scenarios, the TreeRegex cache has only 117 elements and the escapedTexts cache has only 205 elements. However, if you want to replace the static caching, the ExpressionFactory could create a Runner which holds the TreeRegex cache. This Runner would be passed to RegularExpression and CucumberExpression constructors (small API change), with the advantage to have only one TreeRegex cache instead of two (one in RegularExpression and CucumberExpression). The Runner could hold the escapedTexts as well.

Caching the TreeRegex in RegularExpression makes the constructor 4 times faster (JMH benchmark: uncached=7'000 ops/s, cached=28'000 ops/s). On my project with 150 stepdefs and 400 test scenarios, this makes no impact because the RegularExpression.<init> was contributing to only 0.34% of the total CPU time. But this may be different with other projects.

Good point on thread-safety. TreeRegex looks thread-safe. GroupBuilder.add() method is not thread-safe because it calls ArrayList.add(), but I don't think this is an issue as GroupBuilder.add() is only called when the GroupBuilder is constructed in TreeRegex.createGroupBuilder(). Maybe the GroupBuilder could be modified to remove the add() method with a Builder pattern in order to ensure thread-safety (TreeRegex.createGroupBuilder() could be moved to this Builder for a better separation of concerns).

[mpkorstanje]

I don't see the issue with ParameterTypeRegistry : the proposed solution only cache things that are "really constant" (i.e. that are not impacted by cucumber-java8).

I was hoping to keep a non-static cache in the ExpressionFactory and then retain a reference to the factory in Cucumber-JVM. But this isn't feasible right now. While I'm not too worried about leaking memory this way, not having statics anywhere makes it much easier to reason about (concurrent) code.

And while this proposal does make steps towards cucumber/cucumber-jvm#2035 it would become mostly obsolete the moment we drop cucumber-java8 and build every cucumber expression exactly once. So I would rather spend time working towards improvement that don't become obsolete in the future.

Would it be possible to create an optimization for escapeRegex that doesn't depend on caching?

[jkronegg]

I'll try to optimize escapeRegex without caching (I'm thinking about a custom String.replace(String,String) method, but this would require more effort and the code would be more complex than a simple regexp).

[jkronegg]

I've refactored the escapeRegex method with two different methods inspired by String.replace(String,String):

Method	Description	ops/s
escapeRegex0	The original method CucumberExpression.escapeRegex	1'200'000
escapeRegex1	Escaping character by character	8'300'000
escapeRegex2	Escaping characters by blocs	6'300'000

The escapeRegex1 is 7 times faster than the original version and is implemented as follows:

/**
 * List of characters to be escaped.
 * The last char is '}' with index 125, so we need only 126 characters.
 */
public static final boolean[] CHAR_TO_ESCAPE = new boolean[126];
static {
    CHAR_TO_ESCAPE['^'] = true;
    CHAR_TO_ESCAPE['$'] = true;
    CHAR_TO_ESCAPE['['] = true;
    CHAR_TO_ESCAPE[']'] = true;
    CHAR_TO_ESCAPE['('] = true;
    CHAR_TO_ESCAPE[')'] = true;
    CHAR_TO_ESCAPE['{'] = true;
    CHAR_TO_ESCAPE['}'] = true;
    CHAR_TO_ESCAPE['.'] = true;
    CHAR_TO_ESCAPE['|'] = true;
    CHAR_TO_ESCAPE['?'] = true;
    CHAR_TO_ESCAPE['*'] = true;
    CHAR_TO_ESCAPE['+'] = true;
    CHAR_TO_ESCAPE['\\'] = true;
}

public static String escapeRegex1(String text) {
    int length = text.length();
    StringBuilder sb = new StringBuilder(length);
    for (int i = 0; i < length; i++) {
        char currentChar = text.charAt(i);
        if (currentChar < CHAR_TO_ESCAPE.length && CHAR_TO_ESCAPE[currentChar]) {
            sb.append('\\');
        }
        sb.append(currentChar);
    }
    return sb.toString();
}

The code is pretty simple and elegant.

The escapeRegex1 is implemented as follows:

// CHAR_TO_ESCAPE ommited for brivety (same as above)

public static String escapeRegex2(String text) {
    int length = text.length();
    StringBuilder sb = new StringBuilder(length);
    int blocStart=0;
    for (int i = 0; i < length; i++) {
        char currentChar = text.charAt(i);
        if (currentChar < CHAR_TO_ESCAPE.length && CHAR_TO_ESCAPE[currentChar]) {
            if (i > blocStart) {
                // flush previous block
                sb.append(text, blocStart, i);
            }
            sb.append('\\');
            sb.append(currentChar);
            blocStart=i+1;
        }
    }
    if (length > blocStart) {
        // flush remaining characters
        sb.append(text, blocStart, length);
    }
    return sb.toString();
}

The code is a bit more complex and slower than escapeRegex1.

The full CucumberExpression benchmark is now (the ops/s cannot be compared with the ones from the original post because this is not on the same machine):

Benchmark	cached calls to escapeRegex	cached TreeRegex creation	ops/s
CucumberExpressionBenchmark.createExpression0	no	no	97
CucumberExpressionBenchmark.createExpression1	yes	no	101
CucumberExpressionBenchmark.createExpression2	no	yes	113
CucumberExpressionBenchmark.createExpression3	yes	yes	119
CucumberExpressionBenchmark.createExpression4	no (optimized escapeRegex1)	no	104

So the escapeRegex1 lead to a total 7% improvement over the curent implementation, in the same range as the variant with cached calls to escapeRegex. This is not significant right now (as we escape the same regexp several times), but may become significant the day we get rid of cucumber-java8.

Should I do a PR with only this optimization with escapeRegex1 (i.e. without caching the TreeRegex and without caching calls to escapeRegex) ?