Releases: kimwalisch/primesieve
primesieve-7.6
This is a minor new release, the API and ABI (Application binary interface) are backwards compatible.
The CPU cache size detection has been improved on Linux and on the new Apple Silicon CPUs. I have also finally found a way to get rid of goto
without deteriorating performance i.e. by annotating branches with likely
or unlikely
.
ChangeLog
- The primesieve GUI application has been deprecated/removed. It only works with QT4 which has reached end-of-life.
- Get rid Travis-CI because it is not free anymore.
CpuInfo.cpp
: Linux kernel CPU detection has been updated.CpuInfo.cpp
: Add workaround for sysctl bug (macOS & iOS).Erat.hpp
: Use CTZ instruction on x64 and ARM64 CPUs.config.hpp
: TuneFACTOR_ERATSMALL
factor.EratSmall.cpp
: Get rid ofgoto
.EratSmall.cpp
: Optimize switch statement.EratSmall.cpp
: Annotate switch cases with fallthrough.EratMedium.cpp
: Get rid ofgoto
.EratMedium.cpp
: Optimize switch statements.EratMedium.cpp
: Annotate switch cases with fallthrough.EratBig.cpp
: Simplify main sieving loop.- doc/C_Examples.md: libprimesieve C code examples.
- doc/CPP_Examples.md: libprimesieve C++ code examples.
primesieve-7.5
This is a minor new release, the API and ABI (Application binary interface) are backwards compatible.
Highlights
primesieve::iterator::next_prime()
has been sped up by about 10%. Since primesieve::iterator
is also used under the hood for generating an array (or vector) of primes that should also run slightly faster.
I have also removed the https://primesieve.org website because it simply took too much effort to maintain it and make it look nice across all devices, operating systems and browsers. Hence primesieve's main homepage is now its GitHub repo: https://github.com/kimwalisch/primesieve
Changelog
Erat.cpp
: Silence MSVC debug warning.StorePrimes.hpp
: Add workaround forwindows.h
max/min macros.PrimeGenerator.cpp
: Cache more primes.SievingPrimes.cpp
: Cache more primes.cmdoptions.cpp
: Support options of type:--option VALUE
.help.cpp
: Improve help menu.CMakeLists.txt
: Require CMake 3.4 instead 3.9.primesieve.pc.in
: Fix libdir and includedir.README.md
: Add libprimesieve multi-threading section.BUILD.md
: Add detailed build instructions.doc/ALGORITHMS.md
: Info from https://primesieve.org.doc/primesieve.txt
: New AsciiDoc man page.
For Linux package maintainers
primesieve-7.5 includes a new man page written using AsciiDoc. Previously primesieve's man page was generated using the help2man
program. primesieve includes a ready to distribute man page at primesieve/doc/primesieve.1
. If your Linux distribution requires that man pages must be generated from source you can find the related build instructions here: BUILD.md#man-page-regeneration.
primesieve-7.4
This release fixes 2 bugs, improves caching of small primes and adds a new --test
option to the primesieve console application.
- CpuInfo.cpp: Fix MinGW CPU detection.
- CMakeLists.txt: Fix cross compilation bug.
- Add
--test
option: Runs self tests. - IteratorHelper.cpp: Improve caching of small primes.
- ParallelSieve.cpp: Non-blocking status updates.
- PrimeSieve.cpp: Simplify status update.
- travis.yml: Test using GCC 5, 6, 7, 8, Clang 7 and MinGW.
primesieve-7.3
primesieve-7.3 improves the cache efficiency of the sieving algorithm for large sieving primes. By using aligned memory it is possible to reduce the number of pointer indirections which reduces cache pollution. I have measured a speed up of 15% near 1e18 and a speed up of 25% near 1e19.
- EratBig.cpp: Improve cache efficiency.
- MemoryPoop.cpp: Allocate buckets aligned by
sizeof(Bucket)
. - Bucket.hpp:
sizeof(Bucket)
is now a power of 2. - primesieve::iterator: Support C++ move semantics.
- cmdoptions.cpp: Fix array out of bounds bug.
- CpuInfo.cpp: Fix MinGW/MSYS2
-Wcast-function-type
warning.
primesieve-7.2
primesieve-7.2 features a new algorithm for medium sieving primes that improves the CPU's branch prediction rate by sorting the sieving primes (before using them). On AMD EPYC CPUs I have measured a speedup of up to 20% and on Intel Skylake CPUs I have measured a speedup of up to 10%. Ever since primesieve was created in 2010 its algorithm for medium sieving primes has been slower than yafu's algorithm for medium sieving primes. This performance issue has now been fixed!
Benchmark primesieve 7.1 vs 7.2
Start | primesieve 7.1 AMD EPYC 7401P |
primesieve 7.2 AMD EPYC 7401P |
primesieve 7.1 Intel Xeon 8124M |
primesieve 7.2 Intel Xeon 8124M |
1010 | 2.73 sec | 2.27 sec | 1.97 sec | 1.83 sec |
1011 | 3.18 sec | 2.65 sec | 2.25 sec | 2.06 sec |
1012 | 4.00 sec | 3.25 sec | 2.64 sec | 2.39 sec |
1013 | 5.24 sec | 4.11 sec | 3.22 sec | 2.92 sec |
1014 | 6.44 sec | 5.03 sec | 3.82 sec | 3.53 sec |
1015 | 7.67 sec | 6.04 sec | 4.40 sec | 4.08 sec |
1016 | 8.81 sec | 7.22 sec | 5.03 sec | 4.72 sec |
1017 | 10.53 sec | 8.51 sec | 5.84 sec | 5.60 sec |
At each start offset primesieve counted the primes inside an interval of size 10^10 using a single thread.
primesieve-7.1
primesieve-7.1 runs up to 30% faster on Intel Skylake-X CPUs!
The default sieve size is now (L2 cache size / 2). Using a sieve size that is slightly smaller than the L2 cache size allows other important data structures to also fit into the L2 cache. This reduces the number of L2 cache misses which improves performance on CPUs with slow L3 caches. primesieve-7.1 will also run slightly faster (< 3%) on most other Intel CPUs.
- api.cpp: Default sieve size = (L2 cache size / 2).
- CpuInfo.cpp: Improved CPU info detection.
- Erat.cpp: Lazy PreSieve initialization.
- EratSmall.cpp: Fix too large sieve size.
- help.cpp: Update help menu (--help).
- ParallelSieve.cpp: Improved load balancing.
- --cpu-info: New option, prints CPU information.
- Rename kilobytes to KiB because it is more accurate.
- Faster Windows binary built using clang-cl.
primesieve-7.0
Performance improvements
The next_prime()
function of primesieve::iterator
has been improved.
Up until now libprimesieve sieved an interval of size sqrt(n) and stored the primes inside that interval in an array. next_prime()
then iterated over the primes in the array. Once there were no more primes available in the array libprimesieve regenerated new primes which incurred an initialization overhead of sqrt(n) * log log sqrt(n) operations to recompute the sieving primes. This initialization overhead has been removed in primesieve-7.0 which gives a 2x speed improvement for next_prime()
when iterating over primes ≥ 10^15.
next_prime() benchmark
Start | primesieve 7.0 | primesieve 6.4 | primegen 0.97 | Math-Prime-Util-GMP |
0 | 2.66 sec | 3.42 sec | 7.50 sec | 15.26 sec |
1010 | 2.82 sec | 3.53 sec | 7.36 sec | 17.98 sec |
1011 | 3.19 sec | 3.89 sec | 7.31 sec | 27.05 sec |
1012 | 3.46 sec | 4.51 sec | 7.70 sec | 51.59 sec |
1013 | 3.97 sec | 5.63 sec | 10.06 sec | 112.59 sec |
1014 | 4.46 sec | 8.41 sec | 17.60 sec | 285.31 sec |
1015 | 4.97 sec | 10.70 sec | 41.45 sec | 813.77 sec |
1016 | 5.56 sec | 11.29 sec | 122.44 sec | 2,439.96 sec |
1017 | 6.29 sec | 11.69 sec | 508.56 sec | 9,115.23 sec |
1018 | 7.61 sec | 12.24 sec | 2,986.10 sec | NaN |
primesieve, primegen and Math-Prime-Util are the fastest open source prime number generation libraries. The benchmark above has been run on an Intel Core-i7 6700 CPU and all libraries have been compiled using GCC 8 with -O3
. At each start offset the benchmark programs iterated over the primes inside an interval of size 10^10 using next_prime()
.
API Changes
None, the API is backwards compatible with primesieve-6.x.
Breaking ABI Changes
New variables have been added to the C++ primesieve::iterator class and the C primesieve_iterator struct. Hence applications that link against the shared libprimesieve need to be recompiled. Users that have written primesieve bindings for other programming languages are affected by these ABI changes and need to update their code.
primesieve-6.4
See the ChangeLog for what's new.
primesieve-6.4-rc2
See the ChangeLog for what's new.
primesieve-6.4-rc1
See the ChangeLog for what's new.