solutions problems optimisation mathematical and optimization

problems - optimization or optimisation



¿Cuáles son las optimizaciones más hardcore que has visto? (12)

El " Zen of Assembly Language " de Michael Abrash tuvo algunas cosas ingeniosas, aunque admito que no recuerdo detalles de mi cabeza.

En realidad, parece que todo lo que escribió Abrash contenía algunas cosas ingeniosas de optimización.

No estoy hablando de cosas algorítmicas (por ejemplo, usar quicksort en lugar de bubblesort), y no estoy hablando de cosas simples como desenrollar loop.

Estoy hablando de cosas hardcore . Como Tiny Teensy ELF , The Story of Mel ; prácticamente todo en la demoscene, y así sucesivamente.

El cracker EFF DES , que usó hardware personalizado para generar claves candidatas (el hardware que hicieron podría probar que una clave no es la solución, pero no pudo probar que una clave fuera la solución), que luego se probaron con un código más convencional.

El compilador Stalin Scheme es bastante loco en ese aspecto.

He ido a las referencias de arquitectura Intel (o AMD) para ver qué instrucciones hay. movsx : mover con la extensión de signo es increíble para mover pequeños valores con signo a espacios grandes, por ejemplo, en una instrucción.

Del mismo modo, si sabes que solo usas valores de 16 bits, pero puedes acceder a todos los EAX, EBX, ECX, EDX, etc., entonces tienes 8 ubicaciones muy rápidas para los valores: solo gira los registros en 16 bits para acceder al otro valores.

Una vez vi una declaración de switch con muchas case vacías, un comentario en la parte superior del interruptor decía algo así como:

Se agregaron sentencias de casos que nunca se golpean porque el compilador solo convierte el interruptor en una tabla de saltos si hay más de N casos

Olvidé lo que N era. Esto estaba en el código fuente de Windows que se filtró en 2004 .

Mi favorito es la raíz cuadrada inversa de coma flotante a través de operaciones enteras. Este es un pequeño truco sobre cómo se almacenan los valores de coma flotante y se puede ejecutar más rápido (incluso haciendo un 1 / resultado es más rápido que la función de raíz cuadrada de stock estándar) o producir resultados más precisos que los métodos estándar.

En c / c ++ el código es: (de Wikipedia)

float InvSqrt (float x) { float xhalf = 0.5f*x; int i = *(int*)&x; i = 0x5f3759df - (i>>1); // Now this is what you call a real magic number x = *(float*)&i; x = x*(1.5f - xhalf*x*x); return x; }

Una optimización muy biológica

Antecedentes rápidos: los trillizos de nucleótidos de ADN (A, C, G y T) codifican aminoácidos, que se unen en proteínas, que son las que componen la mayoría de los seres vivos.

Normalmente, cada proteína diferente requiere una secuencia separada de tripletes de ADN (su "gen") para codificar sus aminoácidos, por lo que, por ejemplo, 3 proteínas de longitud 30, 40 y 50 requerirían 90 + 120 + 150 = 360 nucleótidos en total. Sin embargo, en los virus, el espacio es primordial, por lo que algunos virus se superponen a las secuencias de ADN para diferentes genes , utilizando el hecho de que hay 6 posibles "marcos de lectura" para usar para la traducción de ADN a proteína (es decir, comenzar desde una posición que es divisible por 3, desde una posición que divide 3 con el resto 1, o desde una posición que divide 3 con el resto 2, y lo mismo de nuevo, pero leyendo la secuencia en reversa).

Para la comparación: intente escribir un programa de lenguaje ensamblador x86 donde la función de 300 bytes doFoo() comienza en el offset 0x1000 ... y otra función de 200 bytes doBar() comienza en el offset 0x1001! (Propongo un nombre para esta competencia: ¿Eres más inteligente que la Hepatitis B? )

¡Esa es la optimización del espacio hardcore !

ACTUALIZACIÓN: Enlaces a más información:

El empacador FSG 2.0 fabricado por un equipo polaco, específicamente diseñado para empacar ejecutables hechos con ensamblaje. Si el ensamblaje del embalaje no es lo suficientemente impresionante (lo que se supone que es casi tan bajo como sea posible), el cargador que viene con 158 bytes es completamente funcional. Si intenta empaquetar cualquier ensamblador hecho .exe con algo como UPX , arrojará una NotCompressableException hacia usted;)

En un motor de videojuegos (sin nombre) con el que trabajé, habían reescrito la herramienta de exportación de modelos (lo que convierte una malla Maya en algo que carga el juego) para que en lugar de solo emitir datos, realmente emitan la transmisión exacta de microinstrucciones que serían necesarias para representar ese modelo particular. Usó un algoritmo genético para encontrar el que funcionaría en el número mínimo de ciclos. Es decir, el formato de datos para un modelo dado era en realidad una subrutina perfectamente optimizada para representar solo ese modelo. Entonces, dibujar una malla en la pantalla significaba cargarla en la memoria y ramificarse en ella.

(Esto no era para PC, sino para una consola que tenía una unidad vectorial separada y paralela a la CPU).

En los primeros días de DOS cuando usábamos disquetes para todo el transporte de datos también había virus. Una forma común para que los virus infectaran diferentes computadoras fue copiar un gestor de arranque de virus en el sector de arranque de un floppydisc insertado. Cuando el usuario insertó el floppydisc en otra computadora y se reinició sin recordar quitar el disquete, el virus se ejecutó e infectó el disco duro, por lo tanto infectando permanentemente la PC host. Un virus particularmente molesto que me infectó se llamaba "Formulario", para combatir esto escribí un sector de inicio de disquete personalizado que tenía las siguientes características:

  • Valide el sector de arranque del disco duro del host y asegúrese de que no esté infectado.
  • Valide el sector de inicio floppy y asegúrese de que no esté infectado.
  • Código para eliminar el virus del disco duro si estaba infectado.
  • Código para duplicar el sector de inicio del antivirus en otro disquete si se presionó una tecla especial.
  • Código para iniciar el disco duro si todo estaba bien y no se encontraron infecciones.

Esto se hizo en el espacio del programa de un sector de inicio, alrededor de 440 bytes :)

El mayor problema para mis compañeros fueron los mensajes muy crípticos que se muestran porque necesitaba todo el espacio para el código. Era como "FFVD RM?", Que significaba "FindForm Virus Detected, Remove?"

Estaba bastante contento con ese pedazo de código. La optimización fue el tamaño del programa, no la velocidad. Dos optimizaciones bastante diferentes en el ensamblaje.

Hace algunos años, escribí un motor de juego basado en mosaicos para el Apple IIgs en lenguaje ensamblador 65816. Esta era una máquina bastante lenta y la programación "en el metal" es un requisito virtual para lograr un rendimiento aceptable.

Para actualizar rápidamente la pantalla de gráficos, uno tiene que asignar la pila a la pantalla para usar algunas instrucciones especiales que le permiten actualizar 4 píxeles de pantalla en solo 5 ciclos de máquina. Esto no es nada particularmente fantástico y se describe en detalle en IIgs Tech Note # 70 . El núcleo del núcleo duro fue cómo tuve que organizar el código para que sea lo suficientemente flexible como para ser una biblioteca de propósito general sin dejar de mantener la velocidad máxima.

Descompuse la pantalla de gráficos en líneas de escaneo y creé un buffer de código de 246 bytes para insertar los códigos de operación 65816 especializados. Se necesitan 246 bytes porque cada línea de exploración de la pantalla de gráficos tiene 80 palabras de ancho y se requiere 1 palabra adicional en cada extremo para un desplazamiento suave. La instrucción Push Effective Address (PEA) ocupa 3 bytes, por lo que 3 * (80 + 1 + 1) = 246 bytes.

La pantalla de gráficos se representa saltando a una dirección dentro del búfer de código de 246 bytes que corresponde al borde derecho de la pantalla y parcheando en una instrucción BRanch Always (BRA) en el código en la palabra que sigue inmediatamente a la palabra más a la izquierda. La instrucción BRA toma como argumento un desplazamiento de 8 bits firmado, por lo que apenas tiene el rango para saltar fuera del búfer de código.

Incluso esto no es demasiado difícil, pero la verdadera optimización de núcleo duro viene aquí. Mi motor gráfico en realidad admitía dos capas de fondo independientes y mosaicos animados usando diferentes secuencias de código de 3 bytes, dependiendo del modo:

  1. El fondo 1 usa una instrucción Push Effective Address (PEA)
  2. El segundo plano utiliza una instrucción Load Indirect Indexed (LDA ($ 00), y) seguida de un push (PHA)
  3. Los mosaicos animados utilizan una instrucción Load Direct Page Indexed (LDA $ 00, x) seguida de un push (PHA)

La restricción crítica es que los 65816 registros (X e Y) se usan para referenciar datos y no se pueden modificar. Además, el registro directo de la página (D) se establece en función del origen del segundo fondo y no puede modificarse; el registro del banco de datos se establece en el banco de datos que contiene datos de píxeles para el segundo fondo y no se puede cambiar; el puntero de la pila (S) se asigna a la pantalla de gráficos, por lo que no hay posibilidad de saltar a una subrutina y regresar.

Dadas estas restricciones, tuve la necesidad de manejar rápidamente los casos donde una palabra que está a punto de ser empujada a la pila es mixta, es decir, la mitad proviene del Fondo 1 y la mitad del Fondo 2. Mi solución fue cambiar la velocidad de la memoria. Como todos los registros normales estaban en uso, solo tenía el registro del contador de programas (PC) para trabajar. Mi solución fue la siguiente:

  1. Defina un fragmento de código para hacer la mezcla en el mismo banco de programas de 64K que el buffer de código
  2. Crea una copia de este código para cada una de las 82 palabras
  3. Hay una correspondencia 1-1, por lo que el retorno del fragmento de código puede ser una dirección codificada
  4. ¡Hecho! Tenemos una subrutina codificada que no afecta los registros de la CPU.

Aquí están los fragmentos de código reales

code_buff: PEA $0000 ; rightmost word (16-bits = 4 pixels) PEA $0000 ; background 1 PEA $0000 ; background 1 PEA $0000 ; background 1 LDA (72),y ; background 2 PHA LDA (70),y ; background 2 PHA JMP word_68 ; mix the data word_68_rtn: PEA $0000 ; more background 1 ... PEA $0000 BRA *+40 ; patched exit code ... word_68: LDA (68),y ; load data for background 2 AND #$00FF ; mask ORA #$AB00 ; blend with data from background 1 PHA JMP word_68_rtn ; jump back word_66: LDA (66),y ...

El resultado final fue un blitter casi óptimo que tiene una sobrecarga mínima y genera más de 15 fotogramas por segundo a 320x200 en una CPU de 2,5 MHz con un bus de memoria de 1 MB / s.

Una vez escribí una búsqueda de clave RC5 de fuerza bruta que procesaba dos claves a la vez, la primera clave usaba la tubería entera, la segunda clave usaba las tuberías SSE y las dos se intercalaban en el nivel de instrucción. Esto se combinó con un programa supervisor que ejecutó una instancia del código en cada núcleo del sistema. En total, el código corrió unas 25 veces más rápido que una versión C ingenua.