Datadog Cut APM Java Startup Time by 24% With a Trie Trick
Quick Reads
- Datadog’s APM team reduced Java startup overhead by over 24% in four years.
- The key fix: encoding a prefix trie as a single JVM string constant.
- On Java 8, the new approach is nearly 5x faster than the old code-based matcher.
- The solution now powers Live Debugger and CI Visibility features as well.
Datadog’s APM engineering team has cut Java startup time significantly by encoding a prefix trie directly as a JVM string constant, a subtle but high-impact fix that rewrites how the agent decides which classes to instrument.
Datadog Application Performance Monitoring (APM) helps engineers understand performance throughout an application, including during startup. For Java, using APM involves attaching an agent to the JVM that automatically transforms classes to add observability, an approach known as instrumentation. Instrument too few classes and you miss key details. Instrument too many and startup suffers.
That trade-off sits at the heart of a four-year optimization effort. Over the past four years, the Datadog APM team reduced class-matching overhead by 30%. Optimizing class matching during startup is particularly challenging because the just-in-time (JIT) compiler has not yet optimized the matcher code, and profilers have not captured enough samples to identify hot spots.
The first step in class matching is always the fastest one: checking the class name. Class names provide a cheap way to prune classes and packages compared to structural and class hierarchy matches, which need to parse the class file and may require parsing additional class files to inspect related types. So before anything else, APM checks each class name against a curated ignore list of prefixes.
The challenge, however, is that this happens very early. When you attach an agent on the command line, the JVM calls the agent’s premain method before it calls the application’s main method. At this point, hardly any classes have been loaded and the JIT compiler is cold. That cold environment makes every line of code expensive. Worse, Java 8 adds a further constraint: It does not start the JIT compiler until after premain, so code there is interpreted and unoptimized.
The team needed a data structure that was fast to query without being expensive to build. A classic trie was the obvious candidate. But a conventional trie requires looking up a resource, reading a file, parsing content, and constructing nodes, all inside the constrained premain phase. That ruled it out.
The result was ClassNameTrie, a prefix trie encoded as a JVM constant. The JVM loads the string constant as part of class loading, making the encoded trie accessible through a single bytecode instruction (ldc). There is no need to look up resources or perform I/O. Furthermore, because the string constant is embedded directly in the class that uses it, it survives repackaging. The compact encoding also improves cache locality.
The encoding works by storing the entire trie structure inside a single Java string. Each char in the string can hold 2 bytes, giving 65,536 unique values. How those values are interpreted is entirely up to the developer, which means both control information and content can be stored in the same string. Each node in the trie encodes the number of branches, the branch characters sorted for binary search, a value for each branch, and jump offsets to child nodes.
Branch values carry meaning through their top bits. Values have three possible meanings: a leaf, which provides a definitive result and stops the search; a bud, which provides a potential result but allows the search to continue; and the length of the inline segment string for that branch. This compact layout means matching a class name requires almost no memory allocation and very few instructions.
The results are striking. The benchmark results confirm that ClassNameTrie is much faster than the old code-based approach, especially on Java 8, where it is nearly 5x faster. It is even faster than a classic radix trie during cold start, due to its compact representation and cache locality.
In practice, the gains stack up quickly. In a real-world Spring Boot application, ignoring uninteresting classes by name reduced instrumented startup time by 20%. Switching from the code-based approach to ClassNameTrie saved a further 1% while making the ignore list much easier to maintain and grow.
The team then took things a step further. Realizing they now had an efficient way to map class names to integers, they built a known types index that maps class names directly to numbered instrumentations. This shortcut saved another 3%, bringing total savings to more than 24% compared to not filtering by class name.
Datadog APM Java startup performance gains have not stayed confined to one feature. ClassNameTrie is now used in other APM features, including Live Debugger and Continuous Integration (CI) Visibility, to filter and classify class names.
All code discussed is available from Datadog’s open source instrumentation helper library. You can also try the interactive ClassNameTrie demo to see how the encoding behaves with your own data.
For more on Datadog’s Application Performance Monitoring and the Java Instrumentation API used in this work, see the official documentation. Engineers interested in working on problems like this can explore open engineering roles at Datadog.
