¿Trabajar ensamblaje en línea en C para paridad de bits?

4 minutos de lectura

avatar de usuario
étale-cohomology

Estoy tratando de calcular el paridad de bits de un gran número de uint64. Por paridad de bits me refiero a una función que acepta un uint64 y genera 0 si el número de bits establecidos es par, y 1 en caso contrario.

Actualmente estoy usando la siguiente función (por @Troyseph, que se encuentra aquí):

uint parity64(uint64 n){
  n ^= n >> 1;
  n ^= n >> 2;
  n = (n & 0x1111111111111111) * 0x1111111111111111;
  return (n >> 60) & 1;
}

La misma página SO tiene la siguiente rutina de ensamblaje (por @papadp):

.code

; bool CheckParity(size_t Result)
    CheckParity PROC
    mov     rax, 0
    add     rcx, 0
    jnp     jmp_over
    mov     rax, 1
jmp_over:
    ret
CheckParity ENDP

END

que aprovecha la máquina bandera de paridad. Pero no puedo hacer que funcione con mi programa C (sé que casi no hay ensamblaje).

Pregunta. ¿Cómo puedo incluir el código anterior (o similar) como ensamblado en línea en mi archivo fuente C, para que el parity64() la función ejecuta eso en su lugar?

(Estoy usando GCC con Ubuntu 14 de 64 bits en un Intel Xeon Haswell)


En caso de que sea de alguna ayuda, el parity64() La función se llama dentro de la siguiente rutina:

uint bindot(uint64* a, uint64* b, uint64 entries){
    uint parity = 0;

    for(uint i=0; i<entries; ++i)
      parity ^= parity64(a[i] & b[i]);  // Running sum!

    return parity;
}

(Se supone que este es el “producto escalar” de dos vectores sobre el campo Z/2Z, también conocido como GF(2).)

  • Omitiste el UL sufijos en el 111...

    –MM

    10 de mayo de 2017 a las 4:34

  • @MM Buena captura, gracias

    – étale-cohomología

    10 de mayo de 2017 a las 4:35

  • deberías hacer algo como uint64 parity = 0; for (...) parity ^= a[i] & b[i]; return parity64(parity);` Esto debería ser más rápido, especialmente si el bucle se vectoriza.

    – Ross Ridge

    10 de mayo de 2017 a las 5:41

  • @RossRidge Eso corre significativamente más rápido. Voy a convencerme ahora de que las dos versiones son equivalentes.

    – étale-cohomología

    10 de mayo de 2017 a las 5:48

  • La paridad es el XOR horizontal de todos los bits. XOR es asociativo, por lo que puede optimizar haciendo XOR “vertical” hasta que tenga un acumulador y luego calculando la paridad de eso.

    – Peter Cordes

    19 de septiembre de 2017 a las 5:03

  • Sheeze, esa es una gran respuesta, llena de consejos sólidos que solo provienen de la escuela de la experiencia. Bien hecho.

    –David C. Rankin

    12 de mayo de 2017 a las 4:34

  • El análisis es increíble. Necesitamos más respuestas de este tipo en SO. ¡Estoy tomando notas!

    –Ajay Brahmakshatriya

    12 de mayo de 2017 a las 4:47


  • Que hermosa respuesta..! Algunas notas: no tiene sentido suponer que el “ensamblaje en línea” es más rápido, ya que eventualmente todo lo es; es solo una cuestión de si uno puede “ensamblar” el compilador. Si bien es imposible en general, a veces el programador simplemente tiene más información sobre el propósito de un fragmento de código que lo que el compilador puede inferir del código en sí (sin decir que ese sea el caso aquí). (Quiero decir, los compiladores son inteligentes, pero están lejos de ser agentes de inteligencia general). En este caso, sin embargo, estaba entusiasmado sobre todo por acceder a cosas que C no expone, es decir. la bandera de la paridad

    – étale-cohomología

    12 mayo 2017 a las 12:51

  • ¡Gran respuesta! Creo que podría mejorarse moviendo su análisis empírico a una ubicación más prominente (por ejemplo, la parte superior de la respuesta)… Podría proporcionar una introducción como “Contrariamente a la afirmación implícita de que el ensamblado en línea es más rápido que el código C optimizado, descubrí que este no es necesariamente el caso. El análisis que se muestra a continuación prueba, empíricamente, que la versión proporcionada en C es *igual de rápida como la versión de ensamblaje en línea”.* Luego, una vez que haya cautivado al lector con las figuras, presente la idea de que la optimización prematura está equivocada. No obstante, ¡bien hecho!

    – autista

    13 de mayo de 2017 a las 3:30

  • __builtin_parityl parece funcionar. Y funciona más rápido que la otra función que estoy usando.

    – étale-cohomología

    10 de mayo de 2017 a las 4:34

  • Verifique la salida del ensamblaje con gcc -S, objdump -S o similar

    – hdante

    10 de mayo de 2017 a las 4:36

  • El problema aquí es que el indicador de paridad en x86/x86-64 solo se basa en el byte bajo del resultado.

    -Michael Petch

    10 de mayo de 2017 a las 4:26

  • @étale-cohomology: en realidad no funciona. Si desea la paridad de todo el registro de 64 bits, debe buscar otras soluciones.

    -Michael Petch

    10 de mayo de 2017 a las 4:31

  • No necesitas el salto, usa setp en su lugar

    – Benoît

    10 de mayo de 2017 a las 4:40

  • @AjayBrahmakshatriya entiendo operand type mismatch for setp

    – étale-cohomología

    10 de mayo de 2017 a las 5:03

  • No, __builtin_parityl() está obligado a trabajar más rápido. Está escrito de la manera más optimizada según el objetivo.

    –Ajay Brahmakshatriya

    10 de mayo de 2017 a las 5:24

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad