Предыстория: я уже много раз слышал/читал о том, что double начинает дико тупить, если получаются числа меньше 1e-306. Подобные разговоры всплывали после одного из контестов в зоне NEERC, после одного из раундов TC, еще видел такие фразы в обсуждении некоторых задач на различных online judge. Обычно советуют лечить это с помощью if (value<eps)value=0; Так как это мне всегда помогало, то выглядело вполне правдоподобно. Насколько это правда на самом деле?
Актуальная проблема: недавно столкнулся с похожей проблемой на СF. Сравните 3 сабмита: 7256779, 7256781, 7256786. Они отличаются только в void mult, при этом первое решение работает в десяток раз медленней двух остальных. Один из АС сабмитов действительно с костылем if(value<eps), в другом же разница в том, что две переменные заменены на локальные вместо глобальных. Кто-то может более-менее понятно объяснить, откуда такая разница в продуктивности?
Идем дальше. Выбросим из кода все лишнее) Этот код работает быстро и без проблем. Если переписать его вот так, в стиле кода, из-за которого и была создана эта тема, то продуктивность резко падает после 7 итерации (46 мс для 7 итераций, 1092 мс для 8 итераций, 2698 мс для 9 итераций). Обратите внимание, что в этом коде уже есть if (value<eps), но оно не помогает. Если сделать переменные локальными, как было в одном из примеров выше, то решение начинает проседать на одну итерацию позднее (62 мс для 8 итераций, 1653 мс для 9 итераций). Почему вообще так? И почему в этом случае костыль с <eps абсолютно никак не влияет на ситуацию — хотя в начальной задаче, в, казалось бы, аналогичной ситуации, локализация переменных/eps-костыль — одинаково полезные, с любым одним из этих фиксов решение отрабатывает 70 итераций за 7 секунд, без них — 11 итераций за 1.2 секунды, 12 итераций за 8 секунд, дальше TL.
Такие числа, у которых экспонента на грани минимального значения, называются денормализованными и проблема с производительностью действительно существует, но в данной задаче вроде почти не проявляется, ибо из-за умножения числа зануляются раньше, чем становятся денормализованными.
Разница между первой и второй посылкой, если верить ассемблеру, в том, что компиялтор в первом случае, видимо, боится, что temp и v могут пересекаться, потому на каждой итерации трёх вложенных циклах пишет значение в память. Во втором случае они точно не пересекаются, потому сначала всё суммируется на регистр, потом один раз записывается. Т.е. принудительная запись во временную переменную всё лечит: 7257602
В третьем случае какая-то фигня и компилятор опять считает, что temp с v не пересекается и делает то же самое, что и во втором. Отсюда, в общем-то, у них и время одинаковое.
Спасибо за линк, ознакомлюсь)
А как объяснять компилятору, что он зря переживает? Какими-то директивами или чем-то еще? Больше интересует АСМ-подход, т.е. в предположении, что мои возможности ограничены возможностями пользователя online judge/участника АСМ-контеста. Как вообще застраховать себя от такого — каждый раз при подобных алгоритмах (вроде умножения матриц) делать эту дополнительную переменную? Или банально писать все на векторах?
Сомневаюсь, что компилятору в общем случае можно сказать, что пара каких-нибудь указателей — это непересекающиеся массивы. Для аргументов функций можно попытаться использовать restrict, но как по-простому применить его в данном случае, не добавляя аргументов mult — не знаю. Раз уж речь конкретно про ACM, то можно ещё попытаться выкрутиться, используя только глобальные переменные.
А почему вообще первые несколько итераций выполняются быстро, а потом скорость резко падает? Если наивно предполагать "каждый раз писать — медленно, хранить промежуточные в регистре — быстро", то какая разница — первая это итерация или двадцатая? Или между итерациями как-то изменяется участок памяти, в который мы пишем (что тоже как-то интуитивно нелогично, ведь работаем с одними и теми же переменными все время) и время доступа к нему? Или там что-то еще более хитрое?
Я запускал этот код в запуске под всеми С++ по очереди. Результаты примерно одинаковые, можно посмотреть на output — сначала быстрые итерации, потом усталость дает о себе знать и итерации уже совсем не быстрые:)
overflow для вещественных чисел ненамного лучше underflow :) После определённой итерации числа уходят в бесконечность и становятся NaN'ами, в этот момент и начинает всё тормозить.
Если начальные значения уменьшить раз в 100, то все итерации примерно одинаковое время будут считаться.
В C это, кажется, можно сделать так:
А в C++ придётся делать нестандартно, как-то так:
Ух ты, работает :) И первый вариант кода, получавший TL, с добавленным restricted получает ОК. Спасибо.