public
Created

! vs unsafeIndex

  • Download Gist
post.md
Markdown

Ответ на вопрос в этом посте.

Для начала слегка модифицируем код, чтоб он компилировался.

import qualified Data.List.Stream as S
import qualified Data.Vector.Unboxed as U

f n = let arr = U.enumFromTo 1 n 
      in S.sum $ S.map (\i -> arr U.! (i `rem` n)) $ S.unfoldr (\i -> if i < n then Just (i, i+1) else Nothing) 0

main = print $ f 100000000

Запустив скомпилированный с -O2 код мы получим такой вот отчет:

   2,006,833,012 bytes allocated in the heap
           4,984 bytes copied during GC
     400,026,076 bytes maximum residency (2 sample(s))
         566,376 bytes maximum slop
             383 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  3062 collections,     0 parallel,  0.02s,  0.02s elapsed
  Generation 1:     2 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.13s elapsed)
  MUT   time    1.23s  (  1.67s elapsed)
  GC    time    0.02s  (  0.02s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    1.25s  (  1.81s elapsed)

  %GC time       1.2%  (1.1% elapsed)

  Alloc rate    1,628,383,629 bytes per MUT second

  Productivity  98.8% of total user, 68.0% of total elapsed

Легко видеть, что через эфемерное поколение со свистом пролетает 2 гигабайта сверхкороткоживущих объектов. Обратите внимание, что до копирования они не доживают.

И это при том, что выделять память в цикле тут, в общем-то, незачем. Конвейер ФВП фьюзится в хвосторекурсивную функцию, которая всю работу и делает. Если ее отчистить от всяких Core-излишеств и подсократить несущественное, то вот что мы получаем:

loop_sum :: Int# -> Int# -> Int#
loop_sum s i =
    case i <# 100000000 of
      False -> s
      True -> 
        let rem :: Int#
            rem = remInt# i 100000000 in
        let boxed_rem :: Int
            boxed_rem = I# rem in
        let boxed_n :: Int
            boxed_n = I# n in
        case rem >=# 0 of
            False -> error1 ... (checkIndex_msg boxed_rem boxed_n)) ...
            True ->
              case rem <# n of
                False -> error1 ...
                True -> loop_sum 
                    (s +# (indexIntArray# byteArray (start +# rem)))
                    (i +# 1)

Видно, что все вычисления производятся с анбоксед-типами, в куче память для этого не выделяется. А выделяется она для того, чтоб передать индексы в развесистую функцию error1 (если бы я скопировал ее сюда со всеми аргументами - код бы вырос раза в два) сообщающую о выходе за границы массива. При этом память в куче для этих несчастных индексов выделяется не после того, когда выход за границы обнаружен, а всегда. Зарание. За что, спросите вы? А просто так.

Ну и, понятное дело, если заменить ! на unsafeIndex, то ничего в куче выделяться в этой worker-функции не будет:

     400,607,500 bytes allocated in the heap
           2,376 bytes copied during GC
          26,152 bytes maximum residency (1 sample(s))
          19,708 bytes maximum slop
             383 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:     1 collections,     0 parallel,  0.00s,  0.00s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.06s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.80s  (  1.06s elapsed)
  GC    time    0.00s  (  0.06s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.80s  (  1.12s elapsed)

  %GC time       0.0%  (5.0% elapsed)

  Alloc rate    503,525,618 bytes per MUT second

  Productivity 100.0% of total user, 71.3% of total elapsed

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.