Supongamos que tengo una matriz de 1 000 000 de elementos y varios subprocesos de trabajo, cada uno de los cuales manipula datos en esta matriz. Los subprocesos de trabajo pueden estar actualizando elementos ya poblados con nuevos datos, pero cada operación está limitada a un solo elemento de matriz y es independiente de los valores de cualquier otro elemento.

El uso de un solo mutex para proteger toda la matriz claramente daría como resultado una gran contención. En el otro extremo, podría crear una matriz de exclusión mutua que tenga la misma longitud que la matriz original, y para cada array[i] bloquearía la mutex[i] mientras operaba en ella. Suponiendo una distribución uniforme de los datos, esto eliminaría principalmente la contención de bloqueo, a costa de una gran cantidad de memoria.

Creo que una solución más razonable sería tener una matriz de n mutexes (donde 1 < n < 1000000). Luego, para cada array[i] , bloquearía mutex[i % n] mientras operaba en él. Si n es lo suficientemente grande, aún puedo minimizar la contención.

Entonces, mi pregunta es, ¿existe una penalización de rendimiento al usar una gran cantidad (por ejemplo,> = 1000000) de mutexes de esta manera, más allá del aumento del uso de memoria? Si es así, ¿cuántos mutexes puede usar razonablemente antes de comenzar a ver la degradación?

Estoy seguro de que la respuesta a esto es algo específica de la plataforma; Estoy usando pthreads en Linux. También estoy trabajando en la configuración de mis propios puntos de referencia, pero la escala de datos en los que estoy trabajando hace que consuma mucho tiempo, por lo que agradecería alguna orientación inicial.

Esa fue la pregunta inicial. Para aquellos que solicitan información más detallada sobre el problema, tengo 4 archivos de datos binarios de varios GB que describen en algún lugar cerca de quinientos millones de eventos que se están analizando. La matriz en cuestión es en realidad la matriz de punteros que respaldan una tabla hash encadenada muy grande. Leemos los cuatro archivos de datos en la tabla hash, posiblemente agregándolos si comparten ciertas características. La implementación existente tiene 4 subprocesos, cada uno de los cuales lee un archivo e inserta registros de ese archivo en la tabla hash. La tabla hash tiene 997 bloqueos y 997*9973 = ~10 000 000 punteros. Al insertar un elemento con hash h , primero bloqueo mutex[h % 997] antes de insertar o modificar el elemento en bucket[h % 9943081] . Esto funciona bien y, por lo que sé, no hemos tenido demasiados problemas con la contención, pero hay un cuello de botella en el rendimiento porque solo usamos 4 núcleos de una máquina de 16 núcleos. (Y aún menos a medida que avanzamos, ya que los archivos generalmente no son todos del mismo tamaño). Una vez que todos los datos se han leído en la memoria, los analizamos, lo que utiliza nuevos hilos y una nueva estrategia de bloqueo ajustada a los diferentes carga de trabajo

Estoy intentando mejorar el rendimiento de la etapa de carga de datos cambiando a un grupo de subprocesos. En el nuevo modelo, todavía tengo un subproceso para cada archivo que simplemente lee el archivo en fragmentos de ~1 MB y pasa cada fragmento a un subproceso de trabajo en el grupo para analizar e insertar. La ganancia de rendimiento hasta ahora ha sido mínima, y el perfil que hice parecía indicar que el tiempo invertido en bloquear y desbloquear la matriz era el culpable probable. El bloqueo está integrado en la implementación de la tabla hash que estamos usando, pero permite especificar la cantidad de bloqueos que se usarán independientemente del tamaño de la tabla. Espero acelerar las cosas sin cambiar la implementación de la tabla hash.