El defecto del fragmento de código de Stack Overflow más copiado de la historia (2019)

 (programming.guide)
3 puntos por GN⁺ 2023-09-28 | 1 comentarios | Compartir por WhatsApp
  • La respuesta de Java humanReadableByteCount, escrita en 2010, fue identificada en un estudio de 2018 como el fragmento de código de Stack Overflow más copiado, pero producía resultados incorrectos en los valores límite del formateo de tamaños en bytes
  • Este código aprovechaba que prefijos como kB, MB y GB son potencias de 1000 o 1024, y elegía la unidad mediante cálculo logarítmico en lugar de un bucle
  • El bug principal era un problema de umbral de redondeo por el que 999,999 bytes se mostraba como "1000.0 kB" en modo SI, cuando según la especificación, si el rango numérico debía ser de 1 a 999.9, lo correcto era "1.0 MB"
  • En valores más grandes también se sumaba la limitación de precisión de punto flotante de double, por lo que la entrada 999,949,999,999,999,999 devolvía 1000.0 PB; para corregirlo hicieron falta cálculo de umbrales, reducción de escala, ajuste del patrón de bits y strictfp
  • El código final maneja negativos y hasta Long.MIN_VALUE, pero perdió la simplicidad original; al copiar código de Stack Overflow también hacen falta pruebas de casos límite y atribución de la fuente

La simplificación que buscaba la respuesta de 2010

  • El problema era dar formato a una cantidad de bytes como una cadena fácil de leer
    • Ejemplo: mostrar 123,456,789 bytes como "123.5 MB"
    • La especificación implícita era que la parte numérica del resultado estuviera entre 1 y 999.9, con el sufijo de tamaño adecuado
  • La respuesta previa usaba un enfoque basado en bucles: recorría EB, PB, TB, GB, MB, kB, B desde la unidad más grande y elegía la primera menor que la cantidad de bytes
  • La nueva respuesta usaba Math.log y Math.pow para reducir bucles y ramas
    • En modo SI, la unidad es 1000
    • En notación binaria, la unidad es 1024
    • El valor exp = log(bytes) / log(unit) se convertía a entero y se usaba como índice del prefijo
    • Los prefijos eran "kMGTPE" en SI y "KMGTPE" en binario, agregando "i" en el caso binario

El alcance de la copia y el episodio de OpenJDK

  • El artículo de Sebastian Baltes Usage and Attribution of Stack Overflow Code Snippets in GitHub Projects analiza cómo se usan los fragmentos de código de Stack Overflow en proyectos de GitHub y cómo se atribuye su origen
  • El método consistía en extraer fragmentos de código del volcado de datos de Stack Overflow y compararlos con código de repositorios públicos de GitHub
    • La pregunta central era si se estaba cumpliendo la atribución exigida por la licencia CC BY-SA 3.0 de Stack Overflow
    • El resultado fue que la mayoría de los usuarios no incluía la atribución adecuada
  • La respuesta con ID 3758880 aparecía en la primera posición de la tabla del artículo y en ese momento tenía cientos de miles de vistas y más de 1,000 votos positivos
  • Si buscas humanReadableByteCount en GitHub, aparecen miles de casos de uso, y en un repositorio local puedes comprobarlo con este comando
git grep humanReadableByteCount
  • También se encontró una coincidencia en el repositorio de OpenJDK
    • Ese código no incluía atribución, y la licencia de OpenJDK no era compatible con CC BY-SA 3.0
    • Sebastian Baltes preguntó en la lista de correo de desarrollo de OpenJDK si el código había sido copiado de Stack Overflow hacia OpenJDK o al revés
    • El autor de la respuesta no trabajaba todavía en Oracle cuando se integró ese commit y no contribuyó a ese parche
    • Después se registró un issue y el código fue eliminado

El primer bug: el valor límite con muchos 999

  • Los problemas que parecían sospechosos a primera vista no eran la causa real
    • El valor máximo de long es 2^63 - 1, aproximadamente 9.2 × 10^18, así que no llega a pasar de las unidades posteriores a EB
    • Cuando bytes < unit, el primer if lo maneja, así que exp no llega a ser 0 ni falla charAt(exp - 1)
  • El problema real era el umbral de redondeo
    • La entrada 999,999 bytes se convertía en "1000.0 kB" en modo SI
    • Si la especificación exige que la parte numérica esté entre 1 y 999.9, el resultado correcto es "1.0 MB"
  • En el momento de escribirlo, las 22 respuestas publicadas, incluyendo las que usaban Apache Commons y bibliotecas de Android, tenían este bug o alguna variante
  • La clave de la solución era el umbral que decide cuándo subir exp a la siguiente unidad
    • El punto de cambio de k a M es 999,950, donde el valor ya está más cerca de 1 MB que de 999.9 k
    • El cambio de M a G ocurre en 999,950,000
    • En modo binario, el umbral no es un entero, así que hace falta ceil
if (bytes >= Math.ceil(Math.pow(unit, exp) * (unit - 0.05)))
    exp++;

El segundo bug: el límite de precisión de double

  • Incluso con esa corrección, la entrada 999,949,999,999,999,999 seguía mostrando 1000.0 PB, cuando el resultado correcto era 999.9 PB
  • La causa no era la fórmula matemática en sí, sino el límite de precisión de double
    • En la representación IEEE 754, los valores de punto flotante cercanos a 0 son densos, pero los valores grandes están mucho más espaciados
    • Con double muy grandes, incluso restar Long.MAX_VALUE puede no cambiar el valor
double a = Double.MAX_VALUE;
double b = a - Long.MAX_VALUE;
System.err.println(a == b); // prints true
  • El cálculo problemático aparecía en dos lugares
    • La división realizada en el argumento de String.format
    • El cálculo del umbral para decidir si había que aumentar exp
  • El primer problema se resolvió reduciendo el valor intermedio de bytes a un rango con mejor precisión y ajustando exp
    • La idea es que el resultado final de todos modos se redondea, así que se pueden descartar dígitos menos significativos
if (exp > 4) {
    bytes /= unit;
    exp--;
}
  • En el segundo problema, los bits bajos sí importaban
    • 999,949,99…9 y 999,950,00…0 debían clasificarse con exponentes distintos
    • Había 12 umbrales posibles entre SI y binario, y solo uno producía un resultado incorrecto
    • Ese resultado erróneo se identificó y corrigió mediante un patrón de bits que terminaba en D00
    • Como la corrección dependía del patrón de bits de un resultado específico de punto flotante, se añadió strictfp

Entradas negativas y el código final

  • Como Java no tiene long sin signo, también se añadió manejo para cantidades negativas de bytes
    • Antes, una entrada de -10,000 se mostraba como -10000 B
    • Se introdujo absBytes para que los cálculos relacionados con exp se hicieran sobre el valor absoluto
  • Long.MIN_VALUE requería un tratamiento especial
    • Porque -Long.MIN_VALUE == Long.MIN_VALUE
    • Por eso, si bytes == Long.MIN_VALUE, se usa Long.MAX_VALUE; en los demás casos se usa Math.abs(bytes)
  • La versión final incluye strictfp, corrección de umbrales, manejo de Long.MIN_VALUE y reducción de escala en exponentes grandes
  • El código que buscaba evitar bucles y ramas excesivas terminó siendo más difícil de leer que la versión original después de pulir todos los casos límite
  • Para un código moderno con calidad de producción, puede consultarse este artículo aparte: Formatting byte size to human readable format

La lección que queda para el trabajo real

  • Un fragmento de código de Stack Overflow puede tener bugs, incluso con miles de votos positivos
  • El código copiado necesita, sobre todo, pruebas de casos límite
  • La aritmética de punto flotante es difícil de manejar en valores límite y números grandes
  • Al copiar código, hace falta una atribución adecuada, o eso puede convertirse en un problema real

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-09-28
Opiniones en Hacker News

  • Es interesante que todas las respuestas que usan valores hardcodeados y sentencias if (o while) hacen como máximo 5 comparaciones.
    Si las unidades solo llegan hasta B, KiB, MiB, GiB, TiB y EiB, también se puede resolver con un máximo de 3 sentencias if. Si verificas si es GiB o más, ya sabes que no es B/KiB/MiB, así que gana la búsqueda binaria.
    Incluso si se extiende hasta ZiB y YiB, bastan como máximo 3 comparaciones, mientras que el enfoque hardcodeado llega hasta 7. Si yo lo escribiera, no usaría log/pow/punto flotante porque la probabilidad de equivocarse es demasiado alta; hardcodearía sentencias if, pero usando búsqueda binaria.

    • El enfoque de búsqueda binaria podría ser más lento que simplemente hacer 6 comprobaciones. Es probable que este último tome una sola rama, y como las ramas son muy lentas, conviene mantener el código lo más lineal posible.
    • Depende de la distribución de la entrada. Si los valores pequeños son muy comunes, la búsqueda lineal podría ser mejor.
    • Me parece un pésimo criterio de ingeniería. Una solución simple puede ser revisada fácilmente por tus colegas, las condiciones de borde se ven con claridad y es más fácil comprobar si las pruebas las cubren.
      Con este tipo de código se está haciendo mucho trabajo para usar código más lento, más complejo y más difícil de probar y revisar.

  • (2019) Discusiones anteriores:
    https://news.ycombinator.com/item?id=21693431
    https://news.ycombinator.com/item?id=21698619
    https://news.ycombinator.com/item?id=27533684

  • No lo entiendo. Si hay 7 sufijos, puedes elegir el correcto con búsqueda binaria, y bastan 3 comparaciones. O, si lo haces de forma simple, son solo 6 comparaciones.
    No veo por qué usar log() dos veces, pow() una vez y ceil() sería mejor que el enfoque simple. El bug descrito aquí es un ejemplo perfecto de lo que pasa por querer pasarse de listo.

    • Parece que el autor reconoció que era menos legible y volvió a una forma con loop: https://programming.guide/java/formatting-byte-size-to-human...
      Aun así, como toma en cuenta el bug de redondeo, es un poco mejor que el primer ejemplo de código del artículo original.
    • El autor también dice al principio que en realidad no es mejor que el loop.
      Además, las 6 comparaciones solo ocurren en el valor máximo, y en el uso real parece poco probable. Si la mayoría de los valores están en el rango de B o KB, el enfoque lineal podría ser mejor.

  • Es autopromoción descarada, pero si en vez de copiar de S/O quieres formatear tamaños de forma rápida y precisa en un formato legible para humanos, también puedes usar nuestra biblioteca open source PrettySize. Hay una versión para Rust [0] y otra para .NET [1], y también hace que las operaciones lógicas type-safe sobre tamaños de archivo sean seguras y fáciles.
    El snippet de S/O tiene 4 líneas, pero estas bibliotecas son mucho más completas e incluyen pruebas, opciones de formato de salida, conversiones de tamaño, etc.
    [0]: https://github.com/neosmart/prettysize-rs
    [1]: https://github.com/neosmart/PrettySize.net

    • La cultura de reemplazar una solución de 4 líneas por una biblioteca enorme fue la que produjo left-pad.

  • Es pura curiosidad, pero ¿de verdad hay bastantes desarrolladores que simplemente copian código no confiable de Stack Overflow y lo pegan en sus aplicaciones?
    Es famosa la suposición de que la gente simplemente copia de Stack Overflow, pero hasta ver a alguien hacerlo de verdad, pensaba que era casi un chiste. Yo también uso Stack Overflow como punto de partida cuando resuelvo problemas en áreas que no conozco bien, pero nunca he copiado el código tal cual.
    Normalmente un fragmento de código no hace exactamente solo lo que necesito, así que tengo que revisar la API y construir mi propia solución con base en el enfoque explicado. Especialmente en Python, Stack Overflow muchas veces me ha orientado hacia APIs de nicho útiles.

    • Hace tiempo trabajé con un desarrollador al que nadie podía impedirle copiar código en cuanto veía una respuesta. Ni siquiera leía la pregunta para verificar si era el mismo problema que tenía, y tampoco leía la respuesta.
      Literalmente era Google → clic en el primer enlace de Stack Overflow que aparecía → copiar/pegar el primer bloque de código que veía, y a veces ni siquiera era el mismo lenguaje. Durante la programación en pareja había que quitarle físicamente los dispositivos de entrada. Si le decías que estaba mal, antes de que terminaras de hablar ya estaba pegando el segundo fragmento de código de la página, y era extrañamente rápido.
      Es un caso extremo, pero hay muchos desarrolladores con la mentalidad de “necesito código; Stack Overflow tiene código; ¡resuelto!”, sin pensar en absoluto si es la solución adecuada.
    • Sí, eso pasa, y ocurre más seguido cuanto más se siente como algo fuera del alcance de la parte del programa que me interesa.
      De todos modos siempre usamos código de librerías hecho por desconocidos para las partes de plomería que no nos importan mucho. Si quiero profundizar y entenderlo, probablemente lo escriba yo mismo, pero si quiero que esa parte “simplemente funcione” y seguir avanzando con el proyecto, se convierte en desarrollo guiado por errores del compilador.
    • Casi nunca copio/pego tal cual, por las razones que menciona el autor. En cambio, intento entender la solución y, si hace falta, la transcribo a mano línea por línea hasta comprenderla bien, y desde ahí refactorizo.
      También cambio los nombres de las variables. Muchas veces hay demasiados foo, bar y baz, lo que dificulta la lectura para una persona. Si vuelvo a encontrar el mismo problema, también me resulta más fácil recordar qué hice que si lo hubiera copiado a ciegas.
    • La gente realmente hace eso. Después de ver una cantidad enorme de código y configuraciones TLS incorrectos de Stack Overflow, quedé bastante convencido de que la mayoría de los sistemas funcionan sin validar correctamente los certificados.
    • Probablemente aún no hayas tenido el placer de trabajar en bases de código creadas por veinteañeros de 23 años tomando Adderall.

  • No entiendo por qué usan un logaritmo de punto flotante si lo que necesitan es log 2.
    Si no se me escapa nada, la siguiente expresión da exactamente floor(log2(value)) para valores positivos menores que 2^63 bytes, y es mucho más rápida:
    Long.bitCount( (Long.highestOneBit(value) << 1) - 1) - 1

    • Las unidades “normales” son potencias de 10, así que este método no es correcto.

  • En cuanto vi el fragmento de código, noté la operación log de punto flotante y una división sobre enteros, así que lo descarté mentalmente de inmediato como código demasiado ingenioso y, por eso mismo, inherentemente propenso a errores.

    • Ese es básicamente el punto del artículo.

  • La cadena de conocimiento llega hasta el fondo. Muestra lo difícil que es volver a guardar incluso un pedacito mínimo de conocimiento una vez que se ha sacado.
    Con Stack Exchange perdiendo rápidamente a sus colaboradores activos, me pregunto qué haría falta para corregir esas respuestas de pistolero rápido que después resultan estar equivocadas. Y también qué significa para nuestro conocimiento colectivo que estas respuestas “ligeramente incorrectas” queden cada vez más fijadas en los historiales de búsqueda y, con el tiempo, en la historia de los LLM.

  • Me recuerda al entrenamiento militar básico. Los instructores solían darles a los reclutas, deliberadamente y sin instrucciones, una tarea que nadie sabía hacer, y luego se iban.
    Entonces siempre alguien empezaba de la manera incorrecta, y todos los demás lo seguían.

    • Me pregunto si esto se agrava por la tendencia humana a no querer verse peor que los demás. Puede llevar a que incluso personas inteligentes sigan ideas malas o precipitadas, con resultados absurdos.
      En los pronósticos económicos públicos pasa algo parecido. A quien se equivoca solo mientras los demás aciertan se lo trata con mucha más dureza que a quienes se equivocan junto con todos.
    • ¿Cuál era el objetivo de ese entrenamiento?

  • En este tipo de algoritmos, no necesariamente consideraría los errores de punto flotante como un “defecto”. Si el código define una solución lógica y matemáticamente correcta, para mí eso en sí mismo está “bien”.
    Resolver los errores de punto flotante es un nivel por encima de eso, y es algo que solo se hace cuando realmente importa. Puedo imaginar un lenguaje de programación futuro perfecto en el que los errores de punto flotante no existan y ni siquiera haya que considerarlos; el 99% de mis algoritmos, en ese sentido, están dirigidos a un lenguaje así.