Improve feature loading performance by changing UUID generator

[jkronegg]

👓 What did you see?

The Cucumber Java event bus uses UUID as event identifiers. These UUIDs are generated using the JDK java.util.UUID.randomUUID().
This kind of generators known to be slow (e.g. https://stackoverflow.com/questions/14532976/performance-of-random-uuid-generation-with-java-7-or-java-6). On my project (~450 test scenarios, ~50 rules) this UUID generator takes about 25% of the feature file loading time on the IntelliJ profiler flame graph (~2% of the total CPU time).

This generator is used for each each rule and each scenario step line : that corresponds to ~100'000 calls for my project.

✅ What did you expect to see?

Using a faster UUID generator would improve the feature file loading performance. For example, https://github.com/cowtowncoder/java-uuid-generator provides a time sequence UUID generator which is much faster.

From what I've seen, the solution could be very simple as the EventBus is instanciated in io.cucumber.core.runtime.Runtime.Builder with UUID::randomUUID : we need to change this generator to get a good performance improvement. Note that other calls to UUID.randomUUID() are also made elsewhere in the project but I didn't saw big performance impact.

📦 Which tool/library version are you using?

Cucumber Java 7.11.1

🔬 How could we reproduce it?

Steps to reproduce the behavior:

1. Run IntelliJ profiler on a project with about 50 rules with cucumber-java 7.11.1.
2. Look for the loadFeatures block on the flame graph: on the top is the java.util.UUID.randomUUID() call
   uuid_flame_graph.zip

📚 Any additional context?

N/A

[jkronegg]

The following librairies have been selected as alternatives to generate the UUIDs:

Library	Licence	Benchmarked by creator	Latest commit
JDK java.util.UUID.randomUUID() (OpenJDK 17)	?	?	may 2022
https://github.com/cowtowncoder/java-uuid-generator (JUG)	Apache License 2.0.	yes	jan 2023
https://github.com/f4b6a3/uuid-creator	MIT License	yes	oct 2022

As Cucumber has a MIT License project, all three alternatives are allowed from the license point of view.

The following libraries have not been selected as potential replacements:

• The Apache commons-id library was not selected because it looks unmaintened (latest build in 2006) and has no official release (it's still in sandbox mode).
• The eaio-uuid library was not selected because it looks unmaintened (latest commit in 2018) and is not documented. Moreover, it generates it's own com.eaoi.uuid.UUID class, not the JVM java.util.UUID, which would make integration harder.

Regarding thread-safety, all selected alternatives are thread-safe:

• uuid-creator is benchmarked with multiple threads, so it is assumed to be thread-safe
• JUG is described as thread-safe (I didn't verify)

I benchmarked the UUID librairies with some parameters that are known to provide better performance.

I also tested the generators in realworld conditions on a project with ~450 test scenarios and ~50 rules, I passes a Supplier<UUID> instance which measures the time passed to generate the UUIDs:

public class UuidSuplier implements Supplier<UUID> {
  static AtomicLong time = new AtomicLong(0);

    @Override
    public UUID get() {
        long t0 = System.nanoTime();
        UUID uuid = ... // generate the UUID
        long t1 = System.nanoTime();
        System.out.println(time.addAndGet(t1-t0)); // displays total time in ns
        return uuid;
    }
}

These are the results:

Library	generator type	JMH benchmark Millions ops/s (higher is better)	real-world performance; time to generate all UUIDs [ms] (lower is better)
JUG	time-based epoch (Type 7)	1.1	268
JDK	random (Type 4)	1.1	189
uuidCreator	time-based (Type 1)	10.0	99
uuidCreator	time-based epoch (Type 7/2)	34.5	77
JUG	time-based (Type 1)	too fast to be benchmarked	12
new UUID(Thread.currentThread().getId(), atomicLong.incrementAndGet())	thread-safe counter-based	133	2.5

To summarise, by using the JUG library with time-based Type 1 UUID generator, the gain is about 177 ms on a real project (about 5% of the Cucumber test scenario execution on the project).

@mpkorstanje, @mattwynne : are you ok with the principle of replacing java.util.UUID.randomUUID() by a JUG time-based UUID ? If yes, I'll propose a PR.

[mpkorstanje]

Unfortunately I haven't had time to consider this yet.

[mpkorstanje]

Unfortunately I've not been able to give this the consideration this is due just yet. Never the less this are my quick consideration:

• I believe that Single step expression is compiled into regex more than once (thus it makes test execution slower) #2035 is a major contributing factor this this problem. The resolution of this depends on the deprecation of cucumber-java8 and it's replacement with cucumber-lambda (Consider cucumber-java-lambda as a replacement for cucumber-java8 #2279). This is unfortunately a long way away.
• I would like to avoid adding a dependency to Cucumber.
• I would like to retain the ability to use random UUIDs. The messages from one process should not collide with those from another process. This becomes much more likely when using a time based UUID.
• A brief glance at the difference UUID generators shows a cacophony of possible options and properties for the different generators. I do not believe we can pick the correct one for all use cases.

Based on this I reckon the best course of action would be to

1. Retain the random UUID generator as the default
2. Refactor the default UUID generator into a implementation that is loaded via SPI.
3. Provide a property to select other UUID generators via SPI (note: this should work with cucumber.properties, junit-platform.properties, @CucumberOption, environment variables and the CLI).

For reference look at the current ObjectFactoryServiceLoader implementation.

If you are willing to write a pull request for this, I would be happy to accept it.

[jkronegg]

I think a time-based UUID will work (there is no collision risk when using multithreading in the same JVM because the generators are have a time-based component and a counter component).

But I agree on the other arguments:

• On my project, the parser generates about 5000 UUIDs when the rest of test framework generates about 90'000 UUIDs: thus, it's probably true that Single step expression is compiled into regex more than once (thus it makes test execution slower) #2035 is a major contributing factor (although I didn't verify).
• It's better to avoid adding dependencies.
• There are lot of configuration options in UUID generators.

Configuring the UUID generator using SPI is a good solution to delegate the choice to the user. But as the user will need to add specific configuration, it's not guaranteed that many people will use this feature.

@mpkorstanje do you think it is worth doing it now, or is it better to invest development time on #2035 / #2279 ?

[mpkorstanje]

I think a time-based UUID will work (there is no collision risk when using multithreading in the same JVM because the generators are have a time-based component and a counter component).

Reports may be generated on different JVMs at the same time. A typical example would be one suite that tests against Firefox and another against Safari. The exact browser is configured through a property. These are then executed concurrently on different Gitlab runners.

There are of course solutions for this as well but the advantage of the random UUID is that they'll work in all situations.

But as the user will need to add specific configuration, it's not guaranteed that many people will use this feature.

That is rather unfortunate indeed. Though technically the cost is rather low. So in my estimation it evens out.

@mpkorstanje do you think it is worth doing it now, or is it better to invest development time on #2035 / #2279 ?

As a maintainer I would generally favour the long term approach. But the 5% improvement you mentioned is something that can be achieved in the short term and mostly without my input. So I think it mostly depends on your willingness and interests.

[jkronegg]

Ok, I'll do it.