Ответ 1
Глядя на ядро из 7.6.1, с -O2 и -dsuppress-uniques, функция, выполняющая работу, Main.main_$spoly_$wa является структурно (почти) идентичной, использую ли я int или Int64 как индекс тип. Поскольку ядро длинное и сложное, здесь вывод diff:
$ diff Int_core.dump-simpl Int64_core.dump-simpl
11,12c11,12
< (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)
< (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int))
---
> (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int)
> (Main.C (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int))
26,27c26,27
< (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)
< (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)))
---
> (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int)
> (Main.C (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int)))
Различные типы индексов, это, конечно, разные.
33,40d32
< l :: GHC.Types.Int
< [LclId]
< l = GHC.Types.I# sc } in
< let {
< u :: GHC.Types.Int
< [LclId]
< u = GHC.Types.I# sc1 } in
< let {
Для типа индекса int GHC создает несколько более информативные ошибки для индексов вне границ, для чего ему нужна нижняя и верхняя граница допустимых индексов. (Реализация index по умолчанию не переопределена в instance Ix Int64.)
45,46c37
< GHC.Types.False ->
< case poly_$w$j5 (GHC.Types.I# a) l u of wild2 { };
---
> GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild1 { };
Различные ошибки, indexError и hopelessIndexError. Следующие различия также касаются только ошибок индекса.
49,50c40
< GHC.Types.False ->
< case poly_$w$j5 (GHC.Types.I# a) l u of wild2 { };
---
> GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild2 { };
58c48
< case poly_$w$j4 y (GHC.Types.I# sc2) of wild3 { };
---
> case poly_$w$j3 y (GHC.Types.I# sc2) of wild4 { };
62c52
< case poly_$w$j4 y (GHC.Types.I# sc2) of wild5 { };
---
> case poly_$w$j3 y (GHC.Types.I# sc2) of wild5 { };
77,78c67
< GHC.Types.False ->
< case poly_$w$j3 (GHC.Types.I# a1) l u of wild6 { };
---
> GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild6 { };
81,82c70
< GHC.Types.False ->
< case poly_$w$j3 (GHC.Types.I# a1) l u of wild7 { };
---
> GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild7 { };
Теперь еще раз разный тип индекса:
110c98
< GHC.Types.Int
---
> GHC.Int.Int64
152c140
< s GHC.Types.Int GHC.Types.Int>)>)
---
> s GHC.Int.Int64 GHC.Types.Int>)>)
И, наконец, 0 и 1 получили разные имена верхнего уровня.
177,178c165,166
< 0 -> (# sc5, lvl5 #);
< 1 -> (# sc5, lvl6 #)
---
> 0 -> (# sc5, lvl #);
> 1 -> (# sc5, lvl1 #)
Таким образом, весь код, который выполняет фактическую работу, идентичен. Тем не менее, один вызывает переполнение стека (хотя достаточно только -K9M [-K8731K здесь, -K8730K not]), а другой нет.
Разница действительно вызвана ошибками индекса. Код с индексами int выделяет два вложенных в квадрат int в каждом рекурсивном вызове, который не выделяет код Int64, потому что
Main.main_$spoly_$wa [Occ=LoopBreaker]
:: forall s.
GHC.Prim.Int#
-> GHC.Prim.Int#
-> GHC.Prim.Int#
-> GHC.Prim.MutableByteArray# s
-> (GHC.Prim.~#)
*
(Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)
(Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int))
-> GHC.Prim.Int#
-> GHC.Prim.State# s
-> (# GHC.Prim.State# s, GHC.Types.Int #)
содержит две ссылки на массив.
Это использует больше стека, и эти бокс-теги int должны быть собраны в мусор, что приводит к значительно большим значениям GC. Кроме того, thunk для индексной ошибки немного больше, чем hopelessIndexError thunk.
Теперь, если вы поможете компилятору
- удаление оболочки newtype
- делает функцию строгой в массиве (с помощью шаблонов bang или
data C a = C !a)
или некоторые другие способы, он создает лучший код, который управляет без для данного аргумента, поскольку в рабочем документе имеется только одна ссылка на массив, и, следовательно, распределение помеченных int для границ isn Не нужно.
Обратите внимание, что этот алгоритм вызывает переполнение стека для немного больших аргументов даже при помощи компилятора.