Reading Large Files in Java getting really slow

Question

I am trying to read a large file ~200 MB (~300 million lines of text). I am using a relatively standard way of reading like:

for (int i = 1; i <= numProcs; i++) {
    System.out.println("Parsing " + traceFilePrefix + i + ".prg");
    System.out.println("##########################");

    try {
        String line;
        int instrType;
        String hexAddr;
        ArrayList<Trace> traces = new ArrayList<Trace>();

        int lineNum = 1;

        BufferedReader br = new BufferedReader(new FileReader(traceFilePrefix + numProcs + "/" + traceFilePrefix + i + ".PRG"));
        while ((line = br.readLine()) != null) {
            line = line.toUpperCase();
            // validate line format
            if (line.matches(regexLineFormat)) {
                StringTokenizer tokenizer = new StringTokenizer(line);
                instrType = Integer.parseInt(tokenizer.nextToken());
                hexAddr = tokenizer.nextToken();

                traces.add(new Trace(instrType, hexAddr));
            } else {
                // line is in invalid format
                System.err.println("ERR: line " + lineNum + " is invalid \"" + line + "\"");
            }
            lineNum++;

            if (lineNum % 1000 == 0) System.out.println("line " + lineNum); 
        }
        br.close();
        processorsTraces.add(i-1, traces);
    } catch (Exception e) {
        e.printStackTrace();
    }
}

I find that reading slows down at about line 20 million... in face it doesnt seem to progress at all ... how can I improve this? Whats the problem in this simple piece of code?

A latest run seem to run out of heap space ... I guess I cant store data in an arraylist like that?

This is supposed to be a simulator. It first parses trace files containing hexadecimal addresses of memory accesses. Then is supposed to run simulation of these data. This code snipplet only parses and stores the traces in an arraylist.

Answer 1

The issue is almost certainly in the structure of your Trace class, and it's memory efficiency. You should ensure that the instrType and hexAddress are stored as memory efficient structures. The instrType appears to be an int, which is good, but just make sure that it is declared as an int in the Trace class.

The more likely problem is the size of the hexAddress String. You may not realise it but Strings are notorious for 'leaking' memory. In this case, you have a line and you think you are just getting the hexString from it... but in reality, the hexString contains the entire line.... yeah, really. For example, look at the following code:

public class SToken {

    public static void main(String[] args) {
        StringTokenizer tokenizer = new StringTokenizer("99 bottles of beer");
        int instrType = Integer.parseInt(tokenizer.nextToken());
        String hexAddr = tokenizer.nextToken();
        System.out.println(instrType + hexAddr);
    }
}

Now, set a break-point in (I use eclipse) your IDE, and then run it, and you will see that hexAddr contains a char[] array for the entire line, and it has an offset of 3 and a count of 7.

Because of the way that String substring and other constructs work, they can consume huge amounts of memory for short strings... (in theory that memory is shared with other strings though). As a consequence, you are essentially storing the entire file in memory!!!!

At a minimum, you should change your code to:

hexAddr = new String(tokenizer.nextToken().toCharArray());

But even better would be:

long hexAddr = parseHexAddress(tokenizer.nextToken());

---

EDIT: Request to get help on how to debug the code:

To debug the code, you need to set a break-point in the method. Select the line System.out.println(...); and use the key-board short-cut Ctrl-Shift-B which will toggle a break-point, and you will get the 'dot' marker like the picture below:

Then, with that break-point enabled, you need to debug the program:

Right-click on the 'main' word in the public static void main (String[] ...) and select 'Debug As -> Java Application'

This should prompt you to go to the 'Debug' perspective, and you will have a window with the 'Variables' displayed. One of the variables will be hexAddr and you can expand it to show its contents. Here's a screen-shot:

From the variables section there are a few things of note. At the bottom, the 'value' variable is highlighted, and it's internal value is shown in the area below ( [9, 9, , b, o, ......, r]

You can see the count and offset variables for hexAddr too. This means that the hexAddr variable stores the char[] array for the entire line, but also stores an offset and count in that array which it uses for managing the subset of the chars that this String instance is interested in

Answer 2

I see several issues that could impact performance

    if (line.matches(regexLineFormat)) {

If the file is large, compiling the regular expression would be a performance bottleneck. Suggest to put the following block in to a static block:

 Pattern regexLineFormatPattern = Pattern.compile(regexLineFormat);

And then use

if (regexLineFormatPattern.matcher(line).matches()){

References: Java Doc of Pattern class

And then since you are already using regular expression, you could try to use regular expression to complete the work done by StringTokenizer to replace the following code:

StringTokenizer tokenizer = new StringTokenizer(line);
instrType = Integer.parseInt(tokenizer.nextToken());
hexAddr = tokenizer.nextToken();

The Matcher#group method would be helpful to extract the value from the String.

The code would be like this:

//outside the looop, better in a static block
String regexLineFormat = "(\d+) ([^ ]+) ...."//define the capture groups here.

Pattern regexLineFormatPattern = Pattern.compile(regexLineFormat);

//in the method, inside the loop

Matcher matcher = regexLineFormatPattern.matches(line);

if( matcher.matches()){
   traces.add(new Trace(Integer.parseInt(matcher.group(1)),matcher.group(2)));
}

Answer 3

First: When memory is an issue, you cannot read the entire data set into memory. You need to follow an algorithm similar to (pseudo code)

while(notDone){
   readFixedAmountOfData();
   processData();
}

Right now, you are doing

readALLData(); // <- everything goes into memory
processData();

For specific points in your code:

• If you know the data is ASCII text, don't use Reader classes and don't use Strings, use raw InputStream (or some derivative) and use byte[].
• avoid superfluous calls that create excess objects (e.g. line = line.toUpperCase() creates a new String -- do you really need it in upper case?)
• What does the Trace class look like? That will play a significant part of this.

Answer 4

I would split this up into a 2-threaded program.

The first thread simply reads into a chunk of the file, say 100.000 (or 1 000.000) first lines, and stores it in an array.

Then the second thread would parse the lines and evaluate them according to your rules.

The first thread would then continue reading the next 100.000 lines, and the second thread does it magic on those lines, and so on until there are no more lines in the file.

What else? Well, you dont actually need your lineNum variable, because i will always have the same value.

Answer 5

If the file I/O is really what is slowing you down. Then you should consider how much memory you can afford to use at a given time, and find the trade of between the two.

Decide how much memory you can spare, then read in as much of the file as possible. Then parse out the lines once it is all loaded.

Reading in larger chunks will increase your file I/O speed.

Answer 6

Since you have a 300/200 bytes per line, this means that you'll have a lot of identical items in your list. Consider flyweight pattern to save your memory requirements. As experiment, add the same item 300 mln times in your list. It is the minumum amount of memory you need. See if you have so much.

I wonder how do you manage to have a type/address with 1.5 bytes/instruction. Since hex address is supposed to be different every time, you cannot use flyweight. Yet, you may use the heap as a cache whereas the program is stored on disk. Yet, java is bad for disk swapping again.

Since you'll have a memory map, it may be cheaper to allocate an array int[max_hex_address] for storing the types. A 300 million of integers is only 1.2 GB.

Answer 7

First thing you should change in the code is avoid reading binary file using FileReader. It is meant for reading streams of character. You can use FileInputStream.

Close io streams in finally block so that they are closed even if an exception is thrown.

Also try increasing the buffer size of the BufferedReader.