C++ константа, складывающая цикл для простых чисел
Взглянув на предыдущие вопросы 1, 2, мне стало интересно, могу ли я заставить компилятор выполнить постоянное свертывание для следующего кода, который печатает простые числа.
#include <iostream>
using namespace std;
inline bool is_prime(int n)
{
if(n<2)
return false;
for(int i=2;i*i<=n;i++)
if(n%i==0)
return false;
return true;
}
int main()
{
for(int i=0;i<20;i++)
if(is_prime(i))
cout<<i<<endl;
return 0;
}
И я строю это через:
g++ -O3 -S main.cpp -o main.asm
В результате несколько:
2,3,5,7,11,13,17,19
Я хотел бы заставить компилятор взглянуть на код, похожий на
for(int x:{2,3,5,7,11,13,17,19})
cout<<x<<endl;
или же
cout<< 2 <<endl;
cout<< 3 <<endl;
cout<< 5 <<endl;
cout<< 7 <<endl;
cout<< 11 <<endl;
cout<< 13 <<endl;
cout<< 17 <<endl;
cout<< 19 <<endl;
Но чтение сборки показывает, что ничего не происходит.
Я даже использовал __builtin_expect но это не сработало.
Есть ли способ заставить оптимизатор компилятора читать цикл for и использовать преимущество в том, что выходные данные известны?
Я хотел бы сделать это без использования шаблонного метапрограммирования.
PS. Моя настоящая цель - просто протестировать компилятор, а не эффективный метод вычисления простых чисел. Я просто хочу показать своим друзьям, насколько мощным является компилятор C++.
Если разделение is_prime Это вызывает беспокойство, я положил все внутри основного и никакой разницы не наблюдалось:
#include <iostream>
using namespace std;
int main()
{
for(int n=2;n<20;n++)
{
bool is_prime=true;
for(int i=2;i*i<=n;i++)
if(n%i==0)
{
is_prime=false;
break;
}
if(is_prime)
cout<<n<<endl;
}
return 0;
}
Есть еще один пример, который не оправдывает компилятор:
#include <iostream>
#include <vector>
using namespace std;
int prime_after6000()
{
int n=6000;
do
{
bool is_prime=true;
for(int i=2;i*i<=n;i++)
if(n%i==0)
{
is_prime=false;
break;
}
if(is_prime)
return n;
n++;
}while(true);
}
int main()
{
cout<<prime_after6000()<<endl;
return 0;
}
монтаж:
...
main:
.LFB1907:
.cfi_startproc
subq $8, %rsp
.cfi_def_cfa_offset 16
movl $6000, %esi ;;;;;;;;;;;;;;;;;;;; bad
.L18:
testb $1, %sil
je .L15
movl $2, %ecx
jmp .L16
.p2align 4,,10
.p2align 3
.L17:
movl %esi, %eax
cltd
idivl %ecx
testl %edx, %edx
je .L15
.L16:
addl $1, %ecx
movl %ecx, %eax
imull %ecx, %eax
cmpl %esi, %eax
jle .L17
movl $_ZSt4cout, %edi
call _ZNSolsEi
movq %rax, %rdi
call _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_
xorl %eax, %eax
addq $8, %rsp
.cfi_remember_state
.cfi_def_cfa_offset 8
ret
.p2align 4,,10
.p2align 3
.L15:
.cfi_restore_state
addl $1, %esi
jmp .L18
.cfi_endproc
.LFE1907:
.size main, .-main
.p2align 4,,15
.type _GLOBAL__sub_I__Z15prime_after6000v, @function
_GLOBAL__sub_I__Z15prime_after6000v:
...
1 ответ
Здесь есть фундаментальное недопонимание компиляторов. Давайте внимательно рассмотрим программу, которую вы написали, и подумаем о том, что вы ожидаете от компилятора.
Основной характеристикой программы является то, что она не принимает никаких входных данных, но выдает выходные данные, записывая в cout, Имейте в виду, что is_prime функция не является встроенной в компилятор; компилятор рассматривает это как просто еще одну функцию. Это важно, и я вернусь к этому позже.
Как компилятор преобразует программу так, как вы описали? Как это может сделать что-то подобное? То есть, как компилятор может преобразовать эти два вложенных цикла в простую последовательность операторов, которые записывают целые числа в cout? Единственный способ, которым он может это сделать, - выполнить программу, чтобы выяснить все значения, которые должны быть записаны в cout,
Это не имеет никакого смысла, не так ли? Давайте посмотрим на общую картину и рассмотрим все программы (или последовательности операторов), которые имеют одинаковую характеристику; те, которые не принимают никакого ввода, но испускают вывод. Возникает вопрос: почему компилятор не выполняет исходный код и не просто генерирует код, записывающий выходные значения? По следующим причинам:
- Что если выполнение программы занимает слишком много времени? Что, если в нем была ошибка, которая заставляла его работать в течение неожиданного количества времени? Нет даже гарантии, что программа когда-нибудь остановится. Что именно должен делать компилятор?
- В конечном счете, цель компилятора не в том, чтобы выполнить исходный код, а в том, чтобы создать функционально эквивалентный нативный код, который потенциально оптимизирован. В конце концов, если программа не принимает никаких входных данных (например, ваш код), вы можете просто скомпилировать код и запустить его один раз, чтобы увидеть выходные данные. Код должен быть выполнен в любом случае, компилятором или запуском исполняемого двоичного файла, и в любом случае это займет одинаковое количество времени. В обоих случаях код должен быть скомпилирован и выполнен. Так что такая оптимизация не добавляет реальной ценности. Тем не менее, это отличается от шаблонов, которые должны быть сведены компилятором к обычному коду во время компиляции. Кроме того, интерпретация была бы лучшей моделью выполнения для таких программ. Вы не хотите беспокоиться о компиляции кода? Идите вперед и используйте интерпретатор Python или любой другой интерпретатор.
- Реализация такой оптимизации может быть трудной или невозможной в целом. Что если механизм, использованный для создания выходных данных, имеет побочные эффекты, которые могут изменить будущие выходные значения? Компилятор точно не знает, что происходит, когда вы пишете
cout, Стандартный поток вывода может быть перенаправлен на что-то странное. Таким образом, программы, которые не принимают никакого ввода, не обязательно проще для компилятора оптимизировать.
Тем не менее, простые куски кода, которые могут быть оценены за очень ограниченное количество времени, действительно оцениваются компилятором. Эта оптимизация называется постоянным сворачиванием. Куски кода, которые не влияют на состояние программы, могут быть удалены без их выполнения. Например, если вы удалили cout<<i<<endl; компилятор просто оптимизирует оставшуюся часть кода. Это называется устранением мертвого кода. Компиляторы выполняют эти оптимизации, потому что они могут выполняться компилятором систематическим образом и потому, что они очень эффективны на реальных кодовых базах.
Но что произойдет, если is_prime функция была присуща компилятору? В этом случае компилятор, вероятно, будет иметь встроенную таблицу часто используемых простых чисел и очень быструю реализацию тестирования простоты. Затем вы можете ожидать от компилятора развернуть loop в основной функции несколько раз, может быть, даже полностью, содержащий только выходные операторы, по существу выполняя преобразование, которое вы ищете.