4 mil millones de sentencias if

4 mil millones de sentencias if

• Mientras revisaba recientemente las redes sociales, encontré esta captura de pantalla en un tren.
• Este código es un ejemplo perfecto del intercambio entre tiempo y memoria.
• Quise implementarlo en C para mejorar el rendimiento.

Estructura del código

• Se escribió código en C para determinar si un número es par o impar.
• Se compiló con las optimizaciones desactivadas.
• Funciona correctamente para los números del 0 al 10, pero aparecen problemas con números mayores.

Metaprogramación

• Se usó Python para hacer metaprogramación de sentencias if.
• Se generó un programa que determina si enteros de 8 bits son pares o impares.

Extensión a 16 bits

• Se amplió el programa del mismo modo para enteros de 16 bits.
• Se generó y compiló un archivo C de aproximadamente 130k líneas.

Desafío de 32 bits

• Se intentó ampliar el programa para enteros de 32 bits.
• Se generó un archivo C de 330 GB, pero el compilador falló por falta de espacio en el heap.
• Debido a las limitaciones del formato Portable Executable, no fue posible procesar archivos de más de 4 GB.

Escritura directa de código máquina

• Se escribió directamente la función IsEven en lenguaje ensamblador x86-64.
• Se usó Python para compilar manualmente el código máquina.

Generación del ejecutable

• Se generó un archivo de 40 GB que determina si todos los enteros de 32 bits son pares o impares.
• Se mapeó el archivo en memoria y se ejecutó el código usando un puntero a función.

Corrección final del bug

• Se reemplazó por la función strtoul para resolver el problema al parsear enteros sin signo.
• El programa es muy rápido y devuelve resultados en menos de 10 segundos incluso para números muy grandes.

Opinión de GN⁺

• Importancia: Este artículo ayuda a entender el intercambio entre tiempo y memoria, un concepto básico de la programación. También es un buen caso para mostrar cómo el código no optimizado afecta el rendimiento real.
• Interés: Resulta interesante el proceso de explorar experimentalmente las diferencias de rendimiento entre lenguajes de programación y los límites de los compiladores. En particular, es divertida la comparación entre Python y C en el intento de mejorar el rendimiento.
• Lección: Este artículo muestra que, para resolver problemas complejos, a veces enfoques que parecen ineficientes pueden ser útiles en la práctica. También destaca la importancia de buscar soluciones creativas en ciencias de la computación.

[GN⁺]

Comentarios de Hacker News

• Resumen del primer comentario:

  • Recuerdos sobre el primer programa que escribió en 1996, cuando tenía 16 años.
  • Se obsesionó con un programa que dibujaba wireframes rotando después de ver el apéndice de gráficos por computadora de un libro de álgebra lineal.
  • Como no conocía los arreglos, hardcodeó variables y también configuró cada elemento de la matriz de rotación como variables.
  • Sí conocía los punteros, así que escribía directamente en direcciones de memoria para dibujar en pantalla.

• Resumen del segundo comentario:

  • Presenta un ejemplo que podría resolverse con un simple "for loop" en lugar de un enfoque complejo mediante generación de código.

• Resumen del tercer comentario:

  • Broma sobre los paquetes npm is-even e is-odd.
  • Imagina que al usar npm install se descargaría un paquete de 40 GB.

• Resumen del cuarto comentario:

  • Propone usar una base de datos para clasificar números pares e impares.
  • Mapear números y su clasificación en una base de datos SQLite evitaría tener que actualizar el programa.

• Resumen del quinto comentario:

  • Considera que el artículo es muy divertido.
  • Opina que deberían publicar el código fuente en línea para que ChatGPT pueda aprender de él.

• Resumen del sexto comentario:

  • Propone una idea para una versión distribuida.
  • Cada host verificaría si coincide con su propio nombre de dominio y devolvería el resultado.

• Resumen del séptimo comentario:

  • Sugiere vender esta tecnología a AWS y ofrecerla como la API AWS EvenOrOdd.
  • Opina que el programa sería más potente aprovechando el poder de la nube.

• Resumen del octavo comentario:

  • Se pregunta cómo procesar 40 GB de instrucciones con una velocidad de lectura de disco de 800 MB/s * 10 segundos.
  • Especula que habría smart caching a nivel de sistema operativo o alguna optimización donde la CPU se salte instrucciones.

• Resumen del noveno comentario:

  • Explica una técnica para evitar operaciones costosas usando una tabla de búsqueda.
  • Comparte una experiencia reemplazando la división de enteros de 8 bits por una tabla de búsqueda, con el ejemplo de la biblioteca libdivide.

• Resumen del décimo comentario:

  • Sugiere una optimización usando búsqueda binaria.
  • Hace una broma sobre cómo ejecutar con complejidad temporal O(logN) usando sentencias if-else anidadas.