• Results
• Download

TL;DR

This is my benchmark that generates prime numbers without using unsigned integer division instructions and it instead uses the Eratosthenes algorithm, which is based on a bit array.

It maintains a bit array in RAM in which each bit indicates the presence or absence of a prime number.

Eratosthenes works by setting all multiples of every known prime throughout the bit array, then finding the first 0 bit after the last discovered prime number, which always will be a prime.

For every new prime that is discovered, I add it to an output buffer and then set all bits in the array that represent its multiples. Then repeat... until I reach the end of the array.

In my code the bit array represents only odd numbers, for efficiency's sake, because even numbers are never prime except the number 2. Thus:

• Bit 3 in the first byte of the bit array represents the number 7, which is prime.
• Bit 7 in the first byte of the bit array represents the number 15, which is not prime but is a multiple of the primes 3 and 5.

Because the entire bit array has to be updated for every new prime number that is discovered, this algorithm is susceptible to slowdown due to paging when the bit array's size is large enough to use more than the available RAM.

To ensure the bit array is located entirely in RAM and isn't paged out, especially on systems with minimal RAM, there are a few measures that one can take.

• Size the array to be exactly as large as needed and no larger.
• Turn off the swap partition or swap file.
• Disable unnecessary system services e.g. the CUPS printer daemon.
• Run the program on a Linux system that doesn't use bloated systemd.
• Lastly, I devised an optional two-bit-array approach that deallocates the lower array when it's no longer needed.

Findings

1. Even implementing this in C, it is much faster than my unsigned division algorithm.
2. Eratosthenes involves some overhead: When seeking X million primes, the bit array should be about 1.4X megabytes in size, where a megabyte is 1,048,576 bytes.
3. The run is always slower at the beginning because it has to set more bits for lower primes than
than for larger primes.
4. As the run proceeds, the lower parts of the bit array can be ignored because
earlier bits represent multiples of already-found primes.
5. My assembly language optimizations are only very slightly more effective than GCC's optimized code.
6. The larger the output array the better because disk I/O is very costly.

Results

I generated all of these results on 64-bit systems.

The program can also run on 32-bit systems; I developed that mode in a container using podman.

100 million primes

I used a bit array of size 122 MB.

MBA = Macbook Air

The resulting primes.dat file can be found here.

1 billion primes

I used a bit array of size 1.328 GB.

The resulting primes.dat file can be found here.

2 billion primes

I used a bit array of size 2.74 GB.

The resulting primes.dat file can be found here.

3 billion primes

I used a bit array of size 4.19 GB.

The resulting primes.dat file can be found here.

4 billion primes

I used a bit array of size 5.65 GB.

The resulting primes.dat file can be found here.

5 billion primes

I used a bit array of size 7.13 GB.

* The i5-4278U with 8GB RAM required the RAM pressure workaround, described below.

The resulting primes.dat file can be found here.

6 billion primes

I used a bit array of size 8.619 GB.

The resulting primes.dat file can be found here.

8 billion primes

I used a bit array of size 11.64 GB.

The resulting primes.dat file can be found here.

10 billion primes

I used a bit array of size 14.675 GB.

The resulting primes.dat file can be found here.

12 billion primes

I used a bit array of size 17.741671 GB.

The resulting primes.dat file can be found here.

Download

The source code:

• zEratosthenes 0.13

RAM pressure workaround with -2 option

When testing a Macbook Pro with Intel Core i5-4278U and 8GB of RAM, which was running Debian Linux and therefore systemd, I had to use two bit arrays totalling 7.13 GB, with included a lower bit array of 1024 MB that was deallocated as early as possible during the run. This was necessary because I found that Linux was eventually killing the program due to excessive RAM pressure, even in multi-user (non-graphical) mode.

The -2 command line option tells the program to split the bit array into two buffers.

The root cause may be systemd, because when I compared the Debian x86 machine to the Star64 RISC-V single-board computer, which in contrast uses a non-systemd distro, I found that the Star64 had no trouble providing enough of that board's 8GB RAM to run to zEratosthenes to completion without use of the two-array kludge.

Related links

• Intel Core i5 4278U specs
• Snapdragon 750G specs
• StarFive JH-7110 specs