
                       SIEVE OF ERATOSTHENES BENCHMARK 
                            version $( sieve -v )
                                  2016-2020

INTRODUCTION

  The goal of this benchmark is to measure relative performance of historic
  CPUs from the dawn of computing up until recently, when vector units,
  multiple cores and graphics and tensor accelerators took over, making a
  single core integer performance of a less importance.

  As any benchmark, it is far from being objective and it only measures the
  performance in a specific task, the sieve of Eratosthenes, in our case.
  Still, it is better than nothing and we believe that we have chosen a good
  compromise between simplicity of implementation and integer performance
  relevance. So the outcomes of this benchmark should correlate with the
  CPU's single core performance in compiling, graph algorithms, automated
  theorem proving, database searches, text processing, loss less data
  compression and similar integer tasks that are uneasy to vectorize. On the
  other hand, the performance of things like computer graphics, physics
  simulations or even as simple thing as block memory moves would be rather
  unrelated to the outcomes of this benchmark since they vastly benefit from
  the presence of special CPU units that cannot be easily employed in the
  sieve task.

  Specifically, we chose it as a benchmark because

  (1) it scales with the CPU addressing capability --- if measured an
      average execution time of a single iteration of the inner loop we
      could in principle compare 8 bit machine computing primes up to 10000
      with a 64 bit machine computing primes up to 10^11.

  (2) exercises loads, stores, bit manipulations and (to some extent)
      branching --- this is what you'd expect from an integer CPU. At the
      same time CPUs with wider than 8 bit data paths cannot benefit much
      from them, which is fair to 8 bit machines --- note that this has an
      effect that the performance ratio between, say, 32 bit CPU to an 8 bit
      machine as given by this benchmark would be a lower bound on 32 bit
      CPU speedup in most practical applications.

  (3) does not require multiplication so it does not penalize old machines
      that only had add and shift instructions.

  Unlike other benchmarks, this one does not output a single number but
  rather a table of execution times for different memory footprints. This
  allows for realistic testing of 8-bit machines with limited memory as well
  as modern machines with many gigabytes of memory. It is also revealing the
  effect of CPU caches. It often happens that CPU A seems to be faster than
  CPU B for some array size while the opposite is true for others.

  Also, we wanted to get maximum out of each architecture. That's why there
  is a hand-tuned assembly for most platforms there. Quite a great care was
  devoted to its coding. This allows us to compare CPUs directly with more
  confidence, irrespective of the compiler used (but we also tested several
  compilers and BASIC interpreters just to see the big picture -- in the 80s
  they evolved at a similar pace the CPUs themselves did).

PORTING

  If you plan to port this benchmark to your favorite CPU, read this section
  because certain rules must be adhered to so that the results would be
  meaningfully comparable.

  First of all, the sieve is represented by individual bits (0 indicating a
  prime, 1 non-prime) usually stored in an array of bytes (it is up to the
  CPU if little endian or big endian is used). This way the benchmark
  exercises enough of bit manipulations as opposed to naive version where
  all byte would be wasted for representing logical value. Bits are indexed
  from 0, so at index 0 there is a flag for number 0, at index 1 flag for 1
  and so on.
  
  The algorithm then goes on by filling the array with 0b01010101 pattern
  indicating that multiples of two are not primes. This is the (only, AFAIK)
  place where the CPU could use its vector units to fill the array quickly
  (it won't have much performance impact, though).

  Then the main loop tests numbers, starting from k=3 (i.e. at bit index 3).
  If it is zero (i.e. a prime) it crosses out all its multiples from the
  array by setting bits at index j*3 to one, starting with j=2. This then
  repeats with k=k+1 (it is IMPORTANT not to skip by 2 to get comparable
  timing results).
  
  Note that it is enough to test only for k such that k*k<N (where N-1 is
  the last number-index in the bit array). This is because for k>=sqrt(N)
  any non-prime number <N would have a form of q*k, where 1 < q < k, which
  means that q=p1*p2..pn (its primes that are <=q) and we have already
  processed that and by doing so we have already crossed out all q*k numbers
  for q>1.
  
  Similarly, we could have started from j=k instead of j=2 but we don't from
  a reason described later. Please resist a temptation to make your
  implementation even faster by doing so --- you would lose comparability to
  other machines.

  It is IMPORTANT that you test that your implementation does really compute
  primes and primes only (for that you can run sieve -l to list them, or
  sieve -a to print the byte array and easily compare as files).

  Finally, it is important to benchmark at sieve sizes as implemented in
  sieve.cc when creating the result table, so that we could easily compute
  ratios between different CPUs in the respective points.
    
  Namely, the testing starts from an array l=30 bytes long, being expanded
  by using the following formula: l=max(l+1,11*l/10). If you just plug in an
  assembly routine to sieve.cc (a preferable way when C++ compiler could be
  run for a target platform), you don't have to care about this.
  
  For each size, the benchmark should measure a time in microseconds it took
  to perform full run and it should also output the total number of
  executions of the inner loop body. To compute this, it is necessary to
  have another implementation with the counter. This one not being timed,
  only being used to compute how many times the inner loop was executed.

ALLOWED TRICKS

  Generally all programming tricks are allowed to make the implementation as
  fast as possible except those forbidden in the CAVEATS section and things
  like taking a list of primes and making a self-extracting zip file out of
  it or using completely different algorithm for producing primes.
  
  Behave as if you were given an algorithm which you have to implement as
  fast as possible using the best tricks of time (of the target CPU). So you
  can use loop unrolling for 32 bit in-order machines, self-modifying code
  for 8bit CPUs and so on.
  
  Also, there's a question of memory addressing. A general rule of thumb is
  to only demand what is natural for the given architecture. So, for 32 or
  64 bit CPUs it should be able to address half of the addressable memory.
  For 8 bit CPUs it should be able to work with 64 KiB (minus program and
  necessary OS size). For certain 16 bit CPUs like 68000 it should be able
  to address at least 8 MiB, for others, like 8088 which are more like an
  advanced 8-bit machine with bank mapping unit build-in, it is better to
  demand just 64 KiB (because otherwise we could have demanded that 8bit
  machines with more than 64 KiB should use their memory bank switching to
  test larger arrays but that would just benchmark a different thing than
  what was benchmarked on the other machines).

  There is an exception in BASIC implementations that only provide 16 bit
  integers -- it is OK there that the maximum array size is 8 KiB.

CAVEATS

  (1) Originally, we ran the inner i+=k-cycle from i=2*k, which is
      redundant. Testing from k*k works just as well because for a=2 to k-1,
      the a*k was already visited by primes that a is composed of. I
      realized that only after we have already made lots of measurements so
      it was too late to change it. Moreover, it turned out that the
      performance difference is less than 10% (you can check for yourself by
      defining FAST_VERSION macro when compiling (or by calling make
      fast_sieve)). More interestingly, the faster version even turned out
      to blur impact of CPU caches in the plot so what was originally an
      omission became a wanted feature for CPU testing as it generates
      higher cache pressure.
  
  (2) In the outer loop we could have step by k+=2 (or step by 1 and
      represent only odd numbers in the array), but we do it by k++. This is
      to exercise branching (and branch prediction unit) more.

  It is important to adhere to these two requirements to get comparable
  results. These requirements are analogous to Linpak's routines being
  disallowed to use fast algorithms for matrix multiplications.

SEE ALSO

  KEY_to_FILES		describing what architecture is implemented where 
  KEY_to_RESULTS	rationalizing naming conventions of the results

CREDITS

  David Klusacek	Most of the programming, especially the hand tuned
			assembly codes. Sieve implementations that do not
			mention their author explicitly in the source code
			or in messages they print were written by David
			Klusacek. He also did some benchmarking too.

  Jiri Zima		Most of the benchmarking, some programming.
			Interpretation of the results.


