Uso realista de la palabra clave 'restringir' C99?

Question

Estaba buscando documentación y preguntas/respuestas y lo he mencionado. Leí una breve descripción, indicando que sería básicamente una promesa del programador que el puntero no se utilizará para señalar en otro lugar.

¿Alguien puede ofrecer algunos casos realistas donde vale la pena realmente usar esto?

Answer 1

restrict dice que el puntero es lo único que accede al objeto subyacente. Elimina el potencial de alias de punteros, lo que permite una mejor optimización por parte del compilador.

Por ejemplo, supongamos que tengo una máquina con instrucciones especializadas que pueden multiplicar vectores de números en la memoria, y tengo el siguiente código:

void MultiplyArrays(int* dest, int* src1, int* src2, int n) 
{ 
    for(int i = 0; i < n; i++) 
    { 
     dest[i] = src1[i]*src2[i]; 
    } 
} 

El compilador necesita para manejar correctamente si dest, SRC1, y superposición src2, lo que significa que debe hacer una multiplicación a la vez, de principio a fin. Al tener restrict, el compilador puede optimizar este código para utilizar las instrucciones vectoriales.

EDITAR: Wikipedia tiene una entrada en restrict, con otro ejemplo, here.

Answer 2

El Wikipedia example es muy illuminating.

Muestra claramente cómo permite guardar una instrucción de montaje.

Sin restringir:

void f(int *a, int *b, int *x) { 
    *a += *x; 
    *b += *x; 
} 

Pseudo montaje:

load R1 ← *x ; Load the value of x pointer 
load R2 ← *a ; Load the value of a pointer 
add R2 += R1 ; Perform Addition 
set R2 → *a  ; Update the value of a pointer 
; Similarly for b, note that x is loaded twice, 
; because a may be equal to x. 
load R1 ← *x 
load R2 ← *b 
add R2 += R1 
set R2 → *b 

Con restringir:

void fr(int *restrict a, int *restrict b, int *restrict x); 

Pseudo montaje:

load R1 ← *x 
load R2 ← *a 
add R2 += R1 
set R2 → *a 
; Note that x is not reloaded, 
; because the compiler knows it is unchanged 
; load R1 ← *x 
load R2 ← *b 
add R2 += R1 
set R2 → *b 

¿GCC realmente lo hace?

GCC 4.8 Linux x86-64:

gcc -g -std=c99 -O0 -c main.c 
objdump -S main.o 

Con -O0, que son los mismos.

Con -O3:

void f(int *a, int *b, int *x) { 
    *a += *x; 
    0: 8b 02     mov (%rdx),%eax 
    2: 01 07     add %eax,(%rdi) 
    *b += *x; 
    4: 8b 02     mov (%rdx),%eax 
    6: 01 06     add %eax,(%rsi) 

void fr(int *restrict a, int *restrict b, int *restrict x) { 
    *a += *x; 
    10: 8b 02     mov (%rdx),%eax 
    12: 01 07     add %eax,(%rdi) 
    *b += *x; 
    14: 01 06     add %eax,(%rsi) 

Para los no iniciados, la calling convention es:

• rdi = primer parámetro
• rsi = segundo parámetro
• rdx = tercer parámetro

La salida de GCC fue incluso más clara que el artículo wiki: 4 instrucciones frente a 3 instrucciones.

matrices

Hasta ahora hemos ahorro de instrucciones individuales, pero si el puntero representan matrices para ser puesto en loop, un caso de uso común, entonces un montón de instrucciones podrían salvarse, como se ha mencionado por supercat.

Considérese, por ejemplo:

void f(char *restrict p1, char *restrict p2) { 
    for (int i = 0; i < 50; i++) { 
     p1[i] = 4; 
     p2[i] = 9; 
    } 
} 

Debido a restrict, un compilador inteligente (o humano), podría optimizar que a:

memset(p1, 4, 50); 
memset(p2, 9, 50); 

que es potencialmente mucho más eficiente, ya que puede ser de montaje optimizado en una implementación de libc decente (como glibc): Is it better to use std::memcpy() or std::copy() in terms to performance?

¿GCC realmente lo hace?

GCC 5.2.1.Linux x86-64 Ubuntu 15.10:

gcc -g -std=c99 -O0 -c main.c 
objdump -dr main.o 

Con -O0, ambos son lo mismo.

Con -O3:

• con restringir:

  3f0: 48 85 d2    test %rdx,%rdx 
  3f3: 74 33     je  428 <fr+0x38> 
  3f5: 55      push %rbp 
  3f6: 53      push %rbx 
  3f7: 48 89 f5    mov %rsi,%rbp 
  3fa: be 04 00 00 00   mov $0x4,%esi 
  3ff: 48 89 d3    mov %rdx,%rbx 
  402: 48 83 ec 08    sub $0x8,%rsp 
  406: e8 00 00 00 00   callq 40b <fr+0x1b> 
           407: R_X86_64_PC32  memset-0x4 
  40b: 48 83 c4 08    add $0x8,%rsp 
  40f: 48 89 da    mov %rbx,%rdx 
  412: 48 89 ef    mov %rbp,%rdi 
  415: 5b      pop %rbx 
  416: 5d      pop %rbp 
  417: be 09 00 00 00   mov $0x9,%esi 
  41c: e9 00 00 00 00   jmpq 421 <fr+0x31> 
           41d: R_X86_64_PC32  memset-0x4 
  421: 0f 1f 80 00 00 00 00 nopl 0x0(%rax) 
  428: f3 c3     repz retq 
  

  Dos memset llamadas como se esperaba.

• sin restringir: no hay llamadas stdlib, sólo un 16 iteración amplia loop unrolling, que no tengo la intención de reproducir aquí :-)

no he tenido la paciencia de referencia, pero creo que la versión restringida será más rápida.

C99

Veamos el estándar por el bien integridad.

restrict dice que dos punteros no pueden apuntar a regiones de memoria superpuestas.El uso más común es para argumentos de función.

Esto restringe cómo se puede invocar la función, pero permite más optimizaciones en tiempo de compilación.

Si la persona que llama no sigue el contrato restrict, comportamiento indefinido.

Los C99 N1256 draft 6.7.3/7 "calificadores de tipo" dice:

El uso previsto de la clasificación para restringir (como la clase de registros de almacenamiento) es promover la optimización y eliminación de todas las instancias del calificador de todas las unidades de traducción de preprocesamiento que componen un programa conforme no cambian su significado (es decir, el comportamiento observable).

y 6.7.3.1 "Definición formal de restringir" da los detalles sangrientos.

regla de alias estricto

La palabra clave restrict sólo afecta a los punteros de tipos compatibles (por ejemplo, dos int*) debido a las estrictas reglas de alias dice que aliasing tipos incompatibles es un comportamiento no definido por defecto, y así compiladores puede asumir que lo hace no sucede y optimiza de distancia.

Ver: What is the strict aliasing rule?

Véase también

• C++ 14 todavía no tienen un análogo de restrict, pero GCC tiene __restrict__ como una extensión: What does the restrict keyword mean in C++?
• Muchas de las preguntas que le piden : de acuerdo con los detalles sangrientos, ¿este código UB o no?
  • Understanding restrict qualifier by examples
  • Restricted pointer questions
  • Is it legal to assign a restricted pointer to another pointer, and use the second pointer to modify the value?
• A "cuándo utilizar" pregunta: ¿When to use restrict and when not to
• El relacionada GCC __attribute__((malloc)), que dice que el valor de retorno de una función no es alias de cualquier cosa: GCC: __attribute__((malloc))