Alex Rivera | Logout

Poor performance with large Java lists

Asked 2012-03-06T23:26:36.883
11

I'm trying to read a large text corpus into memory with Java. At some point it hits a wall and just garbage collects interminably. I'd like to know if anyone has experience beating Java's GC into submission with large data sets.

I'm reading an 8 GB file of English text, in UTF-8, with one sentence to a line. I want to split() each line on whitespace and store the resulting String arrays in an ArrayList<String[]> for further processing. Here's a simplified program that exhibits the problem:

/** Load whitespace-delimited tokens from stdin into memory. */
public class LoadTokens {
    private static final int INITIAL_SENTENCES = 66000000;

    public static void main(String[] args) throws IOException {
        List<String[]> sentences = new ArrayList<String[]>(INITIAL_SENTENCES);
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        long numTokens = 0;
        String line;

        while ((line = stdin.readLine()) != null) {
            String[] sentence = line.split("\\s+");
            if (sentence.length > 0) {
                sentences.add(sentence);
                numTokens += sentence.length;
            }
        }
        System.out.println("Read " + sentences.size() + " sentences, " + numTokens + " tokens.");
    }
}

Seems pretty cut-and-dried, right? You'll notice I even pre-size my ArrayList; I have a little less than 66 million sentences and 1.3 billion tokens. Now if you whip out your Java object sizes reference and your pencil, you'll find that should require about:

  • 66e6 String[] references @ 8 bytes ea = 0.5 GB
  • 66e6 String[] objects @ 32 bytes ea = 2 GB
  • 66e6 char[] objects @ 32 bytes ea = 2 GB
  • 1.3e9 String referen
java memory text garbage-collection large-files
Edit
Report

1 Answer

2

Idea 1

Start by considering this:

while ((line = stdin.readLine()) != null) {

It at least used to be the case that readLine would return a String with a backing char[] of at least 80 characters. Whether or not that becomes a problem depends on what the next line does:

String[] sentence = line.split("\\s+");

You should determine whether the strings returned by split keep the same backing char[].

If they do (and assuming your lines are often shorter than 80 characters) you should use:

line = new String(line);

This will create a clone of the copy of the string with a "right-sized" string array

If they don't, then you should potentially work out some way of creating the same behaviour but changing it so they do use the same backing char[] (i.e. they're substrings of the original line) - and do the same cloning operation, of course. You don't want a separate char[] per word, as that'll waste far more memory than the spaces.

Idea 2

Your title talks about the poor performance of lists - but of course you can easily take the list out of the equation here by simply creating a String[][], at least for test purposes. It looks like you already know the size of the file - and if you don't, you could run it through wc to check beforehand. Just to see if you can avoid that problem to start with.

Idea 3

How many distinct words are there in your corpus? Have you considered keeping a HashSet<String> and adding each word to it as you come across it? That way you're likely to end up with far fewer strings. At this point you would probably want to abandon the "single backing ch

answered 2012-03-06T23:36:07.330

Your Answer