c++ - respiratorio - tecnicas manuales de fisioterapia respiratoria

El uso de este puntero provoca una desoptimización extraña en el bucle dinámico

Question

Recientemente me encontré con una desoptimización extraña (o más bien perdí la oportunidad de optimización).

Considere esta función para desempaquetar de manera eficiente conjuntos de enteros de 3 bits a enteros de 8 bits. Descomprime 16 ints en cada iteración de bucle:

void unpack3bit(uint8_t* target, char* source, int size) {
   while(size > 0){
      uint64_t t = *reinterpret_cast<uint64_t*>(source);
      target[0] = t & 0x7;
      target[1] = (t >> 3) & 0x7;
      target[2] = (t >> 6) & 0x7;
      target[3] = (t >> 9) & 0x7;
      target[4] = (t >> 12) & 0x7;
      target[5] = (t >> 15) & 0x7;
      target[6] = (t >> 18) & 0x7;
      target[7] = (t >> 21) & 0x7;
      target[8] = (t >> 24) & 0x7;
      target[9] = (t >> 27) & 0x7;
      target[10] = (t >> 30) & 0x7;
      target[11] = (t >> 33) & 0x7;
      target[12] = (t >> 36) & 0x7;
      target[13] = (t >> 39) & 0x7;
      target[14] = (t >> 42) & 0x7;
      target[15] = (t >> 45) & 0x7;
      source+=6;
      size-=6;
      target+=16;
   }
}

Aquí está el ensamblado generado para partes del código:

 ...
 367:   48 89 c1                mov    rcx,rax
 36a:   48 c1 e9 09             shr    rcx,0x9
 36e:   83 e1 07                and    ecx,0x7
 371:   48 89 4f 18             mov    QWORD PTR [rdi+0x18],rcx
 375:   48 89 c1                mov    rcx,rax
 378:   48 c1 e9 0c             shr    rcx,0xc
 37c:   83 e1 07                and    ecx,0x7
 37f:   48 89 4f 20             mov    QWORD PTR [rdi+0x20],rcx
 383:   48 89 c1                mov    rcx,rax
 386:   48 c1 e9 0f             shr    rcx,0xf
 38a:   83 e1 07                and    ecx,0x7
 38d:   48 89 4f 28             mov    QWORD PTR [rdi+0x28],rcx
 391:   48 89 c1                mov    rcx,rax
 394:   48 c1 e9 12             shr    rcx,0x12
 398:   83 e1 07                and    ecx,0x7
 39b:   48 89 4f 30             mov    QWORD PTR [rdi+0x30],rcx
 ...

Se ve bastante eficiente. Simplemente un shift right seguido de una and , y luego una store al búfer de target . Pero ahora, mira lo que sucede cuando cambio la función a un método en una estructura:

struct T{
   uint8_t* target;
   char* source;
   void unpack3bit( int size);
};

void T::unpack3bit(int size) {
        while(size > 0){
           uint64_t t = *reinterpret_cast<uint64_t*>(source);
           target[0] = t & 0x7;
           target[1] = (t >> 3) & 0x7;
           target[2] = (t >> 6) & 0x7;
           target[3] = (t >> 9) & 0x7;
           target[4] = (t >> 12) & 0x7;
           target[5] = (t >> 15) & 0x7;
           target[6] = (t >> 18) & 0x7;
           target[7] = (t >> 21) & 0x7;
           target[8] = (t >> 24) & 0x7;
           target[9] = (t >> 27) & 0x7;
           target[10] = (t >> 30) & 0x7;
           target[11] = (t >> 33) & 0x7;
           target[12] = (t >> 36) & 0x7;
           target[13] = (t >> 39) & 0x7;
           target[14] = (t >> 42) & 0x7;
           target[15] = (t >> 45) & 0x7;
           source+=6;
           size-=6;
           target+=16;
        }
}

Pensé que el ensamblado generado debería ser el mismo, pero no lo es. Aquí hay una parte de esto:

...
 2b3:   48 c1 e9 15             shr    rcx,0x15
 2b7:   83 e1 07                and    ecx,0x7
 2ba:   88 4a 07                mov    BYTE PTR [rdx+0x7],cl
 2bd:   48 89 c1                mov    rcx,rax
 2c0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2c3:   48 c1 e9 18             shr    rcx,0x18
 2c7:   83 e1 07                and    ecx,0x7
 2ca:   88 4a 08                mov    BYTE PTR [rdx+0x8],cl
 2cd:   48 89 c1                mov    rcx,rax
 2d0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2d3:   48 c1 e9 1b             shr    rcx,0x1b
 2d7:   83 e1 07                and    ecx,0x7
 2da:   88 4a 09                mov    BYTE PTR [rdx+0x9],cl
 2dd:   48 89 c1                mov    rcx,rax
 2e0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2e3:   48 c1 e9 1e             shr    rcx,0x1e
 2e7:   83 e1 07                and    ecx,0x7
 2ea:   88 4a 0a                mov    BYTE PTR [rdx+0xa],cl
 2ed:   48 89 c1                mov    rcx,rax
 2f0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 ...

Como puede ver, introdujimos una load redundante adicional de la memoria antes de cada turno ( mov rdx,QWORD PTR [rdi] ). Parece que el puntero de target (que ahora es un miembro en lugar de una variable local) siempre debe recargarse antes de almacenarlo. Esto ralentiza el código considerablemente (alrededor del 15% en mis mediciones).

Primero, pensé que tal vez el modelo de memoria de C ++ exige que un puntero miembro no se almacene en un registro, sino que deba volverse a cargar, pero esto parecía una elección incómoda, ya que haría imposible muchas optimizaciones viables. Así que me sorprendió mucho que el compilador no almacenara el target en un registro aquí.

Intenté almacenar en caché el puntero del miembro en una variable local:

void T::unpack3bit(int size) {
    while(size > 0){
       uint64_t t = *reinterpret_cast<uint64_t*>(source);
       uint8_t* target = this->target; // << ptr cached in local variable
       target[0] = t & 0x7;
       target[1] = (t >> 3) & 0x7;
       target[2] = (t >> 6) & 0x7;
       target[3] = (t >> 9) & 0x7;
       target[4] = (t >> 12) & 0x7;
       target[5] = (t >> 15) & 0x7;
       target[6] = (t >> 18) & 0x7;
       target[7] = (t >> 21) & 0x7;
       target[8] = (t >> 24) & 0x7;
       target[9] = (t >> 27) & 0x7;
       target[10] = (t >> 30) & 0x7;
       target[11] = (t >> 33) & 0x7;
       target[12] = (t >> 36) & 0x7;
       target[13] = (t >> 39) & 0x7;
       target[14] = (t >> 42) & 0x7;
       target[15] = (t >> 45) & 0x7;
       source+=6;
       size-=6;
       this->target+=16;
    }
}

Este código también produce el ensamblador "bueno" sin tiendas adicionales. Entonces, supongo: el compilador no puede elevar la carga de un puntero miembro de una estructura, por lo que dicho "puntero activo" siempre debe almacenarse en una variable local.

• Entonces, ¿por qué el compilador no puede optimizar estas cargas?
• ¿Es el modelo de memoria C ++ lo que prohíbe esto? ¿O es simplemente una deficiencia de mi compilador?
• ¿Es mi suposición correcta o cuál es la razón exacta por la que no se puede realizar la optimización?

El compilador en uso fue g++ 4.8.2-19ubuntu1 con optimización g++ 4.8.2-19ubuntu1 . También probé clang++ 3.4-1ubuntu3 con resultados similares: Clang incluso puede vectorizar el método con el puntero de target local. Sin embargo, el uso del puntero this->target produce el mismo resultado: una carga adicional del puntero antes de cada tienda.

Verifiqué el ensamblador de algunos métodos similares y el resultado es el mismo: parece que un miembro de this siempre tiene que recargarse antes de una tienda, incluso si tal carga simplemente se puede elevar fuera del bucle. Tendré que volver a escribir una gran cantidad de código para deshacerme de estos almacenes adicionales, principalmente almacenando el puntero en una variable local que se declara sobre el código activo. Pero siempre pensé que jugar con detalles como el almacenamiento en caché de un puntero en una variable local seguramente calificaría para la optimización prematura en estos días en que los compiladores se han vuelto tan inteligentes. Pero parece que estoy equivocado aquí . El almacenamiento en caché de un puntero de miembro en un bucle activo parece ser una técnica de optimización manual necesaria.

Answer 1

El alias de puntero parece ser el problema, irónicamente entre this y this->target . El compilador está teniendo en cuenta la posibilidad bastante obscena que inicializó:

this->target = &this

En ese caso, escribir en this->target[0] alteraría el contenido de this (y por lo tanto, this-> target).

El problema de alias de memoria no está restringido a lo anterior. En principio, cualquier uso de this->target[XX] dado un valor (in) apropiado de XX podría apuntar a this .

Estoy mejor versado en C, donde esto puede remediarse declarando variables de puntero con la palabra clave __restrict__.

Answer 2

El problema aquí es el alias estricto que dice que se nos permite alias a través de un char * y eso evita la optimización del compilador en su caso. No se nos permite alias a través de un puntero de un tipo diferente que sería un comportamiento indefinido, normalmente en SO vemos este problema en el que los usuarios intentan alias a través de tipos de puntero incompatibles .

Parece razonable implementar uint8_t como un carácter sin signo y si miramos cstdint en Coliru , incluye stdint.h que typedefs uint8_t de la siguiente manera:

typedef unsigned char       uint8_t;

Si usó otro tipo que no sea char, el compilador debería poder optimizar.

Esto está cubierto en el borrador del estándar C ++ sección 3.10 Valores y valores que dice:

Si un programa intenta acceder al valor almacenado de un objeto a través de un valor gl diferente de uno de los siguientes tipos, el comportamiento es indefinido

e incluye la siguiente viñeta:

• un tipo de carácter char o unsigned.

Tenga en cuenta que publiqué un comentario sobre posibles soluciones alternativas en una pregunta que pregunta cuándo es uint8_t ≠ unsigned char? y la recomendación fue:

La solución trivial, sin embargo, es usar la palabra clave restrict, o copiar el puntero a una variable local cuya dirección nunca se toma para que el compilador no tenga que preocuparse por si los objetos uint8_t pueden alias.

Dado que C ++ no admite la palabra clave restrictiva , debe confiar en la extensión del compilador, por ejemplo, gcc usa __restrict__, por lo que no es totalmente portátil, pero la otra sugerencia debería serlo.

Answer 3

Las reglas de alias estrictas permiten que char* alias cualquier otro puntero. Entonces this->target puede alias con this , y en su método de código, la primera parte del código,

target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;

es de hecho

this->target[0] = t & 0x7;
this->target[1] = (t >> 3) & 0x7;
this->target[2] = (t >> 6) & 0x7;

ya que this puede modificarse cuando modifica this->target contenido this->target .

Una vez que this->target se almacena en caché en una variable local, el alias ya no es posible con la variable local.