Compile time optimization of String concatenation

Question

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);
}

How would it preallocate? What does the compiler know about the size of the keys and values in parameters, at runtime? — Sotirios Delimanolis
– Sotirios Delimanolis, Commented Feb 10, 2018 at 2:17
StringBuilder is backed by a char array directly. If instead of StringBuilder stringBuilder = new StringBuilder("");, you used something like StringBuilder stringBuilder = new StringBuilder(256); you would find that the overhead is reduced, as the StringBuilder will preallocate the internal buffer to 256 elements, reducing the possibility that the buffer needs to be resized dynamically (the size of the buffer and the size of the content are two different states which the builder will manage itself) — MadProgrammer
– MadProgrammer, Commented Feb 10, 2018 at 2:17
Can't Java compiler optimization make it traverse through the collection and count the total size of the result string in order to avoid costs of reallocation in the worst case scenario? — Dmitrii Demenev
– Dmitrii Demenev, Commented Feb 10, 2018 at 2:20
@DmitriiDemenev How? The contents of the Map are defined at run time — MadProgrammer
– MadProgrammer, Commented Feb 10, 2018 at 2:22
@DmitriiDemenev In this case, I would say, no, the Javac is not going to perform any additional optimisation that would pre-calculate the size of the contents — MadProgrammer
– MadProgrammer, Commented Feb 10, 2018 at 2:52

meriton · Accepted Answer · 2018-02-10 03:20:32Z

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.

Stephen C · Accepted Answer · 2018-09-25 01:35:48Z

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.

TimGallagher · Accepted Answer · 2018-09-25 01:17:40Z

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

Collectives™ on Stack Overflow

Compile time optimization of String concatenation

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related