CODEWITHSUNDEEP
javaoptimizationstring-concatenation
Dmitrii Demenev
Dmitrii Demenev

Reputation: 845

Compile time optimization of String concatenation

I'm curious, how far the optimization of the following code snippet will go.

To what I know, whenever the capacity of StringBuffer is extended, it costs some CPU work, because its content is required to be reallocated. However, I guess Java compiler optimization can precalculate the required capacity instead of doing multiple reallocations.

The question is: will the following snippet of code be optimized so?

public static String getGetRequestURL(String baseURL, Map<String, String> parameters) {
    StringBuilder stringBuilder = new StringBuilder();
    parameters.forEach(
            (key, value) -> stringBuilder.append(key).append("=").append(value).append("&"));
    return baseURL + "?" + stringBuilder.delete(stringBuilder.length(),1);
}

Upvotes: 0

Views: 1769

Answers (3)

Stephen C
Stephen C

Reputation: 718758

First of all:

  • You can find out what (javac) compile time optimizations occur by looking at the bytecodes using the javap tool.

  • You can find out what JIT compiler optimizations are performed by getting the JVM to dump the native code.

So, if you need to know how your code has been optimized (on a particular platform) for practical reasons, then you should check.

In reality, the optimizations by javac are pretty simple-minded, and do not go to the extent of precalculating buffer sizes. I haven't checked, but I expect that the same is true for the JIT compiler. I doubt that it makes any attempt to preallocate a StringBuilder with an "optimal" size.

Why?

The reasons include the following:

  • An inaccurate precalculation (on average) doesn't help, and may be worse than doing nothing.
  • An accurate precalculation typically involves measuring the (dynamic) lengths of the actual strings to be joined.
  • Implementing the optimization logic would be complicated, and would make the optimizers slower and more effort to maintain.
  • At runtime, the String mensuration introduces overheads. Whether you would come out ahead often enough to make a difference is difficult to determine. (People don't like optimizations that make their code run slower ...)
  • There are better (more efficient) ways to do large scale text assembly than using String concatenation. The programmer (who has more knowledge of the problem domain and application logic) can optimize this better than a compiler. If it matters enough to spend the developer effort on this.

Upvotes: 2

TimGallagher
TimGallagher

Reputation: 101

One optimization is to set the baseURL and ampersand in the stringBuilder instead of using the String concatenate at the end, such as:

public static String getGetRequestURL(String baseURL, Map<String, String> parameters) {
  StringBuilder stringBuilder = new StringBuilder(baseURL);

  stringBuilder.append("&");

  parameters.forEach((key, value) -> stringBuilder.append(key).append("=").append(value).append("&"));

  stringBuilder.setLength(stringBuilder.length() - 1);
  return stringBuilder.toString();
}

If you want a little more speed and since javac or JIT will not optimize based potential string size, you can track that yourself without incurring much overhead, but adding a max size tracker, such as this:

protected static URL_SIZE = 256;

public static String getGetRequestURL(String baseURL, Map<String, String> parameters) {
  StringBuilder stringBuilder = new StringBuilder(URL_SIZE);

  stringBuilder.append(baseURL);
  stringBuilder.append("&");

  parameters.forEach((key, value) -> stringBuilder.append(key).append("=").append(value).append("&"));

  int size = stringBuilder.length();
  if (size > URL_SIZE) {
    URL_SIZE = size;
  }

  stringBuilder.setLength(size - 1);
  return stringBuilder.toString();
}

That said, with some testing of 1 million calls, I found that the different version preformed as (in milliseconds):

  • Your version: total = 1151, average = 230
  • Above version 1: total = 936, average = 187
  • Above version 2: total = 839, average = 167

Upvotes: 1

meriton
meriton

Reputation: 70564

In Java, most optimization is performed by the runtime's just in time compiler, so generally javac optimizations don't matter much.

As a consequence, a Java compiler is not required to optimize string concatenation, though all tend to do so as long as no loops are involved. You can check the extent of such compile time optimizations by using javap (the java decompiler included with the JDK).

So, could javac conceivably optimize this? To determine the length of the string builder, it would have to iterate the map twice. Since java does not feature const references, and the compiler has no special treatment for Map, the compiler can not determine that this rewrite would preserve the meaning of the code. And even if it could, it's not at all clear that the gains would be worth the cost of iterating twice. After all, modern processors can copy 4 to 8 characters in a single cpu instruction. Since memory access is sequential, there won't be any cache missing while growing the buffer. On the other hand, iterating the map a second time will likely cause additional cache misses, because the Map entries (and the strings they reference) can be scattered all over main memory.

In any case, I would not worry about the efficiency of this code. Even if your URL is 1000 characters long, resizing the buffer will take about 0.1 micro seconds. Unless you have evidence that this really is a performance hotspot, your time is probably better spent elsewhere.

Upvotes: 4

Related Questions