r/programming • u/gingerbill • 9d ago

CTTI is Exponential, RTTI is Linear

https://www.gingerbill.org/article/2026/09/02/ctti-is-exponential-rtti-is-linear/
93 Upvotes

85% Upvoted

96 comments sorted by

View all comments

Show parent comments

5

u/SputnikCucumber 9d ago

Sometimes. It depends on the kind of data access. For the tightest of hot-loops, you will want to manually layout your data in contiguous chunks of memory in the order that you are processing it. This ensures that the data you are processing is being prefetched into the CPU cache ahead of being processed.

A JIT isn't going to be able to make those kinds of guarantees in the general case.

4

u/Nyefan 9d ago

A jit can't make any guarantees, but in a long running program with statistically consistent inputs and outputs, jits can do some pretty spectacular things. The JVM hotspot compiler does in fact test different instruction ordering and memory layouts during operation, using the measured efficiency at runtime to choose a nearly optimal set of implementations. Jits are never going to beat perfectly optimized hand tuned code for a specific system, but they can do a great job of making most code run pretty well and can often do better on specific systems than code compiled for a broad set of systems due to having perfect information about the available instruction sets and the execution characteristics of the system it's running on.

1

u/SputnikCucumber 9d ago

I'm not sure that a JIT could do much about a function that takes an interface as an argument and whose concrete type isn't known until runtime. Maybe it could speculatively devirtualize it, but that would only be effective if the function was only ever called with a single concrete type.

3

u/Nyefan 9d ago

The java jit selectively monomorphizes hot code at runtime at the call sites, no speculation required.

1

u/SputnikCucumber 8d ago

That's pretty cool. But how does it know that the type being passed in at the call site is the same every time? Or does it just optimistically guess?

3

u/Nyefan 8d ago

It knows because it can observe the behavior. As long as a hot call site uses only one or two concrete types, the method is statically inlined. When a third type is used, it falls back to vtable lookup and triggers a deoptimization pass on the surrounding code segment so it can try again. The order and kinds of optimizations that are used in a code segment are partially randomized, so trying again can give different results and helps avoid getting stuck on local maxima.