¿Función ‘memcpy’ que soporta desplazamientos por bits individuales?

Estaba pensando en resolver esto, pero parece ser una gran tarea. Si tomo este por mi cuenta, es probable que lo escriba de varias maneras y escoja la mejor, así que pensé en hacer esta pregunta para ver si hay una buena biblioteca que resuelva esto o si alguien tiene ideas o consejos.

void OffsetMemCpy(u8* pDest, u8* pSrc, u8 srcBitOffset, size size) { // Or something along these lines. srcBitOffset is 0-7, so the pSrc buffer // needs to be up to one byte longer than it would need to be in memcpy. // Maybe explicitly providing the end of the buffer is best. // Also note that pSrc has NO alignment assumptions at all. } 

Mi aplicación es crítica con respecto al tiempo, por lo que quiero solucionar esto con una sobrecarga mínima. Esta es la fuente de la dificultad / complejidad. En mi caso, es probable que los bloques sean bastante pequeños, tal vez de 4 a 12 bytes, por lo que las cosas memcpy a gran escala (por ejemplo, la captura previa) no son tan importantes. El mejor resultado sería el que se ajuste más rápido para la entrada de ‘tamaño’ constante, entre 4 y 12, para búferes src aleatorios no alineados.

  • La memoria debe moverse en bloques de tamaño de palabra siempre que sea posible
  • La alineación de estos bloques de tamaño de palabra es importante. pSrc no está alineado, por lo que es posible que tengamos que leer unos pocos bytes en el frente hasta que esté alineado.

¿Alguien tiene, o sabe, algo similar implementado? ¿O alguien quiere probar esto para que sea lo más limpio y eficiente posible?

Edit: Parece que la gente está votando este “cierre” por “demasiado amplio”. Unos pocos detalles de estrechamiento serían que AMD64 es la architecture preferida, así que asummos que. Esto significa poco endian, etc. Esperamos que la implementación se ajuste al tamaño de una respuesta, por lo que no creo que esto sea demasiado amplio. Solicito respuestas que sean una sola implementación a la vez, aunque hay algunos enfoques.

Comenzaría con una implementación simple como esta:

 inline void OffsetMemCpy(uint8_t* pDest, const uint8_t* pSrc, const uint8_t srcBitOffset, const size_t size) { if (srcBitOffset == 0) { for (size_t i = 0; i < size; ++i) { pDest[i] = pSrc[i]; } } else if (size > 0) { uint8_t v0 = pSrc[0]; for (size_t i = 0; i < size; ++i) { uint8_t v1 = pSrc[i + 1]; pDest[i] = (v0 << srcBitOffset) | (v1 >> (CHAR_BIT - srcBitOffset)); v0 = v1; } } } 

(advertencia: código sin probar!).

Una vez que esto funcione, perfílelo en su aplicación: puede encontrarlo lo suficientemente rápido para sus necesidades y, por lo tanto, evitar los inconvenientes de una optimización prematura. Si no, entonces tiene una implementación de referencia de referencia útil para un trabajo de optimización adicional.

Tenga en cuenta que para copias pequeñas, la sobrecarga de las pruebas de alineación y de tamaño de palabra, etc. puede superar cualquier beneficio, por lo que un simple byte por byte como el anterior puede ser casi óptimo.

Tenga en cuenta también que las optimizaciones pueden depender de la architecture: las microoptimizaciones que benefician a una CPU pueden ser contraproducentes en otras.

Creo que la solución trivial de byte por byte (consulte la respuesta de @ PaulR) es el mejor enfoque para bloques pequeños, a menos que pueda satisfacer las siguientes restricciones adicionales:

  1. El búfer de entrada se asigna con algún relleno, es decir, acceder a algunos bytes después de que el último no se bloquee.
  2. El búfer de salida también se asigna con algo de relleno, y no importa si se sobrescriben unos pocos bytes después de la ubicación del resultado deseado. Si importa, necesitarás hacer más cosas para preservar esos bytes posteriores al final.
  3. Los rangos de entrada y salida involucrados no se superponen (incluyendo algunos bytes de relleno más después del final), al igual que en memcpy.

Si puede, entonces es posible boost la granularidad del algoritmo. Es muy fácil cambiar la respuesta de @ PaulR para usar palabras uint64_t lugar de uint8_t bytes en todas partes. Como resultado, funcionaría más rápido.

Podemos usar SSE para boost aún más el tamaño de la palabra. Ya que en SSE no hay forma de cambiar todo el registro en bits, tenemos que hacer dos cambios para los enteros de 64 bits, luego pegar los resultados juntos. El pegado se realiza mediante _mm_shuffle_epi8 desde SSSE3, lo que permite mezclar bytes en el registro XMM de manera arbitraria. Para cambiar, usamos _mm_srl_epi64 , porque esa es la única manera de desplazar enteros de 64 bits por un número no inmediato de bits. He agregado la palabra clave de restrict de C (como macro) a los argumentos del puntero, porque si tienen un alias, el algoritmo no funcionará de todos modos.

Aquí está el código:

 void OffsetMemCpy_stgatilov(uint8_t *RESTRICT pDest, const uint8_t *RESTRICT pSrc, const uint8_t srcBitOffset, const size_t size) { __m128i bits = (sizeof(size_t) == 8 ? _mm_cvtsi64_si128(srcBitOffset) : _mm_cvtsi32_si128(srcBitOffset)); const uint8_t *pEnd = pSrc + size; while (pSrc < pEnd) { __m128i input = _mm_loadu_si128((__m128i*)pSrc); __m128i reg = _mm_shuffle_epi8(input, _mm_setr_epi8(0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14)); __m128i shifted = _mm_srl_epi64(reg, bits); __m128i comp = _mm_shuffle_epi8(shifted, _mm_setr_epi8(0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, -1, -1)); _mm_storeu_si128((__m128i*)pDest, comp); pSrc += 14; pDest += 14; } } 

Procesa 14 bytes por iteración. Cada iteración es bastante simple, también hay algo de código antes del bucle. Aquí está el código de ensamblaje de todo el cuerpo de la función generado por MSVC2013 x64:

  movzx eax, r8b movd xmm3, rax lea rax, QWORD PTR [rdx+r9] cmp rdx, rax jae SHORT $LN1@OffsetMemC movdqa xmm1, XMMWORD PTR __xmm@0e0d0c0b0a0908070706050403020100 movdqa xmm2, XMMWORD PTR __xmm@ffff0e0d0c0b0a090806050403020100 sub rcx, rdx npad 11 $LL2@OffsetMemC: movdqu xmm0, XMMWORD PTR [rdx] add rdx, 14 pshufb xmm0, xmm1 psrlq xmm0, xmm3 pshufb xmm0, xmm2 movdqu XMMWORD PTR [rcx+rdx-14], xmm0 cmp rdx, rax jb SHORT $LL2@OffsetMemC $LN1@OffsetMemC: ret 0 

IACA dice que la función completa tiene un rendimiento de 4,5 ciclos y una latencia de 13 ciclos en Ivy Bridge, dado que el bucle se ejecuta una vez y no ocurren problemas con cachés / twigs / deencoding. Sin embargo, en referencia, se gastan 7,5 ciclos en una de esas llamadas en promedio.

Estos son breves resultados de rendimiento de referencia en Ivy Bridge 3.4 Ghz (ver más resultados en el código):

 (billions of calls per second) size = 4: 0.132 (Paul R) 0.248 (Paul R x64) 0.45 (stgatilov) size = 8: 0.0782 (Paul R) 0.249 (Paul R x64) 0.45 (stgatilov) size = 12: 0.0559 (Paul R) 0.191 (Paul R x64) 0.453 (stgatilov) 

Sin embargo, tenga en cuenta que en el mundo real el rendimiento puede ser drásticamente diferente de los resultados de referencia.

Código completo con benchmarking y resultados más detallados están aquí .

    Intereting Posts