Haskell cola concurrente rápida

Así que puedo darles una pequeña visión general de algunos de los análisis de Chan y TQueue (que pipes-concurrency está usando internamente aquí) que motivaron algunas decisiones de diseño que entraron en unagi-chan. No estoy seguro de si va a responder a su pregunta. Recomiendo bifurcar diferentes colas y jugar con variaciones mientras se compara para obtener una buena idea de lo que está sucediendo.

Chan

Chan parece:

data Chan a
 = Chan (MVar (Stream a)) -- pointer to "head", where we read from
        (MVar (Stream a)) -- pointer to "tail", where values written to

type Stream a = MVar (ChItem a)
data ChItem a = ChItem a (Stream a)

Es una lista enlazada de MVar s. Los dos MVar s en el acto de tipo Chan como punteros a la cabeza y cola actual de la lista, respectivamente. Así es como se ve una escritura:

writeChan :: Chan a -> a -> IO () 
writeChan (Chan _ writeVar) val = do 
    new_hole <- newEmptyMVar   mask_ $ do
    old_hole <- takeMVar writeVar           -- [1]
    putMVar old_hole (ChItem val new_hole)  -- [2]
    putMVar writeVar new_hole               -- [3]

En 1 el escritor toma un bloqueo en el extremo de escritura, en 2 nuestro elemento a se pone a disposición del lector, y en 3 el extremo de escritura se desbloquea para otros escritores.

Esto realmente funciona bastante bien en un escenario de un solo consumidor/un solo productor (ver el gráfico aquí) porque las lecturas y las escrituras no compiten. Pero una vez que tienes varios escritores concurrentes puedes empieza a tener problemas:

• Un escritor que golpea 1 mientras que otro escritor está en 2 se bloqueará y será descheduled (el más rápido que he sido capaz de medir un cambio de contexto es ~150ns (bastante maldito rápido); probablemente hay situaciones en las que es mucho más lento). Así que cuando tienes muchos escritores contendiendo básicamente estás haciendo un gran viaje de ida y vuelta a través del planificador, en una cola de espera para el MVar y, finalmente, la escritura puede completarse.

• Cuando un escritor consigue descheduled (porque se agotó el tiempo) mientras que en 2, mantiene un bloqueo y no se permitirá que se completen las escrituras hasta que se pueda reprogramar de nuevo; esto se convierte en un problema cuando estamos sobre-suscritos, es decir, cuando nuestra relación subprocesos/núcleo es alta.

Finalmente, el uso de un MVar-por-elemento requiere cierta sobrecarga en términos de asignación, y lo más importante cuando acumulamos muchos objetos mutables, podemos causar una gran cantidad de presión GC.

TQueue

TQueue es genial porque STM hace que sea súper simple razonar sobre su corrección. Es una cola funcional de estilo dequeue, y un write consiste simplemente en leer la pila de writer, consing nuestro elemento, y escribirlo de nuevo:

data TQueue a = TQueue (TVar [a])
                       (TVar [a])

writeTQueue :: TQueue a -> a -> STM ()
writeTQueue (TQueue _ write) a = do  
  listend <- readTVar write   -- a transaction with a consistent 
  writeTVar write (a:listend) -- view of memory

Si después de que un writeTQueue escribe su nueva pila de nuevo, otra escritura intercalada hace lo mismo, una de las escrituras se volverá a intentar. A medida que se intercalan más writeTQueue, el efecto de la contención se empeora. Sin embargo, el rendimiento se degrada mucho más lentamente que en Chan porque solo hay una única operación writeTVar que puede anular writeTQueues competidores, y la transacción es muy pequeña (solo una lectura y una (:)).

Una lectura funciona al "desquejar" la pila desde el lado de escritura, invertirla, y almacenar la pila invertida en su propia variable para un fácil "popping" (en conjunto, esto nos da O (1) push y pop amortizados)

readTQueue :: TQueue a -> STM a
readTQueue (TQueue read write) = do
  xs <- readTVar read
  case xs of
    (x:xs') -> do writeTVar read xs'
                  return x
    [] -> do ys <- readTVar write
             case ys of
               [] -> retry
               _  -> case reverse ys of
                       [] -> error "readTQueue"
                       (z:zs) -> do writeTVar write []
                                    writeTVar read zs
                                    return z

Los lectores tienen una cuestión de contención moderada simétrica para los escritores. En el caso general, los lectores y los escritores no se sostienen, sin embargo cuando la pila de lectores está agotada los lectores están luchando con otros lectores y escritores. Sospecho que si precargaste un TQueue con suficientes valores y luego lanzaste 4 lectores y 4 escritores, podrías inducir livelock mientras el reverso luchaba por completarlo antes de la siguiente escritura. También es interesante notar que a diferencia de MVar, una escritura a un TVar en la que muchos lectores están esperando los despierta a todos simultáneamente (esto podría ser más o menos eficiente, dependiendo del escenario).

I sospeche que no ve muchas de las debilidades de TQueue en su prueba; principalmente está viendo los efectos moderados de la contención de escritura y la sobrecarga de una gran cantidad de asignación y GC'ing una gran cantidad de objetos mutables.

Unagi-chan

unagi-chan fue diseñado en primer lugar para manejar bien la contención. Es conceptualmente muy simple, pero la implementación tiene algunas complejidades

data ChanEnd a = ChanEnd AtomicCounter (IORef (Int , Stream a))

data Stream a = Stream (Array (Cell a)) (IORef (Maybe (Stream a)))

data Cell a = Empty | Written a | Blocking (MVar a)

Los lados de lectura y escritura de la cola comparten el Stream en el que coordinan los valores de paso (desde de escritor a lector) e indicaciones de bloqueo (de lector a escritor), y los lados de lectura y escritura tienen cada uno un contador atómico independiente. Una escritura funciona como:

1. Un escritor llama al atómico incrCounter en el contador de escritura para recibir su índice único en el que coordinar con su lector (único)

2. El escritor encuentra su célula y realiza un CAS de Written a

3. Si tiene éxito, sale, de lo contrario, ve que un lector lo ha vencido y está bloqueando (o procediendo a bloquear), por lo que hace un (\Blocking v)-> putMVar v a) y sale.

Una lectura funciona de una manera similar y obvia.

La primera innovación es hacer que el punto de contención sea una operación atómica que no se degrade bajo contención (como lo haría un bucle CAS/retry o un bloqueo similar a Chan). Basado en un simple benchmarking y experimentación, el primop fetch-and-add, expuesto por la biblioteca atomic-primops funciona mejor.

Entonces en 2 tanto el lector como el escritor necesitan realizar solo uno comparar e intercambiar (el camino rápido para el lector es una simple lectura no atómica) para terminar la coordinación.

Así que para tratar de hacer unagi-chan bueno, {[39]]}

• Use fetch-and-add para manejar el punto de contención

• Utilice técnicas lockfree tales que cuando estamos sobresuscritos un hilo siendo descheduled en épocas inoportunas no bloquee progreso para otros hilos (un escritor bloqueado puede bloquear a lo sumo el lector "asignado" a él por el contador; lea las advertencias re. excepciones asincrónicas en los documentos unagi-chan, y tenga en cuenta que Chan tiene una semántica más agradable aquí)

• Utilice una matriz para almacenar nuestros elementos, que tiene mejor localidad (pero ver más abajo) menor sobrecarga por elemento y pone menos presión sobre el GC

Una nota final re. uso de una matriz: las escrituras concurrentes en una matriz son generalmente una mala idea para escalar porque causa una gran cantidad de tráfico de coherencia de caché, ya que las líneas de caché se invalidan de un lado a otro en los hilos de writer. El el término general es "falso compartir". Pero también hay ventajas en cuanto a caché y desventajas de los diseños alternativos que se me ocurre que escribirían rayas o algo así; he estado experimentando con esto un poco, pero no tengo nada concluyente en este momento.

Un lugar en el que legítimamente estamos preocupados con el intercambio falso es en nuestro contador, que alineamos y rellenamos con 64 bytes; esto efectivamente se mostró en los puntos de referencia, y el único inconveniente es el aumento del uso de memoria.