Efficient conversion of ArrayList to multi-line String in JAVA

Question

ArrayList<String[]> writtenClasses = new ArrayList<String[]>();
// usually there is functional code here that populates
// ArrayList<String[]> writtenClasses with variably 3000
// String[] objects always of exactly 8 lines each

ArrayList<String> processedClasses = new ArrayList<String>();
for(String[] classLines: writtenClasses)
{
    for(String classLine: classLines)
    {
        processedClasses.add(classLine);
    }
}

String result = "";
for(String fileLine: processedClasses)
{
    result += fileLine + "\n";
}

My code is above. It works fine and produces exactly the result I want, just slowly. It takes about 10ms per item of ArrayList writtenClasses which is okay until I give it bigger jobs. I suspect that there is something there to do with ArrayLists that is taking so long, but timing and printing to console job stats after each run revealed little.

This above code is an adaptation of earlier code in hopes to improve efficiency. It does so by about 4%. The below code is the old method I used which takes just a little longer than the above.

for(String[] classLines: writtenClasses)
{
    for(String classLine: classLines)
    {
        result += classLine + "\n";
    }
    writtenClasses.set(writtenClasses.indexOf(classLines), null);
}

I do writtenClasses.set(writtenClasses.indexOf(classLines), null); merely for the purposes of memory efficiency, and my stats show that it uses memory more efficiently with an undetectable amount of CPU effort.

This is my second question here on StackOverflow and i've done my best to follow the rules, but if i'm asking this badly or being inadvertently inconsiderate in some way, please, highlight that to me and i'll address that. :)

Try using StringBuilder instead of concatenating your strings and see if that helps boost performance? — Michael0x2a, Sep 09 '14 at 05:47
Just out of interest - can you run your solution under load **without a StringBuilder** (see comment below http://stackoverflow.com/a/25737459/512155) and see whether that makes a noticeable difference? Seems like most people here (myself included) weren't aware that this is 'coding from the last decade'... — Jan Groth, Sep 09 '14 at 23:48
@Java-Now-A-Pro: _Really_? That's quite the opposite of what the comment suggested... :o — Jan Groth, Sep 10 '14 at 06:23
In reply to Jan: i'm sorry, I don't understand... To which comment do you refer to with 'the comment'? — Scruffy, Sep 11 '14 at 04:30

icza · Accepted Answer · 2014-09-09T06:16:38.783

3

There is absolutely no use creating the intermediate processedClasses list. Also, StringBuilder will speed up significantly the process:

// Consider a large initial size to even avoid reallocation, here I used 64 KB
StringBuilder sb = new StringBuilder(65536);

for (String[] classLines : writtenClasses)
    for (String lines : classLines)
        sb.append(lines).append('\n');

// Note: you might not even need to convert it to String, read reasoning below
String result = sb.toString();

We build the content in a StringBuilder which implements the CharSequence interface. Many classes accept CharSequences and not just Strings. A good example is a FileWriter. In these cases you don't even need to convert the StringBuilder to a String because the StringBuilder can be passed just as easily as its String result which may be another performance advantage if the content is really big.

edited Sep 09 '14 at 06:16

answered Sep 09 '14 at 05:54

icza

389,944
63
907
827

Thanks! On a big job my program was taking an hour, you brought this down to a second and a half. I agree with your first statement; it was painful to break that up in that it felt wrong to do so. I realise that I should not have gigabyte long strings in memory, but I must ask what happens to a StringBuilder when filled with a string 2^31 long and then appended to. Might have to ask this separately... Cheers! – Scruffy Sep 09 '14 at 08:07
It crashes with an `OutOfMemoryException: Requested array size exceeds VM limit` like almost all data structures based on an array and exponential growth. _"2^31 entries should be enough for anobody"_ :( – Clément MATHIEU Sep 09 '14 at 19:12

score 3 · Answer 2 · answered Sep 09 '14 at 06:22

The problem has been pointed out by other answers. With Java 8, an alternative to the two nested loops and a StringBuilder is to use a stream and a joining collector*:

String result = writtenClasses.stream()
        .flatMap(array -> Arrays.stream(array))
        .collect(joining("\n"));

_{*requires import static java.util.Collectors.joining;}

score 1 · Answer 3 · answered Sep 09 '14 at 05:50

1

Not a proper answer, but too awkward to read in a comment:

String result = "";
for(String fileLine: processedClasses)
{
    result += fileLine + "\n";
}

That is creating a million String instances. I guess using a StringBuilder here should have a positive effect on performance.

answered Sep 09 '14 at 05:50

Jan Groth

14,039
5
40
55

Your example does NOT create million String instances. This very common use case has been optimized since at very least a decade by all vendors. Javac detects this pattern and automatically replaces the string concatenation by a StringBuilder. You can easily see it using `javap`. However, the double loop from OP's code tricks the compiler and a string is create for each outer loop. TL;DR: in theory you are right, in practice you don't care for simple and regular loops like your example. – Clément MATHIEU Sep 09 '14 at 19:08

score 1 · Answer 4 · answered Sep 09 '14 at 05:53

The main pain point here probably isn't the ArrayList, but the use of the + operator with Strings. Since Strings are immutable in java, each invocation forces the creation of a new object and copying of all the data, which, as you stated, may be quite long.

A faster way to do this would be to use a StringBuilder, which does not (necessarily) force the copying of the data on each operation:

StringBuilder result = new StringBuilder();
for(String[] classLines: writtenClasses)
{
    for(String classLine: classLines)
    {
        result.append(classLine).append('\n');
    }
}

score 0 · Answer 5 · edited May 23 '17 at 11:56

based on this question

ewall:

At what point do you switch to StringBuilder? When it effects memory or performance. Or when it might. If you're really only doing this for a couple strings once, no worries. But if you're going to be doing it over and over again, you should see a measurable difference when using StringBuilder.

StringBuilder myString = new StringBuilder();

     for(String classLine: classLines)
        {
           myString.append(classLine).append("\n");
        }

StringBuilder would somehow improve your performance.

Efficient conversion of ArrayList to multi-line String in JAVA

5 Answers5