Estoy tratando de escribir mi primer programa de subprocesos múltiples en C bajo Linux. Ya tengo un programa que juega con la configuración y el restablecimiento de bits en un gran búfer, ahora solo quiero hacerlo más rápido, lo más rápido posible sin escribir todo en ensamblador.
Para el programa de subproceso único, definí mis propias macros para la manipulación de bits (se ven grandes y feas, pero funcionan):
#define CELL_SIZE (64) #define getBit(bitIdx, arr) ( arr[ (bitIdx) / CELL_SIZE ] & ( (1uL << (CELL_SIZE - 1)) >> (bitIdx) % CELL_SIZE)) #define resetBit(bitIdx, arr) ( arr[ (bitIdx) / CELL_SIZE ] &= ~( (1uL << (CELL_SIZE - 1)) >> (bitIdx) % CELL_SIZE))Obviamente, esas operaciones son cualquier cosa MENOS atómicas.
Investigué un poco y encontré varias respuestas. Algunas respuestas son sobre cómo escribir mis propias funciones en ensamblador (que quiero evitar).
Otros sitios ( este o este ) parecen hablar exactamente sobre lo que necesito, excepto que no tengo idea de cómo usar esas interfaces/macros.
Intenté las siguientes inclusiones, pero no funcionan.
#include <linux/bitmap.h> #include <asm/bitops.h>Entonces, básicamente, pregunto cómo puedo usar lo que ya está implementado para hacer mi trabajo. ¿Qué encabezado(s) debo incluir?
No me importa si las interfaces no están en el núcleo, siempre y cuando se haga el trabajo.
Nota: cada subproceso (re)establecería exactamente un bit a la vez; no planeo nada complicado de VOODOO.
Una pregunta secundaria sería: cuál sería más rápido (en general, escrito en pseudocódigo):
reset_bit();o
if ( bit_is_set() ) reset_bit();Muy a menudo, la operación reset_bit() no es necesaria, ya que el bit ya está reiniciado. La misma pregunta sobre la configuración de un bit establecido.
Para responder a la pregunta directamente, la solución más directa y fácilmente disponible es C11 <stdatomic.h> que debería proporcionar cualquier compilador C moderno para un sistema multiprocesador.
Las operaciones disponibles incluyen OR/AND atómico que puede usar para establecer y borrar bits. Así que podrías hacer
#include <stdatomic.h> #include <stdint.h> #include <stddef.h> typedef uint64_t cell_t; #define CELL_SIZE (64) static inline _Atomic cell_t *get_cell(size_t bitIdx, _Atomic cell_t *arr) { return arr + (bitIdx / CELL_SIZE); } static inline cell_t get_mask(size_t bitIdx) { return (1uL << (CELL_SIZE - 1)) >> (bitIdx) % CELL_SIZE; } static inline cell_t getBit(size_t bitIdx, _Atomic cell_t *arr) { return atomic_load(get_cell(bitIdx, arr)) & get_mask(bitIdx); } static inline void resetBit(size_t bitIdx, _Atomic cell_t *arr) { atomic_fetch_and(get_cell(bitIdx, arr), ~get_mask(bitIdx)); } static inline void setBit(size_t bitIdx, _Atomic cell_t *arr) { atomic_fetch_or(get_cell(bitIdx, arr), get_mask(bitIdx)); }Me tomé la libertad de reemplazar sus macros con funciones en línea, que son preferibles en prácticamente todas las situaciones.
Es posible que pueda acelerar un poco las cosas, en algunas plataformas, usando las versiones *_explicit con memory_order_relaxed , pero depende en gran medida de cómo se usarán las funciones, y una introducción al orden de la memoria está fuera del alcance de esta publicación.
Las implicaciones de rendimiento son más difíciles. Las operaciones atómicas de lectura, modificación y escritura son mucho más lentas que las no atómicas, por lo general. Y si hay contienda entre las CPU por las líneas de caché, eso ralentiza aún más las cosas. A menos que pueda controlar estos aspectos muy bien, su plan de poner más núcleos a trabajar en la tarea probablemente la hará más lenta.
En cuanto a su última pregunta sobre si probar el bit primero, es difícil de decir. Una carga es generalmente más rápida que una lectura-modificación-escritura. Sin embargo, el costo de hacer la prueba y la bifurcación condicional, y especialmente la posibilidad de predecir mal esa bifurcación, puede anular los ahorros.