11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Comment the traces.add and see if you title is correct. I feel that reading is not a problem at all. It should be a memory, an issue of storing the millions of small objects. Actually, the average size of your lines is 300/200 = 1.5 bytes per item. The overhead will be huge. Since java performance is based on JIT, it does not care about memory efficiency and you will have about 100 bytes overhead per evert 1.5 bytes of real data. You'll need about 30 GB to store all your 300 mln items. Java is not suitable for this task and you have a wrong title. \$\endgroup\$ – Val Nov 7 '13 at 18:07
  • \$\begingroup\$ To be pedantic… a 200 MB file cannot possibly contain 300 million lines of text. \$\endgroup\$ – 200_success Dec 31 '13 at 20:51
18
+50
\$\begingroup\$

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:

enter image description here

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:

enter image description here

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ok I will change hex address to int first. Its currently a string \$\endgroup\$ – Jiew Meng Nov 7 '13 at 12:32
  • \$\begingroup\$ When I execute your code, I just get "99bottles" how do you get the array and stuff? I am using Eclipse J2EE Kepler. \$\endgroup\$ – Jiew Meng Nov 7 '13 at 13:05
  • \$\begingroup\$ "String theory" is true .... believe it or not. Haters will hate... :) \$\endgroup\$ – rolfl Nov 7 '13 at 13:33
  • 1
    \$\begingroup\$ Note that the char[] sharing is no longer true in recent Oracle/OpenJDK releases (at least in Java 7 and I think even in newer Java 6 releases), it has been modified so that every String has its own char[]. \$\endgroup\$ – Joachim Sauer Nov 7 '13 at 14:23
  • 2
    \$\begingroup\$ @rolfl: I mis-remembered the exact versions: it's JDK8 since b40 and JDK7 since u6: mail.openjdk.java.net/pipermail/core-libs-dev/2012-May/… \$\endgroup\$ – Joachim Sauer Nov 8 '13 at 10:11
6
\$\begingroup\$

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)));
}
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The lecturer advised against using a threaded program because of complexities it introduces. I agree, this is supposed to be a small relatively easy assignment ... \$\endgroup\$ – Jiew Meng Nov 7 '13 at 11:31
  • \$\begingroup\$ I +1 because your answer corresponds to the (mis)title. \$\endgroup\$ – Val Nov 7 '13 at 18:16
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I was commenting on the file read, as that can help speed it up. Space issues need to be address as a separate thing, which I was not addressing. \$\endgroup\$ – Christopher J Nov 8 '13 at 16:03
  • \$\begingroup\$ That is why I am telling that you ignored the question. Author clearly says that his problem is dramatically slowed down due to memory limit, which you do not address. Just saying that you have ignored the question does not mean that you responded the real issue. \$\endgroup\$ – Val Nov 8 '13 at 18:16
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
-1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Oh i put close() in try since it also throws an exception. And in this simple program I thought of avoiding the need for so much try catch. Ok but I'll follow ur advice and try changing things \$\endgroup\$ – Jiew Meng Nov 7 '13 at 11:32
  • \$\begingroup\$ But I am actually reading characters? Its a text file? \$\endgroup\$ – Jiew Meng Nov 7 '13 at 11:35
  • \$\begingroup\$ I saw you have extension PRG \$\endgroup\$ – Kinjal Nov 7 '13 at 11:37
  • \$\begingroup\$ for some reason its a "PRG" file ... but the data inside is just text \$\endgroup\$ – Jiew Meng Nov 7 '13 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.