Давайте назовем три программы A , B и C соответственно.
C против B
Начнем с самого простого: C имеет дополнительное ограничение (b >= a) относительно B .Интуитивно это означает, что пространство поиска, пройденное в C , меньше, чем в B .Мы можем рационализировать это, отметив, что вместо того, чтобы разбираться по каждой возможно переставленной паре a, b (из которых мы знаем, что 1000^2=1000000 возможных пар), мы вместо этого не рассматриваем все те случаи, когда b меньше, чем a.Предположительно, проверка того, производит ли b >= a небольшой дополнительный код (сравнение), который перевешивается вычислениями, избегается при запуске сравнения, поэтому мы отмечаем (небольшое) ускорение.Достаточно справедливо.
B против A
Следующее немного сложнее: кажется, что A имеет то же самоеограничение как C (b >= a), но закодировано по-другому (то есть здесь у нас это закодировано как диапазон значений, которые b может достичь в List Monad).Тогда мы можем подумать, что A должен работать быстрее, чем B (как, впрочем, и должно работать аналогично C ).Очевидно, что нашей интуиции не хватает.
К ядру
Теперь, поскольку мы не всегда можем доверять нашей интуиции, мы должны исследовать то, что на самом деле происходит в сгенерированном . GHC Core .Давайте дампим ядро для наших 3 программ (без оптимизации):
for p in A B C
do
ghc -ddump-simpl $p.hs >> $p.core
done
Если мы сравним B.core и C.core, отметим, что оба файла имеют примерно одинаковую структуру:
Начнем с вызова нескольких знакомых функций (System.IO.print ...), (Data.List.product ...) и (GHC.List.head ...)
Далее мы определим пару вложенных рекурсивных функций с сигнатурой:
ds_dxd [Occ=LoopBreaker]
:: [GHC.Integer.Type.Integer] -> [[GHC.Integer.Type.Integer]]
Мы вызываемкаждая из этих определенных функций перечисления имеет вид:
(GHC.Enum.enumFromTo
@ GHC.Integer.Type.Integer
GHC.Num.$fEnumInteger
(GHC.Integer.smallInteger 1)
(GHC.Integer.smallInteger 1000)))
и выполняет нашу логику в самой внутренней определенной функции.Следует отметить, что в B.core мы видим
case GHC.Classes.==
@ GHC.Integer.Type.Integer
...
(GHC.Num.+
...
(GHC.Real.^
...
ds3_dxc
(GHC.Integer.smallInteger 2))
(GHC.Real.^
...
ds8_dxg
(GHC.Integer.smallInteger 2)))
(GHC.Real.^
...
c_abw
(GHC.Integer.smallInteger 2))
, соответствующий простому фильтру всех возможных значений, соответствующих нашему ограничению, тогда как в C.core вместо этого мы имеем:
case GHC.Classes.>=
@ GHC.Integer.Type.Integer GHC.Classes.$fOrdInteger ds8_dxj ds3_dxf
of _ {
GHC.Bool.False -> ds5_dxh ds9_dxk;
GHC.Bool.True ->
let {
...
case GHC.Classes.==
...
, соответствующий добавлению дополнительного ограничения >= перед нашим триплетным ограничением, и, следовательно, поиск по меньшему числу целых чисел для более короткого времени выполнения, как и ожидает наша интуиция.
При сравнении A.coreи B.core, мы сразу видим знакомую структуру (вложенную пару рекурсивных функций, каждая из которых вызывается через перечисление), и фактически получается, что выходные данные ядра для A и B почти идентичны!Разница, по-видимому, заключается в самом внутреннем перечислении:
ds5_dxd
(GHC.Enum.enumFromTo
@ GHC.Integer.Type.Integer
GHC.Num.$fEnumInteger
ds3_dxb
(GHC.Integer.smallInteger 1000))
, где мы видим диапазон перечисления от заданной индукционной переменной ds3_dxb до 1000, в отличие от сохранения в качестве статического диапазона ([1..1000]).
Что тогда дает?Разве это не означает, что A должен работать быстрее, чем B ?(мы наивно ожидаем, что A будет работать аналогично C , учитывая, что они реализуют те же ограничения).Что ж, получается, что различные оптимизации компиляции в игре приводят к чрезвычайно сложному поведению, а различные комбинации часто дают неинтуитивные (и откровенно странные) результаты, и в этом случае мы имеем два компилятора, взаимодействующихдруг с другом: ghc и gcc.Чтобы иметь возможность понять эти результаты, мы должны положиться на сгенерированное оптимизированное ядро (В конечном счете, это действительно сгенерированный ассемблер, который действительно рассчитывает, но пока мы его проигнорируем).
На оптимизированное ядро и далее
Давайте сгенерируем оптимизированное ядро:
for p in A B C
do
ghc -O3 -ddump-simpl $p.hs >> $p.core
done
и сравните нашего проблемного потомка ( A ) с его более быстрыми аналогами. Сравнительно B и C оба выполняют класс оптимизаций, которые один A не может: с плавающей точкой и лямбда-лифтинг . Мы можем убедиться в этом, заметив, что наши рекурсивные функции в B и C содержат на 40 меньше строк кода, что приводит к более тесным внутренним циклам. Чтобы понять, почему A не извлекает выгоду из этой оптимизации, мы должны взглянуть на код, который не выдается:
let {
c1_s10T
:: GHC.Integer.Type.Integer
-> [[GHC.Integer.Type.Integer]]
-> [[GHC.Integer.Type.Integer]]
[LclId, Arity=2, Str=DmdType LL]
c1_s10T =
\ (ds2_dxg :: GHC.Integer.Type.Integer)
(ds3_dxf :: [[GHC.Integer.Type.Integer]]) ->
let {
c2_s10Q [Dmd=Just L] :: GHC.Integer.Type.Integer
[LclId, Str=DmdType]
c2_s10Q = GHC.Integer.minusInteger lvl2_s10O ds2_dxg } in -- subtract
case GHC.Integer.eqInteger
(GHC.Integer.plusInteger lvl3_s10M (GHC.Real.^_^ ds2_dxg lvl_r11p))
-- add two squares (lve3_s10M has been floated out)
(GHC.Real.^_^ c2_s10Q lvl_r11p)
-- ^ compared to this square
of _ {
GHC.Bool.False -> ds3_dxf;
GHC.Bool.True ->
GHC.Types.:
@ [GHC.Integer.Type.Integer]
(GHC.Types.:
@ GHC.Integer.Type.Integer
ds_dxe
(GHC.Types.:
@ GHC.Integer.Type.Integer
ds2_dxg
(GHC.Types.:
@ GHC.Integer.Type.Integer
c2_s10Q
(GHC.Types.[] @ GHC.Integer.Type.Integer))))
ds3_dxf
} } in
то есть вычитание (minusInteger) и равенство (eqInteger), а также два квадрата (^_^) выполняются в критической секции нашего цикла (представленной телом вспомогательной функции ), тогда как та же вспомогательная функция в C.core содержит меньше вычислений (и если мы продолжим копать, мы увидим, что это потому, что GHC не может определить, безопасно ли выводить эти вычисления на этапе оптимизации). Это соответствует нашему более раннему анализу, так как мы видим, что ограничение (b >= a) действительно существует , в отличие от C , мы не смогли выпустить большинство избыточный расчет вне цикла.
Для подтверждения давайте увеличим границы произвольно (для демонстрации) границ цикла, скажем, до [1..10000]. Мы должны ожидать, что A поведение во время выполнения должно быть асимптотически близко к C во время выполнения, так же как мы ожидаем, что B останется в пыли.
➜ time ./A
./A 0.37s user 0.01s system 74% cpu 0.502 total
➜ time ./B
./B 3.21s user 0.02s system 99% cpu 3.246 total
➜ time ./C
./C 0.33s user 0.01s system 99% cpu 0.343 total
и что вы знаете, это так, как мы ожидаем! Ваши начальные границы были просто слишком малы для того, чтобы пролить свет на любые интересные характеристики производительности (что бы вам ни говорила теория, постоянные накладные расходы имеют значение на практике ). Другой способ взглянуть на этот результат заключается в том, что наша первоначальная интуиция о том, что A соответствует производительности C , была на самом деле более точной, чем она показалась на первый взгляд.
Конечно, все это может быть излишним для имеющегося примера кода, но этот вид анализа может быть очень полезным в условиях ограниченных ресурсов.