Преимущество в избежании множественных переходов

Ответ 1

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

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

В присутствии лень этот кодовый трюк может привести к противоположным результатам. Имея полные уравнения, например. Компилятор Haskell GHC способен выполнять все виды оптимизации, которые полностью исключают списки и превращают код в эквивалент циклов. Это происходит, когда мы скомпилируем код, например. -O2.

Записывание парциальных уравнений может помешать оптимизации этого компилятора и заставить фактически создавать функции - с резким замедлением полученного кода. Я попробовал ваш код cachedList и увидел, что время выполнения 0.01s превратилось в 0.20s (не помните прямо сейчас точный тест, который я сделал).

Ответ 2

Выполнение нескольких дополнительных арифметических команд в вашем теле цикла дешевле, чем выполнение нескольких дополнительных извлечений памяти, в основном.

Переходы означают много доступа к памяти, поэтому чем меньше вы делаете, тем лучше. Слияние обходов уменьшает трафик памяти и увеличивает вычислительную нагрузку прямой линии, поэтому вы получаете лучшую производительность.

Конкретно рассмотрим эту программу для вычисления некоторой математики в списке:

go :: [Int] -> [Int]
go = map (+2) . map (^3)

Ясно, что мы проектируем его с двумя обходами списка. Между первым и вторым обходами результат сохраняется в промежуточной структуре данных. Тем не менее, это ленивая структура, поэтому стоит только O(1) память.

Теперь компилятор Haskell сразу же подключает две петли:

go = map ((+2) . (^3))

Почему? В конце концов, как сложность O(n), так? Разница заключается в постоянных факторах.

Учитывая эту абстракцию: для каждого шага первого конвейера мы делаем:

  i <- read memory          -- cost M
  j = i ^ 3                 -- cost A
  write memory j            -- cost M
  k <- read memory          -- cost M
  l = k + 2                 -- cost A
  write memory l            -- cost M

поэтому мы платим 4 обращения к памяти и 2 арифметические операции.

Для конденсированного результата имеем:

  i <- read memory          -- cost M
  j = (i ^ 3) + 2           -- cost 2A
  write memory j            -- cost M

где A и M являются постоянными факторами для выполнения математики в ALU и доступа к памяти.

Существуют и другие постоянные факторы (две ветки цикла) вместо одного.

Так что, если доступ к памяти не является бесплатным (это не так, по длинному снимку), вторая версия всегда быстрее.

Обратите внимание, что компиляторы, которые работают с неизменяемыми последовательностями, могут реализовать array fusion, преобразование, которое делает это для вас. GHC является таким компилятором.

Ответ 3

Есть еще одна очень важная причина. Если вы переходите список только один раз, и у вас нет другой ссылки на него, GC может освободить память, заявленную элементами списка, когда вы проходите их. Более того, если список генерируется лениво, у вас всегда есть только постоянное потребление памяти. Например

import Data.List

main = do
    let xs = [1..10000000]
        sum = foldl' (+) 0 xs
        len = foldl' (\_ -> (+ 1)) 0 xs
    print (sum / len)

вычисляет sum, но ему нужно сохранить ссылку на xs, и память, которую он занимает, не может быть выпущена, потому что это необходимо для вычисления len позже. (Или наоборот). Таким образом, программа потребляет значительную часть памяти, чем больше xs, тем больше памяти она нуждается.

Однако, если мы перемещаем список только один раз, он создается лениво, и элементы могут быть GC немедленно, поэтому независимо от того, насколько велик список, программа принимает только O(1) память.

{-# LANGUAGE BangPatterns #-}
import Data.List

main = do
    let xs = [1..10000000]
        (sum, len) = foldl' (\(!s,!l) x -> (s + x, l + 1)) (0, 0) xs
    print (sum / len)

Ответ 4

Извините заранее за ответ в чате.

Это очевидно очевидно, но если мы говорим о производительности, вы всегда должны проверять гипотезы, измеряя.

Несколько лет назад я думал о операционной семантике GHC, машины STG. И я задал себе тот же вопрос - наверно, знаменитые алгоритмы "одного прохода" не так уж велики? Он выглядит только как один обход на поверхности, но под капотом у вас также есть структура цепочек тромбов, которая обычно очень похожа на исходный список.

Я написал несколько версий (различающихся строгостью) знаменитой проблемы RepMin - учитывая дерево, заполненное числами, генерирует дерево той же формы, но заменяет каждое число минимальным количеством всех чисел. Если моя память правильная (помните - всегда проверяйте материал самостоятельно!), Наивный алгоритм с двумя проходами выполняется намного быстрее, чем различные умные алгоритмы с одним обходом.

Я также поделился своими наблюдениями с Саймоном Марлоу (мы оба были в летней школе FP за это время), и он сказал, что они используют этот подход в GHC. Но не для повышения производительности, как вы могли подумать. Вместо этого он сказал, что для большого АСТ (например, Haskell) запись всех конструкторов занимает много места (в терминах строк кода), и поэтому они просто уменьшают количество кода, записывая только один (синтаксический) обход.

Лично я избегаю этого трюка, потому что если вы допустили ошибку, вы получите цикл, который очень неприятно отлаживать.