Di questi 3 metodi per leggere le liste collegate dalla memoria condivisa, perché il 3 ° più veloce?

Question

Ho un programma "server" che aggiorna molti elenchi collegati nella memoria condivisa in risposta a eventi esterni. Voglio che i programmi client notino un aggiornamento su uno qualsiasi degli elenchi il più rapidamente possibile (latenza più bassa). Il server contrassegna lo state_ del nodo di una lista collegata come FILLED una volta che i suoi dati sono stati compilati e il puntatore successivo è stato impostato su una posizione valida. Fino ad allora, il suo state_ è NOT_FILLED_YET. Sto usando le barriere della memoria per assicurarmi che i client non vedano lo state_ come FILLED prima che i dati all'interno siano effettivamente pronti (e sembra funzionare, non vedo mai dati corrotti). Inoltre, state_ è volatile per essere sicuro che il compilatore non risolva il controllo da parte del client dei loop.

Mantenendo il codice server esattamente lo stesso, ho trovato 3 metodi diversi per il client per la scansione degli elenchi collegati per le modifiche. La domanda è: perché il 3 ° metodo è più veloce?

Metodo 1: Round robin su tutte le liste collegate (chiamati 'canali') in modo continuo, cercando di vedere se tutti i nodi sono cambiate a 'RIEMPITO':

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)); 
     } 
    } 
} 

Metodo 1 ha una latenza molto bassa quando l'allora il numero di canali era piccolo. Ma quando il numero di canali è cresciuto (250 K +) è diventato molto lento a causa del loop su tutti i canali. Così ho provato ...

Metodo 2: Assegna un ID a ciascun elenco collegato. Tenere una "lista aggiornamenti" separata a lato. Ogni volta che uno degli elenchi collegati viene aggiornato, inserire il relativo ID nell'elenco degli aggiornamenti. Ora dobbiamo solo monitorare l'elenco degli aggiornamenti singoli e controllare gli ID che otteniamo da esso.

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)); 
    } 
} 

Il metodo 2 ha dato una latenza TERRIBILE. Considerando che il Metodo 1 potrebbe dare meno di 10 secondi di latenza, il Metodo 2 inesplicabilmente dovrebbe avere una latenza di 8 ms! Usando gettimeofday sembra che la modifica in update_cursor-> state_ sia stata molto lenta per propagare dalla vista del server al client (sono su una scatola multicore, quindi presumo che il ritardo sia dovuto alla cache). Così ho provato un approccio ibrido ...

Metodo 3: mantenere l'elenco di aggiornamento. Ma passa continuamente su tutti i canali, e all'interno di ogni iterazione controlla se l'elenco degli aggiornamenti è stato aggiornato. Se è così, vai con il numero premuto su di esso. In caso contrario, controlla il canale a cui è attualmente iterata.

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 latenza di questo metodo era equivalente al Metodo 1, ma ridimensionata a un numero elevato di canali. Il problema è che non ho idea del perché. Solo per dare una svolta alle cose: se disapprovo la parte 'found via update', stampa tra OGNI LATENCY LOG MESSAGE. Il che significa che le cose si trovano sempre solo nella lista degli aggiornamenti! Quindi non capisco come questo metodo può essere più veloce rispetto al metodo 2.

Il codice compilabile completo (richiede GCC ed amplificare-1.41) che genera stringhe casuali come dati di test e ': http://pastebin.com/0kuzm3Uf

Aggiornamento: Tutti e 3 i metodi sono effettivamente spinlocking fino a quando si verifica un aggiornamento. La differenza sta nel tempo impiegato per notare che l'aggiornamento si è verificato. Loro all tassano continuamente il processore, in modo che non spieghi la differenza di velocità. Sto testando su una macchina a 4 core con nient'altro in esecuzione, quindi il server e il client non hanno nulla con cui competere. Ho persino creato una versione del codice in cui gli aggiornamenti segnalano una condizione e i client sono in attesa di una condizione: non ha aiutato la latenza di nessuno dei metodi.

Update2: Nonostante ci siano 3 metodi, ho provato solo 1 alla volta, quindi solo 1 server e 1 cliente sono in competizione per il membro dello stato.

Answer 1

La risposta è stata difficile da capire, e per essere onesti sarebbe difficile con le informazioni che ho presentato anche se qualcuno avesse effettivamente compilato la fonte codice che ho fornito avrebbero avuto una possibilità di combattere;) Ho detto che "trovato tramite lista di aggiornamento" è stato stampato dopo ogni messaggio di registro di latenza, ma questo non era vero - era vero solo per quanto potevo scorrere in il mio terminale All'inizio c'erano una manciata di aggiornamenti trovati senza usare la lista degli aggiornamenti.

Il problema è che tra il momento in cui ho impostato il punto di partenza nell'elenco di aggiornamento e il punto di partenza in ciascuno degli elenchi di dati, ci sarà un certo ritardo perché queste operazioni richiedono tempo. Ricorda, le liste stanno crescendo per tutto il tempo che sta succedendo. Considera il caso più semplice in cui ho 2 liste di dati, A e B. Quando imposto il punto di partenza nell'elenco di aggiornamento ci sono 60 elementi in esso, a causa di 30 aggiornamenti nell'elenco A e 30 aggiornamenti nell'elenco B. Di loro 've alternano:

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

Ma poi dopo ho impostato la lista aggiornamento per lì, ci sono una serie di aggiornamenti di B e non aggiornamenti di A. poi ho impostato i miei punti di partenza in ciascuna delle liste di dati. I miei punti di partenza per gli elenchi di dati saranno dopo il che aumento di aggiornamenti, ma il mio punto di partenza nell'elenco di aggiornamento è prima di tale aumento, quindi ora ho intenzione di verificare un sacco di aggiornamenti senza trovarli. L'approccio misto di cui sopra funziona meglio perché, eseguendo il iterating su tutti gli elementi quando non riesce a trovare un aggiornamento, chiude rapidamente il divario temporale tra il punto in cui si trova l'elenco di aggiornamenti e dove si trovano gli elenchi di dati.

Answer 2

Ho notato che in entrambi i metodi 1 e 3 avete una linea, ACQUIRE_MEMORY_BARRIER, che presumo abbia qualcosa a che fare con le condizioni di multi-threading/race?

entrambi i casi, il metodo 2 non ha posti che significa il seguente codice ...

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

sta per martello il processore. Il modo tipico per fare questo tipo di compito produttore/consumatore è usare un qualche tipo di semaforo per segnalare al lettore che la lista di aggiornamento è cambiata. Una ricerca di multi-threading produttore/consumatore dovrebbe darti un gran numero di esempi. L'idea principale qui è che questo permette al thread di andare a dormire mentre è in attesa che lo stato update_cursor-> cambi. Questo impedisce a questo thread di rubare tutti i cicli della CPU.

Answer 3

Ipotesi: il metodo 2 blocca in qualche modo l'aggiornamento di essere scritto dal server.

Una delle cose che puoi martellare, oltre ai core del processore stessi, è il tuo cache coerente. Quando leggi un valore su un dato core, la cache L1 su quel core deve acquisire l'accesso in lettura a quella linea cache, il che significa che deve invalidare l'accesso in scrittura a quella linea che ha qualsiasi altra cache. E viceversa per scrivere un valore. Questo significa che continuerai a ping-pongare la linea di cache avanti e indietro tra uno stato "write" (nella cache del server-core) e uno "read" (nella cache di tutti i core client).

Le complessità delle prestazioni della cache x86 non sono qualcosa a cui sono completamente familiare, ma sembra del tutto plausibile (almeno in teoria) che cosa si sta facendo avendo tre diversi thread che martellano questa posizione di memoria tanto quanto loro può con le richieste di accesso di lettura è in procinto di creare un attacco denial-of-service sul server impedendogli di scrivere su quella linea di cache per alcuni millisecondi occasionalmente.

Potrebbe essere possibile eseguire un esperimento per rilevare ciò osservando il tempo impiegato dal server per scrivere effettivamente il valore nell'elenco di aggiornamento e verificare se c'è un ritardo corrispondente alla latenza.

Si potrebbe anche essere in grado di provare un esperimento di rimozione della cache dall'equazione, eseguendo tutto su un singolo core in modo che i thread client e server stiano tirando fuori dalla stessa cache L1.

Answer 4

Non so se avete mai letto le colonne Concurrency di Herb Sutter. Sono piuttosto interessanti, specialmente quando si entra nei problemi della cache.

In effetti lo Method2 sembra meglio qui perché l'ID è inferiore ai dati in generale significherebbe che non è necessario eseguire round-trip nella memoria principale troppo spesso (che è tassativo).

Tuttavia, ciò che può realmente accadere è che si dispone di una tale linea di cache:

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

che poi crea contesa.

Ecco l'articolo di Herb Sutter: Eliminate False Sharing. L'idea di base è semplicemente gonfiare artificialmente il tuo ID nell'elenco in modo che occupi interamente una riga di cache.

Controlla gli altri articoli della serie mentre ci sei. Forse avrai qualche idea. C'è un bel buffer circolare lock-free, penso che potrebbe essere d'aiuto per il tuo elenco di aggiornamento :)