Будет ли какой-либо компилятор/исполняемый файл функционального языка сокращать все привязанные итерации до одного при его применении? С точки зрения программиста мы могли оптимизировать функциональный код с такими конструкциями, как ленивость и потоки, но мне интересно узнать другую сторону истории. Мой функциональный пример написан в Scala, но, пожалуйста, не ограничивайте свои ответы на этот язык.
Функциональный способ:
// I assume the following line of code will go
// through the collection 3 times, one for creating it
// one for filtering it and one for summing it
val sum = (1L to 1000000L).filter(_ % 2 == 0).sum // => 250000500000
Я бы хотел, чтобы компилятор оптимизировал к императивному эквиваленту:
/* One iteration only */
long sum, i;
for (i = 1L, sum = 0L; i <= 1000000L; i++) {
if (i % 2 == 0)
sum += i;
}
Несколько лет назад я разместил два сообщения в блоге о этой теме:
http://jnordenberg.blogspot.de/2010/03/scala-stream-fusion-and-specialization.html http://jnordenberg.blogspot.de/2010/05/scala-stream-fusion-and-specialization.html
Обратите внимание, что специализация и оптимизация, выполненные компилятором Scala, с тех пор значительно улучшились (возможно, в Hotspot), поэтому сегодня результаты могут быть даже лучше.
Haskell - это нестрогий язык по определению, все реализации, которые я знаю, используют ленивую оценку для обеспечения нестрогой семантики.
Аналогичный код (с аргументами для начала и конца, поэтому оценка времени компиляции невозможна)
val :: Int -> Int -> Int
val low high = sum $ filter even [low .. high]
вычисляет сумму только с одним обходом и в постоянной малой памяти. [low .. high] - синтаксический сахар для enumFromTo low high, а определение enumFromTo для Int в основном
enumFromTo x y
| y < x = []
| otherwise = go x
where
go k = k : if k == y then [] else go (k+1)
(на самом деле реализация GHC использует unboxed Int# по причинам эффективности рабочего go, но это не влияет на семантику, а для других типов Integral это определение аналогично).
Определение filter есть
filter :: (a -> Bool) -> [a] -> [a]
filter _pred [] = []
filter pred (x:xs)
| pred x = x : filter pred xs
| otherwise = filter pred xs
и sum:
sum l = sum' l 0
where
sum' [] a = a
sum' (x:xs) a = sum' xs (a+x)
Соблюдая это, даже без каких-либо оптимизаций, оценка продолжится
sum' (filter even (enumFromTo 1 6)) 0
-- Now it must be determined whether the first argument of sum' is [] or not
-- For that, the application of filter must be evaluated
-- For that, enumFromTo must be evaluated
~> sum' (filter even (1 : go 2)) 0
-- Now filter knows which equation to use, unfortunately, `even 1` is False
~> sum' (filter even (go 2)) 0
~> sum' (filter even (2 : go 3)) 0
-- 2 is even, so
~> sum' (2 : filter even (go 3)) 0
~> sum' (filter even (go 3)) (0+2)
-- Once again, sum asks whether filter is done or not, so filter demands another value or []
-- from go
~> sum' (filter even (3 : go 4)) 2
~> sum' (filter even (go 4)) 2
~> sum' (filter even (4 : go 5)) 2
~> sum' (4 : filter even (go 5)) 2
~> sum' (filter even (go 5)) (2+4)
~> sum' (filter even (5 : go 6)) 6
~> sum' (filter even (go 6)) 6
~> sum' (filter even (6 : [])) 6
~> sum' (6 : filter even []) 6
~> sum' (filter even []) (6+6)
~> sum' [] 12
~> 12
Это было бы, конечно, менее эффективным, чем цикл, поскольку для каждого элемента перечисления должна быть создана ячейка списка, тогда для каждого элемента, передающего фильтр, должна быть создана ячейка списка, только для того, чтобы ее немедленно уничтожить по сумме.
Убедитесь, что использование памяти действительно невелико:
module Main (main) where
import System.Environment (getArgs)
main :: IO ()
main = do
args <- getArgs
let (low, high) = case args of
(a:b:_) -> (read a, read b)
_ -> error "Want two args"
print $ sum $ filter even [low :: Int .. high]
и запустите его,
$ ./sumEvens +RTS -s -RTS 1 1000000
250000500000
40,071,856 bytes allocated in the heap
12,504 bytes copied during GC
44,416 bytes maximum residency (2 sample(s))
21,120 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 75 colls, 0 par 0.00s 0.00s 0.0000s 0.0000s
Gen 1 2 colls, 0 par 0.00s 0.00s 0.0002s 0.0003s
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.01s ( 0.01s elapsed)
GC time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.01s elapsed)
%GC time 6.1% (7.6% elapsed)
Alloc rate 4,367,976,530 bytes per MUT second
Productivity 91.8% of total user, 115.8% of total elapsed
Он выделил около 40 МБ для 0,5 миллиона ячеек списка (1) и немного изменился, но максимальная резиденция была около 44 КБ. Запуская его с верхним пределом в 10 миллионов, общее распределение (и время работы) растет в 10 раз (минус постоянный материал), но максимальное местожительство остается неизменным.
(1) GHC объединяет перечисление и фильтр и производит только четные числа в диапазоне по типу Int. К сожалению, он не может сбежать sum, так как это левая сгиб, а каркас слияния GHC только сливает правильные складки.
Теперь, чтобы слить и sum, нужно много работать, чтобы преподавать GHC, чтобы сделать это с помощью правил перезаписи. К счастью, это было сделано для многих алгоритмов в пакете vector, и если мы его используем,
module Main where
import qualified Data.Vector.Unboxed as U
import System.Environment (getArgs)
val :: Int -> Int -> Int
val low high = U.sum . U.filter even $ U.enumFromN low (high - low + 1)
main :: IO ()
main = do
args <- getArgs
let (low, high) = case args of
(a:b:_) -> (read a, read b)
_ -> error "Want two args"
print $ val low high
мы получаем более быструю программу, которая больше не выделяет никаких ячеек списка, трубопровод действительно переписан в цикл:
$ ./sumFilter +RTS -s -RTS 1 10000000
25000005000000
72,640 bytes allocated in the heap
3,512 bytes copied during GC
44,416 bytes maximum residency (1 sample(s))
17,024 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 0 colls, 0 par 0.00s 0.00s 0.0000s 0.0000s
Gen 1 1 colls, 0 par 0.00s 0.00s 0.0001s 0.0001s
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.01s ( 0.01s elapsed)
GC time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.01s elapsed)
%GC time 1.0% (1.2% elapsed)
Alloc rate 7,361,805 bytes per MUT second
Productivity 97.7% of total user, 111.5% of total elapsed
Здесь ядро, которое GHC производит для (работника) val, если кому-то интересно:
Rec {
Main.main_$s$wfoldlM'_loop [Occ=LoopBreaker]
:: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int#
[GblId, Arity=3, Caf=NoCafRefs, Str=DmdType LLL]
Main.main_$s$wfoldlM'_loop =
\ (sc_s303 :: GHC.Prim.Int#)
(sc1_s304 :: GHC.Prim.Int#)
(sc2_s305 :: GHC.Prim.Int#) ->
case GHC.Prim.># sc1_s304 0 of _ {
GHC.Types.False -> sc_s303;
GHC.Types.True ->
case GHC.Prim.remInt# sc2_s305 2 of _ {
__DEFAULT ->
Main.main_$s$wfoldlM'_loop
sc_s303 (GHC.Prim.-# sc1_s304 1) (GHC.Prim.+# sc2_s305 1);
0 ->
Main.main_$s$wfoldlM'_loop
(GHC.Prim.+# sc_s303 sc2_s305)
(GHC.Prim.-# sc1_s304 1)
(GHC.Prim.+# sc2_s305 1)
}
}
end Rec }
В теории, как писал один комментатор, компилятор может уменьшить это до результата во время компиляции. Невообразимо, что это делается с некоторыми макросами, но не очень вероятно в общих случаях.
Если вы вставляете вызов .view, вы получаете ленивую семантику в Scala, и, следовательно, будет выполняться только одна итерация, хотя и не такая простая, как ваш императивный код:
val lz = (1L to 1000000L).view.filter(_ % 2 == 0) // SeqView (lazy)!
lz.sum
P.S. Ваше предположение неверно, что в противном случае есть три итерации. (1L to 1000000L) создает NumericRange, который не включает итерацию по элементам. Таким образом, .view сохраняет одну итерацию.