4 mil millones de sentencias if

 (andreasjhkarlsson.github.io)
3 puntos por GN⁺ 2023-12-29 | 1 comentarios | Compartir por WhatsApp
  • Una idea juguetona de resolver la detección de números pares/impares solo enumerando comparaciones, sin usar %, se fue ampliando de 8 bits a 32 bits y terminó mostrando los límites del compilador y del formato de ejecutable
  • Al generar automáticamente if (number == n) con un generador en Python, los rangos de 8 y 16 bits funcionaron, pero en 32 bits la cantidad de comparaciones explotó hasta aprox. 4.2 mil millones
  • La versión en C de 32 bits produjo, tras 48 horas, un archivo C de 330GB aprox., y MSVC no pudo compilarlo por el límite de números de línea y falta de espacio en heap
  • Para esquivar la restricción de 4GB de los ejecutables PE, se generaron directamente instrucciones x86-64 y se creó un binario de 40GB, isEven.bin, que luego se invocó como código ejecutable mediante memory mapping en Windows
  • El programa final, tras cambiar atoi por strtoul, pudo clasificar correctamente también valores grandes de 32 bits, y para entradas grandes devolvía el resultado en unos 10 segundos en un equipo con Core i5 12600K, 32GB de memoria y SSD M.2

Determinar si un número es par o impar usando solo comparaciones

  • El punto de partida fue una captura de código vista en redes sociales, con una forma de resolver el clásico problema de determinar si un número es par o impar sin usar la operación modulus
  • La estructura consistía en poner if (number == n) para cada número y mostrar con printf si ese número era par o impar
  • El primer ejemplo en C usaba uint8_t number = atoi(argv[1]); y escribía manualmente comparaciones del 0 al 10
  • Se compiló con /Od para desactivar optimizaciones y evitar que el compilador cambiara el algoritmo
    • 0, 4 daban even
    • 3, 7 daban odd
    • 50, 11, 99 no mostraban nada
  • La causa era que después del último if ya no había más comparaciones que procesar, así que hacían falta más sentencias if

Generar sentencias if con Python

  • En vez de escribir todas las comparaciones a mano, se usó un enfoque de metaprogramación en el que Python imprimía el código C
  • El script de Python generaba comparaciones de 0 a 255 con for i in range(2**8)
    • Si i % 2 == 0, emitía printf("even\n");
    • Si no, printf("odd\n");
  • El programa C generado funcionó en todo el rango de 8 bits
    • 99 daba odd
    • 50 daba even
    • 240 daba even
    • 241 daba odd

Hasta 16 bits, compilar en C sí funcionó

  • El mismo enfoque se extendió a uint16_t y range(2**16)
  • El archivo C generado tenía unas 130 mil líneas
  • Tras compilarlo con MSVC, funcionó correctamente con varios valores
    • 21000 daba even
    • 3475 daba odd
    • 3 daba odd
    • 65001 daba odd
    • 65532 daba even
  • El ejecutable pesaba unos 2MB, y en una PC con 31.8GB de memoria eso no causó problemas

El archivo C de 32 bits y los límites del compilador

  • El siguiente objetivo fue procesar todo el rango de 32 bits con comparaciones usando uint32_t y range(2**32)
  • En 32 bits hay 65,536 veces más números que en 16 bits
  • Tras ejecutar el generador de Python durante 48 horas, se obtuvo un archivo C de 330GB aprox.
  • La compilación con MSVC pronto chocó con sus límites
    • warning C4049: el compilador alcanzó el límite de números de línea y dejó de emitir line numbers
    • el límite de números de línea era 16777215
    • fatal error C1060: compiler is out of heap space
  • El formato Portable Executable (.exe) de Windows también tiene la restricción de que cuesta superar los 4GB, así que la ruta de compilar en C un ejecutable con más de 4 mil millones de comparaciones quedó bloqueada
  • Como referencia, se mencionó la restricción relacionada de tamaño máximo de un archivo PE

Generar y ejecutar código máquina directamente

  • Para evitar los límites del compilador y del formato de ejecutable, se cambió a un método que escribía directamente instrucciones x86-64 en un binario
  • La función objetivo tenía forma de IsEven, recibiendo el argumento en ECX y devolviendo el resultado en EAX
    • XOR EAX, EAX fijaba el valor de retorno por defecto en 0 para impar
    • Para cada número se emitía CMP ECX, i
    • Si era par, hacía INC EAX y luego RET
    • Si era impar, hacía directamente RET
  • Se usaron x86-64 assembly y opcode, y los opcodes de cada instrucción se consultaron con ChatGPT
  • El script de Python abría isEven.bin en binario y escribía instrucciones de comparación para todos los números desde 0 hasta 2**32 - 1
  • El isEven.bin generado pesaba unos 40GB e incluía aprox. 4.2 mil millones de comparaciones necesarias para cubrir todos los números de 32 bits

Invocar 40GB de código con memory mapping en Windows

  • El programa anfitrión en C abría isEven.bin y, en vez de leer el archivo completo, lo mapeaba en memoria usando la API de Windows
  • El flujo de ejecución era el siguiente
    • Abrir isEven.bin con CreateFileA usando permisos GENERIC_READ | GENERIC_EXECUTE
    • Comprobar el tamaño de archivo de 64 bits con GetFileSizeEx
    • Especificar PAGE_EXECUTE_READ en CreateFileMapping
    • Crear un mapeo legible y ejecutable con MapViewOfFile
    • Convertir el puntero mapeado a un puntero de función int (*isEven)(int) e invocarlo
  • Este método permite tratar el archivo de 40GB como si ya estuviera en memoria, dejando al sistema operativo la colocación real mediante memoria virtual
  • En la primera prueba casi todo funcionó bien, pero 4200000000 devolvía odd, así que apareció un resultado incorrecto
  • La causa fue que atoi no manejaba correctamente valores unsigned grandes, y al cambiarlo por strtoul(argv[1], NULL, 10), 4200000000 pasó a dar even y 4200000001, odd

Observaciones de rendimiento

  • Los números pequeños devolvían resultado de inmediato, y hasta los valores grandes cercanos al límite de 2^32 respondían en unos 10 segundos
  • El entorno de prueba era un Core i5 12600K, 32GB de memoria y un SSD M.2
  • La velocidad máxima de lectura del SSD observada durante el cálculo fue de aprox. 800MB/s
  • Sigue siendo llamativo que se obtuviera ese nivel de rendimiento incluso en una situación donde había que leer 40GB desde disco, mapearlos a memoria física y el CPU apenas podía aprovechar beneficios de caché

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-12-29
Opiniones de Hacker News

  • Ojalá todavía tuviera uno de los primeros programas que escribí. En 1996, cuando tenía 16 años, vi la sección de gráficos por computadora en el apéndice de un libro de álgebra lineal y, con lo que había aprendido de programación el semestre anterior, me obsesioné con un programa que dibujaba wireframes rotativos de algunas figuras.
    Por eso casi repruebo la clase, pero en ese momento todavía no conocía los arrays, así que todos los vértices y elementos de la matriz de rotación eran variables hardcodeadas por separado, y para la multiplicación de matrices también tenía que copiar y pegar una larga lista de cálculos para cada vértice y modificarla, sin usar bucles.
    Para dibujar en pantalla había que escribir en memoria a partir de cierta dirección, así que sí sabía de punteros, y también tenía un bucle para rasterizar las líneas entre vértices. En definitiva, ya tenía el concepto de arrays e indexación, pero no sabía crearlos yo mismo.

    • A mí me pasó algo parecido. Alrededor de los 12 años intenté hacer un juego de Pac-Man en BASIC y me quedé bloqueado pensando que tenía que escribir por separado la lógica de los 4 fantasmas, desde (x1,y1) hasta (x4,y4).
      Le dije a mi padre que quería usar algo como xn, yn dentro de un bucle for, donde n indicara de qué fantasma se trataba, y él sacó un libro de BASIC y me mostró que x(n) realmente existía.
      Me acuerdo de esto cuando se habla de educación. Los conceptos abstractos se entienden mejor cuando el estudiante tiene una necesidad real; algo que puede sonar confuso aunque lo expliques todo el día encaja en segundos o minutos si resuelve su propio problema.
    • La solución obvia es usar la parte inferior de la pantalla como memoria de trabajo mientras se dibuja la parte superior. Para cuando llegue abajo ya casi no quedarán cálculos por hacer, y como usa memoria rápida de la GPU, se siente muy CUDA y muy IA.
    • Me recuerda a mis primeros tiempos como freelancer. Lo único que tenía era un VPS pequeño con PHP, y tenía que procesar hojas de cálculo de 5.000 a 10.000 filas, que para 2002/2003 eran bastante grandes.
      Como no venía de ciencias de la computación, leía el archivo de la forma más tonta posible, y por los bucles anidados seguía teniendo errores de uso de memoria y falta de espacio. Así que puse $variable = null en todos los lugares posibles, y de verdad funcionó.
    • Mi éxito de secundaria, Snake para TI-83, también era parecido. Guardaba las coordenadas x, y de cada segmento de la serpiente en variables separadas, y como en TI-83 BASIC había un número limitado de variables disponibles, la serpiente no podía crecer más allá de eso.
    • Después de aprender por mi cuenta print, input, if y goto leyendo la documentación, la primera función de GWBasic que aprendí pidiéndole ayuda a otra persona fue chain.

  • Parece demasiado sobreingenierizado. No entiendo por qué llegar a generar código; se puede resolver con un simple bucle for.
    En isOdd, basta con alternar odd = !odd desde 0 hasta n y luego devolverlo.
    Enlace al Playground: https://go.dev/play/p/8TIfzGrdWDF
    Todavía no hice profiling, pero por intuición y experiencia en la industria, esto es rápido.

    • Una implementación de verdadera calidad de producción siempre debería usar recursión. Si n == 0, devuelve false; si es positivo, devuelve !isOdd(n-1); si es negativo, devuelve !isOdd(n+1).
    • Se puede confirmar que esta versión en Rust es rápida.
      El ensamblador sale como testq %rdi, %rdi, setg %al, andb %dil, %al, retq.
      Puedes ver el ensamblador haciendo clic en ... junto a build: https://play.rust-lang.org/?version=stable&mode=release&edit...
      Lamentablemente, parece que Go Playground no soporta salida de ensamblador.
    • No hay que olvidar la función par. isEven(n int64) bool { return !isOdd(n) }
    • Si n = infinito, va a iterar infinitamente.
    • Se puede mejorar con recursión de cola.

  • Este enfoque encaja perfecto con el paquete npm is-even[1], que tiene 196,023 descargas semanales, o con el paquete npm is-odd[2], que tiene 285,501. Sería genial escribir npm install y que empezara a bajar un is-even de 40 GB y un is-odd de 40 GB
    [1] https://www.npmjs.com/package/is-even
    [2] https://www.npmjs.com/package/is-odd

    • Siempre vale la pena mencionar que estos paquetes son el resultado de un spammer dedicado de npm[1] que intentó meterse en la mayor cantidad posible de directorios node_modules
      ansi-colors tampoco es un solo paquete con todos los colores, sino que tiene paquetes por color, además de un montón de cosas más. Como estas cosas se cuelan en herramientas CLI o paquetes que parecen razonables y se referencian entre sí, incluso un proyecto real puede terminar arrastrando decenas de paquetes de jonschlinkert con una sola dependencia aparentemente inofensiva
      [1] https://www.npmjs.com/~jonschlinkert
    • Sorprendentemente, como resultado de seguir “no te repitas” en su forma más pura, is-even depende de is-odd
      Después de var isOdd = require('is-odd');, todo lo que hay es module.exports = function isEven(i) { return !isOdd(i); };
    • Esta persona no lo sabía, pero al revisar los árboles de código fuente de 2 de nuestras apps frontend, el paquete is-number del que depende is-odd estaba siendo traído por bastantes otros paquetes
      Si en JS realmente fuera engorroso determinar si un valor es de tipo número, este paquete podría tener sentido, pero pensaría que existe algún paquete más general que también maneje otros tipos incorporados
      Eso sí, isNumber también trata como números las cadenas que pueden convertirse a número, lo que puede producir resultados raros. Por ejemplo, const a = '1'; isNumber(a); // true, pero const b = a + a; termina siendo la cadena '11'
      Claro que 2*a se vuelve 2, y 1+'1' y '1'+1 se vuelven ambos '11', que es la tontería estándar de JS, pero por eso la respuesta de que '1' es un número puede no ser correcta. Aun así, este paquete se descargó 46 millones de veces la semana pasada, y solo fue bajo por Navidad; las semanas anteriores promediaban unos 70 millones. Como en nuestro proyecto, la mayoría probablemente son dependencias
    • Una vez hice el paquete nullll[1], que solo exporta un null pero usa 400 MB de memoria, y por alguna razón fue marcado en HN[2]
      Con 41 estrellas en GitHub y 100% de cobertura de pruebas[3], claramente estaba listo para producción
      [1]: https://github.com/mickael-kerjean/nulll
      [2]: https://news.ycombinator.com/item?id=17072675
      [3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
    • En realidad, los números de JavaScript no son u32 sino f64, así que eso no alcanza. Incluso soportando solo el rango de enteros seguros, es 2⁵⁴, más de 4 millones de veces mayor que 2³²
      El tamaño del código máquina probablemente solo aumentaría unos 4 bytes por rama, es decir, alrededor de un 40%, así que subiría aproximadamente a 224 exbibytes. Y eso si se omiten perezosamente los últimos 10 bits
      Para hacerlo bien quizá habría que multiplicar eso por 1,000, y no he pensado demasiado en los patrones de NaN, así que podría ser un poco menos. Si también se soporta bigint, simplemente podría ser infinito

  • No sé por qué hacerlo así. Para esto precisamente se inventaron las bases de datos. Basta con guardar en una base de datos SQLite el mapeo de números a la clasificación even/odd
    Este enfoque también tiene la ventaja de que no hay que actualizar el programa cada vez que la clasificación de algún número cambia de impar a par

    • Las bases de datos también necesitan mantenimiento y actualizaciones. Mejor montar un contrato de Ethereum y dar incentivos económicos para que otras personas actúen como oráculos y devuelvan siempre la respuesta correcta
    • Esto parece el tipo de datos que debería estar en Wikidata. Así no haría falta tener una base de datos local; bastaría con una solicitud HTTPS rápida
      El único problema podría ser si TLS en sí depende de una función par/impar, pero probablemente no sea así
    • La tabla debería llamarse even_or_odd y tener columnas como is_odd, is_even, is_zero, is_one, is_two, is_three. El 1 se pondría como is_odd,is_one, y el 2 como is_even,is_two
    • Correcto, pero obviamente habría que usar una base de datos XML
      También ayuda a la portabilidad de los datos y permite mantenerlos en un formato legible para humanos cuando haya que revisarlos a mano
    • Elastic Cloud Parity de AWS ya ofrece esto y es mucho más escalable

  • Es uno de los artículos más divertidos que he leído aquí. Debería subir el código fuente en línea para que ChatGPT pueda “entrenarse” con él

    • Entonces sin duda estaría violando su estricta licencia
      /* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/
      Con un código tan elegante, ¿quién podría culparlo?

  • No entiendo el chiste en absoluto. Incluso aceptando a la persona que hizo esto, lo que me confunde son los 1198 votos positivos actuales
    Una tabla de consulta para valores computables no es algo nuevo ni un chiste. Es una solución real de compromiso entre tiempo y memoria, y el autor también lo sabe
    El problema en sí es absurdo, pero muy primitivo, así que no había dudas de que era posible; y no hubo mediciones reales aparte de la observación de que procesó un programa de 40 GB en su propia computadora durante unos 10 segundos
    Entonces, ¿qué aprendimos? ¿Que un archivo exe no puede superar los 4 GB? ¿Que con 2^32 if, el programa ocupa unos 300 GB? No entiendo por qué 1198 personas lo encontraron interesante
    A diferencia de “Hexing the technical interview” o los artículos de SIGBOVIK, esto no parece una locura, sino simplemente algo sin sentido

    • El chiste es que de verdad lo hizo. Durante décadas la gente ha hecho este tipo de bromas, y este loco de verdad lo llevó a cabo
      Era tan extremo que ningún compilador podía manejarlo, ni siquiera los ensambladores conocidos. Así que tuvo que generar directamente el binario en código máquina para que funcionara, y de hecho funciona. Es una locura
    • Es cierto que las tablas de consulta para valores computables no son nuevas, pero si desactivas la optimización, 4 mil millones de sentencias if no se van a compilar como una tabla de consulta
      Cada if se evaluaría en orden para ver si coincide con la entrada, y la salida de que el programa original termina mucho más rápido con números pequeños respalda eso. Es porque los números pequeños están al principio del código
      En cambio, con un switch con 4 mil millones de case, esperaría que se compilara como algún tipo de tabla de consulta. Aunque no sé cómo se vería el código compilado sin optimización cuando el tipo de dato es un entero sin signo
    • A veces la gente hace cosas para causar risa
    • Lo entendí como una parodia de esos posts de blog que satirizan lo inútil que es rebelarse contra la sabiduría convencional. Es un chiste bastante seco

  • Es una tecnología asombrosa. Debería vendérsela a AWS para que la ofrezca como Enterprise-ready AWS EvenOrOdd API a todos los que no saben alojar correctamente un ejecutable de 40 GB
    Con el poder de la nube, este programa sería imparable

    • Tiene toda la pinta de estar esperando convertirse en una función Lambda

  • Me sorprende que nadie haya intervenido sobre el hecho de que el programa “procesó” 40 GB de instrucciones con apenas unos 800 MB/s * 10 segundos de lectura de disco
    Supongo que hay algún caché inteligente a nivel del sistema operativo, pero entonces eso significa que el benchmark con n cercano a 2^32 no se ejecutó correctamente
    O quizá la CPU sea lo bastante inteligente como para saltar por delante de millones de instrucciones

    • Con un “potente equipo gamer con 31.8 GB de memoria”, si el caché del sistema de archivos es más o menos fuerte con escaneos repetidos/secuenciales, en la reejecución solo tendría que leer unos 8 GB
      Al principio pensé que las matemáticas estarían mal, pero haciendo cuentas rápidas parece bastante plausible. Más aún porque todos los números están redondeados de forma vaga, y el valor de entrada tampoco era el máximo absoluto, sino solo un valor alto
    • Parece que era compresión o datos que seguían en RAM. La CPU no puede ponerse inteligente aquí porque no sabe cuáles serán los if futuros
      No sabe si ese código está en orden, si es único, ni siquiera si son instrucciones válidas. En teoría, durante la ejecución del programa se podría cambiar algún if por un bucle infinito. El sistema operativo no lo permitiría, claro
    • También existe la paginación predictiva. El sistema operativo puede adivinar qué página se pedirá a continuación
    • No puede ser por la CPU. En realidad es código mapeado en memoria, y el predictor de saltos no podría provocar fallos de página para traer la siguiente página de código
      Me da mucha curiosidad. El patrón de acceso lineal ayudaría, pero ¿800 MiB/s?
    • Como el programa se carga con mmap, las páginas que no se usan solo ocupan entradas en la tabla de páginas y no se cargan. Lo que realmente se carga son únicamente las páginas a las que se salta directamente. Es un truco elegante

  • El genio visionario Ross van der Gussom ahora es mi criatura mítica favorita

    • Basta con ver Python como una forma de hacer scripting sobre C y saltarse la mayor parte o toda la compilación. Si Python es lento, probablemente lo estás usando mal
      Recomiendo este artículo: https://cerfacs.fr/coop/fortran-vs-python
    • Hice una búsqueda web para ver si “Ross van der Gussom” era un chiste interno, y los 2 primeros resultados eran el artículo original y este comentario padre

  • Todo el texto se siente como una alegoría del desarrollo de LLM. Si lo escribiera un crítico, diría que consiste en gastar recursos enormes y “datos de entrenamiento” para “memorizar” la solución
    Me pregunto si esa era la intención del autor

    • Solo por el título pensé que sería el anuncio de un nuevo modelo 4B, así que probablemente sí
    • Al leer el título esperaba totalmente que fuera un texto sobre LLM
    • Sí. Parece un modelo LLM de 40B ejecutando un bucle for. Esta alegoría se siente como la motivación real del texto, y parece tratar sobre el absurdo que se avecina, no sobre ingeniería