Бенчмаркинг фильтра и раздела

Я тестировал производительность функции 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?

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

Ответы

Ответ 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."

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

Тесты различают два случая:

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

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

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

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

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

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

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

Задача Stackoverflow "Необработанный шаблон не утечка памяти в рекурсии, но почему?" может дать более подробную информацию об обработке пар в рекурсии partition.