分段素筛

Question

在互联网上看到这个高效的分段素筛，请帮助我理解它的工作，特别是下一个向量的使用。

分段大小的具体选择如何影响性能？

const int L1D_CACHE_SIZE = 32768;
void segmented_sieve(int64_t limit, int segment_size = L1D_CACHE_SIZE)
{
    int sqrt = (int) std::sqrt((double) limit);
    int64_t count = (limit < 2) ? 0 : 1;
    int64_t s = 2;
    int64_t n = 3;

    // vector used for sieving
    std::vector<char> sieve(segment_size);

    // generate small primes <= sqrt
    std::vector<char> is_prime(sqrt + 1, 1);
    for (int i = 2; i * i <= sqrt; i++)
        if (is_prime[i])
            for (int j = i * i; j <= sqrt; j += i)
                is_prime[j] = 0;

    std::vector<int> primes;
    std::vector<int> next;

    for (int64_t low = 0; low <= limit; low += segment_size)
    {
        std::fill(sieve.begin(), sieve.end(), 1);

        // current segment = interval [low, high]
        int64_t high = std::min(low + segment_size - 1, limit);

        // store small primes needed to cross off multiples
        for (; s * s <= high; s++)
        {
            if (is_prime[s])
            {
                primes.push_back((int) s);
                next.push_back((int)(s * s - low));
            }
        }
        // sieve the current segment
        for (std::size_t i = 1; i < primes.size(); i++)
        {
            int j = next[i];
            for (int k = primes[i] * 2; j < segment_size; j += k)
                sieve[j] = 0;
            next[i] = j - segment_size;
        }

        for (; n <= high; n += 2)
            if (sieve[n - low]) // n is a prime
                count++;
    }

    std::cout << count << " primes found." << std::endl;
} 

Answer 1

这里有一个更简洁的相同算法的公式，这应该使原理更加清晰(完整的、可运行的用于分段大小时间的.cpp @ pastebin的一部分)。这是一个填充的(只有赔率的)筛子，而不是数素数，但所涉及的原则是相同的。下载并运行.cpp以查看分段大小的影响。基本上，最优的应该是在L1缓存大小为您的CPU。太小，并且由于增加的回合数的开销开始占主导地位；太大，你将受到L2和L3缓存的较慢时间的惩罚。另见分割如何提高Eratosthenes筛的运行时间？。

void initialise_packed_sieve_4G (void *data, unsigned segment_bytes = 1 << 15, unsigned end_bit = 1u << 31)
{
   typedef std::vector<prime_and_offset_t>::iterator prime_iter_t;
   std::vector<prime_and_offset_t> small_factors;

   initialise_odd_primes_and_offsets_64K(small_factors);

   unsigned segment_bits = segment_bytes * CHAR_BIT;
   unsigned partial_bits = end_bit % segment_bits;
   unsigned segments     = end_bit / segment_bits + (partial_bits != 0);

   unsigned char *segment = static_cast<unsigned char *>(data);
   unsigned bytes = segment_bytes;

   for ( ; segments--; segment += segment_bytes)
   {
      if (segments == 0 && partial_bits)
      {
         segment_bits = partial_bits;
         bytes = (partial_bits + CHAR_BIT - 1) / CHAR_BIT;
      }

      std::memset(segment, 0, bytes);

      for (prime_iter_t p = small_factors.begin(); p != small_factors.end(); ++p)
      {
         unsigned n = p->prime;
         unsigned i = p->next_offset;

         for ( ; i < segment_bits; i += n)
         {
            set_bit(segment, i);
         }

          p->next_offset = i - segment_bits;
      }
   }
}

如果每个分段都没有记住偏移量，那么每次都必须使用至少一个除法和一个乘法来重新计算每一个重新计算的索引，再加上条件项或严重的比特欺骗。当筛选完整的2^32数字范围(每个32 KBytes的8192段)时，至少有53,583,872个缓慢的除法和相同数量的较快的乘法；这大约是在初始化一个完整的2^32筛子所需的时间上增加了大约1秒(只有厄特索提尼为2^31位)。

下面是一些实际的代码，这些代码来自我的一个旧筛，它使用了这种“重构”的数学方法：

for (index_t k = 1; k <= max_factor_bit; ++k)
{
   if (bitmap_t::traits::bt(bm.bm, k))  continue;

   index_t n = (k << 1) + 1;     // == index_for_value(value_for_index(k) * 2) == n
   index_t i = square(n) >> 1;   // == index_for_value(square(n))

   if (i < offset)
   {
      i += ((offset - i) / n) * n;
   }

   for ( ; i <= new_max_bit; i += n)
   {
      bitmap_t::traits::bts(bm.bm, i); 
   }
}

对于完整的筛子(VC++)，这大约需要5.5秒；使用相同的编译器，首先显示的代码只需4.5秒，或者使用gcc 4.8.1 (MinGW64)的代码只需3.5秒。

下面是gcc的计时：

sieve bits = 2147483648 (equiv. number = 4294967295)

segment size    4096 (2^12) bytes ...   4.091 s   1001.2 M/s
segment size    8192 (2^13) bytes ...   3.723 s   1100.2 M/s
segment size   16384 (2^14) bytes ...   3.534 s   1159.0 M/s
segment size   32768 (2^15) bytes ...   3.418 s   1198.4 M/s
segment size   65536 (2^16) bytes ...   3.894 s   1051.9 M/s
segment size  131072 (2^17) bytes ...   4.265 s    960.4 M/s
segment size  262144 (2^18) bytes ...   4.453 s    919.8 M/s
segment size  524288 (2^19) bytes ...   5.002 s    818.9 M/s
segment size 1048576 (2^20) bytes ...   5.176 s    791.3 M/s
segment size 2097152 (2^21) bytes ...   5.135 s    797.7 M/s
segment size 4194304 (2^22) bytes ...   5.251 s    780.0 M/s
segment size 8388608 (2^23) bytes ...   7.412 s    552.6 M/s

digest { 203280221, 0C903F86, 5B253F12, 774A3204 }

注意:从那个时候起，一个额外的秒可以通过一个叫做“预选”的技巧被剃掉，也就是把一个预先计算好的图案放进位图中，而不是在开始的时候对它进行归零。这使得gcc的时间缩短到2.1秒，对于全筛网，使用这是早期.cpp的被黑副本。此技巧与高速缓存大小块中的分段筛选一起非常好地工作。

Answer 2

我不是这方面的专家，但直觉告诉我：

1. 极限筛搜索表 适应CPU的L1缓存，以充分利用当前硬件体系结构的性能提升的好处。
2. next向量 如果您想分割筛子，那么您必须记住每个已筛选的质数的最后一个索引，例如：

0 1 2 3 4 5 6 7维0 1 2 3 4 6 7 x 0 1 2 3 5 6 7

- sieved primes: 2,3,5
- segment size: 8

0 1 3 4 5 6 7链段每个素数的x_5_x_x_^ //下值偏移量

所以当填充下一段时，你继续顺利地.