Pull to refresh
-1
Karma
0
Rating
  • Followers 5
  • Following 3

День рождения Ершова

Я знаю, что значит «open source». Речь не о том, что программисты старой школы, вышедшие на пенсию, его создали. Но именно они являются причиной столь бурного роста в последние годы.

День рождения Ершова

Я всегда считал, что современный уровень развития open source обусловлен в основном тем, что программисты старой школы вышли на пенсию. И им просто не удалось найти себе более интересное занятие, чем программирование. Раньше я думал, что это произошло неожиданно для всех. Но, оказывается, Ершов уже тогда предвидел, что через тридцать лет будет миллион программистов, которые ничем не будут заняты.

Объяснение эксперимента о ветвлениях, или философские изыскания на тему бенчмарков в вакууме и в… реальности

Вот если бы вы сразу сказали, что отрицательное время в рамках вашего эксперимента имеет смысл, можно было бы сэкономить кучу сил. Тогда я сразу бы понял, что вообще не понимаю вашего замысла. К слову, я и сейчас его не понимаю. Но теперь эксперимент выглядит так, как будто в нём есть какой-то смысл… пусть и непонятный мне.

Объяснение эксперимента о ветвлениях, или философские изыскания на тему бенчмарков в вакууме и в… реальности

Но если вы не пытались делать выводов о скорости работы функции отдельно, то зачем было измерять время работы цикла без функции и вычитать его из времени выполнения цикла с функцией? В чём смысл этой операции? Чтобы понять какая из функций работает быстрее именно в этих конкретных условиях, не нужно специально пытаться нейтрализовать влияние этих условий на результат. Наоборот, нужно сравнивать между собой интегральные замеры, включающие время выполнения как самой функции, так и окружающих её условий.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Поздно. Он уже проверил. И у него получились разные результаты при разных значениях операндов.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Я говорю о людях вообще. Мне не нужно знать, с какими конкретно людьми вы будете иметь дело, чтобы предсказать, какие у вас будут с ними проблемы. У всех людей есть одно общее свойство — они не телепаты. Мой прогноз основан только на этом свойстве людей.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Ну, тогда просто согласимся на том, что обычно условный переход ничего не стоит и париться на счёт него не нужно.

А о чём в действительности был ваш эксперимент, вы расскажете в другой раз. И лучше кому-нибудь другому. Я уже устал от того, что вы мне постоянно пересказываете суть вашего эксперимента разными словами, каждый раз делая акцент на том, что я его неправильно понял, хотя каждый следующий пересказ лишь укрепляет мою уверенность в том, что я правильно понял суть с первого раза.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Добро пожаловать в реальность! В будущем все люди, с которыми вы будете иметь дело, только тем и будут заниматься, что приписывать вам те мысли и цели, которые, как они думают, у вас есть. Телепатов, к сожалению, нет. Но это не мешает людям думать, что они точно знают мысли других. Вам придётся как-то научиться жить с этим. И не факт, что сможете. У многих гиков это не получается и со временем они начинают не любить окружающих за то, что их никто не понимает.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Ну, на это я даже не знаю, что сказать. Эксперимент совершенно точно выглядит как эксперимент по исследованию ветвлений. Понятно, что на примере каких-то конкретных функций, и что сами эти функции не имеют значения. Но предметом исследование определённо является само ветвление и его влияние на тайминг. Если это на самом деле не так, и реальная цель вашего эксперимента состоит, например, в исследовании того, сколько человек поведутся на призыв и начнут запускать бессмысленный и некорректный бенчмарк на своих машинах, то тогда у меня нет возражений по существу. Если эксперимент был социальным, то он действительно удался.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Суть в том, что а) эксперимент здесь не нужен; б) эксперимент смоделирован неверно.

Не нужен он потому, что выводы, которые вы делаете, как бы, из эксперимента можно сделать, исходя лишь из понимания того, как работает процессор. Т.е. на основе одной лишь теории. Вообще без практического эксперимента. Разумеется, процессоры оптимизированы под типовой сценарий, который выполняется в большинстве программ. В таком типовом сценарии IF почти всегда стоит 0. Если же у вас особая специфика и условные переходы в вашей программе непредсказуемы, то, разумеется, вашей программе эти оптимизации ничем не помогают.

А смоделирован эксперимент неверно, потому что он не учитывает параллельность работы нескольких конвейеров. Вот вы говорите про видеокарты. Соответственно, про конвейеры должны знать. И хотя напрямую сравнивать видеокарты с обычными процессорами в этом смысле нельзя. В видеокартах этих конвейеров тысячи. Но и вообще никак не учитывать этот вопрос в эксперименте тоже нельзя, потому что в обычном современном процессоре конвейеров десятки. И они намного сложнее и эффективнее тех, что в видеокартах. Внутри конвейера ассемблерные инструкции могут менять последовательность своего исполнения, могут разбиваться на несколько этапов, чтобы поменять последовательность можно было хотя бы у этих отдельных этапов. Это всё вносит такую суровую неопределённость в процесс, что сама идея эксперимента, призванного исследовать в таких условиях отдельный IF, смехотворна. Это все равно, как крутить рулетку, пытаясь экспериментальным образом выявить распределение вероятности попадания шарика на определённые числа в ситуации, когда гравитация постоянно меняется и влияет на шарик в каждый момент времени непредсказуемым образом. Маленький ничтожный шарик — это IF, вклад которого в общий тайминг вы пытаетесь исследовать. А гравитация — это оптимизатор, распределяющий работу по конвейерам. Да, гравитация вроде бы не видна и кажется, что её нет. Но её влияние то, что происходит с шариком, более чем существенно.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Но я и не говорил, что оно всегда 0 тактов. Мой первый коммент состоял не только из первого предложения. Фактически, уже со второго предложения начинается объяснение, почему иногда может быть не 0. Естественно, если вы будете специально запутывать предсказатель, то не 0 тактов будет чаще. Но в реальных программах входные данные, как правило, не запутаны. И значит стоимость ветвления в среднем близка к нулю. И обычно можно не беспокоиться о том, что у тебя в программе есть лишний IF, который можно было бы убрать, придумав какой-нибудь изощрённый алгоритм.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Одним предложением это вряд ли можно сформулировать. Важен не размер константы, а количество значащих разрядов, а иногда и конкретное значение. Например, умножение на 11 можно сделать вообще без умножения. В десятичной системе это часто можно сделать в уме: добавить справа ноль, умножив таким образом на 10, и прибавить к результату операнд. Для двоичной системы тоже несложно придумать алгоритм без умножения: добавить к операнду три нуля, прибавить операнд с двумя добавленными нулями и вычесть операнд. Если я смог придумать такой алгоритм за 10 секунд, то разработчики процессора скорее всего тоже додумались до такой оптимизации за много лет работы и встроили её в блок, выполняющий умножение.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Возможно, я что-то неправильно понял. Мне показалось, что вы каким-то образом обосновываете свою правоту ссылкой на опыт. Это выглядело как заход с козырей. Естественно, я был вынужден ответить тоже козырем. Любой подобный разговор чем-то похож на преферанс, где отвечать нужно той же мастью. А из козырей у меня, к сожалению, есть только старшие карты — туз и король.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Константа разная, поэтому и время работы разное. Операция умножения выполняется за разное время, которое зависит от операндов.

К сожалению, этот вопрос никак не связан с вашим экспериментом. (Хотя я понимаю, что вы считаете иначе.) Эти два цикла можно сравнивать, потому что их потенциальная возможность распараллеливания на несколько конвейеров одинакова. А у вас в эксперименте сравниваются два цикла с разным потенциалом к распараллеливанию. В том варианте, где есть тестируемая функция, каждая итерация потенциально может выполняться на двух конвейерах параллельно. На первый конвейер уходит вычисление нового значения a, на второй — выполнение тестируемой функции, которое от нового значения a не зависит. Грубо говоря, выполнение той функции, которую вы тестируете, происходит параллельно с вычислением нового значения по формуле. Но только тогда, когда дополнительный свободный конвейер есть. Но даже тогда когда его нет, выполнение функции необязательно происходит на том же конвейере, что и вычисление формулы. Возможно, свободный конвейер появится в середине вычисления формулы. Это абсолютно непредсказуемый процесс. А то, что он ещё и выполняется очень много раз в цикле, само по себе сделало бы его ещё более непредсказуемым, если бы это было возможно.

Удивительно, что после столь подробных разъяснений, вы всё ещё не понимаете сути проблемы.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Выяснять ничего не будем. Понятно, что я круче и по числу лет и по качеству опыта. Но заметьте, не я начал делать упор на свой опыт, пытаясь что-то обосновать. Это вы начали. Я про опыт заговорил лишь для того, чтобы напомнить вам, что опыт есть не только у вас.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

А я, основываясь на своём опыте, считаю, что такая корреляция могла бы быть лишь в том случае, если бы в процессоре не было бы оптимизации ветвлений через предсказание переходов. При этом мой опыт больше и лучше вашего. Я занимаюсь программированием только на С++ более 15 лет. А до этого писал на чистом С и ассемблере. Так что вы совершенно напрасно придаёте такое значение своему опыту в нашем с вами разговоре. По сравнению с моим он незначителен (считайте его погрешностью).

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

То, что вы не привели никакой модели эксперимента, — это не оправдание, а скорее отягчающее обстоятельство. Должны были привести, если считаете, что эта модель не следует однозначно из текста программы. Эксперимент, который не имеет никакой модели, не имеет и смысла.

На самом деле, модель вашего эксперимента вытекает из текста программы. Когда я якобы приписал вам цель и модель, я их не выдумал, а прочитал в программе. В ней очень чётко видно, что именно вы пытаетесь измерить. И не менее чётко видно главную ошибку. Вы не учитываете наличие ветвления в точке, где проверяется условие выхода из цикла, которое очень хорошо оптимизируется предсказателем переходов путём распараллеливания цикла на несколько конвейеров. Чтобы доказать состоятельность вашей модели, просто покажите пальцем, где и как вы учитываете то, что это ветвление приведёт к совершенно разным временным параметрам в случае разного объёма параллельной работы непосредственно в теле цикла. На всякий случай скажу, что слова «совершенно разные» означают не то, что они не равны, а то, что они не коррелируют.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

К сожалению, всё ровно наоборот. Традиционно доказывать нужно именно соответствие модели эксперименту. Не наоборот.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

Зачем вы всё это мне объясняете? Это всё понятно из текста программы. Проблема в другом. Не в том, что я не понимаю, что вы хотите измерить, а в том, что вы реально измеряете не то, что хотите. Понимаете? Мысленная модель вашего эксперимента не соответствует тому, как это на самом деле выполняется в процессоре с предсказанием условных переходов. В вашей модели сама циклическая конструкция никак не влияет на вызываемую внутри функцию. Вы просто вычитаете время, затраченное на цикл, из общего времени. В действительности же при выполнении в цикле таких простейших функций конструкция цикла оказывается неразделимо переплетена с самой функцией. Когда вы убираете из цикла вызов функции, процесс выполнения самой циклической конструкции меняется очень существенно. Проще говоря, вы не можете вычислить (А-С). Когда вы измеряете A, в него в качестве составляющей входит время, которое вы обозначаете как С. А когда вы пытаетесь измерить это С отдельно (чтобы вычесть его из A), у вас реально измеряется время, которое даже не С-штрих… это просто другое время — D… оно никак не связано с тем С, которое входит в А. Возможно, какая-то связь между C и D есть, но скорее всего даже разработчики процессоров не сразу скажут, какая именно и есть ли связь вообще.

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

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

Information

Rating
Does not participate
Registered
Activity