Фильтр бенчмаркинга и раздел

Question

Я тестировал производительность функции partition для списков и получил некоторые странные результаты, я думаю.

У нас есть то, что partition p xs == (filter p xs, filter (not . p) xs), но мы выбрали первую реализацию, потому что она выполняет только один обход по списку. Тем не менее, результаты, которые я получил, говорят, что, возможно, лучше использовать реализацию, которая использует два обхода.

Вот минимальный код, который показывает, что я вижу

import Criterion.Main 
import System.Random 
import Data.List (partition) 

mypartition :: (a -> Bool) -> [a] -> ([a],[a]) 
mypartition p l = (filter p l, filter (not . p) l) 



randList :: RandomGen g => g -> Integer -> [Integer] 
randList gen 0 = [] 
randList gen n = x:xs 
    where 
    (x, gen') = random gen 
    xs = randList gen' (n - 1) 

main = do 
    gen <- getStdGen 
    let arg10000000 = randList gen 10000000 
    defaultMain [ 
     bgroup "filters -- split list in half " [ 
     bench "partition100"   $ nf (partition (>= 50)) arg10000000 
     , bench "mypartition100"  $ nf (mypartition (>= 50)) arg10000000 
     ] 
     ] 

Я побежал тесты как с -O и без него, и оба раза я получаю, что двойные обходы лучше.

Я использую ghc-7.10.3 с criterion-1.1.1.0

Мои вопросы:

• Является ли это ожидалось?

• Правильно ли я использую Критерий? Я знаю, что лень может быть сложным, и (filter p xs, filter (not . p) xs) будет выполнять только два обхода, если используются оба элемента кортежа.

• Должно ли это что-то сделать, поскольку списки обрабатываются в Haskell?

Большое спасибо!

Answer 1

На вопрос нет черного или белого ответа. Для того, чтобы рассекать проблема рассмотрим следующий код:

import Control.DeepSeq 
import Data.List (partition) 
import System.Environment (getArgs) 


mypartition :: (a -> Bool) -> [a] -> ([a],[a]) 
mypartition p l = (filter p l, filter (not . p) l) 


main :: IO() 
main = do 
    let cnt = 10000000 
     xs = take cnt $ concat $ repeat [1 .. 100 :: Int] 
    args <- getArgs 
    putStrLn $ unwords $ "Args:" : args 
    case args of 
    [percent, fun] 
     -> let p = (read percent >=) 
     in case fun of 
      "partition"  ->    print $ rnf $ partition p xs 
      "mypartition" ->    print $ rnf $ mypartition p xs 
      "partition-ds" -> deepseq xs $ print $ rnf $ partition p xs 
      "mypartition-ds" -> deepseq xs $ print $ rnf $ mypartition p xs 
      _ -> err 
    _ -> err 
    where 
    err = putStrLn "Sorry, I do not understand." 

Я не использую критерий, чтобы лучше контролировать о порядке оценки. Чтобы получить тайминги, я использую параметр времени исполнения +RTS -s. Различные тестовые примеры выполняются с использованием различных параметров командной строки. Первая опция командной строки определяет, для какого процента данных используется предикат. Вторая опция командной строки выбирает между различными тестами.

Испытания различают два случая:

1. Данные генерируются лениво (второй аргумент partition или mypartition).
2. Данные уже полностью оцениваются в памяти (2-й аргумент partition-ds или mypartition-ds).

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

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

В случае, если 2, partition не может воспроизвести это преимущество, поскольку все элементы уже находятся в памяти.

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

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

И наоборот, если предикат не соответствует многим элементам или все элементы уже находятся в памяти, mypartition работает лучше, поскольку его рекурсия не имеет отношения к парам в отличие от partition.

Вопрос о статировании вопроса «Irrefutable pattern does not leak memory in recursion, but why?» может дать более подробную информацию об обработке пар в рекурсии partition.