Подтвердить что ты не робот

Есть ли какой-либо функциональный язык компилятора/времени выполнения, который оптимизирует цепочку итераций?

Будет ли какой-либо компилятор/исполняемый файл функционального языка сокращать все привязанные итерации до одного при его применении? С точки зрения программиста мы могли оптимизировать функциональный код с такими конструкциями, как ленивость и потоки, но мне интересно узнать другую сторону истории. Мой функциональный пример написан в 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;
}
4b9b3361

ОТВЕТЫ

Ответ 1

Несколько лет назад я разместил два сообщения в блоге о этой теме:

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), поэтому сегодня результаты могут быть даже лучше.

Ответ 2

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 }

Ответ 3

В теории, как писал один комментатор, компилятор может уменьшить это до результата во время компиляции. Невообразимо, что это делается с некоторыми макросами, но не очень вероятно в общих случаях.

Если вы вставляете вызов .view, вы получаете ленивую семантику в Scala, и, следовательно, будет выполняться только одна итерация, хотя и не такая простая, как ваш императивный код:

val lz = (1L to 1000000L).view.filter(_ % 2 == 0) // SeqView (lazy)!
lz.sum

P.S. Ваше предположение неверно, что в противном случае есть три итерации. (1L to 1000000L) создает NumericRange, который не включает итерацию по элементам. Таким образом, .view сохраняет одну итерацию.