Степень оптимизации GHC

Question

Я не очень хорошо знаю, насколько Haskell/GHC может оптимизировать код. Ниже у меня есть довольно "грубая сила" (в декларативном смысле) реализация проблемы n королев. Я знаю, что это может быть написано более эффективно, но это не мой вопрос. Дело в том, что это заставило меня задуматься о возможностях и ограничениях оптимизации GHC.

Я выразил это в том, что считаю довольно простым декларативным смыслом. Фильтровать перестановки [1..n], которые удовлетворяют предикату For all indices i,j s.t j<i, abs(vi - vj) != j-i Я хотел бы надеяться, что это то, что можно оптимизировать, но это также похоже на то, что я спрашиваю много компилятора.

validQueens x = and [abs (x!!i - x!!j) /= j-i | i<-[0..length x - 2], j<-[i+1..length x - 1]] 

queens n = filter validQueens (permutations [1..n])

oneThru x = [1..x]    
pointlessQueens = filter validQueens . permutations . oneThru

main = do
          n <- getLine 
          print $ pointlessQueens $ (read :: String -> Int) n

Это работает довольно медленно и быстро растет. n=10 занимает около секунды и n=12 берет навсегда. Без оптимизации я могу сказать, что рост является факториальным (число перестановок), умноженным на квадратичное (количество различий в предикате для проверки). Есть ли способ, которым этот код может работать лучше с помощью интеллектуальной компиляции? Я попробовал основной ghc варианты такие есть -O2 и не заметил существенной разницы, но я не знаю тонкости (просто добавил flagS)

У меня сложилось впечатление, что функция, которую я вызываю queens не может быть оптимизирован и должен генерировать все перестановки перед фильтром. Есть ли у версии без очков больше шансов? С одной стороны, я чувствую, что умное понимание функций между фильтром и предикатом может отбросить некоторые явно нежелательные элементы еще до того, как они будут полностью сгенерированы, но с другой стороны, кажется, что возникает много вопросов.

Извините, если это кажется бессвязным, я думаю, мой вопрос

1. Является ли точечная версия вышеупомянутой функции более способной к оптимизации?
2. Какие шаги я могу предпринять во время make / compile / link для стимулирования оптимизации?
3. Не могли бы вы кратко описать некоторые возможные (и противопоставить невозможным!) Способы оптимизации для приведенного выше кода? В какой момент процесса это происходит?
4. Есть ли какая-то конкретная часть ghc --make queensN -O2 -v выходной я должен обратить внимание? Ничто не выделяется для меня. Даже не вижу большой разницы в выходе из-за флагов оптимизации

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

PS - permutations это из Data.List и выглядит так:

permutations            :: [a] -> [[a]]
permutations xs0        =  xs0 : perms xs0 []
  where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)

Answer 1

На более общем уровне относительно того, "какую оптимизацию может выполнять GHC", это может помочь немного разбить идею "оптимизации" на части. Существуют концептуальные различия, которые можно провести между аспектами программы, которые можно оптимизировать. Например, рассмотрим:

• Внутренняя логическая структура алгоритма: почти во всех случаях можно смело предполагать, что это никогда не будет оптимизировано. Помимо экспериментальных исследований, вы вряд ли найдете компилятор, который заменит пузырьковую сортировку с сортировкой слиянием или даже вставной сортировкой, и крайне маловероятно, что найдется компилятор, который заменит bogosort чем-то разумным.

• Необязательная логическая структура алгоритма: например, в выражении g (f x) (f x)сколько раз будет f xвычисляться? Как насчет выражения, какg (f x 2) (f x 5)? Они не являются неотъемлемой частью алгоритма, и различные варианты можно взаимозаменять, не влияя ни на что, кроме производительности. Трудности в выполнении оптимизации здесь, по сути, заключаются в том, чтобы понять, когда замена может быть фактически выполнена без изменения смысла, и предсказать, какая версия будет иметь наилучшие результаты. Много ручных оптимизаций попадают в эту категорию, наряду с большой сообразительностью GHC.

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

  Это также та часть, в которой GHC имеет огромное преимущество, потому что лень и чистота делают многие вещи намного проще, и я подозреваю, что приводит к тому, что люди делают насмешливые замечания типа "Оптимизация компиляторов - это миф (за исключением, возможно, в Haskell) ". Но также и к нереалистичному оптимизму в отношении того, что может сделать даже GHC.

• Детали низкого уровня: такие вещи, как макет памяти и другие аспекты окончательного кода. Они, как правило, несколько загадочны и сильно зависят от деталей реализации среды выполнения, ОС и процессора. Подобные оптимизации, по сути, являются причиной того, что у нас есть компиляторы, и, как правило, вам не о чем беспокоиться, если вы не пишете код, требующий больших вычислительных ресурсов (или сами пишете компилятор).

Что касается вашего конкретного примера: GHC не изменит существенную временную сложность вашего алгоритма. Это может быть в состоянии удалить некоторые постоянные факторы. Чего он не может сделать, так это применить улучшения с постоянным коэффициентом, которые не могут быть уверены, что они правильные, особенно те, которые технически изменяют смысл программы такими способами, которые вас не волнуют. В качестве примера можно привести ответ @ sclv, который объясняет, как вы используете print создает ненужные накладные расходы; GHC ничего не мог с этим поделать, и на самом деле текущая форма, возможно, помешает другим оптимизациям.

Answer 2

Здесь есть концептуальная проблема. Перестановки генерируют потоковые перестановки, и фильтр тоже потоковый. Что заставляет все преждевременно, так это "шоу", скрытое в "печати". Измените свою последнюю строку на:

mapM print $ pointlessQueens $ (read :: String -> Int) n

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

Однако не следует ожидать каких-либо улучшений на порядок от оптимизаций ghc (есть несколько очевидных, которые вы получите, в основном связанные со строгостью и сгибами, но раздражать их положением). Как правило, вы получаете постоянные факторы.

Редактировать: как Луки указывает ниже, шоу также потоковое (или, по крайней мере, шоу [Int] есть), но, тем не менее, буферизация строки усложняет понимание подлинной скорости вычислений...

Answer 3

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

В случае вашего вопроса, глупо говорить о возможной / невозможной оптимизации, о флагах компилятора, о том, как наилучшим образом его сформулировать и т. Д., Когда улучшение алгоритма так нагло смотрит нам в глаза.

Одна из первых вещей, которые будут опробованы, это перестановки, начинающиеся с первой ферзя в позиции 1 и второй ферзя в позиции 2 ([1,2...]). Это, конечно, не решение, и нам придется переместить одну из королев. Однако в вашей реализации все перестановки, включающие эту комбинацию двух первых ферзей, будут проверены! Поиск должен остановиться на этом и мгновенно перейти к перестановкам с участием [1,3,...],

Вот версия, которая делает такое сокращение:

import Data.List
import Control.Monad

main = getLine >>= mapM print . queens . read

queens :: Int -> [[Int]]
queens n = queens' [] n

queens' xs n 
 | length xs == n = return xs 
 | otherwise = do 
  x <- [1..n] \\ xs
  guard (validQueens (x:xs))
  queens' (x:xs) n

validQueens x = 
  and [abs (x!!i - x!!j) /= j-i | i<-[0..length x - 2], j<-[i+1..length x - 1]]

Answer 4

Я понимаю, что ваш вопрос касался оптимизации компилятора, но, как показала дискуссия, отсечение необходимо.

Первая известная мне статья о том, как сделать это для задачи n queens на ленивом функциональном языке, - это статья Тернера "Уравнения рекурсии как язык программирования". Вы можете прочитать ее в Google Книгах здесь.

С точки зрения вашего комментария о шаблоне, который стоит запомнить, эта проблема представляет очень мощный шаблон. Отличной статьей об этой идее является статья Филиппа Уодлера "Как заменить отказ списком успехов", которую можно прочитать в Google Книгах здесь

Вот чистая, не монадическая реализация, основанная на реализации Turner Miranda. В случае n = 12 (королев 12 12) он возвращает первое решение за 0,01 с и вычислит все 14 200 решений менее чем за 6 секунд. Конечно, печать этих занимает гораздо больше времени.

queens :: Int -> Int -> [[Int]]
queens n boardsize = 
    queensi n 
        where
          -- given a safe arrangement  of queens in the first n - 1 rows,
          -- "queensi n" returns a list of all the safe arrangements of queens
          -- in the first n rows
          queensi :: Int -> [[Int]]
          queensi 0  = [[]]
          queensi n  = [ x : y | y <- queensi (n-1) , x <- [1..boardsize], safe x y 1]

-- "safe x y n" tests whether a queen at column x would be safe from previous
-- queens in y where the first element of y is n rows away from x, the second
-- element is (n+1) rows away from x, etc.
safe :: Int -> [Int] -> Int -> Bool
safe _ [] _ = True
safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]
-- we only need to check for queens in the same column, and the same diagonals;
-- queens in the same row are not possible by the fact that we only pick one
-- queen per row