De estos 3 métodos para leer listas vinculadas de la memoria compartida, ¿por qué es el tercero más rápido?

Question

Tengo un programa 'servidor' que actualiza muchas listas enlazadas en la memoria compartida en respuesta a eventos externos. Quiero que los programas de los clientes noten una actualización en cualquiera de las listas lo más rápido posible (latencia más baja). El servidor marca el nodo de la lista vinculada state_ como FILLED una vez que se completan sus datos y su siguiente puntero se ha establecido en una ubicación válida. Hasta entonces, es state_ es NOT_FILLED_YET. Estoy usando barreras de memoria para asegurarme de que los clientes no vean el state_ como FILLED antes de que los datos estén realmente listos (y parece que funcionan, nunca veo datos corruptos). Además, state_ es volátil para garantizar que el compilador no levante la comprobación del bucle del cliente.

Manteniendo el código del servidor exactamente igual, he encontrado 3 métodos diferentes para que el cliente escanee las listas enlazadas para ver los cambios. La pregunta es: ¿por qué es el 3er método más rápido?

Método 1: Round robin sobre todas las listas enlazadas (llamados 'canales') de manera continua, buscando para ver si todos los nodos han cambiado a 'LLENO':

void method_one() 
{ 
    std::vector<Data*> channel_cursors; 
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i) 
    { 
     Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment)); 
     channel_cursors.push_back(current_item); 
    } 

    while(true) 
    { 
     for(std::size_t i = 0; i < channel_list.size(); ++i) 
     { 
      Data* current_item = channel_cursors[i]; 

      ACQUIRE_MEMORY_BARRIER; 
      if(current_item->state_ == NOT_FILLED_YET) { 
       continue; 
      } 

      log_latency(current_item->tv_sec_, current_item->tv_usec_); 

      channel_cursors[i] = static_cast<Data*>(current_item->next_.get(segment)); 
     } 
    } 
} 

Método 1 dio una latencia muy baja cuando el entonces el número de canales era pequeño Pero cuando el número de canales creció (250K +), se volvió muy lento debido a la repetición de todos los canales. Así que lo intenté ...

Método 2: Dé a cada lista vinculada una ID. Mantenga una 'lista de actualización' por separado. Cada vez que se actualiza una de las listas enlazadas, inserte su ID en la lista de actualizaciones. Ahora solo tenemos que controlar la lista de actualizaciones individual y verificar las identificaciones que obtenemos de ella.

void method_two() 
{ 
    std::vector<Data*> channel_cursors; 
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i) 
    { 
     Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment)); 
     channel_cursors.push_back(current_item); 
    } 

    UpdateID* update_cursor = static_cast<UpdateID*>(update_channel.tail_.get(segment)); 

    while(true) 
    { 
      ACQUIRE_MEMORY_BARRIER; 
     if(update_cursor->state_ == NOT_FILLED_YET) { 
      continue; 
     } 

     ::uint32_t update_id = update_cursor->list_id_; 

     Data* current_item = channel_cursors[update_id]; 

     if(current_item->state_ == NOT_FILLED_YET) { 
      std::cerr << "This should never print." << std::endl; // it doesn't 
      continue; 
     } 

     log_latency(current_item->tv_sec_, current_item->tv_usec_); 

     channel_cursors[update_id] = static_cast<Data*>(current_item->next_.get(segment)); 
     update_cursor = static_cast<UpdateID*>(update_cursor->next_.get(segment)); 
    } 
} 

Método 2 dio TERRIBLE latencia. Mientras que el Método 1 podría dar menos de 10us de latencia, el Método 2 inexplicablemente a menudo daría una latencia de 8 ms. Al usar gettimeofday, parece que el cambio en update_cursor-> state_ fue muy lento para propocionar desde la vista del servidor hasta la del cliente (estoy en un cuadro multinúcleo, así que supongo que la demora se debe a la memoria caché). Así que probé un enfoque híbrido ...

Método 3: conserve la lista de actualizaciones. Pero recorra todos los canales continuamente, y dentro de cada iteración, compruebe si la lista de actualización se ha actualizado. Si es así, ve con el número que aparece en él. Si no lo ha hecho, verifique el canal en el que hemos iterado actualmente.

void method_three() 
{ 
    std::vector<Data*> channel_cursors; 
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i) 
    { 
     Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment)); 
     channel_cursors.push_back(current_item); 
    } 

    UpdateID* update_cursor = static_cast<UpdateID*>(update_channel.tail_.get(segment)); 

    while(true) 
    { 
     for(std::size_t i = 0; i < channel_list.size(); ++i) 
     { 
      std::size_t idx = i; 

      ACQUIRE_MEMORY_BARRIER; 
      if(update_cursor->state_ != NOT_FILLED_YET) { 
       //std::cerr << "Found via update" << std::endl; 
       i--; 
       idx = update_cursor->list_id_; 
       update_cursor = static_cast<UpdateID*>(update_cursor->next_.get(segment)); 
      } 

      Data* current_item = channel_cursors[idx]; 

      ACQUIRE_MEMORY_BARRIER; 
      if(current_item->state_ == NOT_FILLED_YET) { 
       continue; 
      } 

      found_an_update = true; 

      log_latency(current_item->tv_sec_, current_item->tv_usec_); 
      channel_cursors[idx] = static_cast<Data*>(current_item->next_.get(segment)); 
     } 
    } 
} 

La latencia de este método era tan bueno como el método 1, pero a escala en un gran número de canales. El problema es que no tengo idea de por qué. Solo para lanzar una llave inglesa en las cosas: si descomiento la parte 'encontrado a través de la actualización', se imprime entre TODOS LOS MENSAJES DE REGISTRO DE LETENCIA. ¡Lo que significa que las cosas solo se encuentran en la lista de actualizaciones! Así que no entiendo cómo este método puede ser más rápido que el método 2.

El, código compilables completa (requiere GCC-e impulsar 1.41) que genera cadenas aleatorias como datos de prueba está en: http://pastebin.com/0kuzm3Uf

Actualización: Los 3 métodos son efectivamente spinlocking hasta que ocurra una actualización. La diferencia radica en cuánto tardan en darse cuenta de que se ha producido la actualización. Ellos todos continuamente gravan el procesador, por lo que no explica la diferencia de velocidad. Estoy probando en una máquina de 4 núcleos sin nada más que se ejecute, por lo que el servidor y el cliente no tienen nada con lo que competir. Incluso he hecho una versión del código donde las actualizaciones señalan una condición y hacen que los clientes esperen con la condición, esto no ayudó a la latencia de ninguno de los métodos.

Update2: A pesar de que hay 3 métodos, solo he intentado 1 a la vez, por lo que solo 1 servidor y 1 cliente compiten por el miembro state_.

Answer 1

La respuesta fue difícil de entender, y ser justo sería difícil con la información que presenté aunque si alguien realmente compiló la fuente el código I siempre que tuvieran una oportunidad de luchar;) Dije que "encontrado a través de la lista de actualización" se imprimía después de cada mensaje de registro de latencia, pero esto no era cierto en realidad; solo era cierto en la medida en que podía retroceder en mi terminal. Al principio hubo una gran cantidad de actualizaciones encontradas sin usar la lista de actualizaciones.

El problema es que entre el momento en que establezco mi punto de partida en la lista de actualización y mi punto de partida en cada una de las listas de datos, habrá un retraso porque estas operaciones toman tiempo. Recuerde, las listas están creciendo todo el tiempo que esto está pasando. Considere el caso más simple en el que tengo 2 listas de datos, A y B. Cuando configuro mi punto de partida en la lista de actualización, aparecen 60 elementos, debido a 30 actualizaciones en la lista A y 30 actualizaciones en la lista B. Dicen que 've alternaron:

A 
B 
A 
B 
A // and I start looking at the list here 
B 

Pero entonces después de configurar la lista de actualizaciones de allí, hay una serie de cambios a B y no hay cambios a A. entonces me puso mis puntos de partida en cada una de las listas de datos. Mis puntos de partida para las listas de datos van a ser después de ese aumento de actualizaciones, pero mi punto de partida en la lista de actualización es anterior a ese aumento, así que ahora voy a buscar un montón de actualizaciones sin encontrarlas. El enfoque mixto anterior funciona mejor porque iterando sobre todos los elementos cuando no puede encontrar una actualización, cierra rápidamente la brecha temporal entre dónde está la lista de actualización y dónde están las listas de datos.

Answer 2

He notado tanto en el método 1 como en el método 3 que tiene una línea, ACQUIRE_MEMORY_BARRIER, que supongo que tiene algo que ver con las condiciones de multi-threading/race?

De cualquier manera, el método 2 no tiene ningún duerme lo que significa el siguiente código ...

while(true) 
{ 
    if(update_cursor->state_ == NOT_FILLED_YET) { 
     continue; 
    } 

va a clavar el procesador. La forma típica de hacer este tipo de tarea de productor/consumidor es usar algún tipo de semáforo para indicarle al lector que la lista de actualizaciones ha cambiado. Una búsqueda de multiprocesador productor/consumidor debería proporcionarle una gran cantidad de ejemplos. La idea principal aquí es que esto permite que el hilo se quede dormido mientras espera que el estado update_cursor-> cambie. Esto evita que este hilo robe todos los ciclos de CPU.

Answer 3

Hipótesis: El método 2 bloquea de alguna manera que el servidor no escriba la actualización.

Una de las cosas que puede martillar, además de los núcleos del procesador, es su caché coherente. Cuando lee un valor en un núcleo dado, la caché L1 en ese núcleo debe adquirir acceso de lectura a esa línea de caché, lo que significa que debe invalidar el acceso de escritura a esa línea que tiene cualquier otra caché. Y viceversa para escribir un valor. Esto significa que continuamente hace ping-ponging de la línea de caché hacia adelante y hacia atrás entre un estado de "escritura" (en el caché del núcleo del servidor) y un estado de "lectura" (en los cachés de todos los núcleos de clientes).

Las complejidades del rendimiento de la memoria caché x86 no son algo con lo que esté completamente familiarizado, pero parece completamente plausible (al menos en teoría) que lo que está haciendo al tener tres subprocesos diferentes martilleando esta ubicación de memoria tan difícil como Con las solicitudes de acceso de lectura, puede crear aproximadamente un ataque de denegación de servicio en el servidor que le impide escribir en esa línea de caché durante algunos milisegundos ocasionalmente.

Puede hacer un experimento para detectar esto mirando cuánto tarda el servidor en escribir realmente el valor en la lista de actualización y ver si hay un retraso correspondiente a la latencia.

También podría intentar experimentar la eliminación de la memoria caché de la ecuación, ejecutando todo en un solo núcleo para que los hilos del cliente y del servidor extraigan cosas de la misma memoria caché L1.

Answer 4

No sé si alguna vez ha leído las columnas de Concurrencia de Herb Sutter. Son bastante interesantes, especialmente cuando entiendes los problemas del caché.

De hecho, el Method2 parece mejor aquí porque la identificación es más pequeña que los datos en general significa que no tiene que hacer viajes de ida y vuelta a la memoria principal con demasiada frecuencia (lo cual es agotador).

Sin embargo, lo que realmente puede suceder es que usted tiene una línea de caché como:

Line of cache = [ID1, ID2, ID3, ID4, ...] 
       ^  ^
      client   server 

lo cual crea la discordia.

Aquí está el artículo de Herb Sutter: Eliminate False Sharing. La idea básica es simplemente inflar artificialmente su ID en la lista para que ocupe una línea de caché por completo.

Eche un vistazo a los otros artículos de la serie mientras lo hace. Tal vez obtendrás algunas ideas. Hay un buen búfer circular sin candado, creo que podría ayudar a su lista de actualizaciones :)