Суть в том, что а) эксперимент здесь не нужен; б) эксперимент смоделирован неверно.
Не нужен он потому, что выводы, которые вы делаете, как бы, из эксперимента можно сделать, исходя лишь из понимания того, как работает процессор. Т.е. на основе одной лишь теории. Вообще без практического эксперимента. Разумеется, процессоры оптимизированы под типовой сценарий, который выполняется в большинстве программ. В таком типовом сценарии IF почти всегда стоит 0. Если же у вас особая специфика и условные переходы в вашей программе непредсказуемы, то, разумеется, вашей программе эти оптимизации ничем не помогают.
А смоделирован эксперимент неверно, потому что он не учитывает параллельность работы нескольких конвейеров. Вот вы говорите про видеокарты. Соответственно, про конвейеры должны знать. И хотя напрямую сравнивать видеокарты с обычными процессорами в этом смысле нельзя. В видеокартах этих конвейеров тысячи. Но и вообще никак не учитывать этот вопрос в эксперименте тоже нельзя, потому что в обычном современном процессоре конвейеров десятки. И они намного сложнее и эффективнее тех, что в видеокартах. Внутри конвейера ассемблерные инструкции могут менять последовательность своего исполнения, могут разбиваться на несколько этапов, чтобы поменять последовательность можно было хотя бы у этих отдельных этапов. Это всё вносит такую суровую неопределённость в процесс, что сама идея эксперимента, призванного исследовать в таких условиях отдельный IF, смехотворна. Это все равно, как крутить рулетку, пытаясь экспериментальным образом выявить распределение вероятности попадания шарика на определённые числа в ситуации, когда гравитация постоянно меняется и влияет на шарик в каждый момент времени непредсказуемым образом. Маленький ничтожный шарик — это IF, вклад которого в общий тайминг вы пытаетесь исследовать. А гравитация — это оптимизатор, распределяющий работу по конвейерам. Да, гравитация вроде бы не видна и кажется, что её нет. Но её влияние то, что происходит с шариком, более чем существенно.
Но я и не говорил, что оно всегда 0 тактов. Мой первый коммент состоял не только из первого предложения. Фактически, уже со второго предложения начинается объяснение, почему иногда может быть не 0. Естественно, если вы будете специально запутывать предсказатель, то не 0 тактов будет чаще. Но в реальных программах входные данные, как правило, не запутаны. И значит стоимость ветвления в среднем близка к нулю. И обычно можно не беспокоиться о том, что у тебя в программе есть лишний IF, который можно было бы убрать, придумав какой-нибудь изощрённый алгоритм.
Одним предложением это вряд ли можно сформулировать. Важен не размер константы, а количество значащих разрядов, а иногда и конкретное значение. Например, умножение на 11 можно сделать вообще без умножения. В десятичной системе это часто можно сделать в уме: добавить справа ноль, умножив таким образом на 10, и прибавить к результату операнд. Для двоичной системы тоже несложно придумать алгоритм без умножения: добавить к операнду три нуля, прибавить операнд с двумя добавленными нулями и вычесть операнд. Если я смог придумать такой алгоритм за 10 секунд, то разработчики процессора скорее всего тоже додумались до такой оптимизации за много лет работы и встроили её в блок, выполняющий умножение.
Возможно, я что-то неправильно понял. Мне показалось, что вы каким-то образом обосновываете свою правоту ссылкой на опыт. Это выглядело как заход с козырей. Естественно, я был вынужден ответить тоже козырем. Любой подобный разговор чем-то похож на преферанс, где отвечать нужно той же мастью. А из козырей у меня, к сожалению, есть только старшие карты — туз и король.
Константа разная, поэтому и время работы разное. Операция умножения выполняется за разное время, которое зависит от операндов.
К сожалению, этот вопрос никак не связан с вашим экспериментом. (Хотя я понимаю, что вы считаете иначе.) Эти два цикла можно сравнивать, потому что их потенциальная возможность распараллеливания на несколько конвейеров одинакова. А у вас в эксперименте сравниваются два цикла с разным потенциалом к распараллеливанию. В том варианте, где есть тестируемая функция, каждая итерация потенциально может выполняться на двух конвейерах параллельно. На первый конвейер уходит вычисление нового значения a, на второй — выполнение тестируемой функции, которое от нового значения a не зависит. Грубо говоря, выполнение той функции, которую вы тестируете, происходит параллельно с вычислением нового значения по формуле. Но только тогда, когда дополнительный свободный конвейер есть. Но даже тогда когда его нет, выполнение функции необязательно происходит на том же конвейере, что и вычисление формулы. Возможно, свободный конвейер появится в середине вычисления формулы. Это абсолютно непредсказуемый процесс. А то, что он ещё и выполняется очень много раз в цикле, само по себе сделало бы его ещё более непредсказуемым, если бы это было возможно.
Удивительно, что после столь подробных разъяснений, вы всё ещё не понимаете сути проблемы.
Выяснять ничего не будем. Понятно, что я круче и по числу лет и по качеству опыта. Но заметьте, не я начал делать упор на свой опыт, пытаясь что-то обосновать. Это вы начали. Я про опыт заговорил лишь для того, чтобы напомнить вам, что опыт есть не только у вас.
А я, основываясь на своём опыте, считаю, что такая корреляция могла бы быть лишь в том случае, если бы в процессоре не было бы оптимизации ветвлений через предсказание переходов. При этом мой опыт больше и лучше вашего. Я занимаюсь программированием только на С++ более 15 лет. А до этого писал на чистом С и ассемблере. Так что вы совершенно напрасно придаёте такое значение своему опыту в нашем с вами разговоре. По сравнению с моим он незначителен (считайте его погрешностью).
То, что вы не привели никакой модели эксперимента, — это не оправдание, а скорее отягчающее обстоятельство. Должны были привести, если считаете, что эта модель не следует однозначно из текста программы. Эксперимент, который не имеет никакой модели, не имеет и смысла.
На самом деле, модель вашего эксперимента вытекает из текста программы. Когда я якобы приписал вам цель и модель, я их не выдумал, а прочитал в программе. В ней очень чётко видно, что именно вы пытаетесь измерить. И не менее чётко видно главную ошибку. Вы не учитываете наличие ветвления в точке, где проверяется условие выхода из цикла, которое очень хорошо оптимизируется предсказателем переходов путём распараллеливания цикла на несколько конвейеров. Чтобы доказать состоятельность вашей модели, просто покажите пальцем, где и как вы учитываете то, что это ветвление приведёт к совершенно разным временным параметрам в случае разного объёма параллельной работы непосредственно в теле цикла. На всякий случай скажу, что слова «совершенно разные» означают не то, что они не равны, а то, что они не коррелируют.
Зачем вы всё это мне объясняете? Это всё понятно из текста программы. Проблема в другом. Не в том, что я не понимаю, что вы хотите измерить, а в том, что вы реально измеряете не то, что хотите. Понимаете? Мысленная модель вашего эксперимента не соответствует тому, как это на самом деле выполняется в процессоре с предсказанием условных переходов. В вашей модели сама циклическая конструкция никак не влияет на вызываемую внутри функцию. Вы просто вычитаете время, затраченное на цикл, из общего времени. В действительности же при выполнении в цикле таких простейших функций конструкция цикла оказывается неразделимо переплетена с самой функцией. Когда вы убираете из цикла вызов функции, процесс выполнения самой циклической конструкции меняется очень существенно. Проще говоря, вы не можете вычислить (А-С). Когда вы измеряете A, в него в качестве составляющей входит время, которое вы обозначаете как С. А когда вы пытаетесь измерить это С отдельно (чтобы вычесть его из A), у вас реально измеряется время, которое даже не С-штрих… это просто другое время — D… оно никак не связано с тем С, которое входит в А. Возможно, какая-то связь между C и D есть, но скорее всего даже разработчики процессоров не сразу скажут, какая именно и есть ли связь вообще.
Нигде не говорил подобного. Я отрицаю именно то, что вы на самом деле утверждаете. То, что замер не является точным, — понятно. Это само собой. Речь идёт о том, что он также не является ни чистым, ни почти чистым. Условия замера в случае «пустого» цикла и в случае цикла с функцией совершенно разные.
Это я понял. И из моего предыдущего комментария видно, что я это понял. Я назвал цикл пустым только потому, что соответствующий этому циклу тайминг у вас сохраняется в переменную empty.
Пока вам удалось показать это лишь с опорой на предположение о том, что будто бы вам удаётся измерять время работы функции в цикле отдельно от времени работы самой циклической конструкции. Это не так. Именно поэтому я и начал говорить о способе измерения времени. Я считаю, что измерить время работы настолько крохотных функций путём многократного их повторения в цикле на современном процессоре вообще невозможно. Тем более при использовании ключа -O3.
Это некорректно. Когда вы убираете из цикла вызов тестируемой функции, выполнение кода распределяется по конвейерам процессора совсем по-другому. Условие продолжения цикла (while (a != 0)) — это тоже ветвление. Процессор начинает выполнять следующую итерацию цикла ещё до того, как вычислит формулу, в надежде на то, что a действительно не будет равно нулю. В случае пустого цикла каждая следующая итерация цикла использует один дополнительный конвейер. Пока предыдущее значение a ещё не готово, на этом конвейере уже можно делать всё, что не зависит от a: 1) выбрать какие именно из блоков умножения и сложения будут использованы (и тех и других много); 2) загрузить в них обе константы (19993 и 1); 3) подготовить два временных места для размещения результатов умножения и сложения (внутренних для конвейера); 4) хрен знает что ещё (конвейер делает много такого, что не сразу приходит в голову). А когда в цикле есть ещё и функция, которая тоже зависит от a, то каждая следующая итерация задействует два дополнительных конвейера. Один делает всё то же самое, что и в случае пустого цикла, а второй параллельно начинает выполнять тестируемую функцию и делает всю возможную работу, которую можно сделать до того, как реально упрётся в отсутствие значения a, вычисленного на предыдущей итерации. Короче говоря, я хочу сказать, что замер на пустом цикле вообще никак не соотносится с замером на цикле с тестовой функцией.
Не вижу, чтобы в программе измерялось время вычисления нового значения по формуле. Там измеряется только общее время работы всего цикла. Да это и невозможно сделать. На сам замер уйдёт несравнимо больше времени, чем на вычисление формулы.
Эта разница объясняется иначе. Ветвление тут ни при чём. Это другая оптимизация, которая относится к циклам. Когда оптимизатор видит, что в коде есть цикл, в котором переменная монотонно возрастает/убывает, он переделывает код таким образом, чтобы эта переменная всегда была в регистре. И прямо в регистре он её инкрементит/декрементит, не перекладывая постоянно из регистра в память/кэш и обратно.
Ветвление на современном процессоре стоит 0 тактов. В оптимистичном сценарии. Причём ничего не стоит не только сам if, но и условие внутри него. Это возможно благодаря так называемому предсказанию переходов. Но это название не более, чем маркетинговый трюк. Никакого предсказания в строгом смысле этого слова в процессоре не делается. Просто одновременно с вычислением условия на соседнем конвейере начинается выполнение той ветки, которая будет выполнена в случае true. Таким образом, к тому моменту, когда условие будет реально просчитано, первая ветка уже будет выполнена ровно на столько тактов, сколько потребовалось на вычисление условия. Конечно, если окажется, что условие равно false, то результаты выполнения первой ветки придётся отбросить и начать выполнять вторую ветку с самого начала. Но, во-первых, в компиляторе есть специальная оптимизация. Когда компилятор уверен в том, что наиболее вероятной веткой является else, он тупо переставляет ветки местами и инвертирует условие внутри if. Во-вторых, есть программист, который иногда лучше компилятора знает, какая ветка является более вероятной. Хороший программист всегда ставит наиболее вероятную ветку первой. На тот случай, если оптимизатор в компиляторе не сможет придти к однозначному выводу о необходимости оптимизации. В этом случае оптимизатор просто ничего не меняет и оставляет так, как было у программиста.
А я такое видел однажды. Причём это был сознательный выбор самого разработчика. Он объяснял это тем, что у него IDEA под Linux тормозит сильнее, чем под Windows.
Не нужен он потому, что выводы, которые вы делаете, как бы, из эксперимента можно сделать, исходя лишь из понимания того, как работает процессор. Т.е. на основе одной лишь теории. Вообще без практического эксперимента. Разумеется, процессоры оптимизированы под типовой сценарий, который выполняется в большинстве программ. В таком типовом сценарии IF почти всегда стоит 0. Если же у вас особая специфика и условные переходы в вашей программе непредсказуемы, то, разумеется, вашей программе эти оптимизации ничем не помогают.
А смоделирован эксперимент неверно, потому что он не учитывает параллельность работы нескольких конвейеров. Вот вы говорите про видеокарты. Соответственно, про конвейеры должны знать. И хотя напрямую сравнивать видеокарты с обычными процессорами в этом смысле нельзя. В видеокартах этих конвейеров тысячи. Но и вообще никак не учитывать этот вопрос в эксперименте тоже нельзя, потому что в обычном современном процессоре конвейеров десятки. И они намного сложнее и эффективнее тех, что в видеокартах. Внутри конвейера ассемблерные инструкции могут менять последовательность своего исполнения, могут разбиваться на несколько этапов, чтобы поменять последовательность можно было хотя бы у этих отдельных этапов. Это всё вносит такую суровую неопределённость в процесс, что сама идея эксперимента, призванного исследовать в таких условиях отдельный IF, смехотворна. Это все равно, как крутить рулетку, пытаясь экспериментальным образом выявить распределение вероятности попадания шарика на определённые числа в ситуации, когда гравитация постоянно меняется и влияет на шарик в каждый момент времени непредсказуемым образом. Маленький ничтожный шарик — это IF, вклад которого в общий тайминг вы пытаетесь исследовать. А гравитация — это оптимизатор, распределяющий работу по конвейерам. Да, гравитация вроде бы не видна и кажется, что её нет. Но её влияние то, что происходит с шариком, более чем существенно.
К сожалению, этот вопрос никак не связан с вашим экспериментом. (Хотя я понимаю, что вы считаете иначе.) Эти два цикла можно сравнивать, потому что их потенциальная возможность распараллеливания на несколько конвейеров одинакова. А у вас в эксперименте сравниваются два цикла с разным потенциалом к распараллеливанию. В том варианте, где есть тестируемая функция, каждая итерация потенциально может выполняться на двух конвейерах параллельно. На первый конвейер уходит вычисление нового значения a, на второй — выполнение тестируемой функции, которое от нового значения a не зависит. Грубо говоря, выполнение той функции, которую вы тестируете, происходит параллельно с вычислением нового значения по формуле. Но только тогда, когда дополнительный свободный конвейер есть. Но даже тогда когда его нет, выполнение функции необязательно происходит на том же конвейере, что и вычисление формулы. Возможно, свободный конвейер появится в середине вычисления формулы. Это абсолютно непредсказуемый процесс. А то, что он ещё и выполняется очень много раз в цикле, само по себе сделало бы его ещё более непредсказуемым, если бы это было возможно.
Удивительно, что после столь подробных разъяснений, вы всё ещё не понимаете сути проблемы.
На самом деле, модель вашего эксперимента вытекает из текста программы. Когда я якобы приписал вам цель и модель, я их не выдумал, а прочитал в программе. В ней очень чётко видно, что именно вы пытаетесь измерить. И не менее чётко видно главную ошибку. Вы не учитываете наличие ветвления в точке, где проверяется условие выхода из цикла, которое очень хорошо оптимизируется предсказателем переходов путём распараллеливания цикла на несколько конвейеров. Чтобы доказать состоятельность вашей модели, просто покажите пальцем, где и как вы учитываете то, что это ветвление приведёт к совершенно разным временным параметрам в случае разного объёма параллельной работы непосредственно в теле цикла. На всякий случай скажу, что слова «совершенно разные» означают не то, что они не равны, а то, что они не коррелируют.