Load fifty million integers as quickly as possible in Java

Question

I am working my way through Project Euler. Many of the problems deal with prime number calculations: this is the type of code that can be extracted into a separate class and reused.

While calculating primes can be done quickly using certain methods, I was able to speed up the process of "getting prime numbers" by using a list of primes on disk and loading them. It is an order of magnitude faster than any calculation, but still takes roughly three minutes loading from an SSD.

What I did:

1. I took a publicly-available list of the first fifty million primes (some problems do use a significant portion of those numbers).
2. I wrote a program to convert the numbers from their textual representation to binary using Java's DataOutputStream. The file is simply fifty million four-byte integers in a row.
3. The utility method below loads each integer into an array using DataInputStream. It produces correct results, but it slow.

Is there any way to speed up the process of loading 50,000,000 integers? If I need to preprocess the data differently I am willing to do that.

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;

public class Test {

  public static int[] loadByQuantity(int argNumPrimes) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (DataInputStream in = new DataInputStream(new FileInputStream("primes.bin"))) {
      for (int i = 0; i < primes.length; ++i) {
        primes[i] = in.readInt();
      }
    }
    catch (IOException ex) {
      throw new RuntimeException(ex);
    }
    return primes;
  }

}

Answer 1

Your code is a bit messy, and having the file name hard-coded in to your function is not great. Also, the "Hungarian Notation" (using things like arg to prefix your function parameters - note, it's a parameter, not an argument, by the way)... is not conventional.

On the other hand, I understand this is an exercise to test performance.... and it's not about the resusability (yet) of the code.

Still, I know from experience that reusability will happen, and your code will need some changes.

I also know, from experience, that memory-mapped IO is much faster in Java than other IO forms, so I figured I would have a kick at this problem.

I took my prime generator I had reveiewed here on Code Review previously ( Thread Safe Prime Generator ) and I generated the first 50,000,000 primes in to a file on my own system, then I tested your code against it (and after changing the file name to a parameter, it worked).

Out of interest, generating and writing to file of the primes took about 5 minutes on my computer - 311 seconds - much of which was probably IO time too.

Then, I converted your function to be:

public static int[] loadByQuantity(int argNumPrimes, String fname) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (DataInputStream in = new DataInputStream(new FileInputStream(fname))) {
        for (int i = 0; i < primes.length; ++i) {
            primes[i] = in.readInt();
        }
    } catch (IOException ex) {
        throw new RuntimeException(ex);
    }
    return primes;
}

The only difference is the file-name is now a parameter.

Then I wrote a little test system to time how long your code took for me:

public static void time(Supplier<int[]> task, String name) {
    long nanos = System.nanoTime();
    int[] primes = task.get();
    System.out.printf("Task %s took %.3fms\n", name, (System.nanoTime() - nanos) / 1000000.0);
    System.out.printf("Count %d\nFirst %d\nLast %d\n", primes.length, primes[0], primes[primes.length - 1]);
    System.out.println("----");
}

public static void main(String[] args) {
    int count = 50000000;
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
}

I then implemented the same functionality using an NIO mechanism specifically using memory-mapped IO: http://docs.oracle.com/javase/8/docs/api/java/nio/MappedByteBuffer.html

This type of IO is designed to significantly reduce the amount of memory copies are made of the input file. It also means that Java reads the content out of the OS, without first copying it in to Java's memory space.

For the types of sequential IO this problem has, I expected the performance improvements to be significant.

Further, the MappedByteBuffer has methods getInt() which also decodes 4 bytes in to an int for you: http://docs.oracle.com/javase/8/docs/api/java/nio/ByteBuffer.html#getInt--

Here's the code I came up with. Note, I have used the same exception handling that you use, and also the same array initialization. I believe you should be throwing exceptions from these methods, and not just wrapping them in runtime exceptions:

public static int[] loadByNIO(int argNumPrimes, String fname) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (FileChannel fc = FileChannel.open(Paths.get(fname))) {
        MappedByteBuffer mbb = fc.map(MapMode.READ_ONLY, 0, numPrimes * 4l);
        for (int i = 0; i < numPrimes; i++) {
            primes[i] = mbb.getInt();
        }
    } catch (IOException ex) {
        throw new RuntimeException(ex);
    }
    return primes;
}

I then ran the process a couple of times in the main method, and compared the results:

public static void main(String[] args) {
    int count = 50_000_000;
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
    time(() -> loadByNIO(count, "primes.dat"), "NIO");
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
    time(() -> loadByNIO(count, "primes.dat"), "NIO");
}

The NIO operation is, as expected, significantly faster... 1500 times faster

Task OP took 214163.250ms
Count 50000000
First 2
Last 982451653
----
Task NIO took 141.511ms
Count 50000000
First 2
Last 982451653
----
Task OP took 214633.128ms
Count 50000000
First 2
Last 982451653
----
Task NIO took 159.571ms
Count 50000000
First 2
Last 982451653
----

I admit, it is far faster than I was expecting too.... but, the results are correct.

Now, I encourage you to experiment with how to put this concept behind a Java stream, instead of populating the full 50,000,000 in to an array. By streaming the results you can start your "real" computation sooner, without the latency of having to read all the primes from the file. For example, consider what you could do with logic like:

primes.stream().....

where primes was reading the values on-demand from the file.

Here's the full code I have been running:

package prperf;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.channels.FileChannel.MapMode;
import java.nio.file.Paths;
import java.util.function.Supplier;

public class PrimeReader {

    public static int[] loadByQuantity(int argNumPrimes, String fname) {
        int numPrimes = Math.min(argNumPrimes, 50_000_000);
        int[] primes = new int[numPrimes];
        try (DataInputStream in = new DataInputStream(new FileInputStream(fname))) {
            for (int i = 0; i < primes.length; ++i) {
                primes[i] = in.readInt();
            }
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
        return primes;
    }

    public static int[] loadByNIO(int argNumPrimes, String fname) {
        int numPrimes = Math.min(argNumPrimes, 50_000_000);
        int[] primes = new int[numPrimes];
        try (FileChannel fc = FileChannel.open(Paths.get(fname))) {
            MappedByteBuffer mbb = fc.map(MapMode.READ_ONLY, 0, numPrimes * 4l);
            for (int i = 0; i < numPrimes; i++) {
                primes[i] = mbb.getInt();
            }
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
        return primes;
    }

    public static void time(Supplier<int[]> task, String name) {
        long nanos = System.nanoTime();
        int[] primes = task.get();
        System.out.printf("Task %s took %.3fms\n", name, (System.nanoTime() - nanos) / 1000000.0);
        System.out.printf("Count %d\nFirst %d\nLast %d\n", primes.length, primes[0], primes[primes.length - 1]);
        System.out.println("----");
    }

    public static void main(String[] args) {
        int count = 50_000_000;
        time(() -> loadByQuantity(count, "primes.dat"), "OP");
        time(() -> loadByNIO(count, "primes.dat"), "NIO");
        time(() -> loadByQuantity(count, "primes.dat"), "OP");
        time(() -> loadByNIO(count, "primes.dat"), "NIO");
    }

}

Answer 2

Using BufferedInputStream would be a quick fix with lesser modification of current code.

The reason why readX methods of DataInputStream/FileInputStream are slow is that they ask for IO every time. BufferedInputStream simply loads a chunk of file to reduce the number of IO operations needed. Another solution is to use read() method to load the (whole or part of ) file into an byte array and then retrieve those integers from byte array.

Answer 3

Consider memory mapped files

Disclaimer: This is also for me the first time I'm playing with memory mapped files in Java. The way I'm doing it might be suboptimal or even worse.

I think that Java's DataInputStream has high overhead for portability and error handling that is probably not needed in your situation. The fastest way to achieve your problem that I can think of is to simply mmap() the file into memory, assuming it contains a packed array of 32 bit integers in the host's native byte order.

This is the solution I've come up with.

static int[] load(final File file, final int n) throws IOException {
    try (final FileChannel channel = FileChannel.open(
            file.toPath(),
            StandardOpenOption.READ
    )) {
        final MappedByteBuffer mapping = channel.map(
            FileChannel.MapMode.READ_ONLY,
            0,                 // offset
            n * Integer.BYTES  // length
        );
        mapping.order(ByteOrder.nativeOrder());
        final IntBuffer integers = mapping.asIntBuffer();
        final int[] array = new int[n];
        integers.get(array);
        return array;
    }
}

In order to write the data, I've used the following function.

static void store(final File file, final int[] array) throws IOException {
    try (final FileChannel channel = FileChannel.open(
            file.toPath(),
            StandardOpenOption.READ,
            StandardOpenOption.WRITE,
            StandardOpenOption.CREATE,
            StandardOpenOption.TRUNCATE_EXISTING
    )) {
        final MappedByteBuffer mapping = channel.map(
            FileChannel.MapMode.READ_WRITE,
            0,                            // offset
            array.length * Integer.BYTES  // length
        );
        mapping.order(ByteOrder.nativeOrder());
        final IntBuffer integers = mapping.asIntBuffer();
        integers.put(array);
    }
}

I've benchmarked the functions using an array of 50M random integers. After loading the array, I've also computed its sum and printed it out to make sure the load operation is not optimized away. The results were obtained using the time shell facility and therefore also include the generation of the random data, JVM startup and any other overhead. The results are still very clear.

implementation     store      load

data stream         5:54      1:31
memory mapping      0:01    < 0:01

Separate concerns

I'm confident that I'm not telling you anything new here but for record's sake: Decouple the logic for reading an array of integers from a file from the logic that interprets these integers (as primes). Also don't hardcode the file name or the size of the array into the function that loads them.

Don't camouflage exceptions

Whether or not Java's “handle it or declare it” philosophy regarding exceptions was a good idea is open to debate. However, given that it is as it is, I don't think that working against the system is helpful. We gotta live with what we have now.

Beware the rules

I've only looked briefly into Project Euler and don't know their rules but I wouldn't be surprised if loading data from external resources would be considered cheating. Of course, if you're only doing this for your own amusement, you are free to set your own rules.

Answer 4

In the case of prime numbers your initial assumption is incorrect. Sieving is faster than reading from disk in virtually all cases.

Taking primesieve as an example, generating the first 10^9 primes requires 0.05s on a recent Intel CPU. To be "an order of magnitude faster than any calculation" you'd need to get the read time below 5ms. The memory mapped approach isn't even in the same city as that ballpark.

The biggest optimization is using The Genuine Sieve of Eratosthenes. Phony versions that are actually trial division are surprisingly common. Along with a mod 30 wheel you should be ahead of I/O in pure java, though behind something as highly optimized as primesieve.

[Edit - The work done in the primesieve benchmark is equivalent to generating the primes. The point is that it's virtually always quicker to generate primes rather than attempt to load them. (Counting is used as a benchmark because even printing the list onscreen takes longer than the sieving.) The entire premise of the original code is that it would be orders of magnitude faster than I/O which is incorrect. I was only pointing out that there is a much larger algorithmic performance gain to be had.

To be abundantly clear, that's only in the case of prime numbers. Loading millions of arbitrary integers would be a different proposition, one in which all the other answers are very helpful.

Also in the interest of clarity I wouldn't suggest a native binding to the primesieve library, implementing a segmented sieve (overkill for such a small number of primes), or anything else crazy. I'm only pointing out that a simple sieve and wheel, single threaded, in pure java is likely to be more robust, less aggravating (no I/O exceptions to worry about, files to add to projects, etc) and more performant than reading them from disk. In much the same way that "slow" sorting algorithms can be the fastest in edge cases.

As far as the comments on memory bandwidth go, there are two safe assumptions here. 1) The list of primes will be used for something. 2) If they're generated on the fly there's a decent change they'll still be in the cache when they are used.

Wrapping up about needing ints rather than a bitfield. For such a small list of primes you'd simply sieve over an array of ints anyway. Even if you used a compressed list to save space for whatever reason and needed to populate an array it would be a complete non issue because the original question is reading the primes out of a text file. That's a round trip to the cpu and parsing the number, probably more work that way. ]

Answer 5

A BitSet

One bit for each odd number up to 1,000,000,000, set if prime. That's 50847533 primes, not including 2. Should take about 64MB, vs 200MB for an array of integers. For any odd number you divide by 2 and look up that index.

Incidentally, a fairly simple sieve of Eratosthenes should take much less than three minutes to sieve a billion numbers in Java, more like ten seconds. This example does just that.

public static void main(String[] args) {
    int max = 1000000000;
    BitSet sieve = new BitSet(max/2+1);
    for(int i = 1; i < max/2; i++){
        sieve.set(i,true);
    }

    //the sieve
    for(int p = 3; p*p < max; p += 2){
        if(sieve.get(p/2)){
            for(int m = p*p; m < max; m += p+p){
                sieve.set(m/2,false);
            }
        }
    }

    //count primes and optionally print them out
    int primecount = 0;
    int last = 0;

    for(int p = 3; p < max; p += 2){
        if(sieve.get(p/2)){
            //System.out.println(p);
        }
    }
    System.out.println(primecount);
}

And Primesieve is about two orders of magnitude faster still by actually optimizing.