Степень оптимизации 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)

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

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

1. Может ли точечная версия вышеуказанной функции быть более оптимизированной для оптимизации?
2. Какие шаги я могу предпринять ввремя компиляции / компоновки, чтобы стимулировать оптимизацию?
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 Книгах здесь

monadic, реализация, основанная на реализации 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