python - lenguaje - ¿Cómo es el `min` de dos enteros tan rápido como el ''hackeo de bits''?

python tutorial

Question

Estaba viendo una serie de conferencias sobre ''Hackeo de bits'' y encontré la siguiente optimización para encontrar el mínimo de dos enteros:

return x ^ ((y ^ x) & -(x > y))

Que se dice que es más rápido que:

if x < y:
    return x
else:
    return y

Dado que la función min puede manejar más de solo dos enteros (flotadores, cadenas, listas e incluso objetos personalizados) asumí que llamar a min(x, y) tomaría más tiempo que el hackeo de bits optimizado de arriba. Para mi sorpresa, eran casi idénticos:

>>> python -m timeit "min(4, 5)"
1000000 loops, best of 3: 0.203 usec per loop

>>> python -m timeit "4 ^ ((5 ^ 4) & -(4 > 5))"
10000000 loops, best of 3: 0.19 usec per loop

Esto es cierto incluso para números superiores a 255 (objetos enteros de Python asignados previamente)

>>> python -m timeit "min(15456, 54657)"
10000000 loops, best of 3: 0.191 usec per loop

python -m timeit "15456 ^ ((54657 ^ 15456) & -(54657 > 15456))"
10000000 loops, best of 3: 0.18 usec per loop

¿Cómo es que una función tan versátil como min todavía puede ser tan rápida y optimizada?

^{Nota: Ejecuté el código anterior usando Python 3.5. Supongo que esto es lo mismo para Python 2.7+ pero no he probado}

He creado el siguiente módulo c:

#include <Python.h>

static PyObject * my_min(PyObject *self, PyObject *args){
    const long x;
    const long y;

    if (!PyArg_ParseTuple(args, "ll", &x, &y))
        return NULL;

    return PyLong_FromLong(x ^ ((y ^ x) & -(x > y)));
}

static PyMethodDef MyMinMethods[] = 
{
    { "my_min", my_min, METH_VARARGS, "bit hack min"
    },
    {NULL, NULL, 0, NULL}
};

PyMODINIT_FUNC
initmymin(void)
{
    PyObject *m;

    m = Py_InitModule("mymin", MyMinMethods);
    if (m == NULL)
        return;

}

Lo compilé y lo instalé en mi sistema (una máquina VM de ubuntu). Luego corrí lo siguiente:

>>> python -m timeit ''min(4, 5)''
10000000 loops, best of 3: 0.11 usec per loop

>>> python -m timeit -s ''import mymin'' ''mymin.my_min(4,5)''
10000000 loops, best of 3: 0.129 usec per loop

Si bien entiendo que esta es una máquina virtual, ¿no debería haber una brecha mayor en el tiempo de ejecución con la "piratería de bits" que se descarga en la c nativa?

Answer 1

Aquí hay algunos tiempos en Python 2.7 (porque asumí mal, lo siento):

def mymin(x, y):
    if x < y:
        return x
    return y

10000000 loops, best of 3: 0.0897 usec per loop

def mymin(x, y):
    return y

10000000 loops, best of 3: 0.0738 usec per loop

mymin = min

10000000 loops, best of 3: 0.11 usec per loop

mymin = operator.add

10000000 loops, best of 3: 0.0657 usec per loop

¿Qué significa esto? Significa que casi todo el costo está en llamar a la función. El CPython físico más rápido que puede ir aquí es de 0.066 usec por bucle, que se puede add .

Tu función min en C va a tener

• menos gastos generales porque no trata con argumentos arbitrarios y cmp , pero

• más sobrecarga porque genera un nuevo entero, en lugar de simplemente devolver el anterior. PyArg_ParseTuple probablemente tampoco es rápido.

Las instrucciones reales de C para comparación o cambio de bits no son rentables . Están libres. La ley de Amdahl se está riendo de ti.

Mientras tanto, PyPy toma aproximadamente 0,0003 usec por llamada a min , o 200 veces menos. Evidentemente, las instrucciones en C son al menos tan baratas, ya que se compilan con un buen código de máquina.

Tal vez lo ponga de otra manera ...

¿Qué es más caro que una sucursal o comparación?

• Asignación, lo que Python hace para asignar el marco de la función y para asignar la tupla para almacenar los argumentos en.

• Análisis de cadenas, que hace PyArg_ParseTuple .

• varargs, también utilizado por PyArg_ParseTuple .

• PyLong_FromLong tablas, que realiza PyLong_FromLong .

• goto s goto , realizado por el envío interno del código de bytes de CPython (y creo que 2.7 usa una instrucción switch , que es incluso más lenta).

El cuerpo de min , implementado en C, no es el problema.

Answer 2

Benchmarking es un arte tanto como una ciencia. Dejando a un lado los detalles técnicos de los diversos idiomas y sus implementaciones internas, la declaración que se medirá se llama una vez en una llamada de función en un ejemplo, y dentro de un bucle for en el otro ejemplo donde hay una referencia de matriz.

La sobrecarga de la llamada a la función y la referencia de la matriz y los bucles exceden ampliamente el tiempo de la función que está tratando de medir. Imagina las docenas de instrucciones requeridas para cada uno. ¡Dentro de esa llamada de bucle / función está intentando medir la velocidad de solo unas pocas instrucciones!

El ejemplo de C es mucho mejor, ya que es mucho menos costoso que el ejemplo de Python y se compila y el código de máquina se analiza cuidadosamente. Puede especular sobre la velocidad de ese código de máquina, pero para medirlo realmente necesita un punto de referencia mucho más complejo que maximice la ejecución del código que está intentando probar y minimizó las otras instrucciones. ¡Varias optimizaciones del compilador también pueden distorsionar sus tiempos o incluso optimizar partes de lo que cree que está tratando de medir!

Con el ejemplo de C, para cada iteración, la sobrecarga del bucle es de 4 instrucciones, y lo que está tratando de medir es la velocidad de 1 o 2 instrucciones según los valores. ¡Eso es muy difícil de hacer!

Sin mencionar que está utilizando el tiempo transcurrido como medida e incluso en un sistema "inactivo", hay muchas interrupciones aleatorias, fallas de página y otras actividades para distorsionar los tiempos. Tiene una gran variedad en la que se puede instalar un error. Una operación podría ser más rápida en una máquina CISC que en una máquina RISC, aunque supongo que está hablando de máquinas de clase x86.

Sé que esto no responde a la pregunta, es más un análisis de los métodos de evaluación comparativa utilizados y cómo afectan a obtener una respuesta cuantificable real.

Answer 3

Bueno, el truco de pirateo de bits podría haber sido más rápido en los años 90, pero es más lento en las máquinas actuales por un factor de dos. Compara por ti mismo:

// gcc -Wall -Wextra -std=c11 ./min.c -D_POSIX_SOURCE -Os
// ./a.out 42

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define COUNT (1 << 28)

static int array[COUNT];

int main(int argc, char **argv) {
    (void) argc;
    unsigned seed = atoi(argv[1]);

    for (unsigned i = 0; i < COUNT; ++i) {
        array[i] = rand_r(&seed);
    }

    clock_t begin = clock();

    int x = array[0];
    for (unsigned i = 1; i < COUNT; ++i) {
        int y = array[i];
#if 1
        x = x ^ ((y ^ x) & -(x > y));
# else
        if (y < x) {
            x = y;
        }
#endif
    }

    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    printf("Minimum: %d (%.3f seconds)/n", x, time_spent);
    return 0;
}

En un promedio de 0.277 segundos en la implementación "ingenua", pero 0.442 segundos para la implementación "optimizada". Siempre ten un poco de duda en las clases de CS. Al menos desde la instrucción CMOVxx (agregada con Pentium Pro en 1995) no hay posibilidad de que la solución de pirateo de bits haya sido más rápida.

En un i5-750 (gcc (Debian 5.2.1-23) 5.2.1 20151028):

    optimized naïve
O0  1.367     0.781
O1  0.530     0.274
O2  0.444     0.271
O3  0.442     0.144
Os  0.446     0.273

Pensamiento posterior: los desarrolladores de compiladores son personas muy inteligentes que pasan sus días de trabajo buscando e implementando optimizaciones. Si el truco de pirateo de bits fuera más rápido, entonces su compilador implementaría min() esta manera. Y puede asumir con seguridad que el compilador entiende lo que está haciendo dentro del bucle. Pero las personas que trabajan para Intel, AMD, etc., también son inteligentes, por lo que optimizarán operaciones importantes como min() y max() si ven que los piratas informáticos del compilador hacen piruetas extrañas porque la solución obvia es lenta.

Para el extra curioso: este es el código generado para la implementación "optimizada" con -O3:

    mov    $0x40600b00, %ebp     # int *e = &array[COUNT];
    mov    0x600b00, %ebx        # int x = array[0];
    mov    $0x600b04, %edx       # int *i = &array[1];
loop:
    mov    (%rdx), %eax          # int y = *i;
    xor    %ecx, %ecx            # int tmp = (
    cmp    %ebx, %eax            #     y < x
    setl   %cl                   #   ? 1 : 0 );
    xor    %ebx, %eax            # y ^= x;
    add    $0x4, %rdx            # ++i;
    neg    %ecx                  # tmp = -tmp;
    and    %ecx, %eax            # y &= tmp;
    xor    %eax, %ebx            # x ^= y;
    cmp    %rdx, %rbp            # if (i != e) {
    jne    loop                  #    goto loop; }

Y la implementación ingenua con -Os (-O3 es enorme y está llena de instrucciones SSE que tendría que consultar):

    mov    600ac0, %ebx          # int x = array[0];
    mov    $0x40600abc,%ecx      # int *e = &array[COUNT];
    mov    $0x600ac0,%eax        # int *i = &array[0];
loop:
    mov    0x4(%rax),%edx        # int y = *(i + 1);
    cmp    %edx,%ebx             # if (x > y) {
    cmovg  %edx,%ebx             #    x = y; }
    add    $0x4,%rax             # ++i;
    cmp    %rcx,%rax             # if (i != e) {
    jne    loop                  #    goto loop; }

Answer 4

Esto se debe probablemente a cómo se implementa la función min en python.

Muchas incorporaciones de python en realidad se implementan en lenguajes de bajo nivel como C o ensamblado y utilizan las apis de python para poder ser invocadas en python.

Es probable que su técnica de manipulación de bits sea muy rápida en C, pero en python, la sobrecarga de interpretación de la declaración superará con creces la sobrecarga de llamar incluso una función compleja implementada en un lenguaje de bajo nivel.

Si realmente desea una prueba justa, compare un programa en C, o la extensión Python en C que implementa esa técnica con su llamada a minón de python y vea cómo se compara, espero que eso le explique el resultado que ve.

EDITAR:

Gracias a @ Two-BitAlchemist, ahora puedo dar algunos detalles más sobre razones adicionales por las que este bit no funcionará bien en Python. Parece que los enteros no se almacenan de manera obvia, sino que en realidad son un objeto de expansión bastante complejo diseñado para almacenar números potencialmente muy grandes.

Algunos detalles sobre esto se pueden encontrar here (gracias a Two-BitAlchemist) aunque parece que esto se ha modificado un poco en las versiones más nuevas de python. Aún queda el punto de que ciertamente no estamos manipulando un simple conjunto de bits cuando tocamos un entero en python, sino un objeto complejo donde las manipulaciones de bits son en realidad llamadas a métodos virtuales con una sobrecarga enorme (en comparación con lo que hacen).

Answer 5

Hagamos una inmersión un poco más profunda aquí para descubrir la verdadera razón detrás de esta rareza (si existe).

Permite crear 3 métodos y ver su código de bytes y tiempos de ejecución de python ...

import dis

def func1(x, y):
    return min(x, y)

def func2(x, y):
    if x < y:
        return x
    return y

def func3(x, y):
    return x ^ ((y ^ x) & -(x > y))

print "*" * 80
dis.dis(func1)
print "*" * 80
dis.dis(func2)
print "*" * 80
dis.dis(func3)

La salida de este programa es ...

*****************************************************
  4           0 LOAD_GLOBAL              0 (min)
              3 LOAD_FAST                0 (x)
              6 LOAD_FAST                1 (y)
              9 CALL_FUNCTION            2
             12 RETURN_VALUE        
*****************************************************
  7           0 LOAD_FAST                0 (x)
              3 LOAD_FAST                1 (y)
              6 COMPARE_OP               0 (<)
              9 POP_JUMP_IF_FALSE       16

  8          12 LOAD_FAST                0 (x)
             15 RETURN_VALUE        

  9     >>   16 LOAD_FAST                1 (y)
             19 RETURN_VALUE        
*****************************************************
 12           0 LOAD_FAST                0 (x)
              3 LOAD_FAST                1 (y)
              6 LOAD_FAST                0 (x)
              9 BINARY_XOR          
             10 LOAD_FAST                0 (x)
             13 LOAD_FAST                1 (y)
             16 COMPARE_OP               4 (>)
             19 UNARY_NEGATIVE      
             20 BINARY_AND          
             21 BINARY_XOR          
             22 RETURN_VALUE        

Aquí están los tiempos de ejecución de cada una de estas funciones.

%timeit func1(4343,434234)
1000000 loops, best of 3: 282 ns per loop

%timeit func2(23432, 3243424)
10000000 loops, best of 3: 137 ns per loop

%timeit func3(928473, 943294)
1000000 loops, best of 3: 246 ns per loop

func2 es el más rápido porque tiene la menor cantidad de trabajo que hacer en el intérprete de python. ¿Cómo?. Al observar el código de bytes de func2, vemos que en cualquiera de los casos de x > y o x < y , el intérprete de python ejecutará 6 instrucciones.

func3 ejecutará 11 instrucciones (y, por lo tanto, es casi el doble de lento que func2 ... de hecho, es extremadamente cercano a 137.0 * 11/6 = 251 ns).

func1 tiene solo 5 instrucciones de python, y por la lógica de los 2 puntos anteriores, podríamos pensar que func1 probablemente debería ser el más rápido. Sin embargo, hay una CALL_FUNCTION ahí ... y las llamadas a funciones tienen una gran sobrecarga en Python (porque crea un nuevo marco de evaluación para la llamada de función; eso es lo que vemos en el seguimiento de pila de python: una pila de marcos de evaluación ).

Más detalles: como la interpretación de python, cada instrucción de bytecode de python toma mucho más tiempo que una sola instrucción C / asm. De hecho, puede echar un vistazo al código fuente del intérprete de python para ver que cada instrucción tiene una sobrecarga de aproximadamente 30 declaraciones C (esto se debe a un aspecto muy general del bucle del intérprete principal de ceval.c python). El bucle for (;;) ejecuta una instrucción de python por ciclo de bucle (ignorando las optimizaciones).

https://github.com/python/cpython/blob/master/Python/ceval.c#L1221

Por lo tanto, con tanta sobrecarga para cada instrucción, no tiene sentido comparar 2 pequeños fragmentos de código C en Python. Uno tomará 34 y el otro tomará 32 ciclos de CPU, porque el intérprete de python agrega 30 ciclos de sobrecarga para cada instrucción.

En el módulo C de OP, si hacemos un bucle dentro de la función C para hacer la comparación un millón de veces, ese bucle no tendrá la sobrecarga del intérprete de python para cada instrucción. Probablemente se ejecutará de 30 a 40 veces más rápido.

Consejos para la optimización de Python ...

Haga un perfil de su código para encontrar puntos de acceso, refactorice el código de acceso directo en su propia función (escriba pruebas de punto de acceso antes para asegurarse de que el refactorizador no rompa cosas), evite las llamadas de función del código de acceso directo (funciones en línea si es posible), use el módulo dis en nueva función para encontrar maneras de reducir el número de instrucciones de Python ( if x es más rápido que if x is True ... ¿sorprendido?), y, por último, modifique su algoritmo. Finalmente, si la aceleración de Python no es suficiente, vuelva a implementar su nueva función en C.

ps: La explicación anterior se simplifica para mantener la respuesta dentro de un tamaño razonable. Por ejemplo, no todas las instrucciones de Python toman la misma cantidad de tiempo, y hay optimizaciones, por lo que no todas las instrucciones tienen la misma sobrecarga ... y muchas más cosas. Por favor ignore tales omisiones por el bien de la brevedad.

Answer 6

Hice algo como esto here hace unos días. Siguió después de ejemplos más obvios donde los saltos (mal predichos) estaban matando el rendimiento.

Cada operación [en el algoritmo de Stein] es muy simple: pruebe el bit menos significativo, cambie un bit a la derecha, incremente un int . ¡Pero la rama es un asesino!

Con un núcleo de procesamiento súper escalar altamente segmentado moderno, una rama condicional rompe la tubería. Los procesadores x86 utilizan la predicción de bifurcación y la ejecución especulativa para mitigar esto, pero aquí la decisión de bifurcación es esencialmente aleatoria en cada iteración. Se adivina mal la mitad del tiempo.

⋮

Pero todavía me queda un truco más. if (n>m) std::swap (n, m); es un punto de bifurcación, y tomará de una u otra forma varias veces mientras se desplaza. Es decir, esta es otra rama "mala".

Reemplazar una rama condicional con manipulaciones de bits no ramificadas (explicadas en la publicación; ejemplo más claro que el OP) dio como resultado una aceleración mensurable del código. Este es un resultado diferente al observado en otra respuesta, por lo que mi forma "moderna" podría funcionar mejor, y no es solo un mínimo, sino que tanto el mínimo como el máximo se necesitan simultáneamente, por lo que se necesitan más asignaciones incluso en la implementación regular.

El resultado indica que todo este uso de matemáticas y registros es más barato que la bifurcación: 44 se convierte en 39 o 37, 84 se convierte en 75. Esto es aproximadamente un 11% de aceleración en el algoritmo general .

Answer 7

La forma en que estás midiendo es defectuosa.

timeit es realmente complicado de usar. Cuando escribes esto en la línea de comandos:

$ python -m timeit "min(4, 5)"
10000000 loops, best of 3: 0.143 usec per loop

python con mucho gusto le dirá que tomó 0.143 usec por bucle.

$python -m timeit "any([0,3])"
10000000 loops, best of 3: 0.157 usec per loop

Hm, raro, tiempo de ejecución muy similar.

Ipython arrojará algo de luz:

In [3]: %timeit any([0,3])
The slowest run took 17.13 times longer than the fastest. This could mean that an intermediate result is being cached
10000000 loops, best of 3: 167 ns per loop

Ah, las cosas están siendo cacheadas.

In [1]: %timeit min(4,5)
The slowest run took 18.31 times longer than the fastest. This could mean that an intermediate result is being cached
10000000 loops, best of 3: 156 ns per loop

In [4]: %timeit 4 ^ ((5 ^ 4) & -(4 > 5))
The slowest run took 19.02 times longer than the fastest. This could mean that an intermediate result is being cached
10000000 loops, best of 3: 100 ns per loop

Probé muchas cosas, pero no puedo deshacerme del almacenamiento en caché. No sé cómo medir este código correctamente.