Rendimiento de pthread_mutex_lock/unlock

Question

Me he dado cuenta de que recibo un gran golpe de rendimiento cuando tengo un algoritmo que bloquea y desbloquea un subproceso ALOT.

¿Hay alguna manera de ayudar a esta sobrecarga? ¿Sería el uso de un semáforo más o menos eficiente?

Gracias

typedef struct _treenode{ 
    struct _treenode *leftNode; 
    struct _treenode *rightNode; 
    int32_t data; 
    pthread_mutex_t mutex; 
}TreeNode; 

pthread_mutex_t _initMutex = PTHREAD_MUTEX_INITIALIZER; 

int32_t insertNode(TreeNode **_trunk, int32_t data){ 
    TreeNode **current; 
    pthread_mutex_t *parentMutex = NULL, *currentMutex = &_initMutex; 

    if(_trunk != NULL){ 
     current = _trunk; 
     while(*current != NULL){ 
     pthread_mutex_lock(&(*current)->mutex); 
     currentMutex = &(*current)->mutex; 
     if((*current)->data < data){ 
      if(parentMutex != NULL) 
       pthread_mutex_unlock(parentMutex); 
      pthreadMutex = currentMutex; 
      current = &(*current)->rightNode; 
     }else if((*current)->data > data){ 
      if(parentMutex != NULL) 
       pthread_mutex_unlock(parentMutex); 
      parentMutex = currentMutex; 
      current = &(*current)->leftNode; 
     }else{ 
      pthread_mutex_unlock(currentMutex); 
      if(parentMutex != NULL) 
       pthread_mutex_unlock(parentMutex); 
      return 0; 
     } 
     } 
     *current = malloc(sizeof(TreeNode)); 
     pthread_mutex_init(&(*current)->mutex, NULL); 
     pthread_mutex_lock(&(*current)->mutex); 
     (*current)->leftNode = NULL; 
     (*current)->rightNode = NULL; 
     (*current)->data = data; 
     pthread_mutex_unlock(&(*current)->mutex); 
     pthread_mutex_unlock(currentMutex); 
    }else{ 
     return 1; 
    } 
    return 0; 
} 

int main(){ 
    int i; 
    TreeNode *trunk = NULL; 
    for(i=0; i<1000000; i++){ 
     insertNode(&trunk, rand() % 50000); 
    } 
} 

Answer 1

En lugar de preocuparse por las briznas de hierba, retroceda y observe todo el bosque.

Cualquier algoritmo que dependa de dos subprocesos que puedan pisar estrechamente los dedos de los demás es inherentemente ineficiente. Intenta encontrar una forma de reducir drásticamente la necesidad de interacción.

Por ejemplo, si un hilo produce datos y el otro lo consume, uno puede pensar fácilmente en un algoritmo ineficiente donde el productor publica los datos en la memoria compartida y luego espera que el otro los consuma. Mientras tanto, el consumidor está esperando que el productor termine, etc., etc. Todo esto se simplifica mucho cuando el productor escribe en un archivo o tubería, y el consumidor lo lee.

Answer 2

bloqueo y desbloqueo de las operaciones son muy caros en el caso de pthread_mutex_lock/desbloqueo. Con más detalles sobre el algoritmo, podría hacer algunas sugerencias, pero por lo que puedo decir, no puedo decir nada con seguridad. Los semáforos son una alternativa (de nuevo dependiendo del algoritmo) y también las barreras son otro método útil para la concurrencia. Para ayudar a la sobrecarga, puede hacer cosas como hacer que sus bloqueos tengan una granularidad más pequeña o una granularidad mayor. bloqueos dentro de los bucles que se repiten varias veces son una mala idea y es posible que desee moverlos fuera del bucle. Este es solo un ejemplo, pero probablemente haya más que se me ocurra. Se trata de determinar si el costo del bloqueo es mayor que el de la sección crítica de tu código. Si proporciona su algoritmo o algún código de muestra, me encantaría echarle un vistazo.

Answer 3

pthread_mutex_lock y pthread_mutex_unlock varían en costo dependiendo de la discordia:

1. uso solo hilo - ya sea sólo existe un hilo, o sólo se está utilizando la exclusión mutua y el recurso que protege: bloqueo es prácticamente libre , tal vez 80-100 ciclos como máximo.
2. Múltiples hilos usando el recurso, pero los bloqueos se mantienen por intervalos muy cortos y la contención es rara: el bloqueo tiene algún costo, y es difícil de medir; el costo consiste principalmente en invalidar las líneas de caché de otros núcleos '/ cpus'.
3. Conflicto significativo de bloqueo: casi todas las operaciones de bloqueo y desbloqueo requerirán la asistencia del kernel, y el costo es fácilmente varios miles (posiblemente incluso decenas de miles) de ciclos por bloqueo/desbloqueo.

Aún así, los mutexes deberían ser la primitiva de bloqueo menos costosa en la mayoría de las situaciones y en la mayoría de las implementaciones. Ocasionalmente los spinlocks pueden tener un mejor rendimiento. Nunca esperaría que los semáforos funcionaran mejor.

Answer 4

Por lo que puedo ver, su estrategia de bloqueo no es óptima ya que la mayoría de los bloqueos no se tomarán para cambiar los datos, sino solo para leer y encontrar el camino a través del árbol.

pthread_rwlock_tpodría ayuda en esto. Solo tomaría bloqueos de lectura en la ruta hacia abajo en el árbol hasta que llegue a un nodo donde desea hacer algunas modificaciones. Allí tomarías un bloqueo de escritura.Con eso, podrías tener otros hilos para realizar la misma tarea cuando camines por el árbol en una rama diferente sin molestar a los demás.

Una implementación decente de pthread_rwlock_t haría esto con un contador para los lectores que cambie con operaciones atómicas, siempre y cuando no haya conflicto con los escritores. Esto debería ser muy rápido. Una vez que haya una disputa, sería tan costoso como un mutex, creo.

Answer 5

Sus cerraduras son probablemente demasiado finas. Por supuesto, la granularidad óptima puede variar según la carga de trabajo.

Se puede usar un candado para todo el árbol, y puede obtener mejores resultados. Pero, si haces muchas lecturas y relativamente pocas inserciones/eliminaciones, terminas con todo el árbol bloqueado a menudo sin una buena razón. Es posible que desee utilizar un bloqueo lector-escritor, que permitiría varios lectores al mismo tiempo.

Su pregunta me recordó a this other one, cuando hay una comparación entre el bloqueo de grano fino y el bloqueo de grano grueso para una lista vinculada. Mientras que en la versión de grano grueso cada hilo se ejecutaba por turno (no en paralelo), y el tiempo total de ejecución era ligeramente mayor que la suma del tiempo de ejecución de cada hilo, y en la versión fina el tiempo de ejecución total era mucho menor que el suma del tiempo de ejecución de cada hilo, la sobrecarga adicional de bloqueo de grano fino compensó totalmente estos beneficios, haciendo que la versión de grano fino sea más lenta que la de grano grueso.