How we improved APM Java startup by encoding a prefix trie as a JVM constant (opens in new tab)

Startup performance is critical for users, developers, and cloud costs, but Java APM instrumentation must balance observability against the overhead of transforming classes. Datadog reduced class-matching overhead by 30% over four years by optimizing the first filtering stage: matching class-name prefixes. Its main innovation was encoding a prefix trie as a single JVM string constant, avoiding the startup cost of constructing a conventional trie.

Java Instrumentation and Class Matching

• Java APM uses the Java Instrumentation API to intercept and transform classes as they load.
• Instrumentation adds method advice that records method execution and propagates tracing context.
• Instrumenting every method would be too expensive, so APM first identifies valuable classes.
• Applications may load tens or hundreds of thousands of classes, making efficient filtering important.
• Class-name and package-prefix checks are cheaper than structural or hierarchy-based checks because they avoid parsing class files.
• Datadog therefore begins with a curated ignore list of class and package prefixes.

Startup Constraints in premain

• Agents register transformers in the JVM’s premain phase, before the application’s main method.
• At this point:
  • Few classes have been loaded.
  • The JIT compiler is cold or unavailable, especially on Java 8.
  • Code runs interpreted and unoptimized.
  • Loading or calling certain JDK classes can have irreversible side effects.
• For example, touching java.util.logging initializes LogManager, potentially preventing an application from configuring its own logging manager later.
• These constraints make ordinary data loading, parsing, and object construction undesirable during startup.

Replacing a Hand-Written Matcher with a Trie

• Datadog’s earlier matcher used a complex nested code structure to represent prefixes.
• Although flexible, it was difficult to maintain and required special optimizations for Java 8 startup.
• A trie was a natural replacement because it shares common characters among prefixes and supports efficient lookup.
• A conventional trie would require:
  • Locating and reading a resource.
  • Parsing its contents.
  • Constructing trie nodes.
  • Loading additional code or dependencies.
• Those operations would impose unacceptable costs during premain.

Encoding the Trie as a JVM Constant

• Datadog created ClassNameTrie, which stores the entire prefix trie in a Java string constant.
• The JVM loads the encoded data with a single ldc bytecode instruction.
• This approach avoids resource I/O and runtime trie construction.
• Embedding the data in the class also makes it resilient to repackaging.
• The compact representation improves cache locality and reduces startup work.

Compact Node Representation

• Java strings contain 16-bit char values, allowing each character to encode one of 65,536 possible values.
• Each trie node stores:
  • A character indicating the number of branches.
  • Sorted branch characters, enabling binary search.
  • One value character per branch.
• Value characters encode different outcomes:
  • Leaf: returns a definitive result and ends the search.
  • Bud: records a possible result but permits further matching.
  • Inline segment length: indicates that additional prefix characters are stored directly.
• Buds and leaves can include a glob bit, allowing a match to apply even when extra characters remain in the class name.
• The encoding reserves the remaining value range for match results, with a maximum stored value of 8,191.

The broader lesson is that startup-sensitive JVM code may benefit from moving computation into class-loading time and representing lookup structures in compact constants. For Java agents, precomputed, dependency-free data structures can deliver trie-like performance without the initialization and JIT costs of building them at runtime.