StringBuilder proper size for compound structures like Map>

Question

Given following code as sample:

Map<String, List<String>> warningMap = (Map<String, List<String>>) warningsOrErrorsMapVariable;
StringBuilder warningMessages = new StringBuilder(size?!);

for (Iterator<String> keyIterator = warningMap.keySet().iterator(); keyIterator.hasNext();) {
    Object key = keyIterator.next();
    if (!keyIterator.hasNext()) {
        isLastKey = true;
    }

    List<String> values = warningMap.get(key);

    if (values != null) {
        isLastValue = false;
        for (Iterator<String> valueIterator = values.iterator(); valueIterator.hasNext();) {
            String message = valueIterator.next();
            if (!valueIterator.hasNext()) {
                isLastValue = true;
            }               

            warningMessages.append(message);
            if (!(isLastKey && isLastValue)) {
                warningMessages.append(NEW_LINE);   
            }
        }
    }
}
return warningMessages.toString();

What the best practice to declare StringBuiler with proper size for compound structures?

One of options is predicting size o whole map by mapElems* listElems * predictedListElemSize, the other one is visiting each element and getting exact size, but both of them requires iterating thru all map twice - firstly to get size, secondly to get String values appened to buffer. Is it worth it?

Wont the whole "computing size of elems" be more time consuming than resizing buffer of builder when needed?

Iterate through the lists and accumulate the string lengths? — Oliver Charlesworth, Feb 04 '12 at 13:19

score 3 · Answer 1 · edited May 23 '17 at 12:03

Sounds like a premature optimization to me. Default size isn't actually the best choice in most of the cases (rarely you use StringBuilder for strings shorter than 16 characters), so make a simple assumption.

Unless you really have a performance problem here, added complexity of computing the more-or-less accurate buffer size does not pay off. Just start with slightly bigger buffer 256 or 1024 bytes and forget about it.

In your code I would rather focus on an inefficient loop over Map: you are iterating over keySet() and fetching values on almost every iteration using Map.get(). Iterate using entrySet() from the beginning!

It may or may not be. (I'd be inclined to think not in your example, since String.length() is cheap and O(1).) But the point I'm trying to make is that you shouldn't even be thinking about this unless you've got clear evidence that the optimization (and the extra code complexity) is really necessary.

JB Nizet · Accepted Answer · 2012-02-04T13:35:34.543

Yes, multiplying the size of the map by the expected (estimated) average list size and by the expected (estimated) average String length should be enough.

The growing algorithm of StringBuilder isn't linear: it doubles each time, so you won't gain much by having a precise estimation of its final size.

I doubt this is where you would have any performance problem.

Side note: your code would be easier if you prepended the newline before each element except the first one, and used the foreach loop syntax. You should also iterate throught the entrySet() of the map, rather than iterating throught the keys and doing a lookup at each iteration:

boolean isFirst = true;
for (Map.Entry<String, List<String>> entry : warningMap.entrySet()) {
    List<String> warnings = entry.getValue();
    if (warnings != null) {
        for (String warning : warnings) {
            if (!isFirst) {
                warningMessages.append(NEW_LINE);
            }
            isFirst = false;
            warningMessages.append(warning);
        }
    }
}

StringBuilder proper size for compound structures like Map>

3 Answers3

See also