c - son - paises no alineados pdf

¿La forma más rápida de trabajar con datos no alineados en un proccessor alineado con palabras?

Question

Estoy haciendo un proyecto en un ARM Cortex M0, que no admite acceso desalineado (por 4 bytes), y estoy tratando de optimizar la velocidad de las operaciones en datos no alineados.

Estoy almacenando direcciones de bajo consumo de energía Bluetooth (48 bits) como matrices de 6 bytes en algunas estructuras empaquetadas que actúan como memorias intermedias de paquetes. Debido al empaque, las direcciones BLE no necesariamente comienzan en una dirección alineada con palabras, y tengo algunas complicaciones cuando optimizo mis funciones de acceso a estas direcciones.

El primer enfoque, y el más obvio, es un ciclo for que opera en cada byte de la matriz individualmente. Verificando si dos direcciones son iguales, por ejemplo, se podría hacer así:

uint8_t ble_adv_addr_is_equal(uint8_t* addr1, uint8_t* addr2)
{
  for (uint32_t i = 0; i < 6; ++i)
  {
    if (addr1[i] != addr2[i])
      return 0;
  }
  return 1;
}

Estoy haciendo muchas comparaciones en mi proyecto, y quería ver si podía sacar más velocidad de esta función. Me di cuenta de que para las direcciones alineadas, podría convertirlas en uint64_t y compararlas con las máscaras de 48 bits aplicadas, es decir,

((uint64_t)&addr1[0] & 0xFFFFFFFFFFFF) == ((uint64_t)&addr2[0] & 0xFFFFFFFFFFFF)

Se podrían hacer operaciones similares para escribir, y funciona bien para versiones alineadas. Sin embargo, dado que mis direcciones no siempre están alineadas con las palabras (o incluso a medias palabras), tendría que hacer algunos trucos adicionales para que esto funcione.

En primer lugar, se me ocurrió esta pesadilla no optimizada de una macro de compilación:

#define ADDR_ALIGNED(_addr) (uint64_t)(((*((uint64_t*)(((uint32_t)_addr) & ~0x03)) >> (8*(((uint32_t)_addr) & 0x03))) & 0x000000FFFFFFFF)/
                                    | (((*((uint64_t*)(((uint32_t)_addr+4) & ~0x03))) << (32-8*(((uint32_t)_addr) & 0x03)))) & 0x00FFFF00000000)

Básicamente cambia toda la dirección para comenzar en la posición de memoria alineada con la palabra anterior, independientemente de la compensación. Por ejemplo:

    0       1       2       3
|-------|-------|-------|-------|
|.......|.......|.......|<ADDR0>|
|<ADDR1>|<ADDR2>|<ADDR3>|<ADDR4>|
|<ADDR5>|.......|.......|.......|

se convierte

    0       1       2       3
|-------|-------|-------|-------|
|<ADDR0>|<ADDR1>|<ADDR2>|<ADDR3>|
|<ADDR4>|<ADDR5>|.......|.......|
|.......|.......|.......|.......|

y puedo hacer una comparación segura de dos direcciones de 64 bits, independientemente de su alineación real:

ADDR_ALIGNED(addr1) == ADDR_ALIGNED(addr2)

¡Ordenado! Pero esta operación requiere 71 líneas de ensamblaje cuando se compila con el ARM-MDK, en comparación con 53 cuando se hace la comparación en un bucle for simple (voy a ignorar el tiempo adicional dedicado en las instrucciones de bifurcación aquí), y ~ 30 cuando se desenrolla. Además, no funciona para escrituras, ya que la alineación solo ocurre en los registros, no en la memoria. Desalinearlo de nuevo requeriría una operación similar, y todo el enfoque generalmente parece ser desagradable.

¿Es un bucle de forzado desenrollado trabajando cada byte individualmente realmente la solución más rápida para casos como este? ¿Alguien tiene alguna experiencia con escenarios similares y desea compartir algo de su magia aquí?

Answer 1

Al leer esta documentación de la clase SIMD, encontré cómo asignar variables, tanto estáticamente como dinámicamente, con la alineación adecuada. http://www.agner.org/optimize/vectorclass.pdf

Página 101

Windows, escribe:

__declspec(align(16)) int mydata[1000];

En sistemas tipo Unix, escribe:

int mydata[1000] __attribute__((aligned(16)));

Página 16

Si necesita una matriz de un tamaño que se determina en tiempo de ejecución, entonces tendrá un problema con la alineación. Cada vector debe almacenarse en una dirección divisible por 16, 32 o 64 bytes, de acuerdo con su tamaño. El compilador puede hacer esto al definir una matriz de tamaño fijo, como en el ejemplo anterior, pero no necesariamente con la asignación de memoria dinámica. Si crea una matriz de tamaño dinámico utilizando new, malloc o un contenedor STL , o cualquier otro método, es posible que no consiga la alineación adecuada para los vectores y el programa muy probablemente fallará al acceder a un vector mal alineado. El estándar C ++ dice "Es implementación definida si new-expression, [...] admite tipos sobrealineados". Las posibles soluciones son usar posix_memalign, _aligned_malloc, std :: aligned_storage, std :: align , etc. según lo que admita tu compilador, pero el método puede no ser portable para todas las plataformas.

Answer 2

Puede hacer que su compilador elija la forma más rápida para usted:

#include <stdint.h>
#include <stddef.h>
#include <string.h>

uint64_t unalignedload(char const *packed)
{
  uint64_t buffer;
  memcpy(&buffer, packed, 8);
  return buffer;
}

Esto no es exactamente lo que quiere, ya que la carga de 8 bytes puede segfault si no está alineado y se ejecuta fuera de la página, pero es un comienzo. Si puede agregar dos bytes de relleno al final de la matriz, puede evitar fácilmente ese problema.
gcc y clang parecen optimizar esto bien.

Answer 3

ACTUALIZAR

Ok, como tus datos no tienen ninguna alineación, necesitas leer todos los datos, byte a byte, en búferes alineados correctamente y luego hacer comparaciones realmente rápidas de 64 bits, o, si no vas a usar los datos después las comparaciones, solo lea en los datos como bytes y haga 6 comparaciones, en cuyo caso llamar a memcmp() podría ser una mejor opción.

Para alinear al menos 16 bits:

 u16 *src1 = (u16 *)addr1; 
 u16 *src2 = (u16 *)addr2;

 for (int i = 0; i < 3; ++i)
 {
    if (src1[i] != src2[i])
      return 0;
 }

 return 1;

Será dos veces más rápido que las comparaciones de bytes y podría ser lo mejor que pueda hacer razonablemente siempre que sus datos estén alineados al menos a 2 bytes. También esperaría que el compilador elimine por completo el bucle for y simplemente use sentencias if condicionalmente ejecutadas.

Probar lecturas alineadas de 32 bits no será más rápido a menos que pueda garantizar que la fuente 1 y 2 estén alineadas de manera similar (add1 y 0x03) == (addr2 y 0x03). Si este es el caso, entonces puede leer en un valor de 32 bits y luego un de 16 bits (o viceversa, dependiendo de la alineación inicial) y eliminar 1 comparación más.

Como su base compartida es de 16 bits, puede comenzar allí y el compilador debe generar ldrh tipo ldrh agradables.