c++ - compartir falso en boost:: detail:: spinlock_pool?

c++11 shared-ptr

Question

Encontré esta question SO y al leerla finalmente me llevó a mirar boost::detail::spinlock_pool .

El propósito de boost::detail::spinlock_pool es reducir la contención potencial de un spinlock global mediante la selección de una matriz de spinlock s mediante el hash sobre la dirección de shared_ptr . Esto parece una solución razonable, pero parece haber un problema con la implementación de la versión actual (Boost v1.49).

spinlock_pool administra una matriz asignada estáticamente de 41 instancias de spinlock . Parece que sizeof(spinlock)==4 para las plataformas que miré, lo que significa que, digamos x64 con cachelines de 64 bytes, habrá 16 spinlock s por línea de caché.

Es decir, la matriz completa abarca todas las 2 1/2 líneas de caché.

Es decir, hay un 40% de probabilidad de que un spinlock aleatorio sea falso para compartir con otro.

... que derrota casi por completo el propósito de la piscina en primer lugar.

¿Mi análisis es correcto o me falta algo importante?

ACTUALIZACIÓN: finalmente escribí un pequeño programa de referencia:

#include <boost/shared_ptr.hpp>
#include <boost/thread.hpp>
#include <boost/timer.hpp>
#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;

enum { BufferSize = 1<<24,  SLsPerCacheLine = 1 };

int          ibuffer[BufferSize];

using boost::detail::spinlock;
size_t nslp = 41;
spinlock* pslp = 0;

spinlock& getSpinlock(size_t h)
{
  return pslp[ (h%nslp) * SLsPerCacheLine ];
}


void threadFunc(int offset)
{
  const size_t mask = BufferSize-1;
  for (size_t ii=0, index=(offset&mask); ii<BufferSize; ++ii, index=((index+1)&mask))
  {
    spinlock& sl = getSpinlock(index);
    sl.lock();
    ibuffer[index] += 1;
    sl.unlock();
  }
};


int _tmain(int argc, _TCHAR* argv[])
{
  if ( argc>1 )
  {
    size_t n = wcstoul(argv[1], NULL, 10);
    if ( n>0 )
    {
      nslp = n;
    }
  }

  cout << "Using pool size: "<< nslp << endl;
  cout << "sizeof(spinlock): "<< sizeof(spinlock) << endl;
  cout << "SLsPerCacheLine: "<< int(SLsPerCacheLine) << endl;
  const size_t num = nslp * SLsPerCacheLine;
  pslp = new spinlock[num ];
  for (size_t ii=0; ii<num ; ii++)
  { memset(pslp+ii,0,sizeof(*pslp)); }

  const size_t nThreads = 4;
  boost::thread* ppThreads[nThreads];
  const int offset[nThreads] = { 17, 101, 229, 1023 };

  boost::timer timer;

  for (size_t ii=0; ii<nThreads; ii++)
  { ppThreads[ii] = new boost::thread(threadFunc, offset[ii]); }

  for (size_t ii=0; ii<nThreads; ii++)
  { ppThreads[ii]->join(); }

  cout << "Elapsed time: " << timer.elapsed() << endl;

  for (size_t ii=0; ii<nThreads; ii++)
  { delete ppThreads[ii]; }

  delete[] pslp;

  return 0;
}

SLsPerCacheLine==1 dos versiones del código, una con SLsPerCacheLine==1 , y una con SLsPerCacheLine==8 . 32 bits optimizados con MSVS 2010, se ejecutan en un Xeon W3520 de 4 núcleos a 2.67 GHz (HyperThreading deshabilitado).

Tuve problemas para obtener resultados consistentes de estas pruebas; ocasionalmente se observaron variaciones espurias en el tiempo hasta el 50%. Sin embargo, en promedio, parece que la versión SLsPerCacheLine==8 fue ~ 25-30% más rápida que la versión SLsPerCacheLine==1 con una tabla de spinlock de tamaño 41.

Sería interesante ver cómo se escala con un mayor número de núcleos, NUMA, HyperThreading, etc. Actualmente no tengo acceso a ese tipo de hardware.

Answer 1

BREVE

Usted tiene razón, ya que los spinlocks comparten la misma línea de caché, cuando podrían estar en diferentes líneas de caché. Aka compartir falso. Y bien puede haber cierta ganancia de rendimiento al asignar los bloqueos en diferentes líneas de caché (pero ver más abajo).

Sin embargo, esto NO es lo mismo que la contención de bloqueo. La contención de bloqueo surge cuando un sujeto mantiene un bloqueo, y uno o más de ellos quieren acceder.

Es decir, spinlock_pool tiene una contención de línea de caché causada por bloqueos co-residentes en la misma línea de caché. Pero tiene (reducido) la contención de bloqueo de software.

La contención de bloqueo de software reducido es casi indudablemente buena.

La contención de la línea de caché probablemente duela un poco, como muestran sus puntos de referencia hasta cierto punto, pero es un efecto de segundo orden en comparación con la contención de bloqueo de software.

DETALLE

Fondo

Primero, algunos antecedentes:

Los spinloops clásicos son test-and-test-and-set:

    loop: 
         tmp := load( memory_location_of_sw_lock )
         if( is_locked(tmp) ) goto loop
         was_locked := atomic_hw_locked_rmw( memory_location_of_sw_lock, 
                                             value_that_will_get_sw_lock )
         if( was_locked(tmp) ) goto loop
     got_the_sw_lock:
          ...
          ... critical section
          ...
          // release the lock, e.g.
          memory_location_of_sw_lock := 0

También hay spinlocks de prueba y ajuste, que parecen

    loop: 
         was_locked := atomic_hw_locked_rmw( memory_location_of_sw_lock, 
                                             value_that_will_get_sw_lock )
         if( was_locked(tmp) ) goto loop

Estos pueden tener un rendimiento muy malo en la mayoría de los sistemas de memoria modernos con cachés, escritura simultánea o reescritura. (Aunque algunas de las optimizaciones de hardware que he propuesto hacen que los spinloops de prueba y configuración sean tan rápidos como los spinloops de prueba y de prueba y configuración, un poco más rápidos porque son más pequeños).

Tenga en cuenta que hay dos conceptos diferentes de bloqueo aquí: el bloqueo de "software" que está adquiriendo el bloqueo de giro y el bloqueo de hardware que utiliza la instrucción atomic_hw_locked_rmw, como mem de Intel LOCK INC o CMPXCHG. No nos importa mucho esto último, excepto para saber que, por lo general, se escribe incondicionalmente en la línea de caché que contiene el bloqueo del software e invalida otras copias de la línea de caché. (Hacer que la escritura sea condicional es otra posible optimización de hardware).

O (N ^ 2) la ráfaga de caché se pierde en la contención de bloqueo (software)

Bloquear la contención con los spinloops de prueba y prueba y establecer es particularmente malo. Todos los camareros giran en la cerradura y, cuando se libera, hay una ráfaga de accesos de bus. Un chico gana, los otros se dan cuenta de que han perdido y, finalmente, se acomodan para girar nuevamente. Esta ráfaga de actividad es particularmente mala porque para N chicos en espera (subprocesos / procesos / procesadores) la ráfaga de actividad del bus puede tener un tamaño de O (N ^ 2), porque en el peor de los casos, todos salen de la parte de prueba de una prueba. y-pruebe-y-establezca spinloop, y todos intentan realizar la instrucción atómica RMW bloqueada (lectura-modificación-escritura), como x86 LOCK INC mem o CMPXCHG, al mismo tiempo. Esto significa que todos eventualmente escribirán la línea, aunque todos menos el primero no necesitan escribir el bloqueo porque no obtendrán el bloqueo.

P.ej

Lock is held by P0
P1-PN are spinning in test-and-test-and-set spinloops waiting for it.

P0 releases the lock, e.g. by writing it to 0

P1''s "test-" instruction reads the lock
...
PN''s "test-" instruction reads the lock

All of P1-PN see the lock as released, 
   so they fall out of the "test-" part of the spinloop which uses ordinary instructions
   to the test-and-set part of the spinloop, which uses a hardware atomic RMW like LOCK INC mem

P1''s locked RMW happens, and acquires the spinlock for P1
   It invalidates all other cache lines
   P1 goes away and does something with the data protected by the lock

P2''s locked RMW fails to acquire the spinlock
   It invalidates all other caches because it has a write
   P1 falls back into its test- spinloop

P3''s locked RMW fails
   It invalidates all other caches because it has a write
   P1 falls back into its test- spinloop

...

PN''s locked RMW fails

y ahora, por lo menos, todos los procesadores P2..PN restantes deben hacer los fallos de caché desbloqueados ordinarios para su prueba-spinloop. Esto implica al menos N + (N-1) fallas de caché. Puede ser considerablemente peor, ya que es posible que cada escritura, por un camarero que no logre adquirir el bloqueo, active a todos los demás camareros para que realicen una lectura desbloqueada. Es decir, dependiendo del tiempo, puede obtener

   1 release the lock
   N reads to test- the lock
   1 locked atomic RMW to acquire the lock
   N reads...
   for each of the remaining N-1 processors
      1 locked RMW that fails to acquire the lock
      N reads 

que es O (N ^ 2). O posiblemente, para el procesador M, 1 RMW bloqueado, seguido de 2..M lecturas, que aún es O (N ^ 2).

¿Qué significa esto para esta pregunta?

De acuerdo, si hubo una verdadera contención de bloqueo, se obtiene esta ráfaga O (N ^ 2) de caché cuando se libera un bloqueo en disputa.

Sin embargo, spinlock_pool reparte a los camareros en varios bloqueos. Si hay bloqueos S en el pool de spinlock, hay menos camareros: probablemente menos que N / S (porque la contención tiende a ser superlineal en el número de personas que comparten el mismo bloqueo).

Es decir, con el spinlock_pool de Boost, podría ingenuamente esperar obtener 1/41 de la cantidad de contención, y probablemente menos que eso.

Recuerde, spinlock_pool es un compromiso entre tener un bloqueo por puntero compartido, aumentar el tamaño de los punteros compartidos y hacer que todos los puntos compartidos compartan el mismo bloqueo. Por lo tanto, cualquier disputa en un spinlock de shared_pointer puede ser (a) una verdadera contienda, o (b) una falsa contienda causada por shared_pointers que son hashing independientes de la misma entrada en el spinlock_pool.

Ahora, sí, si en lugar de tener N camareros tienes "solo" N / 41 camareros, entonces la ráfaga sigue siendo O ((N / 41) ^ 2) u O (N ^ 2). Pero, si N suele ser inferior a 41 ... tienes la idea.

Básicamente, el hashing para distribuir los Shared_Pointers en varias entradas de spinlock_pool rápidamente reduce la cantidad de contención.

Pero ... ¿los spinlocks viven en la misma cacheline? Correcto ... pero los camareros en otras líneas de caché no avanzarán a la parte de prueba y configuración de su spinloop.

Es decir, si un bloqueo en conflicto con M meseros comparte una línea de caché con M otros procesos, obtendrá tráfico M * N. Pero si el hashing ha reducido M a O (1), solo obtienes N tráfico.

Y si la mayoría de las veces no hay otros meseros, solo obtienes O (1) bafia en una liberación de bloqueo.

LÍNEA INFERIOR :

La reducción de la contención de bloqueo de software es mucho más beneficiosa en cuanto al rendimiento que la reducción del uso compartido falso de la memoria caché que provoca la contención de la línea de la memoria caché de hardware.

Ahora, todavía puede ser beneficioso ser difícil al no empaquetar tantas entradas de spinlock_pool en la misma línea de caché. Pero esto no es de ninguna manera obvio; es una pregunta empírica, por lo que quiero decir que necesita ejecutar un experimento y variará con la carga de trabajo.

A veces, compartir falsamente estos bloqueos en la misma línea de caché será malo. Un ejemplo clásico son los bloqueos que protegen las colas de ejecución del procesador.

A veces, el intercambio falso de estos bloqueos en la misma línea de caché es bueno: puede proporcionar los mismos beneficios que la captura previa en un caché. Por ejemplo, imagine que ha asignado una serie de punteros_comunitarios compartidos, y que la gente suele acceder a aosptr [i] y luego aosptr [i + 1], etc.

Todo depende de su carga de trabajo. Lo he visto caer en ambos sentidos. Por lo general, en mi experiencia, un bloqueo por línea de caché es mejor, aunque a menudo no es mucho.

MÁS DIVERSIÓN

En caso de que le importe, la optimización de hardware para los spinloops de prueba y prueba y conjunto fue el tema de mi tesis de MS, "Una taxonomía de características de primitivas de sincronización, incluido el bloqueo de abandono del bus": un protocolo de caché de actualización de hardware que eliminó la ráfaga De los accesos de autobuses. No publicado en ninguna publicación formal, excepto Microfiche Universitaria.

Mi trabajo se inspiró en el artículo "El rendimiento de las alternativas de bloqueo de giro para multiprocesadores de memoria compartida" por T Anderson - IEEE Transactions en sistemas paralelos y distribuidos, 1990.

Creo que es justo decir que la mayoría de las publicaciones han estado en software, algoritmos, incluido el famoso bloqueo MCS. Creo que también es justo decir que tales técnicas, si bien populares en teoría, han sido poco utilizadas por los programadores oficiales.

Por cierto, hay algunas optimizaciones de hardware más posibles aquí. Por ejemplo, CMPXCHG no necesita escribir el bloqueo en absoluto. Desafortunadamente, en el hardware de Intel actual, o al menos en el hardware de Intel que diseñé en 1991, que todavía creo que se usa, la única forma de liberar el bloqueo de hardware (que se usa para implementar el RMW atómico bloqueado) es usar una microcódigo escribir "store-unlock". Heck, el microcódigo incluso podría usar LoadLinked / StoreConditional (LL / SC), volviendo al bloqueo en aquellas situaciones en las que un LL / SC ingenuo no hace ningún progreso hacia adelante en algunos hilos.

Es posible que Intel haya arreglado esto recientemente. Dejé Intel en 2009. Intenté arreglarlo, mejorarlo y optimizarlo desde 1991. E Intel ha mejorado mucho el rendimiento de los bloqueos recientemente. Pero creo que se han trabajado principalmente en el rendimiento del bloqueo no contendido, y no se ha optimizado el rendimiento del bloqueo en disputa.

De manera similar, Alain Kagi, en su disertación y en algunas publicaciones, así como la patente http://www.google.com/patents/US6460124 , muestra que al agregar retrasos juiciosos, el hardware del caché puede hacer que los spinlocks sean tan eficientes como los bloqueos en cola.

Algunas de estas optimizaciones de hardware hacen que los spinloops de prueba y configuración sean mejores que los spinloops de prueba y prueba y set.

El desarrollo más reciente ha sido Intel TSX (Extensiones de sincronización transaccional), que consiste en HLE (Hardware Lock Elision (Ravi Rajwar trabajó en esto en UWisc mientras yo y Alain Kagi estaban allí, aunque mi trabajo en sincronización era anterior en UIUC)) y RTM (Memoria transaccional restringida). Ambos ayudan de forma incontenida ... hmm, ayudan con los candados en disputa que están en contienda falsa, por ejemplo, un candado de grano grueso que protege lo que podría ser algo independiente. Es decir, contención de bloqueo falso. De alguna manera, HLE puede hacer que spinlock_pool sea innecesario.

DISCULPA

Lo siento: he proporcionado una respuesta larga que se reduce a "reducir la contención de bloqueo de software puede ser mucho más importante que la contención de línea de caché de hardware para spinloops".

Aunque esperaría que se obtuviera algo de rendimiento al asignar 1 spinloop por línea de caché, puede ser pequeño, y en algunas cargas de trabajo no muy infrecuentes, incluso puede haber una pérdida.

Y para estar seguro, tendrías que medirlo.

Pero, en cualquier caso, la gran ganancia proviene de la reducción de la contención del bloqueo de software.