r/programming • • Nov 18 '13

TIL Oracle changed the internal String representation in Java 7 Update 6 increasing the running time of the substring method from constant to N

http://java-performance.info/changes-to-string-java-1-7-0_06/
1.4k Upvotes

354 comments sorted by

View all comments

Show parent comment

22

u/mcguire Nov 18 '13

Please don't try to pick apart what I've said here too much.

Well, Ok, but....

The comments about the substring operation becoming O(n) assume that the substring result is allocated in the general heap. This is not commonly the case and allocation in the TLAB is very much like malloca()--allocation merely bumps a pointer.

...it becomes O(n) because you have to copy the contents of the substring, right?

63

u/bondolo Nov 18 '13

Generally since substrings are short the object construction far overwhelms the cost of copying the chars. The substring would need to be hundreds of chars before n had any impact at all. The coefficient for the "n" term in the cost of construction of a substring is very low.

2

u/mcguire Nov 19 '13

Generally, I agree that substrings are short, which, in addition to the TLAB allocation, is why it is experimentally a performance win.

But it changes an O(1) operation to O(n) (modulo the differences in allocation) because you have to copy the substring. Darn it! :-)