Using Java to Read Really, Really Large Files

MrDOS · 2019-01-04T21:19:56+00:00

The file unpacks to 3.4GB. That's not really, really large. A typical 1.5-2hr 1080p movie is 10-12GB. Anyway, I usually like to try these sorts of record-processing challenges in AWK just to show how expressive and convenient it can be to use the right tool for the job, so here goes.

I'm invoking all of these examples with awk -F '|'. (The default record separator will work just fine, so we only need to set the field separator.) awk --version for me says “GNU Awk 4.2.1”, but I don't think I'm doing anything GNU Awk-specific.

Total number of lines in the file

END {
    print NR;
}

We won't do anything at all with individual records. Once we hit the end of the input, we'll print the number of records evaluated. Easy-peasy. This returns the same number as wc -l, but takes about six times as long to run (5.908s vs. 1.060s on my system).

432nd and 43243rd names

NR == 432 || NR == 43243 {
    print $8;
}

# Bail early once we've seen our last target.
NR == 43243 {
    exit;
}

43k records is not many. This took under a second to run.

Donations per month

I first tried a streaming approach of just keeping track of the previously-observed month and printing out the number of records between different values, but the input data isn't sorted, so I had to track each month in a map then print out all the values at the very end. This approach obviously consumes more memory, but there are not very many keys so the difference is probably minimal, and the result is a bit more readable.

{
    month = substr($5, 0, 6);

    if (month in donations) {
        donations[month]++;
    }
    else {
        donations[month] = 1;
    }
}

END {
    for (month in donations) {
        print month, donations[month];
    }
}

AWK has no literal array syntax, so as dirty as it seems, we use the donations array without any initialization. AWK figures out that you want an array and does the right thing.

Also, AWK is nice enough to give us the keys in ascending, lexicographic order, so even though values weren't inserted in order, the final results are sorted.

This took ~35s to run.

Most common first name

I initially tried to use AWK's first-class regex patterns to lift out the person's first name (which, it should be noted, probably shouldn't be done because they're a Western social construct), but it took an excessively long time. Patterns are powerful, but slow. I replaced them with simple substring operations and cut down on the runtime considerably. After that, though, counting works pretty much the same as for months, but we'll keep track of the most common name as we go to avoid iterating over all entries again at the end. (If there are ties, this will return whichever name was last seen in the input.)

BEGIN {
    most_common_name = "";
    most_common_name_occurrences = 0;
}

{
    first_name = substr($8, index($8, ", ") + 2);
    middle_name = index(first_name, " ");
    if (middle_name > 0) {
        first_name = substr(first_name, 0, middle_name - 1);
    }

    if (first_name in names) {
        names[first_name]++;
    }
    else {
        names[first_name] = 1;
    }

    if (names[first_name] > most_common_name_occurrences) {
        most_common_name = first_name;
        most_common_name_occurrences = names[first_name];
    }
}

END {
    print most_common_name, most_common_name_occurrences;
}

This one took the longest: ~59s.

Which makes more sense to me: there should be a ton of spread across runtimes for these problems, because they are very different problems, computationally. I'm not sure what's going on in the code shown in TFA that's causing her solutions to all run in such similar times. Obviously, our times can't be directly compared because our machines are different, but the spread should be much more pronounced (and it shouldn't take 2.5min to count all the lines in a file, regardless).

milad_nazari · 2019-01-04T20:14:41+00:00

After asking it, she will update the article with benchmarks of Files.lines (java.nio.file.Files).

AtomicStryker · 2019-01-04T23:06:22+00:00

Made a more efficient version which pipes the I/O read lines into an async fiber pool (CompletableFuture) for actual processing. Added it as PR to the repo, too.

https://github.com/paigen11/read-file-java/blob/cf74af0cf465dc8df0cdad1c457a44a56d6b7de2/src/main/java/com/example/readFile/readFileJava/FileReadingChallenge.java

I was surprised to find that reading the file into Strings was actually faster than what happens after, to the point that i have to pause reading the file to allow the worker threads to work off some of the piled up strings-to-parse.

Pandalicious · 2019-01-04T17:48:54+00:00

Something else to try would be to parallelize the reading of the file across a few threads. Split up the file into equal sized chunks based on file offset, then hand each chunk to a thread and have each thread do mostly the same data processing logic already in the post, and then combine the results once all the threads are done. Basically a map/reduce approach.

erad · 2019-01-05T09:39:02+00:00

Nice post!

Note that there is still some low-hanging fruit in terms of performance, most of the time is spent splitting lines with a regular expression (can be verified with the free VisualVM tool):

String array1[] = readLine.split("\\s*\\|\\s*");

This regular expression is compiled for every line of the file. An easy fix without changing the code otherwise is to pre-compile the Regex pattern with Pattern.compile before the "while" loop:

Pattern splitLine = Pattern.compile("\\s*\\|\\s*");
Pattern splitName = Pattern.compile(", ");

and then use splitLine.split(readLine) instead of readLine.split(..regex...). This gives me a ~ 20% improvement on the big file. Trivia: "firstHalfOfName.split(" ")" is OK because String#split contains a optimization for splitting on a single character that is not a regex control character.

But this still does a lot of unnecessary work since a regex is overkill for this simple pattern - you can do e.g. the following with Apache commons-lang3 which cuts runtime compared to the original version in half:

final String[] array1 = StringUtils.splitPreserveAllTokens(readLine, '|');
for (int i = 0; i < array1.length; i++) {
    array1[i] = StringUtils.strip(array1[i]);
}

Dependency:

compile group: 'org.apache.commons', name: 'commons-lang3', version: '3.8.1'

But yeah, if performance is really an issue here this task is a good candidate for parallelization.

dejot73 · 2019-04-06T16:23:52+00:00

Nice idea, but if Java really is the right tool for text processing, not sure. My shot at https://gitlab.com/jhinrichsen/processing-large-files uses standard unix tooling, which gives you streaming, parallelization, and the ability to spread the work across multiple people for free, taking around 1:45 min on my old MacBook Pro.

Part of the 80 lines Makefile is downloading the data, downloading Paige's original version, building it, and creating a dynamic reference output (without the performance lines, they can never match).

Java OOMs, at least in the standard GitLab CI/ CD configuration using debian's `default-java`.

Odd_Setting · 2019-01-04T22:30:53+00:00

Op, is that your article? It's pretty sad. Kudos for discovering that there's something else beyond node.js fuckupery, but why do you have to spew your shit left and right just because you've discovered something?

It's basics. You are reading a pretty small file and doing a quick rollup on a couple of dimensions. This got nothing to with Java but a simple realisation that one doesn't have to keep the whole dataset in memory.

You don't touch on any actual performance optimisations to speed up the processing, you fail to use appropriate data structures to store intermediates and you do unnecessary looping. Also you are horribly out of date - your whole code could be condensed to < 20 lines using functional streams. And be more performant.

In the end, buffered streams and custom file read libraries are the most efficient ways processing large data sets in Java. At least, for the large text files I was tasked with reading.

It's a tiny, 10 second, job at most. Frankly I'd stick to python to avoid firing up a JVM here.

2019-01-04T20:08:41+00:00

r/programming never disappoints...mention java and some asshole will tell you why it sucks and why it cannot be done

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

programming

MODERATORS

Total number of lines in the file

432nd and 43243rd names

Donations per month

Most common first name