В первую очередь, прошу обратить внимание на то, что эксперимент я назвал словом «пробный» – и это не случайно. Я задумал более детальное изучение особенностей разных алгоритмов, а для этого нужна помощь разных людей (хотя бы косвенная – что-то где-то запустить и сказать результат). Чтобы в будущем сложные эксперименты проходили достаточно гладко, нужно потренироваться, проверить вообще принципиальную возможность делать это подобным образом. Сообщество обычно любит пинать за ошибки в методологии исследования или организации, а мне как раз нужны были конструктивные указания на подобные ошибки. Таковые, к счастью, были.
Во-вторых, прошу меня извинить за то, что я забыл про необходимость хаотичного потока данных, из-за этого кому-то пришлось тестировать всё заново и возникла путаница в том, которую именно версию проверил очередной участник. В своей статье про подсчёт единичных битов я очень хорошо помнил о важности случайного потока входных данных, а вот здесь почему-то забыл. Бывает. Но, как я сказал выше, это первая и самая важная для меня причина проведения пробного эксперимента, чтобы меньше ошибиться в серьёзных исследованиях и заблаговременно учесть возможные конструктивные советы.
Теперь поговорим о методологии самого исследования и о том, в чём вообще необходимость тестировать какие-либо функции на скорость. И есть ли она, эта необходимость. Отсюда и начнётся философия.
Пояснение к слову «ветвление»
Другая из моих ошибок, которые я допустил, в том, что я не пояснил что значит ветвление. Обычно меня мало интересуют академические термины, потому что зачастую они не имеют отношения к реальности, а потому приходится наделять многие слова собственным смыслом.
В той статье имелось в виду именно алгоритмическое (или логическое) ветвление, которое неизбежно появляется в логике программы при вычислении логического выражения и последующих действиях в зависимости от результата этого выражения. Таким образом, когда в коде программы мы видим условие, то по логике (именно по человеческой логике) это ветвление. Почему так? Дело в том, что ветвление вообще говоря сложно определить по нормальному, когда логика алгоритма переводится сначала на ЯП, затем компилятор переводит её на машинный язык, а затем сами инструкции процессора переводятся во внутренние, скажем, RISC-инструкции. На одном этапе ветвление есть, а ну другом нет… а потом снова может появиться.
То есть вы можете думать, что ветвления в вашей программе на языке Си нет, а на самом деле оно есть, или наоборот, вы написал код с ветвлением (в логике), а компилятор придумал, как это сделать без ветвлений в коде. Пример:
u64 a, c;
u32 b;
c = a / b;
Ветвления нет. Правда? На самом деле есть (по крайней мере после компилятора VC++ 2015). Дело в том, что при так называемом «2/1»-делении (когда нечто удвоенного размера делится на нечто одинарного размера) результат может иметь как одинарный, так и двойной размер. В первом случае данная процедура деления будет выполняться с одной инструкцией div, во втором случае – с двумя. Так вот, чтобы понять то, по какой ветке пойти при таком делении, нужно рассчитать размер частного и сделать выбор, этот выбор будет одним из ветвлений перед непосредственным делением. Ещё одним выбором может быть, например, проверка на деление на ноль (хотя обычно такой проверки нет). Короче, процедура деления не сводится к обычному div, это весьма сложная процедура. А программист, глядя на эту запись, может думать, что здесь линейный код.
Второй пример. Функция максимума может выглядеть так:
i32 max1 (i32 a, i32 b) {
return a ^ ((a ^ b) & -(a < b));
}
Здесь, очевидно, нет ветвлений на архитектуре x86, наверное, не будет их и на многих других архитектурах, хотя тут есть прямое логическое сравнение двух чисел. То есть по логике ветвление здесь есть, а по коду нет. Однако замените i32 на i64 и скомпилируйте программу в режиме x86. Ветвления сразу появятся. А вот в таком коде:
i32 maxi1 (i32 a, i32 b) {
i32 d = a-b;
return b + (d&(~(d^((a^b)&(d^a))) >> SHIFT));
}
Ветвлений нет в логике и не будет в программе ни при каком фиксированном размере переменной, которую поддерживает компилятор (речь идёт об x86 при правильной компиляции). Поэтому я и называю это единственным методом поиска максимума (из мне известных), который не содержит ветвлений.
К чему это я всё рассказываю?
Основная проблема программистов, которые немного знают о классических методах оптимизации программ, но не очень глубоко в них разбирались: желание избавляться от ветвлений везде, где только можно. Во-первых, это круто и красиво, во-вторых, можно блеснуть в глазах коллег по цеху, в-третьих, прикосновение к магии завораживает, как-то поднимает самооценку и вот вроде бы не зря живешь. Но очень редко в списке причин на самом деле лежит понимание того, как быстро или как медленно будет работать новый код. Избавляясь от ветвления, программист, во-первых, может его породить, а, во-вторых, может замедлить код из-за того, что новый алгоритм более сложен по своей структуре.
Я хотел показать, что каждому доступен простой эксперимент, который покажет, когда нужно и когда не нужно избавляться от ветвлений в логике. Мы берём разные реализации и сравниваем между собой хотя бы на сферических тестах в вакууме… и в этом есть смысл, о чём я и философствую дальше.
Методология эксперимента
Разумеется, что каждый, кто серьёзно занимался оптимизацией программ, обратил внимание на сильную искусственность подобных замеров времени. Смотрите: мы берём функцию, создаём для её работы идеальные условия и тестируем её в этих идеальных условиях. В моём случае таким условием был простейший цикл. По времени работы этого цикла с вызовом функции в нём и по времени работы пустого цикла мы пытаемся узнать об эффективности самой функции… и кому-то могло показаться, что я так и делаю. На самом деле всё не так просто, потому что так делать нельзя.
В реальных условиях ваша функция будет окружена другим набором инструкций, цикл, в котором она будет запускаться, может оказаться более длинным и запутанным и время работы этой функции может оказаться абсолютно другим. В каком-то смысле такие бенчмарки, как у меня, напоминают показуху в каком-нибудь магазине, который решил посетить высокий чиновник: цены в нём неожиданно становятся в 10 раз ниже, а зарплата персонала в 10 раз выше… но ровно до тех пор, пока чиновник не уйдёт из магазина. Так зачем же вообще заниматься этим, если результат не отражает реальность? Потому что если правильно понимать словосочетание «отражает реальность», то всё встанет на свои места.
А дело всё в том, что я не делаю выводов о скорости работы функции отдельно. Я делаю вывод о том, которая из функций будет быстрее, а которая медленнее именно в этих тепличных условиях. При этом меня интересует большой отрыв по скорости, потому как небольшой отрыв часто затирается сложностью других участков программы, а вот большой отрыв гарантирует (по крайней мере, в моём опыте работы), что в реальных условиях разница будет такой же… при это НЕ важно, будет ли сама функция работать в 100 раз дольше по сравнению с идеальными условиями – выигрывать у более медленной она будет приблизительно с тем же отрывом, что я получаю в этих идеальных условиях. Честно скажу, я не знаю, так ли это в обычных бытовых задачах, но в научных расчётах, когда нужны миллионы машинных часов счёта, это можно считать аксиомой. В моей практике было только так и никак иначе. Теперь давайте попробуем философски осмыслить вообще ценность любого исследования.
В нашем мире значительная часть экспериментов (даже социальных) не лишена того недостатка, что все они искусственные, но по результатам этих экспериментов люди всё равно могут весьма достоверно предсказать некую ситуацию в реальности. Скажем, возьмите то же соревнование по стайерскому бегу. Несколько людей одеваются в беговые трусы, майку и «тапки» (иногда с шипами), делают специальную разминку, выходят на старт и начинают бежать по идеально гладкой и мягкой дорожке, например, 5 км. Это идеальные условия, в которых мастер спорта проходит дистанцию за 14 минут. Если нацепить на мастера валенки и заставить надеть шубу, то он пробежит ту же дистанцию медленнее, особенно по грязи и лужам, скажем, за 18-20 минут… но это всё равно быстрее, чем обычный неподготовленный человек пробежит даже в идеальных условиях. А в равных условиях у него вообще ноль шансов. Можно взять и другие обычные условия: нужно добежать до уходящего автобуса (или успеть на «зелёный» на пешеходном переходе). Простой вопрос: у кого больше шансов успеть на него при достаточно большой дистанции – у мастера по стайерскому бегу или у обычного человека? Понятно, что у первого, причём шансы практически не меняются в зависимости от формы одежды и многих других условий. Однако данное предположение (причём весьма надёжное) мы делаем только на основе того, что видели, как мастера бегают 5 км за 14 минут. Мы просто делаем предсказание на основе знаний, полученных в идеальных условиях. И с огромной вероятностью эти предсказания будут истинными в условиях реальных.
В мире программирования, конечно, всё гораздо сложнее. Например, с чего это я взял, что мои условия, описанные выше, идеальные? Это я их так назвал, а может оказаться, что в реальной программе компилятор найдет способ так «размазать» мою функцию по коду программы, что время её работы станет равным нулю (она будет вычислена параллельно с какими-нибудь сложными операциями неподалёку). Да, такое может быть, и при жёсткой оптимизации программ опытный программист попробует так изменить алгоритм, чтобы максимально сбалансировать команды для одновременного исполнения инструкций, входящих в них, а процессор потом на ходу перемешает эти инструкции ещё лучше. Но это другой разговор, потому что подобные оптимизации не выполняются отдельно для отдельных простых функций вроде sign или abs, всё делается иначе: мы берём узкий участок кода и смотрим на него целиком, на то, можно ли с ним что-то сделать (даже, может, полностью переклеить), чтобы его логический смысл остался прежним, но сложность уменьшилась. У нас ситуация иная: мы хотим выяснить то, насколько быстрой будет та или иная реализация отдельной небольшой функции, предполагая, что эта отдельная небольшая функция будет достаточно сильно нагружена в некотором процессе, но не настолько, чтобы как-то жёстко её оптимизировать и размазывать её по каким-то другим участкам программы.
Именно так часто и пишутся обычные эффективные программы: когда алгоритмическая эффективность устраивает программиста, он достигает дополнительной практической эффективности тем, что использует хорошо оптимизированные отдельные функции, но глубже не лезет, потому что это может оказаться накладно, и ему проще увеличить вдвое число ядер, чем потратить уйму времени, чтобы добиться такого же ускорения на прежнем их количестве. Вот эти хорошо оптимизированные функции пишутся… внимание… под идеальные условия! Та же библиотека MPIR для длинной арифметики, посмотрите код и увидите там множество реализаций функций низкого уровня, заточенных под разные процессоры, причём MPIR будет выигрывать у вашего самопального кода длинной арифметики как на тестах вроде моих (сферических в вакууме), так и в реальных условиях, когда данные имеют не очень предсказуемый характер (понятно, что победить MPIR можно и очень легко, когда заранее знаешь некоторые серьёзные особенности входящих чисел, но я говорю о том, когда не знаешь). И таких примеров в научном мире полно. Функция factor в Maple будет рвать вашу самопальную функцию факторизации полиномов как в идеальных условиях, когда вы измеряете время работы путём многократного повторения случайных тестов одного за другим, так и в реальных программах, где факторизация занимает ощутимую долю ваших вычислений (например, при какой-нибудь работе с рациональными дробями). Конечно, я допускаю то, что вы можете соревноваться с factor из Maple, но таких людей очень мало, а речь идёт об обычных пользователя, которые хотят написать более-менее хорошую программу, но затрудняются в выборе той или иной реализации сильно нагруженной функции.
Что я хочу сказать: не знаю, как в обычном IT-мире, но в научной вычислительной сфере существует чёткая корреляция между бенчмарками вроде моих (сферических) и реальным поведением тестируемых функций в сложных расчётах, когда эти функции вносят ощутимый вклад в сложность всей программы. То есть ежели некая функция f победила функцию g на сферических тестах в 10 раз, то примерно так же дело будет обстоять в реальной программе. И в этом я неоднократно убеждался с помощью профилировщика.
Поясню ещё один момент: в реальных задачах я не встречал необходимости оптимизировать функции min, max, sign и abs. Обычно они встречаются в группе значительно более сложных вычислений, поэтому совершенно незаметны в таблице с результатами профилировки. Просто я часто встречаю программистов, которые считают своим долгом исковеркать код на основе своих интуитивных предположений об оптимизации, тогда как узкое место их программы вообще в другой точке. Не надо так делать.
Тем не менее, мой эксперимент с этими функциями всё же имел для меня смысл, не смотря на искусственность и оторванность от реальности его кажущейся необходимости. Это я объясняю дальше.
Цели эксперимента
Напомню, что основной целью было получить от сообщества обратную связь в виде замечаний, рекомендаций и вообще некоторого поведения. Анализируя всё это, я делаю выводы и могу теперь сделать аналогичные эксперименты более интересными и полезными. Здесь я лишь тренировался и выражаю благодарность всем, кто принял посильное участие.
Вторая цель – проверить качество измерения времени моим способом. Принимая во внимание тот факт, что у кого-то время получалось отрицательным, можно с уверенностью сказать, что над замерами придётся ещё подумать. Это хорошо, потому что аналогичный провал в серьёзном эксперименте был бы для меня очень тяжёлым испытанием.
Третья цель – проверить способность потенциальных участников на Хабре правильно воспринимать ситуацию и действовать с учётом даже возможных отклонений от плана. Такая способность меня вполне устраивает, хотя меня немного разочаровало то, что некоторые участники предоставляли результаты тестирования, когда программа компилировалась без каких-либо ключей оптимизации… я не знаю, какой смысл в таких измерениях. По крайней мере, в научных расчётах это может быть полезно только для отладки. Тут отчасти моя вина, что я не пояснил данный момент, хотя нужно было догадаться, что раз все программисты очень разные, нужно максимально точно формулировать условия. Подобные пробные эксперименты учат пониманию этого, что тоже полезно.
Четвёртая цель – посмотреть на соотношение времён работы функций на разных процессорах и с разными компиляторами. Вот здесь меня удивил один момент. У некоторых пользователей получалось, что функция minu0 работала в разы медленнее остальных семи функций для минимума и максимума. Вот примеры (это именно при хаотичной подаче данных):
Intel(R) Core(TM) i3-2100 CPU @ 3.10GHz GCC 4.9.3-r3 Опции: -std=gnu++11 -O3 mini: 1.22 vs 2.59 maxi: 1.19 vs 2.71 minu: 13.64 vs 3.01 maxu: 1.21 vs 2.54 Intel Core i7-6700K CPU @ 4.00GHz GCC 5.2.1 Опции: -O3 -std=gnu++11 mini: 0.49 vs 0.83 maxi: 0.48 vs 0.82 minu: 10.20 vs 0.74 maxu: 0.49 vs 0.91 Intel(R) Core(TM)2 Duo CPU E7300 @ 2.66GHz GCC 4.8.4 Опции: g++ -std=gnu++11 -О3 sign: 12.95 vs 2.56 abs: 12.74 vs 0.91 mini: 2.31 vs 3.07 maxi: 2.19 vs 3.19 minu: 15.79 vs 3.54 maxu: 2.08 vs 3.77 Raspberry Pi 3, SoC: Broadcom BCM2837, CPU: ARM Cortex-A53 @ 1.2GHz gcc version 4.9.2 (Raspbian 4.9.2-10) options: -std=gnu++11 -O3 mini: 10.74 vs 17.93 maxi: 10.74 vs 14.33 minu: 24.63 vs 7.16 maxu: 10.74 vs 7.16
И так далее, этих примеров много. Причём здесь везде тупил GCC, потому как clang делал всё правильно:
Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz:
Clang 3.7 with Microsoft CodeGen (v140_clang_3_7):
Full optimization (-O3)
mini: 0.41 vs 2.61
maxi: 0.35 vs 9.28
minu: 0.69 vs 2.96
maxu: 0.44 vs 8.83
Там же в комментариях ещё много примеров работы Clang. Не буду приводить примеры, но VC++ 2015 тоже сделал всё правильно. Таким образом, разработчикам компилятора GCC данные примеры должны быть полезны для отладки блока оптимизации. То есть мой эксперимент выявил косяк компилятора, который может проявиться потом где-то в серьёзной программе.
Можно выделить и некоторые другие результаты, заслуживающие внимания, например, в некоторых случаях страшная формула без ветвлений обнаруживает минимум или максимум быстрее формулы с ветвлением. Вот фрагмент:
Raspberry Pi 3, SoC: Broadcom BCM2837, CPU: ARM Cortex-A53 @ 1.2GHz gcc version 4.9.2 (Raspbian 4.9.2-10) options: -std=gnu++11 -O3 minu: 24.63 vs 7.16 maxu: 10.74 vs 7.16
В первой строке ясно – это глюк GCC, о котором я писал выше, а во второй именно поражение метода с ветвлением.
Пятая цель была косвенно обозначена выше – показать обычным программистам, что не нужно фанатично придерживаться какой-то догмы. В каждом случае свой вариант может оказаться лучше и нужно проводить тестирование, чтобы сделать выбор, а не полагаться на слепую уверенность, основанную на оптимизации под четвёртый пень, возникшую в те далёкие времена, когда они учились в университете.
Шестая цель, менее всего значимая, – мне нужно было поделиться своими материалами (ссылки [4-7] из предыдущей статьи), чтобы со временем получить обратную связь, понять, верно ли я двигаюсь, когда пишу подобные статьи наметить для себя дальнейший план работы и отыскать единомышленников. Эту обратную связь я пока не получил, но всему своё время.
Седьмая цель, косвенная, — получить повод написать этот пост, делясь в нём своими мыслями, и провести в нём голосование.
Предлагаю голосовать. Если 80% участников голосования посчитают, что имеет смысл продолжать похожие эксперименты на Хабре (разумеется, более аккуратно), я продолжу и шаг за шагом разберу много разных алгоритмов. Польза для сообщества – обучение, ведь в процессе экспериментов я всегда объясняю или показываю, где прочитать объяснение тех вещей, что тестируются. Другая польза – возможность проверить всё на своём компьютере. Польза для меня – критика, корректировка, подсказки и советы. Если 80% не наберётся, я соберу свою аудиторию для таких экспериментов сам, просто это займёт больше времени, но зато я не буду здесь мешаться.
Голосуем и до новых встреч: )
PS. Пояснение к голосованию: под «более серьёзным» экспериментом подразумевается не более сложный алгоритм (алгоритмы будут разными — от sign(x) до Шёнхаге — Штрассена), а я буду стараться как-то улучшать их качество и потенциальную ценность результата.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Комментарии (1)