Какое влияние предсказание ветвей оказывает на программу на Haskell? - PullRequest
Новая
       33

Какое влияние предсказание ветвей оказывает на программу на Haskell?

1 голос
/ 30 марта 2019

Я сравниваю сортировку при вставке на худший случай (в обратном порядке) и случайный ввод. 

import Control.Monad
import Data.List
import System.Random
import Control.Exception
import Control.DeepSeq
import Criterion.Main

--- Sorting ---
insertionSort :: (Ord a) => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = x `insert` (sort xs)

--- Generators ---
worstCaseGen :: Int -> [Int]
worstCaseGen n = [n, n-1..1]

bestCaseGen :: Int -> [Int]
bestCaseGen n = [1..n]

randomGen :: Int -> StdGen -> [Int]
randomGen n = take n . randoms

--- Testing ---
main = do
  gen <- newStdGen
  randomList <- evaluate $ force $ randomGen 10000 gen
  defaultMain [
    bgroup "Insertion Sort" [ bench "worst" $ nf insertionSort (worstCaseGen 10000)
                            , bench "best" $ nf insertionSort (bestCaseGen 10000)
                            , bench "gen" $ nf last randomList
                            , bench "random" $ nf insertionSort randomList
                            ]
    ]

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

Это мой .cabal, если он помогает: 

executable BranchPrediction
  main-is:             Main.hs
  build-depends:       base >=4.12 && <4.13,
                       random,
                       criterion ==1.5.4.0,
                       deepseq ==1.4.4.0
  default-language:    Haskell2010

1 Ответ

6 голосов
/ 30 марта 2019

Вы назвали sort вместо insertionSort в вашем (предполагаемом) рекурсивном случае.Это оптимизированная для выполнения сортировка слиянием, которая обрабатывает обратный ввод за O (n) раз.Таким образом, ваш «наихудший случай» на самом деле является почти наилучшим случаем для алгоритма, как написано, а не как задумано.

...