Opracowujemy program, który odbiera i przekazuje dalej „wiadomości”, zachowując tymczasową historię tych wiadomości, aby na żądanie mógł przekazać historię wiadomości. Wiadomości są identyfikowane numerycznie, zwykle mają rozmiar około 1 kilobajta i musimy przechowywać setki tysięcy takich wiadomości.
Chcemy zoptymalizować ten program pod kątem opóźnienia: czas między wysłaniem a odebraniem wiadomości musi być poniżej 10 milisekund.
Program został napisany w języku Haskell i skompilowany za pomocą GHC. Okazało się jednak, że przerwy w usuwaniu elementów bezużytecznych są zbyt długie, aby sprostać naszym wymaganiom dotyczącym opóźnienia: ponad 100 milisekund w naszym programie w świecie rzeczywistym.
Poniższy program jest uproszczoną wersją naszej aplikacji. Używa Data.Map.Strictdo przechowywania wiadomości. Wiadomości są ByteStringidentyfikowane przez Int. 1 000 000 wiadomości jest wstawianych w rosnącej kolejności numerycznej, a najstarsze wiadomości są stale usuwane, aby historia obejmowała maksymalnie 200 000 wiadomości.
module Main (main) where
import qualified Control.Exception as Exception
import qualified Control.Monad as Monad
import qualified Data.ByteString as ByteString
import qualified Data.Map.Strict as Map
data Msg = Msg !Int !ByteString.ByteString
type Chan = Map.Map Int ByteString.ByteString
message :: Int -> Msg
message n = Msg n (ByteString.replicate 1024 (fromIntegral n))
pushMsg :: Chan -> Msg -> IO Chan
pushMsg chan (Msg msgId msgContent) =
Exception.evaluate $
let
inserted = Map.insert msgId msgContent chan
in
if 200000 < Map.size inserted
then Map.deleteMin inserted
else inserted
main :: IO ()
main = Monad.foldM_ pushMsg Map.empty (map message [1..1000000])
Skompilowaliśmy i uruchomiliśmy ten program przy użyciu:
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.10.3
$ ghc -O2 -optc-O3 Main.hs
$ ./Main +RTS -s
3,116,460,096 bytes allocated in the heap
385,101,600 bytes copied during GC
235,234,800 bytes maximum residency (14 sample(s))
124,137,808 bytes maximum slop
600 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 6558 colls, 0 par 0.238s 0.280s 0.0000s 0.0012s
Gen 1 14 colls, 0 par 0.179s 0.250s 0.0179s 0.0515s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.652s ( 0.745s elapsed)
GC time 0.417s ( 0.530s elapsed)
EXIT time 0.010s ( 0.052s elapsed)
Total time 1.079s ( 1.326s elapsed)
%GC time 38.6% (40.0% elapsed)
Alloc rate 4,780,213,353 bytes per MUT second
Productivity 61.4% of total user, 49.9% of total elapsed
Ważną metryką jest tutaj „maksymalna przerwa” wynosząca 0,0515 s lub 51 milisekund. Chcemy to zredukować przynajmniej o rząd wielkości.
Eksperymenty pokazują, że długość pauzy w GC jest określana przez liczbę wiadomości w historii. Zależność jest z grubsza liniowa lub być może superliniowa. Poniższa tabela przedstawia tę relację. ( Możesz zobaczyć nasze testy porównawcze tutaj , a niektóre wykresy tutaj ).
msgs history length max GC pause (ms)
=================== =================
12500 3
25000 6
50000 13
100000 30
200000 56
400000 104
800000 199
1600000 487
3200000 1957
6400000 5378
Eksperymentowaliśmy z kilkoma innymi zmiennymi, aby dowiedzieć się, czy mogą one zmniejszyć to opóźnienie, z których żadna nie robi dużej różnicy. Wśród tych nieistotnych zmiennych są: optymalizacja ( -O, -O2); Opcje RTS GC ( -G, -H, -A, -c), liczba rdzeni ( -N), różne struktury danych ( Data.Sequence), rozmiar wiadomości, a ilość generowanych śmieci krótkotrwały. Decydującym czynnikiem jest liczba wiadomości w historii.
Nasza teoria robocza mówi, że przerwy są liniowe w liczbie komunikatów, ponieważ każdy cykl GC musi przejść przez całą dostępną pamięć roboczą i skopiować ją, co jest wyraźnie operacjami liniowymi.
Pytania:
- Czy ta teoria czasu liniowego jest poprawna? Czy długość przerw GC można wyrazić w ten prosty sposób, czy rzeczywistość jest bardziej złożona?
- Jeśli pauza GC jest liniowa w pamięci roboczej, czy istnieje sposób na zredukowanie stałych czynników?
- Czy są jakieś opcje przyrostowego GC lub coś podobnego? Możemy zobaczyć tylko artykuły naukowe. Jesteśmy bardzo chętni do wymiany przepustowości na mniejsze opóźnienia.
- Czy istnieją sposoby na „partycjonowanie” pamięci na mniejsze cykle GC, inne niż dzielenie na wiele procesów?