Slashing Java startup times by encoding prefix tries as JVM string constants

The Problem: High-Speed Filtering in a Hostile Environment

Datadog recently figured out how to filter over one hundred thousand Java class names in milliseconds, during the absolute slowest, most constrained part of the JVM lifecycle. Their solution was to abandon standard code execution almost entirely. Instead, they crammed an entire prefix-trie data structure into a single Java string constant. They repurposed raw 16-bit characters to store branch logic, values, and jump offsets. They proved that when execution speed falls off a cliff, raw data is faster than code.

Picture this. You are writing a Java agent that runs before the application even starts. You have to attach this agent on the command line. The JVM calls your agent’s premain method before it ever touches the application’s main method. Your job is to decide which classes to instrument for observability and which to ignore. A typical enterprise application defines tens of thousands of classes. A large one might load over a hundred thousand. You have to filter them fast, because every millisecond you spend matching strings is a millisecond added to the application’s boot time.

But here is the trap. In the premain phase, you are operating in the dark. The Just-In-Time compiler is completely cold. Code runs interpreted and slow. You cannot trigger outside class loads. You cannot load external dependencies that might conflict with the app later. If you try to use standard java utility logging, you might initialize a singleton that the application needs to customize later, breaking the app before it even boots. You are boxed into an incredibly hostile execution environment.

The Solution: A Trie Encoded in a String

You might wonder why you could not just use a standard data structure or an existing Trie library. A trie is perfect for this. It distributes elements of a key across nodes, so a search for 'ball' and 'bat' shares the 'b' and 'a' nodes. But building a standard tree structure at runtime means executing code. You have to look up a resource, read a file, parse the content, and allocate memory for thousands of individual node objects on the heap. In the premain phase, execution and allocation are exactly what you are penalized for.

Hand-rolled starts-with checks are unmaintainable at scale. A standard library requires dependencies and runtime construction. You need the lookup performance of a trie without the startup cost of actually building one.

This is where the string constant hack comes in. A Java string constant is loaded via a single bytecode instruction: the ldc instruction, which stands for load constant. That bypasses I/O completely. It bypasses external resource lookups. The JVM simply hands you the string directly from the constant pool during class loading.

How the String Becomes a Data Structure

A string in Java is a sequence of 16-bit characters. That gives you 65,536 unique values per character. The JVM does not care how you interpret those bits. You can store structural control information right next to text content. Datadog mapped out a node layout completely flat inside the string.

The first character of a node tells you the number of branches it has. It is immediately followed by the branch characters themselves. These are sorted alphabetically, so the matching algorithm can run a quick binary search across them.

Next come the branch values. They took the 16 bits of a value character and chopped them up. The three highest-order bits are repurposed as bit flags. They tell the parser exactly what kind of node it is looking at. If the top bit is set, the node is a leaf, meaning you have a definitive match and the search stops. If the second flag is set, it is a bud, meaning you have a potential result but you are allowed to keep reading characters. The remaining 13 bits store the actual result value. This caps the maximum value a branch can store at 8,191, which is more than enough for indexing known instrumentation types.

Finally, the node needs to tell the parser where to go next. At the end of the node, they store jump offsets. These tell the matcher how many characters to skip ahead in the string to find the next child node or an inline segment. They store this offset in a single character, calculated relative to the end of the current node.

But what happens if the tree is huge and a jump requires skipping more than 61,439 characters? That exceeds the capacity of the character bits they allocated. So, they reserved a long-jump marker. If that bit is flipped, the character is no longer an offset. It becomes an index into a separate, external long-jump table where the real offset is stored.

Execution as Pointer Arithmetic

The matching process becomes a tight state machine doing pointer arithmetic on a flat array of text. You read the key character. You read the branch count. You binary search the branches. You check the bit flags. You apply the jump offset. You move your pointer down the string. It is a fully functional prefix trie embedded directly into the bytecode. No parsing. No object allocation overhead. Just bitwise operations.

Performance Gains vs. High Maintenance

The execution here is mechanically brilliant. But we need to interrogate the metrics before we rewrite our own codebases.

Datadog published performance charts showing this string trie is nearly five times faster than their old code-based approach. If you look closely at their data, that massive five-times multiplier applies specifically to Java 8. Java 8 is uniquely punishing because it completely defers JIT compilation during premain. Everything runs interpreted. On Java 17 and Java 25, the JVM is significantly smarter about early execution. The gap between this string constant hack and a standard radix trie shrinks drastically on modern runtimes.

They also note that switching to this string-encoded trie saved an additional one percent in instrumented startup time. At an infrastructure scale, one percent is a massive cloud compute savings. But put this in context. If your enterprise application takes ten seconds to boot, one percent is a hundred milliseconds.

What is the cost of chasing that hundred milliseconds? High cognitive load and severe maintenance friction. To use a structure like this, you have to integrate a custom generator into your build pipeline. You have to compile a human-readable list of ignore rules into this heavily bit-shifted string format before you deploy. You also run into hard compiler limits. The JVM has a strict limit of 65,535 bytes for a string literal in the constant pool. If your ignore list grows too large, a single load-constant string instruction will simply fail to compile. And because string literals are interned by the JVM, loading a massive custom-encoded text blob into the constant pool of the agent class means it lives in memory permanently.

Then there is debuggability. If you get a false-positive match in production, you are not stepping through a clean tree of Java objects in your debugger. You are trying to reverse-engineer bitwise operations and jump offsets on raw characters.

The Takeaway: When to Go to Extremes

So the question is whether this extreme level of JVM micro-optimization is relevant to a standard product engineering team, or if it strictly belongs to infrastructure vendors. If you are writing standard business logic, skip this entirely. A standard String.startsWith() check or a normal Radix Trie is vastly easier to maintain. The JIT compiler will aggressively optimize them into highly efficient machine code once the JVM warms up. Your application lifecycle is long enough that optimizing a fraction of a second at startup simply does not matter.

But if you are a platform engineer writing custom java-agents, or an APM vendor where millisecond-level startup overhead dictates whether a client adopts your tool, this is your playbook. The constraints of the premain phase are absolute.

What this teaches us extends beyond Java. When the runtime environment heavily penalizes computation, the winning move is to shift the work entirely. Do the computation at build time. Encode the result as pure, flat data. Skip the initialization phase completely. Datadog bypassed a brutal performance bottleneck not by writing faster code, but by realizing that sometimes the fastest code is no code at all.

This is TAKEYOURPILLS.TECH. Go ship something.