Почему Prelude.drop быстрее обычного? - PullRequest
Новая
       7

Почему Prelude.drop быстрее обычного?

0 голосов
/ 02 июля 2018

Я сделал несколько прогонов: 

main = print $ head . drop (2^30) $ [1..]

- с Prelude.drop и тривиальным drop. Вариант Prelude всегда быстрее примерно на 45%, и я не могу понять, почему. Я даже извлек определение GHC.List.drop из base-4.11.1.0, но оно работает хуже, чем мой тривиальный код! Что происходит?

Вот что я делаю: 

% stack ghc -- --version           
The Glorious Glasgow Haskell Compilation System, version 8.2.2

Prelude.drop: 

% git checkout drop-prelude
% git clean --force
% cat ListTest.hs
module Main where

main = print $ head . drop (2^30) $ [1..]
% stack ghc -- ListTest.hs
[1 of 1] Compiling Main             ( ListTest.hs, ListTest.o )
Linking ListTest ...
% time ./ListTest
1073741825
./ListTest  18.76s user 0.09s system 99% cpu 18.906 total

Тривиально drop: 

% git checkout drop-naive 
% git clean --force
% cat ListTest.hs
module Main where

dropNaive :: Int -> [a] -> [a]
dropNaive 0 xs = xs
dropNaive n [ ] = [ ]
dropNaive n (x: xs) = dropNaive (pred n) xs

main = print $ head . dropNaive (2^30) $ [1..]
% stack ghc -- ListTest.hs
[1 of 1] Compiling Main             ( ListTest.hs, ListTest.o )
Linking ListTest ...
% time ./ListTest
1073741825      
./ListTest  31.56s user 0.12s system 99% cpu 31.774 total

drop от GHC.List: 

% git checkout drop-ghc 
% git clean --force
% cat ListTest.hs 
{-# LANGUAGE BangPatterns #-}

module ListTest where

dropGhc :: Int -> [a] -> [a]
{-# INLINE dropGhc #-}
dropGhc n xs
  | n <= 0     = xs
  | otherwise  = unsafeDrop n xs
  where
    unsafeDrop :: Int -> [a] -> [a]
    unsafeDrop !_ []     = []
    unsafeDrop 1  (_:xs) = xs
    unsafeDrop m  (_:xs) = unsafeDrop (m - 1) xs
% cat ListTestRunner.hs 
import ListTest

main = print $ head . dropGhc (2^30) $ [1..]
% stack ghc -- ListTestRunner.hs
[1 of 2] Compiling ListTest         ( ListTest.hs, ListTest.o )
[2 of 2] Compiling Main             ( ListTestRunner.hs, ListTestRunner.o )
Linking ListTestRunner ...
% time ./ListTestRunner
1073741825            
./ListTestRunner  35.35s user 0.14s system 99% cpu 35.591 total

1 Ответ

0 голосов
/ 03 июля 2018

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

Похоже, вы просто не компилируете с включенной оптимизацией. Прелюдия скомпилирована с оптимизацией и связана, так что вы неявно используете оптимизированный код при использовании прелюдии drop. Локальное воспроизведение (после уменьшения константы с 2^30 до 2^25 & mdash; нет причин заставлять себя ждать так долго), включение оптимизации приводит к тому, что dropGhc и prelude drop имеют одинаковую синхронизацию, а dropNaive - это не значительно хуже. Существует небольшая разница в выражениях между dropGhc и dropNaive, которая может иметь незначительные результаты в сгенерированном коде; У меня нет хорошей интуиции, почему один из них лучше другого.

Также обратите внимание, что base - это специальный пакет в том смысле, что он собирается как часть процесса сборки ghc, используя собственную систему сборки, а не Cabal, как обычные пакеты. Как отметил @sjakobi в комментариях, в конфигурации сборки ghc есть настройка , которая устанавливает уровень оптимизации для base при O2.

...