Комментарии 12
Тестировать микробенчмарки, не глядя на дизассемблер — мракобесие. В видео на CppCon 2015 все это подробно объясняется.
Разумеется, никто не спорит. Но мракобесием на мой взгляд также является любое категоричное высказывание, жёстко разграничивающее мракобесие от науки путём озвучивания каких-то универсальных правил работы. Важным является не то, смотрит кто-то в ассемблер или нет, а то, что он в конечном итоге получает и как это соотносится с его целями.
Есть один достаточно важный случай, когда отношение производительности двух вариантов реализации серьезно меняется при переходе от идеальных условий к реальным. Пусть у нас есть расчет некоторой функции с помощью полиномиального приближения и с помощью таблицы. Тогда в идеальных условиях таблица целиком попадет в L1 и может обогнать расчет полинома, однако в реальных условиях она будет вытеснена из кеша другими данными и скорость доступа к ней серьезно упадет, тогда как полиномиальное приближение будет работать также быстро.
Это называется неправильная постановка эксперимента. Если я знаю, что в реальных условиях на работу функции влияют её условия взаимодействия с кэшем, то буду моделировать эксперимент с учётом этих условий. В эксперименте будут идеальные условия, но с тем же отношением к кэшу. Всё это нужно хорошо заранее предусмотреть, и никто не мешает это сделать, когда знаешь условия задачи заранее. В практике эффективного программирования вообще редко бывает, чтобы задача решалась для универсального случая, чаще всего решают конкретную задачу в конкретных условиях, причём нередко даже учитывают специфику конкретного компьютера. И всё это тоже нетрудно смоделировать.
Но если вы не пытались делать выводов о скорости работы функции отдельно, то зачем было измерять время работы цикла без функции и вычитать его из времени выполнения цикла с функцией? В чём смысл этой операции? Чтобы понять какая из функций работает быстрее именно в этих конкретных условиях, не нужно специально пытаться нейтрализовать влияние этих условий на результат. Наоборот, нужно сравнивать между собой интегральные замеры, включающие время выполнения как самой функции, так и окружающих её условий.
Причин здесь несколько, не все из которых на данный момент могут быть оглашены (за недостатком фактических сведений). Напишу две. Обозначим чистое время работы цикла через C, а точное (если бы мы его знали) время работы тестируемой функции — через A. Совершенно очевидно, что одновременная работа цикла и тестируемой функции будет более быстрой, чем А+С, это именно то, что Вы зачем-то повторяли мне в комментариях к прошлой статье и про что я сразу сказал, что это понятно, а Вы упорно думали, будто я этого не знаю. Инструкции могут исполняться одновременно с определённой степенью этой одновременности. То есть их время работы пересекается в некоторой степени. Для начала мне нужно было определить, будет ли степень пересечения A и C сильно отличаться на разных машинах. Для этого, конечно, можно было поступить иначе, но я решил просто их вычитать и ожидать отрицательного или близкого к нулю значения. Оно появилось. С другой стороны, отрицательное значение может означать серьёзные ошибки самой методики измерения (как мне сообщили, на AMD подобная «замерялка» вообще может глючить в таком виде). Далее, вторая причина, по которой я вычитал — на практике, когда тестируются более сложные функции и значительно более сложным набором входных данных (генерация которых может быть тяжёлой), данная корректировка успешно работает. Она даёт действительно чистое время работы функции («чистое» — это просто название), которое остаётся таким же в реальных условиях. В случае маленьких функции такая корректировка оказывается слишком грубой. Чтобы оценить степень этой грубости, мне нужно всё проверить в разных условиях, и я проверил. Если бы мне нужно было именно чистое время таких маленьких функций, я запускал бы их в разных циклах с разными окружающими помехами, а затем получал бы систему уравнений с несколькими неизвестными, из которых надёжно рассчитывал бы оценку на чистое время. Получив нужную мне информацию, я теперь должен сообразить, как скорректировать подобные эксперименты на будущее. Предвидя Ваш ответ, сразу говорю: ДА, можно было сделать по-другому и, ДА, можно было сделать умнее или глупее, но это будет уже Ваш эксперимент, а не мой. Я же своих целей на данный момент почти добился с минимальными затратами. Для Вас же повторю простую формулу: не нравится — критикуй, критикуя — предлагай, предлагаешь — делай, а делаешь — отвечай.
Вот если бы вы сразу сказали, что отрицательное время в рамках вашего эксперимента имеет смысл, можно было бы сэкономить кучу сил. Тогда я сразу бы понял, что вообще не понимаю вашего замысла. К слову, я и сейчас его не понимаю. Но теперь эксперимент выглядит так, как будто в нём есть какой-то смысл… пусть и непонятный мне.
// Прошу прощения, что комментирую эту статью, а не предыдущую, но туда мне писать уже нельзя.
1. Вы можете объяснить, почему в ваших собственных результатах тестирования в предыдущей статье (как и у большинства отписавшихся), большинство функций отработали заметно быстрее при «хаотичной подаче»?
2. Как я понимаю, ваш способ получения «хаотической» последовательности чисел всё ещё оставляет огромное пространство для различных оптимизаций при компиляции и исполнении. Почему вы не используете случайные числа (как предложил meduzik: habrahabr.ru/post/281629/#comment_8854253)?
3. Есть какой-то факт, гарантирующий, что первые 2^32 элементов последовательность вроде «a[i+1] = (19993 * a[i] + 1) % 2^32» переберут все натуральные числа от 0 до 2^32 — 1 по одному разу?
1. Вы можете объяснить, почему в ваших собственных результатах тестирования в предыдущей статье (как и у большинства отписавшихся), большинство функций отработали заметно быстрее при «хаотичной подаче»?
2. Как я понимаю, ваш способ получения «хаотической» последовательности чисел всё ещё оставляет огромное пространство для различных оптимизаций при компиляции и исполнении. Почему вы не используете случайные числа (как предложил meduzik: habrahabr.ru/post/281629/#comment_8854253)?
3. Есть какой-то факт, гарантирующий, что первые 2^32 элементов последовательность вроде «a[i+1] = (19993 * a[i] + 1) % 2^32» переберут все натуральные числа от 0 до 2^32 — 1 по одному разу?
Хорошие вопросы, отвечаю.
Первый вопрос у меня пока в очереди на обработку, сейчас я не знаю на него ответа.
Второй вопрос: случайные числа использовать не получится, потому что я не знаю ни одного генератора случайных чисел. Псевдослучайные же числа можно генерировать по-разному и мой вариант — это как раз и есть так называемый линейный конгруэнтный генератор псевдослучайных чисел. Он даёт не очень хорошую последовательноть с точки зрения случайности, но она ганрантированно весьма хаотичная и переберёт все числа из диапазона при наличии трёх условий (ответ на третий Ваш вопрос), перечисленных по указанной ссылке. Например, если взять множитель 11, то данный генератор НЕ перебирает все числа — этот факт, о котором многие не знают, можно довольно забавно использовать чтобы запутать человека, с которым споришь: ) Он начнёт искать ошибку в другом месте и обязательно скажет глупость.
Что касается оптимизации метода получения последовательности, то у меня нет целей его оптимизировать. Но, отвечаю, да, это можно сделать массой способов, вплоть до выбора другого генератора.
Первый вопрос у меня пока в очереди на обработку, сейчас я не знаю на него ответа.
Второй вопрос: случайные числа использовать не получится, потому что я не знаю ни одного генератора случайных чисел. Псевдослучайные же числа можно генерировать по-разному и мой вариант — это как раз и есть так называемый линейный конгруэнтный генератор псевдослучайных чисел. Он даёт не очень хорошую последовательноть с точки зрения случайности, но она ганрантированно весьма хаотичная и переберёт все числа из диапазона при наличии трёх условий (ответ на третий Ваш вопрос), перечисленных по указанной ссылке. Например, если взять множитель 11, то данный генератор НЕ перебирает все числа — этот факт, о котором многие не знают, можно довольно забавно использовать чтобы запутать человека, с которым споришь: ) Он начнёт искать ошибку в другом месте и обязательно скажет глупость.
Что касается оптимизации метода получения последовательности, то у меня нет целей его оптимизировать. Но, отвечаю, да, это можно сделать массой способов, вплоть до выбора другого генератора.
Отвечаю на Ваш первый вопрос. На самом деле он следует из комментария grechnik, который написан здесь. В случае последовательной версии цикл полностью сворачивается в константу, поэтому время работы пустого цикла равно нулю (ну, или эпсилон), значит я вычитаю ноль на самом деле. В случае хаотичной версии пустой цикл в константу не сворачивается (хотя сумма чисел та же), поэтому там я вычитаю не ноль. Значит получается, что после вычитания в хаотичной версии числа будут заметно меньше, чем в последовательной, где ничего не вычитается. А это значит, что нужно более аккуратно следить за ходом эксперимента. Это одна из тех мыслей, которую выразил halyavin в первом комментарии к этой статье — нужно смотреть, что с вашим кодом сделал компилятор. Мой эксперимент это тоже показывает, и это как раз очень удачно укладывается в его цели (эксперимент же пробный). Спасибо за вопрос.
Вот голосование и завершилось. Всем спасибо за поддержку и своё мнение. Буду готовить более серьёзные эксперименты.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Объяснение эксперимента о ветвлениях, или философские изыскания на тему бенчмарков в вакууме и в… реальности