۲۷ - ۲سنجش با Criterion

اینکه آدم بخواد بدونه کُدِش چقدر سریع کار می‌کنه، چیزِ خیلی رایجی‌ه. اگه نتونین درست کُدِتون رو بِسَنجین، نمی‌تونین بدونین ۶ میکروثانیه استفاده کردین یا فقط ۵ تا. اون موقع فقط باید از خودتون بپرسین: "حس می‌کنم خوش‌شانسَم؟"*

*

م. شوخی رو گرفتین؟؟

اگه ترجیح میدین عملکرد ِ کُدتون رو به حدس و گمان نسپرین، بهترین راه‌ش اینه که چندبار عملکرد‌ِش رو اندازه بگیرین تا به یه بازه‌ی اطمینان برسین. خوشبختانه همه‌ی زحمت‌های این کار رو برایان اُسالیوان در کتابخونه ِ محشرِ ‏‎criterion‎‏ کشیده.

‏‎criterion‎‏ آموزش خیلی خوبی هم داره، با این حال ما هم روی یه مثال کار می‌کنیم تا بتونین با این فصل پیش برین. تو این برنامه یه نسخه از ‏‎(!!)‎‏ می‌نویسیم که ‏‎Maybe‎‏ برمی‌گردونه تا دیگه نیازی به تهی نباشه. موقعِ کامپایل ِ کد برای سنجش، یادتون باشه از پرچم‌های ‏‎-O‎‏ یا ‏‎-O2‎‏ برای GHC استفاده کنین. هم میشه بصورت دستی در زمانِ اجرای GHC تعیین‌شون کرد:

-- stack با
$ stack ghc -- -O2 bench.hs

-- stack بدون
$ ghc -O2 bench.hs

هم میشه از طریق تنظیمات ‏‎Cabal‎‏ (‏‎ghc-options‎‏) تعیین‌شون کرد.

خوب، اول ماژول رو آماده کنیم:

module Main where

import Criterion.Main

infixl 9 !?
_      !? n | n < 0 = Nothing
[]     !? _         = Nothing
(x:_)  !? 0         = Just x
(_:xs) !? n         = xs !? (n-1)

myList :: [Int]
myList = [1..9999]

main :: IO ()
main = defaultMain
  [ bench "index list 9999" $
      whnf (myList !!) 9998
  , bench "index list maybe index 9999" $
      whnf (myList !?) 9998
  ]

نسخه‌ای که خودمون از ‏‎(!!)‎‏ تعریف کردیم چیزِ جدیدی نداره. گفتیم که یه اوپراتور میانوند با شرکت‌پذیری از چپ (‏‎infixl‎‏) با تقدم ِ ۹ باشه. از فصلِ ۲ به بعد زیاد از این دوتا صحبت نکردیم. اوپراتور ِ ‏‎(!!)‎‏ ِ معمولی که در ‏‎base‎‏ تعریف شده هم همین تقدم و شرکت‌پذیری رو داره.

اگه از یه ماژول ِ ‏‎Main‎‏ بنچمارک می‌گیرین، باید ماژول ِ ‏‎Criterion.Main‎‏ رو از ‏‎criterion‎‏ وارد کنین. معمولاً یه پاراگراف ِ بنچمارک توی فایلِ ‏‎.cabal‎‏ نوشته میشه که مثل یه اجراشدنی رفتار می‌کنه. اما میشه با Stack بنچمارکِ "یکبار مصرف" هم داشت:

$ stack build criterion
$ stack ghc -- -O2 benchIndex.hs
$ ./benchIndex

تو مثالی که بالاتر نوشتیم، ‏‎main‎‏ از یکی از تابع‌های ‏‎criterion‎‏ به اسمِ ‏‎whnf‎‏ استفاده می‌کنه. همونطور که احتمالاً حدس میزنین، تابع‌های ‏‎whnf‎‏ و ‏‎nf‎‏ (اون هم از ‏‎criterion‎‏) به حالت معمولی با سر ضعیف و حالت معمولی اشاره دارن. قبلاً گفتیم که حالت معمولی با سر ضعیف تا اولین داده‌ساز حساب می‌کنه. یعنی اگه بیرونی‌ترین داده‌ساز‌ِتون یه ‏‎Maybe‎‏ باشه، فقط اونقدری حساب می‌کنه که بفهمه ‏‎Just‎‏ ِه یا ‏‎Nothing‎‏ – اگه ‏‎Just a‎‏ دارین، هزینه‌ی محاسبه‌ی اون مقدار ‏‎a‎‏ رو حساب نمی‌کنه.

اگه از ‏‎nf‎‏ استفاده می‌کردین، یعنی می‌خواستین علاوه بر هزینه‌ی محاسبه‌ی اولین داده‌ساز، هزینه‌ی محاسبه‌ی کاملِ ‏‎a‎‏ هم حساب میشد. برای تشخیص بین اینکه ‏‎whnf‎‏ مناسب‌تره یا ‏‎nf‎‏، باید ببینین چه چیزی رو می‌خواین بنچمارک کنین، و اینکه رسیدن به داده‌ساز ِ اول همه‌ی کاری که می‌خواین اندازه بگیرین رو انجام میده یا نه. تفاوتِ بین این دوتا و نحوه‌ی تصمیم‌گیری بین‌شون رو بعداً بیشتر توضیح میدیم.

تو این مثال، دوتا چیز رو می‌خوایم مقایسه کنیم: زمانِ محاسبه تا حالت معمولی با سر ضعیف، بعد از اعمال ِ اوپراتورِ اندیس‌گیری به اون لیستِ طولانی؛ یکی با استفاده از اوپراتور اصلی و یکی هم با اون نسخه‌ی امنی که خودمون تعریف کردیم. دلیلی که فقط تا حالت معمولی با سر ضعیف لازم داریم، اینه که هم ‏‎(!!)‎‏ و ‏‎(!?)‎‏ هر دو وقتی یه داده‌ساز برمی‌گردونن که همه‌ی کار رو کردن. از سه حالتِ اول معلومه:

_      !? n | n < 0 = Nothing
[]     !? _         = Nothing
(x:_)  !? 0         = Just x

تابع فقط وقتی به این سه حالت میرسه که همون قدری که قراره لیست رو طی کنه، طی کرده باشه. حالت بازگشتی ِ زیر داده‌سازی برنمی‌گردونه. در عوض انقدر خودش رو صدا میزنه تا به یکی از سه حالتِ بالا برسه. محاسبه تا WHNF در یه موردِ بازگشتی مثل این متوقف نمیشه (نمی‌تونه):

(_:xs) !? s         = x !? (n-1)
-- ‎‏تابع خودش رو صدا زده،‏‎
-- ‎‏نیست.‏‎ WHNF هنوز

وقتی کد بالا تا حالت معمولی حساب بشه، انقدر ادامه میده تا به اندیس ِ مورد نظر برسه؛ یا میرسه به المان، یا میرسه به آخرِ لیست. یه مثال ببینیم:

[1, 2, 3] !? 2
-- منطبق با حالت آخر

(_: [2, 3]) !? 2
  = [2, 3] !? (2-1)
-- داده‌ساز نیست، ادامه بده

[2, 3] !? 1
-- منطبق با حالت آخر

(_: [3]) !? 1
  = [3] !? (1-1) 
-- داده‌ساز نیست، ادامه بده

[3] !? 0
-- Just منطبق با حالت

(x:[]) !? 0 = Just x
-- ‎‏متوقف میشیم.‏‎ Just سَرِ

اینجا برحسبِ اتفاق می‌دونستیم که ‏‎x‎‏ مقدارِش ۳ بود، اما اگه در لحظه‌ی ساختِ لیست به صورتِ فرصت‌طلبانه محاسبه نشده بود، ثانک میشد.

حالا تایپِ این تابع‌ها رو ببینیم:

defaultMain :: [Benchmark] -> IO ()

whnf :: (a -> b) -> a -> Benchmarkable
nf :: Control.DeepSeq.NFData b =>
      (a -> b) -> a -> Benchmarkable

دلیل اینکه اون دوتا تابع برای آرگومانِ اول‌شون یه تابع می‌خوان اینه که جواب‌شون به اشتراک گذاشته نشه، چیزی که فصلِ قبل توضیح دادیم. می‌خوایم برای هر نمونه‌ی بنچمارک، کلِ کار رو دوباره انجام بده، و این طراحی جلوی اشتراک‌گذاری رو می‌گیره. دقت کنین که اگه می‌خواین از نوع‌داده ِ خودتون با ‏‎nf‎‏ استفاده کنین، باید یه نمونه ِ ‏‎NFData‎‏ براش تعریف کنین. مثال‌هایی از این کار رو می‌تونین از کتابخونه ِ ‏‎deepseq‎‏ در Hackage پیدا کنین.

هدف ما تو این مثال، اینه که کاری کنیم عملکرد ِ ‏‎(!?)‎‏ و ‏‎(!!)‎‏ یکسان بشن. تعریفی که اینجا برای ‏‎(!?)‎‏ نوشتیم براساسِ تعریف ‏‎(!!)‎‏ در گزارش هسکل ِه. توی ‏‎base‎‏ این شکلیه:

-- و base در Data.List برین به مستنداتِ
-- ‎‏کلیک کنین‏‎ (!!) ‎‏برای‏‎ source روی لینک

#ifdef USE_REPORT_PRELUDE 
xs !! n | n < 0 =
  error "Prelude.!!: negative index"
[] !! _         =
  error "Prelude.!!: index too large"
(x:_) !! 0      = x
(_:xs) !! n     = xs !! (n-1)
#else

با این حال بعد از اینکه بنچمارک‌ها رو اجرا کنین، می‌بینین که نسخه‌ای که ما براساس کدِ بالا نوشتیم، خیلی سریع نیست.* خب، درسته! اکثر وقت‌هایی که هم یه نسخه‌ی Report و هم یه نسخه‌ی غیرِ Report از یه تابع در ‏‎base‎‏ هست، به این خاطره که یه راه برای بهینه و سریع‌تر کردن‌ش پیدا شده بوده. اگه پایین‌ترِ ‏‎#else‎‏ رو نگاه کنیم، نسخه‌ای که جایگزین شده رو پیدا می‌کنیم:

-- ‎‏، و‏‎bottom یه negIndex
-- هست const bottom یه tooLarge

{-# INLINABLE (!!) #-}
xs !! n
  | n < 0     = negIndex
  | otherwise =
      foldr
      (\x r k -> case k of
                   0 -> x
                   _ -> r (k-1))
      tooLarge xs n
*

اگه نتایج عجیب‌غریبی از بنچمارک گرفتین، ممکنه کلکِ پاک کردنِ build‌ِتون، کمک کنه. اگه با Stack کار می‌کنین، دستورِ ‏‎stack clean‎‏، و اگه با Cabal کار می‌کنین، دستورِ ‏‎cabal clean‎‏ رو اجرا کنین. گاهی اوقات اتفاقات غیرقابل توضیح پیش میان؛ ولی این کار زیاد لازم نمیشه.

نسخه‌ی غیرِ Report با ‏‎foldr‎‏ نوشته شده، و ‏‎foldr‎‏ در اکثر موارد از بهینه‌سازی‌های متنوع و چندتا قانونِ بازنویسی بهره‌منده (با عرض پوزش، این قوانین رو توضیح نمیدیم). این نسخه یه پراگما هم داره که به GHC میگه در صورتی که تخمین‌زننده‌ی هزینه صلاح دونست، اجازه داره جایی که تابع استفاده شده، کُدِش رو دَرخط کنه. پس همین تغییرات رو به نسخه‌ی خودمون اضافه کنیم تا از همین بهینه‌سازی‌ها استفاده کنه:

infixl 9 !?
{-# INLINABLE (!!) #-}
xs !? n
  | n < 0     = Nothing
  | otherwise =
      foldr
      (\x r k ->
        case k of
          0 -> Just x
          _ -> r (k-1))
      (const Nothing) xs n

اگه این رو اجرا کنین... می‌بینین فرقِ زیادی نکرده. پس چی کار میشه کرد تا عملکرد‌ِش بهتر شه؟

خوب، تایپ سیگنچری در کار نیست (مگه خودتون نوشته باشین). با تعیینِ تایپِ اون آرگومانِ عددی به ‏‎Int‎‏، عملکردِش مثلِ اوپراتورِ اصلی میشه:

infixl 9 !?
{-# INLINABLE (!!) #-}
(!?) :: [a] -> Int -> Maybe a
xs !? n
  | n < 0     = Nothing
  | otherwise =
      foldr
      (\x r k ->
        case k of
          0 -> Just x
          _ -> r (k-1))
      (const Nothing) xs n

تابعِ توی ماژول‌ِتون رو به این تغییر بدین و دوباره بنچمارک بگیرین تا مطمئن بشین.

مشکل اینجا بود که ‏‎Num a => a‎‏ به تایپِ ‏‎Integer‎‏ تعیین می‌شد (از طریقِ پیش‌فرضی‌سازی تایپ)، و کلاً ‏‎Integer‎‏ بازدهیِ کمتری نسبت به ‏‎Int‎‏ داره. نسخه‌ای که با ‏‎Int‎‏ نوشته شده، تبدیل به یه حلقه ِ ابتدایی‌تر و سریع‌تر میشه. خودتون از دو راه می‌تونین ببینین: یکی اینکه ‏‎Int‎‏ رو با ‏‎Integer‎‏ عوض کنین و کدِ رو دوباره اجرا کنین، یا GHC Core ِ خروجیِ هر نسخه رو با هم مقایسه کنین.

توضیح بیشتر برای ‏‎whnf‎‏ و ‏‎nf‎‏

برگردیم به اینکه چطور بین ‏‎whnf‎‏ و ‏‎nf‎‏ تصمیم بگیریم. ‏‎whnf‎‏ برای زمانی خوبه که رسیدن به اولین داده‌ساز، نشونه‌ی خوبی از انجامِ کاری که می‌خواین اندازه بگیرین باشه. یه مثال ساده بزنیم، برنامه‌ای برای پیدا کردنِ یه جور داده از یه پایگاه داده در نظر بگیرین، بر فرض برنامه‌ای که دنبال اسمِ یه شخص می‌گرده و می‌بینه که آیا آدرسی برای اون آدم ثبت شده یا نه. اگه داده‌ای پیدا کنه، ممکنه اون اطلاعات رو توی یه فایل چاپ کنه.

به احتمال زیاد، اون بخشی از برنامه که عملکردِش مَدِ نظره، تابعِ جستجو ایه که داده رو پیدا و وجودیت‌ش رو تعیین می‌کنه؛ نه سرعتِ کامپیوتر در چاپِ یه لیست آدرس توی فایل. در چنین حالتی، چیزی که موردِ نظره در سطحِ حالت معمولی با سر ضعیف ِه، و ‏‎whnf‎‏ زمان لازم برای پیدا‌کردنِ داده و تعیین اینکه ‏‎Nothing‎‏ ِه یا ‏‎Just a‎‏ رو دقیق‌تر میگه.

اما اگه علاوه بر زمان لازم برای پیدا‌کردنِ داده، زمان لازم برای چاپِ نتایج هم مهم باشه، اون موقع باید تا حالت معمولی محاسبه بشه. گاهی اوقات چنین اندازه‌گیری‌ای به درد می‌خوره. به زودی چندتا مثال می‌بینیم.

فعلاً دوتا اوپراتورِ اندیس‌گیری که داریم رو در نظر می‌گیریم: یکی ‏‎(!!)‎‏ که در ‏‎base‎‏ تعریف شده، و یکی اونی که خودمون نوشتیم و بجای تهی از ‏‎Maybe‎‏ استفاده می‌کنه.

در اولی، تایپِ نتیجه‌ی نهایی میشه ‏‎a‎‏. تابع انقدر خودش رو صدا میزنه تا یا تهی برگردونه یا مقدارِ اون اندیس رو. در هر صورت، کلِ کاری که می‌خواین اندازه بگیرین رو انجام میده: طی‌کردنِ لیست. محاسبه تا WHNF یعنی سرِ مقدارِ ‏‎a‎‏ متوقف میشه.

در دومی که با ‏‎Maybe‎‏ کار می‌کنه، محاسبه تا WHNF یعنی یا سرِ ‏‎Just‎‏ یا سرِ ‏‎Nothing‎‏ متوقف میشه. با ‏‎whnf‎‏ محتویاتِ داده‌ساز ِ ‏‎Just‎‏ محاسبه نمیشه، اما با ‏‎nf‎‏ محاسبه میشن. چون اینجا می‌خوایم بینیم چقدر طول میکشه تا این کد به مقدار واقع در اندیس ِ ورودیِ لیست برسه، هر دوی اونها برای بنچمارک مناسب‌اند.

مثال‌مون رو با چندتا تغییر ببینیم:

module Main where

import Criterion.Main
import Debug.Trace

myList :: [Int]
myList = trace "myList was evaluated"
         ([1..9999] ++ [undefined])

-- رو بنویسین (!?) ‎‏اینجا نسخه‌ی خودتون برای‏‎

main :: IO ()
main = defaultMain
  [ bench "index list 9999" $
      whnf (myList !!) 9998
  , bench "index list maybe index 9999" $
      nf (myList !?) 9999
  ]

دقت کنین چی کار کردیم. در اندیس ِ ۹۹۹۹ یه ‏‎undefined‎‏ اضافه کردیم و با اوپراتورِ ‏‎(!!)‎‏ به اندیس ِ قبلی‌ش می‌رسیم، چون هیچ ساختارِ داده‌ای (مثلِ ‏‎Nothing‎‏ یا ‏‎Just‎‏) اطرافش نداره که محاسبه رو نگه داره. هم ‏‎whnf‎‏ و هم ‏‎nf‎‏ الزاماً اون مقدارِ تهی رو اجبار می‌کنن.

برای بنچمارکِ ‏‎(!?)‎‏، ‏‎whnf‎‏ رو به ‏‎nf‎‏ تغییر دادیم. حالا در اولین اجرای بنچمارک، ‏‎undefined‎‏ در اندیس ِ آخر رو محاسبه می‌کنه و شکست می‌خوره: 

benchmarking index list maybe index 9999
criterion1: Prelude.undefined

یه مقدارِ تابعی که بجای یه ساختارِ داده تهی برگردونه هم، می‌تونه نقشِ نقطه‌ی توقف برای WHNF رو بازی کنه. اینها رو ببینین:

Prelude> (Just undefined) `seq` 1
1
Prelude> (\_ -> undefined) `seq` 1
1
Prelude> ((\_ -> Just undefined) 0) `seq` 1
1
Prelude> ((\_ -> undefind) 0) `seq` 1
*** Exception: Prelude.undefined

بیشتر مواقع ‏‎whnf‎‏ جوابِ کار رو میده.

موردی که ‏‎nf‎‏ به کار میاد

حالا یه مثال ببینیم که ‏‎whnf‎‏ برای بنچمارکینگ کافی نیست. یه چیزی که بر خلافِ ‏‎(!!)‎‏، بازگشتیِ حفاظت‌شده داره:

module Main where

import Criterion.Main 

myList :: [Int]
myList = [1..9999]

main :: IO ()
main = defaultMain
  [ bench "map list 9999" $
      whnf (map (+1)) myList
  ]

این یه مثال از بازگشتیِ حفاظت‌شده هست، چون یه داده‌ساز بین هر مرحله‌ی خوداتکایی قرار گرفته. وقتی با ‏‎map‎‏ سروکار داریم، اون ساختارِ داده میشه سلولِ cons. با بازگشتیِ حفاظت‌شده میشه مراحلِ خوداتکایی رو دونه‌به‌دونه تا حالتِ معمولی با سر ضعیف مصرف کرد.

با ‏‎foldr‎‏، هم میشه بازگشتی محافظت‌شده و هم میشه بازگشتیِ محافظت‌نشده تعریف کرد، که تماماً بستگی به کاری که تابع فولدینگ انجام میده داره تا قابلیت‌های خودِ ‏‎foldr‎‏. حالا نتیجه‌ی بنچمارک چی میشه؟

Linking bin/bench ...
time
  8.844 ns   (8.670 ns .. 9.033 ns)
  0.998 R²   (0.997 R² .. 1.000 R²)
mean
  8.647 ns   (8.567 ns .. 8.751 ns)
std dev
  293.3 ps   (214.7 ps .. 412.9 ps)
variance introduced by outliers:
  57% (severly inflated)

خوب یه کم مشکوک‌ه. واقعاً پیمایش ِ ۱۰۰۰۰ المانِ یه لیستِ پیوندی توی هسکل فقط ۸٫۸ نانوثانیه طول میکشه؟ قبلاً یه مثال از اینکه تقریباً چقدر باید طول بکشه دیدیم. اینجا بنچمارک‌مون زیادی تنبل ِه. مشکل اینجاست که ‏‎map‎‏ از بازگشتیِ محافت‌شده استفاده می‌کنه، و سلول‌های cons ِ لیست، بینِ هر بازگشت ِ ‏‎map‎‏ قرار گرفتن. شاید از فصل‌های لیست و فولد یادتون باشه. پس نهایتاً همین‌قدر بیشتر حساب نمی‌کنه:

(_ : _)

پس نه یکی به مقدار اضافه کرده، نه مابقیِ لیست رو پیش رفته. همینطور سرِ سلول ِ اول نشسته. میشه ‏‎undefined‎‏ رو مرحله به مرحله با چیزهای دیگه جایگزین کرد و بنچمارک گرفت تا ببینیم ‏‎whnf‎‏ چی رو حساب می‌کنه:

-- ‎‏رو اعمال می‌کنه؟‏‎ (+1)
myList = (undefined : [2..9999])

-- اصلاً تو لیست جلوتر میره؟
myList :: [Int]
myList = (undefined : undefined)

-- این دیگه باید بترکه چون دنبال یه
-- ‎‏می‌گرده تا وایسه.‏‎ (->) ‎‏داده‌ساز اول یا‏‎
myList :: [Int]
myList = undefined

اشکالی نداره، درست‌ش می‌کنیم!

-- این تیکه رو
whnf (map (+1)) myList

-- ‎‏به این تغییر بدین: ‏‎
nf (map (+1)) myList

بعد نتیجه این میشه:

time
  122.5 μs   (121.7 μs .. 123.9 μs)
  0.999 R²   (0.998 R² .. 1.000 R²)
mean
  123.0 μs   (122.0 μs .. 125.6 μs)

std dev
  5.404 μs   (2.806 μs .. 9.323 μs)

با درنظر داشتنِ اینکه تماماً یه لیست جدید ساختیم، این خیلی واقعی‌تره. به همین خاطر از اوپراتور اندیس‌گذاری کُندتَر شده – فقط یه مقدار نمیده بیرون، یه لیست جدید هم درست می‌کنه.

بطور کلی، برای تصمیم‌گیری بین ‏‎whnf‎‏ و ‏‎nf‎‏، از خودتون بپرسین: "با رسیدن به داده‌ساز ِ اول، همه یا بیشترِ کاری که مهمه انجام میشه؟" فقط مراقب باشین زیادی از ‏‎nf‎‏ استفاده نکنین. اگه تابعی دارین که برای درست‌کردنِ یه ساختارِ داده ِ پیچیده همه‌ی کار رو انجام میده، ‏‎nf‎‏ باعث میشه کُدتون زیادی کند به نظر برسه و بفرست‌تون دنبالِ نخود سیاه.