How we improved APM Java startup by encoding a prefix trie as a JVM constant

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.