Comparison of substring operation performance between .NET and Java

Question

Taking substrings of a string is a very common string manipulation operation, but I heard that there might be considerable differences in performance/implementation between the Java and .NET platform. Specifically I heard that in Java, java.lang.String offers constant time operation for substring, but in .NET, System.String offers linear performance Substring.

Are these really the case? Can this be confirmed in the documentation/source code, etc? Is this implementation specific, or specified by the language and/or platform? What are the pros and cons of each approach? What should a person migrating from one platform to another look for to avoid falling into any performance pitfalls?

Answer 1

In .NET, Substring is O(n) rather than the O(1) of Java. This is because in .NET, the String object contains all the actual character data itself¹ - so taking a substring involves copying all the data within the new substring. In Java, substring can just create a new object referring to the original char array, with a different starting index and length.

There are pros and cons of each approach:

• .NET's approach has better cache coherency, creates fewer objects², and avoids the situation where one small substring prevents a very large char[] being garbage collected. I believe in some cases it can make interop very easy too, internally.
• Java's approach makes taking a substring very efficient, and probably some other operations too

There's a little more detail in my strings article.

As for the general question of avoiding performance pitfalls, I think I should have a canned answer ready to cut and paste: make sure your architecture is efficient, and implement it in the most readable way you can. Measure the performance, and optimise where you find bottlenecks.

---

¹ Incidentally, this makes string very special - it's the only non-array type whose memory footprint varies by instance within the same CLR.

² For small strings, this is a big win. It's bad enough that there's all the overhead of one object, but when there's an extra array involved as well, a single-character string could take around 36 bytes in Java. (That's a "finger-in-the-air" number - I can't remember the exact object overheads. It will also depend on the VM you're using.)

Answer 2

Using reflector this is what you get from Substring(Int32, Int32)

[SecuritySafeCritical, TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
public string Substring(int startIndex, int length)
{
    return this.InternalSubStringWithChecks(startIndex, length, false);
}

if you keep on going inside the last call is to an

internal static unsafe void wstrcpy(char* dmem, char* smem, int charCount)

that copies the chars using pointers. The complete code actually looks big but you won't see how fast or slow it is until you run it and benchmark it.