How to parse a huge file line by line, serialize & deserialize a huge object efficiently?

Question

I have a file of size around 4-5 Gigs(nearly billion lines). From every line of the file, I have to parse the array of integers and the additional integer info and update my custom data structure. My class to hold such information looks like

class Holder {
    private int[][] arr = new int[1000000000][5]; // assuming that max array size is 5
    private int[] meta = new int[1000000000];
}

A sample line from the file looks like

(1_23_4_55)    99

Every index in the arr & meta corresponds to the line number in the file. From the above line, I extract the array of integers first and then the meta information. In that case,

--pseudo_code--
arr[line_num] = new int[]{1, 23, 4, 55}
meta[line_num]=99

Right now, I am using BufferedReader object and it's readLine method to read each line & use character level operations to parse the integer array and meta information from each line and populate the Holder instance. But, it takes almost half an hour to complete this entire operation.

I used both java Serialization & Externalizable(write the meta and arr) to serialize and deserialize this HUGE Holder instance. And with both of them, the time to serialize is almost half an hour and to deserialize is also almost half an hour.

I would appreciate your suggestions on dealing with this kind of problem & would definitely love to hear your part of story if any.

P.S. Main Memory is not a problem. I have almost 50 GB of RAM in my machine. I have also increased the BufferedReader size to 40 MB (Of course, I can increase this upto 100 MB considering that disk access takes approx. 100 MB/sec). Even cores and CPU is not a problem.

EDIT I

The code that I am using to do this task is provided below(after anonymizing very few information);

public class BigFileParser {

private int parsePositiveInt(final String s) {
    int num = 0;
    int sign = -1;
    final int len = s.length();
    final char ch = s.charAt(0);
    if (ch == '-')
        sign = 1;
    else
        num = '0' - ch;

    int i = 1;
    while (i < len)
        num = num * 10 + '0' - s.charAt(i++);

    return sign * num;
}

private void loadBigFile() {
    long startTime = System.nanoTime();
    Holder holder = new Holder();
    String line;
    try {

        Reader fReader = new FileReader("/path/to/BIG/file");
        // 40 MB buffer size
        BufferedReader bufferedReader = new BufferedReader(fReader, 40960);
        String tempTerm;
        int i, meta, ascii, len;
        boolean consumeNextInteger;
        // GNU Trove primitive int array list
        TIntArrayList arr;
        char c;
        while ((line = bufferedReader.readLine()) != null) {
            consumeNextInteger = true;
            tempTerm = "";
            arr = new TIntArrayList(5);
            for (i = 0, len = line.length(); i < len; i++) {
                c = line.charAt(i);
                ascii = c - 0;
                // 95 is the ascii value of _ char
                if (consumeNextInteger && ascii == 95) {
                    arr.add(parsePositiveInt(tempTerm));
                    tempTerm = "";
                } else if (ascii >= 48 && ascii <= 57) { // '0' - '9'
                    tempTerm += c;
                } else if (ascii == 9) { // '\t'
                    arr.add(parsePositiveInt(tempTerm));
                    consumeNextInteger = false;
                    tempTerm = "";
                }
            }

            meta = parsePositiveInt(tempTerm);
            holder.update(arr, meta);
        }
        bufferedReader.close();
        long endTime = System.nanoTime();
        System.out.println("@time -> " + (endTime - startTime) * 1.0
                / 1000000000 + " seconds");
    } catch (IOException exp) {
        exp.printStackTrace();
    }
}
}

public class Holder {
    private static final int SIZE = 500000000;

    private TIntArrayList[] arrs;
    private TIntArrayList metas;
    private int idx;

    public Holder() {
        arrs = new TIntArrayList[SIZE];
        metas = new TIntArrayList(SIZE);
        idx = 0;
    }

    public void update(TIntArrayList arr, int meta) {
        arrs[idx] = arr;
        metas.add(meta);
        idx++;
    }
}

Answer 1

It simply can't take that long. You're working with some 6e9 ints, which means 24 GB. Writing 24 GB to the disk takes some time, but nothing like half an hour.

I'd put all the data in a single one-dimensional array and access it via methods like int getArr(int row, int col) which transform row and col onto a single index. According to how the array gets accessed (usually row-wise or usually column-wise), this index would be computed as N * row + col or N * col + row to maximize locality. I'd also store meta in the same array.

Writing a single huge int[] into memory should be pretty fast, surely no half an hour.

Because of the data amount, the above doesn't work as you can't have a 6e9 entries array. But you can use a couple of big arrays instead and all of the above applies (compute a long index from row and col and split it into two ints for accessing the 2D-array).

Make sure you aren't swapping. Swapping is the most probable reason for the slow speed I can think of.

Answer 2

It sounds like the time taken for file I/O is the main limiting factor, given that serialization (binary format) and your own custom format take about the same time.

Therefore, the best thing you can do is to reduce the size of the file. If your numbers are generally small, then you could get a huge boost from using Google protocol buffers, which will encode small integers generally in one or two bytes.

Or, if you know that all your numbers are in the 0-255 range, you could use a byte[] rather than int[] and cut the size (and hence load time) to a quarter of what it is now. (assuming you go back to serialization or just write to a ByteChannel)

Answer 3

There are several alternative Java file i/o libraries. This article is a little old, but it gives an overview that's still generally valid. He's reading about 300Mb per second with a 6-year old Mac. So for 4Gb you have under 15 seconds of read time. Of course my experience is that Mac IO channels are very good. YMMV if you have a cheap PC.

Note there is no advantage above a buffer size of 4K or so. In fact you're more likely to cause thrashing with a big buffer, so don't do that.

The implication is that parsing characters into the data you need is the bottleneck.

I have found in other apps that reading into a block of bytes and writing C-like code to extract what I need goes faster than the built-in Java mechanisms like split and regular expressions.

If that still isn't fast enough, you'd have to fall back to a native C extension.

Answer 4

If you randomly pause it you will probably see that the bulk of the time goes into parsing the integers, and/or all the new-ing, as in new int[]{1, 23, 4, 55}. You should be able to just allocate the memory once and stick numbers into it at better than I/O speed if you code it carefully.

But there's another way - why is the file in ASCII? If it were in binary, you could just slurp it up.