• Results
• Download

TL;DR

This is my benchmark that generates prime numbers using unsigned integer division instructions and avoidance of divisions.

It maintains an array that contains the resulting prime numbers, which are also used to factor prospective prime numbers.

What is special about my algorithm is that I maintain prime counters in CPU registers that let me avoid checking about 87% of numbers for primeness.

In addition, in my newer implementations, I use speculative execution to effectively perform 2 divisions simultaneously, on CPUs that allow that.

Because this algorithm is heavily dependent on the division operation, moreso than memory accesses, it is effectively a benchmark of a CPU's division operation, particularly its speculative execution, and secondarily memory access speed.

For enjoyment I've ported the core assembly language routines to multiple instruction set architectures including: x64, i386, aarch64, aarch32, and riscv64, and on x64 I've added AVX support.

Key findings:

1. The Apple Silicon processors are considerably more efficient than X86 processors.

1. All CPUs that allow using speculative execution to effectively parallelize divisions
are faster than those that don't.

1. While Apple Silicon is ARM-based, other ARM-based CPUs are less efficient than it e.g.
the Raspberry Pi 4's Broadcom CPU and a couple Qualcomm Snapdragon CPUs that I tried.

1. Because division instructions are very time-consuming, this algorithm is
much slower than the Sieve of Eratosthenes, despite my design focusing on avoiding divisions.

The algorithm

Instead of eliminating every single multiple of every prime using a bit array, as the Eratosthenes algorithm does, I maintain counters for multiples of the lower primes in the registers.

As the program proceeds from lower into higher candidate numbers, the counters permit skipping over multiples of primes without maintaining a bit array.

For instance, my counter3 is cycled from 0 to 1 to 2 and when we hit 3, it's rolled over to 0. Every time roll over a prime counter, we know that the current candidate number is a multiple of that prime, therefore not prime itself.

Using these counters lets me avoid checking about 87% of all candidate numbers when the counters are located in the CPU's main registers.

The exact percentage varies a little depending on the implementation and how many CPU registers are free to be used for counters e.g. there are more on x64 than on i386.

I also have an implemention that uses the x86 AVX vector registers which has even more counters, but there is a diminishing return, because as one adds more counters the efficiency increases less and less.

What makes this algorithm slower than Eratosthenes is the primeness check, which is very expensive, since it require repeated unsigned integer divisions. Checking a number for primeness entails dividing known primes into it in an attempt to factor it.

A common optimization is to only divide primes up to 1+sqrt(number), because if a larger factor than that exists, then a smaller one must as well and it would have already been encountered in an earlier division.

This algorithm would probably work best in conjunction with an FPGA with let's say 1000 counters to increase the efficiency closer to a theoretical maximum avoidance rate.

One advantage of this algorithm is that it's memory efficient, since there is no bit array as with Eratosthenes; there is only the primes array.

Here is my pseudocode for the my algorithm, checking against the lower 9 primes:

 function generate_primes
 {
  array primes[] = { 2,3,5,7,11,13,17,19,23 }
  array of bytes prime_counters[9] = { 0,0,0,0,0,0,0,0,0 }
  int n_primes = 9
  int n = 0
  while (always) {
   ++n
   for i = 1 to 8 {
    prime_counters[i]++
   }
   bool skip = false
   if prime_counters[0] >= 3 {
    prime_counters[0] = 0
    skip = true
   }
   if prime_counters[1] >= 5 {
    prime_counters[1] = 0
    skip = true
   }
   if prime_counters[2] >= 7 {
    prime_counters[2] = 0
    skip = true
   }
   if prime_counters[3] >= 11 {
    prime_counters[3] = 0
    skip = true
   }
   if prime_counters[4] >= 13 {
    prime_counters[4] = 0
    skip = true
   }
   if prime_counters[5] >= 17 {
    prime_counters[5] = 0
    skip = true
   }
   if prime_counters[6] >= 19 {
    prime_counters[6] = 0
    skip = true
   }
   if prime_counters[7] >= 23 {
    prime_counters[7] = 0
    skip = true
   }
   if (skip) continue
   if (n is even) then continue
   if (is_prime (n, primes, n_primes)) {
    primes[n_primes++] = n
    println ("%llu is prime", n)
   }
  }
  return primes
 }

Results

100 million primes

• MBA means Macbook Air.
• MBP means Macbook Pro.
• Linux on Apple Silicon was Fedora Asahi Linux.
• The Core i5-4278U is an Intel Macbook Pro, tested while running MacOS.
• 4div (aarch64) performs a sequence of 4 divisions to parallelize modulo operations using speculative execution and to minimize loop branch penalties.
• 28div (aarch64) performs a sequence of 28 divisions to parallelize modulo operations using speculative execution and to minimize loop branch penalties.
• 50div (x86_64) performs a sequence of 50 divisions to parallelize divisions using speculative execution and to minimize loop branch penalties.

The last column represents the efficiency of the CPU in generating primes, measured in primes per minute per GHz, with the Apple M1 trumping every other CPU.

Looking at the efficiency, the Apple M2 running the 4div variant of my code matched the Apple M3 (not Pro) also running 4div.

These beat all the recent x86 CPUs which were running non-parallelized divisions by a factor of 3.3.

In general, the efficiency of my parallelized-division is_prime routines was substantially better than doing one division per loop.

All recent x86 processors, both Intel and AMD, 2021, 2022 and 2023 models, curiously computed 2.4 million primes per minute per gigahertz with non-parallelized division.

The Raspberry Pi 4 model B was 3X more efficient than the StarFive RISC-V chip.

The Snapdragon 8 Gen 1, Snapdragon 888 and Snapdragon 750G scores were obtained by installing Termux on my Samsung S23 FE, Samsung S21 FE and A52 5G phones. Termux provides a Linux-like terminal environment, which allows installation of the Clang compiler and numerous other packages.

aarch64 implementation variants

Two basic ways of doing the time-consuming divisions:

• I use unsigned division followed by multiply-subtract (UDIV + MSUB) instructions, one per loop.
• Parallelizing a sequence of UDIV+MSUBs using speculative execution, 4 or 28 per loop.

1. 100 million primes on M2 without branch prediction parallelization takes 5.3 minutes.
2. 100 million primes on M2 with branch prediction parallelization takes 4.0 minutes.

The latter was thus 1.3X faster.

x86_64 implementation variants

I've implemented many variants to the x86_64 code in pursuit of better performance.

Varying where the prime counters on x86_64 are located and how they're used:

• Putting counters in main registers, increasing counters, using compare-branch.
• Putting counters in main registers, decreasing counters, using compare-branch.
• Putting counters in main registers, stuffing 8 counters into each register, rotating to access the counters (ROR), increasing counters, compare-branch.
• Putting counters in AVX registers, maintaining 31 7-bit counters, decreasing counters.
• Putting counters in main registers, increasing counters, using conditional-move (very slow).

Two basic ways of doing the time-consuming divisions:

• Unsigned integer DIV instructions, one per loop.
• Parallelizing a sequence of unsigned integer DIV instructions using speculative execution, up to 57 per loop.

Parallelizing improves the performance of both 64:32 DIV and 128:64 DIV, for instance I did the experiment of using 128:64 DIV alone on the Intel Core i5-4278U:

1. 100 million primes without speculative execution-based parallelization takes 60.6 minutes.
2. 100 million primes with speculative execution-based parallelization takes 46.9 minutes.

Two types of division:

Finally on x86_64, for divisions where the dividends are 32-bit I use the 64:32-bit DIV instruction because it is 3 times as fast as the 128:64-bit DIV.

Results for a Core i5:

What can be learned from this is, it is the slowness of the divisions that has the most negative impact on performance.

The maintainence of the counters is secondary but impactful, if abnormally slow as when implemented with condition move (CMOV) instructions.

i386 implementation variants

There are two, based on the implementation of is_prime:

1. Compare-branch with only one division per loop.
2. Compare-branch with 28 divisions per loop.

I found that 28 was the sweet spot on an i5-4278U, performing better than 16, 24 or 32 divisions per loop.

203.3 million 32-bit primes

There are 203280221 primes that can be expressed in 32 bits or less, beginning with 2. Generating all of them on a 32-bit system running my 32-bit prime sieve gives the following results:

Notes:

• Efficiency is measured in primes/minute/GHz.
• The i5-4278U was running Raspberry Pi OS for x86, which uses 32-bit userland and a 64-bit kernel.

1 billion primes

Finding a billion primes on a 64-bit system requires allocating 7.63 GB of RAM to hold 1,000,000,000 64-bit prime numbers. If your computer has only 8GB of RAM, you may need to shut down the windowing system (e.g. X-Windows) to run this at maximum speed without paging.

Notes:

• Efficiency is measured in primes/minute/GHz.
• The RISC-V board was the Pine64 Star64.

The last column represents the efficiency of the CPU in generating primes, with the Apple M1 still beating the nearest contender by a factor of 3.

One conclusion one could reach is that RAM speed matters when generating 1 billion primes.

• The Apple Silicon processors have tightly coupled RAM that communicates faster than the separate chips you see in other processors.
• At the other extreme, the StarFive JH-7110 is coupled with slow RAM, which hampers its ability to load divisors with sufficient speed.

It is possible that the Apple Silicon CPUs have built-in divider circuits that are 3X faster than microcode-based division.

All systems were running Linux except for the Macbook Airs and the Intel Macbook Pro, which were running MacOS. The M2 Air might be slower than M1 because the M1 Air is known to have a better heat spreader on the CPU and therefore better cooling.

In the presense of super-fast RAM like in the Macs or the Ryzens, CPU speed also matters, as evidenced by the Ryzen 5 and 7 having about the same efficiency scores and differing only in CPU speed.

An interesting observation is the similarity of the efficiency scores between the Raspberry Pi 4b and the Core i5 1240P, which one might naively assume ought to be very different.

If the CPUs are inherently equally inefficient but have different clock speeds, the ratio between their clock speeds should roughly correspond to the inverse of the ratio of their run times:

2 billion primes

Finding two billion primes on a 64-bit system requires allocating 15259 MB of RAM to hold 2,000,000,000 64-bit prime numbers.

Notes:

1. The Ryzen 7 350's performance with single-channel DDR5-5600 was roughly the same as with dual-channel LPDDR5X-7500, suggesting the division operations are a more important determinant of performance than the speed of cache refilling from RAM.
2. The above 7840U result used my original algorithm
which did not use speculative execution to parallelize division. Not that it mattered much.

3 billion primes

Finding three billion primes on a 64-bit system requires allocating 22888 MB of RAM to hold 3,000,000,000 64-bit prime numbers.

4 billion primes

Finding three billion primes on a 64-bit system requires allocating 30518 MB of RAM to hold 4,000,000,000 64-bit prime numbers.

• Efficiency is measured in primes/minute/GHz.

CPU speeds

To verify the expected CPU speed of the Apple Silicon computers, one has to run the utility powermetrics which is a part of MacOS. This displays core speeds in real time. The prime64 program always migrates to a performance core and runs at the highest speed.

For x86 the speed that I give for the core that's running primes64/32 is that of Turbo Boost, because the most demanding process will typically run using that mode, if not immediately then within a second or two.

Reading the live CPU speed

On Linux, a somewhat more precise approach could be possible by continuously reading the current core speed from /sys/devices/system/cpu/cpuNUMBER/cpufreq/scaling_cur_freq for whichever core the program is running on, summing those to determine the total area under a hypothetical core speed over time graph and then at the end, dividing by the total area to get an average CPU speed. This is assuming you know which CPU the process is running on, which may change over time, but it can be obtained by calling sched_getcpu().

However I wrote the core routines in primes64 and primes32 in assembly. The main() code jumps into the core assembly routines and the programs stays there until the test is done. Calling any C function from assembly is awkward and time-consuming, so I limit calls to library functions to only printing.

Analysis

The goal of my program is to find all prime numbers up to a reasonable limit, and not just Merseinne primes or some other subset.

My algorithm has several advantages which explain its speed but it is certainly slower than Eratosthenes.

1. By using counters to identify multiples of the small prime numbers, it avoids testing at least 87% of candidate numbers for primeness, depending on the architecture.
• It avoids divisions for numbers that are already covered by the prime number counters.
• The more counters it uses, the greater the percentage of candidate numbers that it can avoid checking for primality.
2. The bookkeeping data that it uses to avoid checking numbers is entirely in the fastest memory available: CPU registers. I've tried both main registers and vector registers. The latter are usually only slightly faster.
3. The program's memory use is proportional to the number of primes found, not the number of candidate numbers as you see with the Sieve of Eratosthenes.
4. It minimizes divisions by only checking numbers up to 1+sqrt(number).
5. The latest incarnations use speculative execution to perform parallel divisions on a single core, even on x86. Simpler CPUs like those in Raspberry pi's or the RISC-V board cannot do speculative parallel divisions.

Download

The source code:

• primes-1.5.tar.bz2

Changes

• 1.5 reinstates the original C code for use on CPUs other than x86/i386/aarch64/aarch32/riscv64.
• 1.4 optimizes aarch64 single-core parallel division for Linux and MacOS.
• 1.3 adds i386 single-core parallel division for Linux.
• 1.2 adds aarch64 single-core parallel division for Linux and MacOS.
• 1.1 optimizes x86_64, adds single-core parallel division to AVX and ROR2.
• 1.0 adds x86_64 single-core parallel division using speculative execution.
• 0.13 adds support for x86_64 MacOS.
• 0.12 adds an x64 AVX SIMD experiment.
• 0.11 adds various experiments to speed up x64.
• 0.10 adds improvements to i386 and aarch32.
• 0.9 adds support for RISC-V 64.
• 0.8 adds support for i386.
• 0.7 adds support for both Raspberry pi's aarch32 and Apple Silicon's armv8.

Useful links

• AMD Ryzen 7 7840U specs
• AMD Ryzen 7 7730U specs
• AMD Ryzen 7 6850U specs
• AMD Ryzen 5 5650U specs
• Intel Core i5 4278U specs