85
\$\begingroup\$

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;
  }

}
\$\endgroup\$
  • 2
    \$\begingroup\$ how does loading 50.000.000 million integers takes so long (3 minutes? seriously)?. It is just 190 Megabytes. It would just need a fraction of a second on any machine (Even without SSD it should take as maximum a couple of seconds). \$\endgroup\$ – GameDeveloper Jan 29 '17 at 3:01
  • 13
    \$\begingroup\$ @DarioOO good question, which is why I asked. Turns out there is a good reason, as the answers posted before your comment point out. \$\endgroup\$ – user31517 Jan 29 '17 at 5:47
  • 4
    \$\begingroup\$ You should generate them. I've gone through the first 120 problems without ever needing more than sqrt(1e9) (~= 31k) primes. \$\endgroup\$ – Olivier Grégoire Jan 29 '17 at 11:14
  • 3
    \$\begingroup\$ @DarioOO because he's reading every prime separate instead of reading bigger chunks. The current code has 50 million "disk" operations. If he would read like a megabyte at a time it would be done in seconds. \$\endgroup\$ – Pieter B Jan 30 '17 at 8:31
  • 4
    \$\begingroup\$ Wrap the FileInputStream in a BufferedInputStream. Will do wonders. \$\endgroup\$ – Thorbjørn Ravn Andersen Jan 30 '17 at 12:17
104
\$\begingroup\$

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");
    }

}
\$\endgroup\$
  • 17
    \$\begingroup\$ I'm kinda relieved that I wasn't the only one who was taken by surprise how much faster memory mapped I/O is in Java. (Or, should I say, how much overhead streams have.) I was confident that it would make a significant difference but the magnitude is really astonishing. \$\endgroup\$ – 5gon12eder Jan 28 '17 at 21:14
  • 1
    \$\begingroup\$ Thanks for the suggestion (both of you) recommending memory-mapped files. This answer is very thorough and I appreciate the comparisons and benchmarks. I will try this out and see if I get the same results (I should). Regarding naming - that is a bad habit I picked up at my previous employer (it was their coding standard). I'm trying to drop it but sometimes it sneaks back in. \$\endgroup\$ – user31517 Jan 28 '17 at 22:10
  • 27
    \$\begingroup\$ It's worth noting that adding a BufferedInputStream as mentioned here comes in at 700ms on my machine, which is much better than 214seconds, but not as good as 140ms from NIO \$\endgroup\$ – rolfl Jan 29 '17 at 5:43
  • 2
    \$\begingroup\$ Effectively, memory mapped IO does no IO at all in the usual case that the file is cached in the disk buffer (very likely for "only" 50m integers, i.e., 200 MB file) - the disk cache pages are just mapped directly into the process space and you read from them like any other memory source. In a native language you could use this directly as your underlying array, but in Java you have the mismatch between managed arrays are "direct buffers". You could simply feed the ByteBuffer into your algorithm and use the numbers directly though. \$\endgroup\$ – BeeOnRope Jan 29 '17 at 15:28
  • 4
    \$\begingroup\$ The reason it is faster is because the operating system has the disk file cached in memory from the previous read. \$\endgroup\$ – Thorbjørn Ravn Andersen Jan 30 '17 at 12:18
54
\$\begingroup\$

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.

\$\endgroup\$
  • 8
    \$\begingroup\$ Welcome to Code Review! I'm giving you a +1 because you've pointed out a simple but important oversight in the original code that wasn't mentioned by any of the existing answers yet. Your answer would be stronger if you'd augment it with some reasoning and (ideally) also show some data. For me, wrapping an additional BufferedInputStream resulted in a 30 x speedup, which is remarkable. \$\endgroup\$ – 5gon12eder Jan 29 '17 at 2:04
  • 1
    \$\begingroup\$ BufferedInputStream is a great suggestion. I added it to my performance test and it improves the 214 second read to just 700milliseconds (which is great, but not as good as the NIO at 140ms) \$\endgroup\$ – rolfl Jan 29 '17 at 5:42
18
\$\begingroup\$

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.

\$\endgroup\$
12
\$\begingroup\$

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. ]

\$\endgroup\$
  • 1
    \$\begingroup\$ I see. To be fair, IO - under the right scenario - probably is very fast, but not faster by a factor of 10! If you memory map the file, and it's already cached, the IO is a no-op and you use the memory mapped pages from the buffer cache directly. This usually works at about memcpy speed. To be fair though, 10^9 primes in 0.05 is fairly incredible. Assuming 4-byte primes, that's 4 GB / 0.05s = 100 GB/s, far in excess of the memory bandwidth of a typical 4-core system (usually topping out around 25 GB/s). So I'm not even sure how that's possible (perhaps on GPU?). \$\endgroup\$ – BeeOnRope Jan 29 '17 at 16:34
  • 1
    \$\begingroup\$ ... looking at the benchmark results on the primesieve page, I think you likely meant "can find all the primes less than 10^9 in 0.05s", not "generate the first 10^9 primes...". So that would be something like the first 50 million primes. \$\endgroup\$ – BeeOnRope Jan 29 '17 at 16:37
  • 1
    \$\begingroup\$ It's also worth noting that the benchmarks on the referenced page use 8 cores of the CPU concurrently. This, per se, is not a bad thing, but a smarter use of the other 7 cores in an IO-based system would allow time to use the primes at the same time they are loading, instead of consuming all CPU resources just on generation. Additionally, the benchmarks simply counted the primes (yeah, "simply"), but it would slow down if it had to populate an array of all of them in int format. These small differences may, depending on what you do with the primes, make a big impact. \$\endgroup\$ – rolfl Jan 29 '17 at 20:16
  • 1
    \$\begingroup\$ The problem of 'false sieves' only really applies to functional programming languages like Haskell, in which there are a number of cute one liners that produce prime numbers and superficially appear to follow the algorithm but are really just trial division in disguise. Imperative languages like Java don't have that problem, because they generally don't have those cute one liners. The amount of code required to do it properly is about the same for either style. \$\endgroup\$ – James Hollis Jan 31 '17 at 15:55
  • 1
    \$\begingroup\$ In theory there will be a point where loading from a file is faster than a sieve, since even a theoretical best sieve is going to be bounded by at best O(n), whereas loading from a file is O(m) where m is the number of primes (not the input size). For large enough n, m is log log n, so loading from a file is O(log log n) in theory. In practice this crossover point is going to be very large \$\endgroup\$ – mirhagk Jan 31 '17 at 21:05
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ In addition to this, "Every prime number can be expressed as 30k±1, 30k±7, 30k±11, or 30k±13 for some k" stackoverflow.com/questions/2614147/… \$\endgroup\$ – JollyJoker Jan 30 '17 at 9:39
  • 2
    \$\begingroup\$ At this size you would be better off with a BitSet - see this SO answer. \$\endgroup\$ – Boris the Spider Jan 30 '17 at 10:15
  • \$\begingroup\$ Also, run-length encoding of zeroes could help. One byte per 30 numbers would give you 30 megabytes = 240 megabits of data for primes up to a billion, but since only 50 million of those are ones, you'll have long stretches of zeroes. \$\endgroup\$ – JollyJoker Jan 30 '17 at 12:51
  • \$\begingroup\$ @Boris you're right I assumed the boolean array would be represented the way that BitSet actually is, and hadn't actually heard of BitSet. The boolean array was actually slightly faster for sieving, but is even less compact than a simple array of prime integers, so I've switched everything to BitSet. My example is there to demonstrate the data structure, not just the Sieve of Eratosthenes. \$\endgroup\$ – James Hollis Jan 30 '17 at 16:42

Your Answer

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