Действительно ли избыточный избыточный код эффективен?

Question

Я пытаюсь найти несколько простых чисел с ситом алгоритма греческого парня. У меня есть проблемы с эффективностью. Вот код:

void check_if_prime(unsigned number) 
{ 
    unsigned index = 0; 
    while (primes[index] <= std::sqrt(number)) 
    { 
     if (number % primes[index] == 0) return; 
     ++index; 
    } 
    primes.push_back(number); 
} 

И, потому что я закодирован огромное 2/3/5/7/11/13 простого колеса, код 5795 линия тоскует.

for (unsigned i = 0; i < selection; ++i) 
{ 
    unsigned multiple = i * 30030; 
    if (i!=0) check_if_prime(multiple+1); 
    check_if_prime (multiple+17); 
    check_if_prime (multiple+19); 
    check_if_prime (multiple+23); 
    // ...so on until 30029 
} 

Optimization флаги: -O3, -fexpensive-оптимизационные -march = pentium2

25000000 простых чисел в 20 минут с процессором застрял на 50% (не знаю, почему, пытались в реальном времени приоритет, но Бесполезный сильно меняются). Размер выходного текстового файла составляет 256 МБ (позже будет изменен на двоичный файл).

• Сборник требует времени! Это нормально? Как я могу сделать это быстрее без ущерба для эффективности?
• Это утверждение if в начале цикла for OK? Я читал, если утверждения занимают больше всего.
• Что-либо еще относительно кода, а не алгоритма? Что-нибудь, чтобы сделать это быстрее? Какие заявления быстрее других?
• Может быть, даже большее колесо (до 510510, а не только 30030, черт возьми много линий) скомпилируется в течение дня?

Я хочу найти все простые числа до 2^32, а небольшая оптимизация сэкономит несколько часов и электроэнергии. Заранее спасибо!

EDIT: не ищет алгоритм, добиваясь улучшения кода, если это возможно!

Answer 1

Вот что я могу сказать об исполнении вашей программы:

1. Вероятно, ваш основной проблемой является вызов std::sqrt(). Это функция с плавающей запятой, которая предназначена для полной точности результата, и это определенно занимает довольно много циклов. Я уверен, вы будете гораздо быстрее, если вы используете этот чек вместо:

   while (primes[index]*primes[index] < number) 
   

   Таким образом, вы используете целочисленное умножение, которое тривиально для современных процессоров.

2. Оператор if в начале вашего цикла for() не имеет отношения к производительности. Это не выполняется почти достаточно времени. Ваш внутренний цикл - это цикл while в пределах check_if_prime(). Это то, что вам нужно оптимизировать.

3. Я не вижу, как вы делаете вывод. Есть способы сделать вывод, который может сильно замедлить вас, но я не думаю, что это основная проблема (если это вообще проблема).

4. Размер кода может быть проблемой: ваш процессор имеет кэш команд с ограниченной пропускной способностью. Если ваши 6k-строки не вписываются в кеш-память первого уровня, штраф может быть серьезным. Если бы я был вами, я бы переориентировал колесо, используя данные вместо кода, т.е. е.:

   unsigned const wheel[] = {1, 17, 19, 23, ...}; //add all your 6k primes here 
   for (unsigned i = 0; i < selection; ++i) 
   { 
       unsigned multiple = i * 30030; 
       for(unsigned j = 0; j < sizeof(wheel)/sizeof(*wheel); j++) { 
        check_if_prime(multiple + wheel[j]); 
       } 
   } 
   

Answer 2

Получить это работает под отладчиком, и одношаговый его, инструкция по инструкции, и в каждой точке понять, что он делает, и почему.

Это заставляет вас ходить в ботинке процессора, и вы увидите всю глупость, которую делает нудный программист, , и вы увидите, что вы могли бы сделать лучше.

Это один из способов сделать ваш код как можно быстрее.

Размер программы сам по себе влияет только на скорость, если у вас ее так быстро, что кэширование становится проблемой.

Answer 3

Вот удар в некоторых методов для проверки, является ли число простым:

bool is_prime(unsigned int number) // negative numbers are not prime. 
{ 
    // A data store for primes already calculated. 
    static std::set<unsigned int> calculated_primes; 

    // Simple checks first: 
    // Primes must be >= 2. 
    // Primes greater than 2 are odd. 
    if ( (number < 2) 
     || ((number > 2) && ((number & 1) == 0)) 
    { 
    return false; 
    } 

    // Initialize the set with a few prime numbers, if necessary. 
    if (calculated_primes.empty()) 
    { 
    static const unsigned int primes[] = 
    { 2, 3, 5, 7, 13, 17, 19, 23, 29}; 
    static const unsigned int known_primes_quantity = 
     sizeof(primes)/sizeof(primes[0]); 
    calculated_primes.insert(&primes[0], &primes[known_primes_quantity]); 
    } 
    // Check if the number is a prime that is already calculated: 
    if (calculated_primes.find(number) != calculated_primes.end()) 
    { 
    return true; 
    } 

    // Find the smallest prime to the number: 
    std::set<unsigned int>::iterator prime_iter = 
     calculated_primes.lower_bound(number); 
    // Use this value as the start for the sieve. 
    unsigned int prime_candidate = *prime_iter; 
    const unsigned int iteration_limit = number * number; 
    while (prime_candidate < iteration_limit) 
    { 
    prime_candidate += 2; 
    bool is_prime = true; 
    for (prime_iter = calculated_primes.begin(); 
      prime_iter != calculated_primes.end(); 
      ++prime_iter) 
    { 
     if ((prime_candidate % (*prime_iter)) == 0) 
     { 
     is_prime = false; 
     break; 
     } 
    } 
    if (is_prime) 
    { 
     calculated_primes.insert(prime_candidate); 
     if (prime_candidate == number) 
     { 
     return true; 
     } 
    } 
    } 
    return false; 
} 

Примечание: Это непроверенный код, но демонстрирует некоторые методы для проверки, является ли число простым.