Wysoce wydajny unikalny znacznik czasu dla wielu wątków w Haskell

Question

Mam wiele zdarzeń przetwarzania wątków. Chcę przypisać nanosekundowy znacznik czasu do każdego zdarzenia. Jednak musi to być unikalny identyfikator. Tak więc, w tym dziwnym przypadku, że dwa zdarzenia przychodzą tak, że mają przypisany ten sam znacznik czasu, chcę, aby jeden z nich był inkrementowany o jedną nanosekundę. Biorąc pod uwagę, że prawdziwa precyzja nie jest na poziomie nanosekund, to jest ok, jeśli chodzi o znacznik czasu systemu.

W jednym wątku jest to banalny problem. Ale w wielu wątkach staje się trudniejsze. Wydajność jest absolutnie kluczowa, więc pomysł naiwnej synchronizacji na typowym typie generatora id wydaje się, że blokowałby on zbyt wiele.

Czy istnieje podejście, które rozwiązuje ten problem przy minimalnym lub zerowym blokowaniu?

Answer 1

Możesz użyć atomicModifyIORef, aby zaimplementować licznik atomowy. W GHC implementowane jest za pomocą operacji atomowych, a nie blokad.

import Data.IORef 
import System.IO.Unsafe 

counter :: IO Int 
counter = unsafePerformIO $ newIORef 0 

getUnique :: IO Int 
getUnique = atomicModifyIORef counter $ \x -> let y = x + 1 in (y, y) 

Answer 2

Dlaczego nie należy rozdzielać problemów związanych z czasem i unikalnym generowaniem identyfikatorów? Na przykład istnieje standardowy moduł Data.Unique, który zapewnia globalną dostawę unikatowych wartości w IO i powinien być wystarczająco szybki dla większości celów. Lub, jeśli potrzebujesz czegoś bardziej wyszukanego, pakiet concurrent-supply oferuje wysokowydajne, współbieżne unikalne źródło ID z czystym interfejsem.

To powiedziawszy, prawdopodobnie można użyć do tego celu POSIX monotonic clock, np. pakiet clock:

import Control.Monad 
import qualified System.Posix.Clock as Clock 

main :: IO() 
main = replicateM_ 100 $ do 
    time <- Clock.getTime Clock.Monotonic 
    print (Clock.sec time, Clock.nsec time) 

Answer 3

w C językach opartych byśmy normalnie to osiągnąć stosując licznik atomową - nie jest wymagana żadna blokada. Jeśli chcesz również znacznik czasu, będzie to osobna wartość. Nie jestem pewien co do Haskella, ponieważ nie piszę z nim (tak interesujące, jak się wydaje).

Answer 4

• http://hackage.haskell.org/package/greg-client może?

Answer 5

Czy możesz użyć dwóch informacji jako unikalnego identyfikatora? Jeśli tak, nadaj każdemu wątkowi unikalny identyfikator i rekord dla każdego zdarzenia nanosekundowego znacznika czasu i id wątku, który przypisuje znacznik czasu. Następnie problem ogranicza się do tego, co zrobiłbyś w przypadku pojedynczego wątku, aby zagwarantować wyjątkowość sygnatur czasowych. I bez żadnej synchronizacji po inicjalizacji.