Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>My implementation with multi threading (.NET 4.0 required):</p> <pre><code>using System; using System.Collections; using System.Collections.Generic; using System.Threading.Tasks; namespace PrimeGenerator { // The block element type for the bit array, // use any unsigned value. WARNING: UInt64 is // slower even on x64 architectures. using BitArrayType = System.UInt32; // This should never be any bigger than 256 bits - leave as is. using BitsPerBlockType = System.Byte; // The prime data type, this can be any unsigned value, the limit // of this type determines the limit of Prime value that can be // found. WARNING: UInt64 is slower even on x64 architectures. using PrimeType = System.UInt32; /// &lt;summary&gt; /// Calculates prime number using the Sieve of Eratosthenes method. /// &lt;/summary&gt; /// &lt;example&gt; /// &lt;code&gt; /// var lpPrimes = new Eratosthenes(1e7); /// foreach (UInt32 luiPrime in lpPrimes) /// Console.WriteLine(luiPrime); /// &lt;/example&gt; public class Eratosthenes : IEnumerable&lt;PrimeType&gt; { #region Constants /// &lt;summary&gt; /// Constant for number of bits per block, calculated based on size of BitArrayType. /// &lt;/summary&gt; const BitsPerBlockType cbBitsPerBlock = sizeof(BitArrayType) * 8; #endregion #region Protected Locals /// &lt;summary&gt; /// The limit for the maximum prime value to find. /// &lt;/summary&gt; protected readonly PrimeType mpLimit; /// &lt;summary&gt; /// True if the class is multi-threaded /// &lt;/summary&gt; protected readonly bool mbThreaded; /// &lt;summary&gt; /// The current bit array where a set bit means /// the odd value at that location has been determined /// to not be prime. /// &lt;/summary&gt; protected BitArrayType[] mbaOddNotPrime; #endregion #region Initialisation /// &lt;summary&gt; /// Create Sieve of Eratosthenes generator. /// &lt;/summary&gt; /// &lt;param name="limit"&gt;The limit for the maximum prime value to find.&lt;/param&gt; /// &lt;param name="threaded"&gt;True if threaded, false otherwise.&lt;/param&gt; public Eratosthenes(PrimeType limit, bool threaded) { // Check limit range if (limit &gt; PrimeType.MaxValue - (PrimeType)Math.Sqrt(PrimeType.MaxValue)) throw new ArgumentOutOfRangeException(); mbThreaded = threaded; mpLimit = limit; FindPrimes(); } /// &lt;summary&gt; /// Create Sieve of Eratosthenes generator in multi-threaded mode. /// &lt;/summary&gt; /// &lt;param name="limit"&gt;The limit for the maximum prime value to find.&lt;/param&gt; public Eratosthenes(PrimeType limit) : this(limit, true) { } #endregion #region Private Methods /// &lt;summary&gt; /// Calculates compartment indexes for a multi-threaded operation. /// &lt;/summary&gt; /// &lt;param name="startInclusive"&gt;The inclusive starting index.&lt;/param&gt; /// &lt;param name="endExclusive"&gt;The exclusive ending index.&lt;/param&gt; /// &lt;param name="threads"&gt;The number of threads.&lt;/param&gt; /// &lt;returns&gt;An array of thread elements plus 1 containing the starting and exclusive ending indexes to process for each thread.&lt;/returns&gt; private PrimeType[] CalculateCompartments(PrimeType startInclusive, PrimeType endExclusive, ref int threads) { if (threads == 0) threads = 1; if (threads == -1) threads = Environment.ProcessorCount; if (threads &gt; endExclusive - startInclusive) threads = (int)(endExclusive - startInclusive); PrimeType[] liThreadIndexes = new PrimeType[threads + 1]; liThreadIndexes[threads] = endExclusive; PrimeType liIndexesPerThread = (endExclusive - startInclusive) / (PrimeType)threads; for (PrimeType liCount = 0; liCount &lt; threads; liCount++) liThreadIndexes[liCount] = liCount * liIndexesPerThread; return liThreadIndexes; } /// &lt;summary&gt; /// Executes a simple for loop in parallel but only creates /// a set amount of threads breaking the work up evenly per thread, /// calling the body only once per thread, this is different /// to the .NET 4.0 For method which calls the body for each index. /// &lt;/summary&gt; /// &lt;typeparam name="ParamType"&gt;The type of parameter to pass to the body.&lt;/typeparam&gt; /// &lt;param name="startInclusive"&gt;The starting index.&lt;/param&gt; /// &lt;param name="endExclusive"&gt;The exclusive ending index.&lt;/param&gt; /// &lt;param name="parameter"&gt;The parameter to pass to the body.&lt;/param&gt; /// &lt;param name="body"&gt;The body to execute per thread.&lt;/param&gt; /// &lt;param name="threads"&gt;The number of threads to execute.&lt;/param&gt; private void For&lt;ParamType&gt;( PrimeType startInclusive, PrimeType endExclusive, ParamType parameter, Action&lt;PrimeType, PrimeType, ParamType&gt; body, int threads) { PrimeType[] liThreadIndexes = CalculateCompartments(startInclusive, endExclusive, ref threads); if (threads &gt; 1) Parallel.For( 0, threads, new System.Threading.Tasks.ParallelOptions(), (liThread) =&gt; { body(liThreadIndexes[liThread], liThreadIndexes[liThread + 1], parameter); } ); else body(startInclusive, endExclusive, parameter); } /// &lt;summary&gt; /// Finds the prime number within range. /// &lt;/summary&gt; private unsafe void FindPrimes() { // Allocate bit array. mbaOddNotPrime = new BitArrayType[(((mpLimit &gt;&gt; 1) + 1) / cbBitsPerBlock) + 1]; // Cache Sqrt of limit. PrimeType lpSQRT = (PrimeType)Math.Sqrt(mpLimit); int liThreads = Environment.ProcessorCount; if (!Threaded) liThreads = 0; // Fix the bit array for pointer access fixed (BitArrayType* lpbOddNotPrime = &amp;mbaOddNotPrime[0]) { IntPtr lipBits = (IntPtr)lpbOddNotPrime; // Scan primes up to lpSQRT for (PrimeType lpN = 3; lpN &lt;= lpSQRT; lpN += 2) { // If the current bit value for index lpN is cleared (prime) if ( ( lpbOddNotPrime[(lpN &gt;&gt; 1) / cbBitsPerBlock] &amp; ((BitArrayType)1 &lt;&lt; (BitsPerBlockType)((lpN &gt;&gt; 1) % cbBitsPerBlock)) ) == 0 ) { // If multi-threaded if (liThreads &gt; 1) { // Leave it cleared (prime) and mark all multiples of lpN*2 from lpN*lpN as not prime For&lt;PrimeType&gt;( 0, ((mpLimit - (lpN * lpN)) / (lpN &lt;&lt; 1)) + 1, lpN, (start, end, n) =&gt; { BitArrayType* lpbBits = (BitArrayType*)lipBits; PrimeType lpM = n * n + (start * (n &lt;&lt; 1)); for (PrimeType lpCount = start; lpCount &lt; end; lpCount++) { // Set as not prime lpbBits[(lpM &gt;&gt; 1) / cbBitsPerBlock] |= (BitArrayType)((BitArrayType)1 &lt;&lt; (BitsPerBlockType)((lpM &gt;&gt; 1) % cbBitsPerBlock)); lpM += n &lt;&lt; 1; } }, liThreads); } else { // Leave it cleared (prime) and mark all multiples of lpN*2 from lpN*lpN as not prime for (PrimeType lpM = lpN * lpN; lpM &lt;= mpLimit; lpM += lpN&lt;&lt;1) // Set as not prime lpbOddNotPrime[(lpM &gt;&gt; 1) / cbBitsPerBlock] |= (BitArrayType)((BitArrayType)1 &lt;&lt; (BitsPerBlockType)((lpM &gt;&gt; 1) % cbBitsPerBlock)); } } } } } /// &lt;summary&gt; /// Gets a bit value by index. /// &lt;/summary&gt; /// &lt;param name="bits"&gt;The blocks containing the bits.&lt;/param&gt; /// &lt;param name="index"&gt;The index of the bit.&lt;/param&gt; /// &lt;returns&gt;True if bit is set, false if cleared.&lt;/returns&gt; private bool GetBitSafe(BitArrayType[] bits, PrimeType index) { return (bits[index / cbBitsPerBlock] &amp; ((BitArrayType)1 &lt;&lt; (BitsPerBlockType)(index % cbBitsPerBlock))) != 0; } #endregion #region Public Properties /// &lt;summary&gt; /// Gets whether this class is multi-threaded or not. /// &lt;/summary&gt; public bool Threaded { get { return mbThreaded; } } /// &lt;summary&gt; /// Get the limit for the maximum prime value to find. /// &lt;/summary&gt; public PrimeType Limit { get { return mpLimit; } } /// &lt;summary&gt; /// Returns the number of primes found in the range. /// &lt;/summary&gt; public PrimeType Count { get { PrimeType lptCount = 0; foreach (PrimeType liPrime in this) lptCount++; return lptCount; } } /// &lt;summary&gt; /// Determines if a value in range is prime or not. /// &lt;/summary&gt; /// &lt;param name="test"&gt;The value to test for primality.&lt;/param&gt; /// &lt;returns&gt;True if the value is prime, false otherwise.&lt;/returns&gt; public bool this[PrimeType test] { get { if (test &gt; mpLimit) throw new ArgumentOutOfRangeException(); if (test &lt;= 1) return false; if (test == 2) return true; if ((test &amp; 1) == 0) return false; return !GetBitSafe(mbaOddNotPrime, test &gt;&gt; 1); } } #endregion #region Public Methods /// &lt;summary&gt; /// Gets the enumerator for the primes. /// &lt;/summary&gt; /// &lt;returns&gt;The enumerator of the primes.&lt;/returns&gt; public IEnumerator&lt;PrimeType&gt; GetEnumerator() { // Two always prime. yield return 2; // Start at first block, second MSB. int liBlock = 0; byte lbBit = 1; BitArrayType lbaCurrent = mbaOddNotPrime[0] &gt;&gt; 1; // For each value in range stepping in incrments of two for odd values. for (PrimeType lpN = 3; lpN &lt;= mpLimit; lpN += 2) { // If current bit not set then value is prime. if ((lbaCurrent &amp; 1) == 0) yield return lpN; // Move to NSB. lbaCurrent &gt;&gt;= 1; // Increment bit value. lbBit++; // If block is finished. if (lbBit == cbBitsPerBlock) { // Move to first bit of next block. lbBit = 0; liBlock++; lbaCurrent = mbaOddNotPrime[liBlock]; } } } #endregion #region IEnumerable&lt;PrimeType&gt; Implementation /// &lt;summary&gt; /// Gets the enumerator for the primes. /// &lt;/summary&gt; /// &lt;returns&gt;&lt;/returns&gt; IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } #endregion } } </code></pre> <p>The multi-threading works by threading the inner most loop, this way there are no data locking issues because the multiple threads work with a subset of the array and dont overlap for each job done.</p> <p>Seems to be quite fast, can generate all primes up to a limit of 1,000,000,000 on an AMD Phenom II X4 965 processor in 5.8 seconds. Special implementations like the Atkins are faster, but this is fast for the Sieve of Eratosthenes.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow do I implement the Sieve Of Eratosthenes using multithreaded C#?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USAaron Murgatroyd
    1. USAaron Murgatroyd
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COGood, but you miss two optimizations: 1) in multi-threading your inner loop array range continuously increases in size until it considerably exceeds L1 cache size for increasing inefficiency in memory access times, and 2) you only eliminate even number culls whereas a full wheel factorization could eliminate more culls at some cost in increased complexity. Using these two further optimizations, I find the primes to one billion in 1.975 seconds and up to 4294967295 in 8.738 seconds on a machine not much faster than yours: http://stackoverflow.com/a/18139477/549617.
      singulars
      1. PO
      1. USGordonBGood
    2. COcont'd: The above link only uses 2,3,5 wheel factorization but slight further gains could be made using 2,3,5,7,11,13 wheel factorization at a further cost in complexity; however, there is little point in that about two thirds of the time is spent enumerating the found primes in the foreground thread, although it might reduce run times by about a few percent due to increasing the packing of the composite number array. The above code might also benefit from using unsafe code as you do, which is not currently used.
      singulars
      1. PO
      1. USGordonBGood
    3. CONot bad but two further comments: 1) there's not much point to multi-threading here as on my i7 (eight threads) CPU there's only about a 30% speed gain using multi-threading compared to not using it; this is due to extra overheads in threading over all ranges per prime, which is quite inefficient as to memory access as mentioned in my first comment. 2) Your use of unsafe pointers actually slows the program slightly compared to just using the array directly; this is because DotNet JIT compiler doesn't optimize pointers very well even though they eliminate the array bounds checks.
      singulars
      1. PO
      1. USGordonBGood
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload