Many immutable algorithms replace arrays with trees. Trees are pointer-heavy, and pointers are less cache-friendly than arrays.

Memory access is often over 100x the cost of an L1 cache hit. It doesn't take too many of those to make a big difference if you're CPU bound.

My comments are general, I'm sure Clojure has access to arrays where necessary for interop at least.

Again, true, but the big problem I'm facing isn't raw performance so much as it's guaranteed latency.

But the constant factor is Z, a very large number. A number so large it has a color and name. It pays taxes, has lunch and sees movies on the weekend.

Not true in the context of dynamic languages. The constant factor for persistent maps in that context is quite small.