Even worse, with partial evaluation or escape analysis it might still be non allocating to use a substring call today. So the thing about advanced compilers in

Even worse, with partial evaluation or escape analysis it might still be non allocating to use a substring call today. So the thing about advanced compilers in the java world is that they use defined behaviour(results) to do optimisations. And the best optimisations are about not doing work you can avoid. i.e. if you can avoid doing an allocation at all because the (sub)string you just created is only used locally, the object might not be allocated at all (heap|stack) but just registers are reassigned with temporary values needed to calculate the function. So its already common to have O(n) semantics turn into O(1) or even better O(0) ;). In the java world results are specced, not how you need to get them. (Exceptions to this rule exist).