простое число менее 2 миллиардов - использование std :: list снижает производительность

Первое, что нужно сделать, это убедиться, что вы компилируете с включенной оптимизацией. Классы шаблонов стандартной библиотеки c ++ имеют тенденцию работать очень плохо с неоптимизированным кодом, поскольку они генерируют много вызовов функций. Оптимизатор включает большинство этих вызовов функций, что делает их намного дешевле.

std::list является связанным списком. Это в основном полезно, когда вы хотите вставить или удалить элементы случайным образом (т.е. не с конца).

Для случая, когда вы добавляете только конец списка std::list, возникают следующие проблемы:

• Итерация по списку является относительно дорогой, так как код должен следовать указателям на узлы и затем получить данные
• В списке используется гораздо больше памяти, каждому элементу требуется указатель на предыдущий и следующий узлы в дополнение к фактическим данным. В 64-битной системе это равно 20 байтов на элемент, а не 4 для списка int
• Поскольку элементы в списке не являются смежными в памяти, компилятор не может выполнить столько SIMD-оптимизаций и вы будете больше страдать от ошибок кэша ЦП

A std::vector решит все вышеперечисленное, так как его память является смежной, и итерации по ней - просто случай увеличения индекса массива. Вам нужно убедиться, что вы вызываете reserve для вашего вектора в начале с достаточно большим значением, чтобы при добавлении к вектору весь массив не копировался в новый больший массив.

Лучшая оптимизация, чем приведенная выше, - использовать Сито Эратосфена для вычисления ваших простых чисел. Поскольку генерация этого света требует случайного удаления (в зависимости от вашей точной реализации), std::list может работать лучше, чем std::vector, хотя даже в этом случае издержки std::list могут не перевесить его стоимость.

Причина, по которой ваш второй пример занимает больше времени, заключается в том, что вы выполняете std::list.

std::list в C ++ - это связанный список, что означает, что он не использует непрерывную память. Это плохо, потому что для итерации списка вы должны переходить от узла к узлу непредсказуемым образом (к процессору / сборщику). Кроме того, вы, скорее всего, «используете» только несколько байтов каждой кеш-линии. Оперативная память медленная. Извлечение байта из ОЗУ занимает много лота дольше, чем извлечение его из L1. В наши дни процессоры работают быстро, поэтому ваша программа большую часть времени ничего не делает и ожидает поступления памяти.

Вместо этого используйте std::vector. Он хранит все значения один за другим, и итерация очень дешевая. Поскольку вы выполняете итерацию вперед в памяти без скачков, вы используете полную кеш-строку, и ваш модуль предварительной выборки сможет получать дополнительные страницы, прежде чем они понадобятся, потому что ваш доступ к памяти предсказуем.

constexpr int max_prime = 1000000000;
std::bitset<max_prime> *bitset = new std::bitset<max_prime>{};
// Note: Bit SET means NO prime
bitset->set(0);
bitset->set(1);

for(int i = 4; i < max_prime ; i += 2)
    bitset->set(i); // set all even numbers
int max = sqrt(max_prime);
for(int i = 3; i < max; i += 2) { // No point testing even numbers as they can't be prime
    if(!bitset->test(i)) { // If i is prime
        for(int j = i * 2; j < no_primes; j += i)
            bitset->set(j); // set all multiples of i to non-prime
    }
}

time taken:                63.515 seconds
time taken bitset:         1.874 seconds
No of divisions :          1975961174
No of primes found:        5761455
No of primes found bitset: 5761455