Imagen - www.freepik.com
Hace varios años pensé y escribí mucho sobre matemáticas de coma flotante. Fue muy interesante, y en el proceso de investigación, aprendí mucho, pero a veces durante mucho tiempo no usé en la práctica todas estas habilidades que recibieron un trabajo pesado. Por lo tanto, estoy muy contento cada vez que tengo que trabajar en un error que requiere varios conocimientos especializados. En este artículo, contaré tres historias sobre errores de punto flotante que aprendí en Chromium.
Parte 1: expectativas poco realistas
El error se llamaba "JSON no analiza correctamente los enteros de 64 bits"; Al principio no parece un problema de punto flotante o navegador, pero se publicó en crbug.com, así que me pidieron que lo echara un vistazo. La forma más fácil de recrearlo es abriendo las herramientas de desarrollador de Chrome (F12 o Ctrl + Shift + I) y pegando el siguiente código en la consola de desarrollador:
json = JSON.parse(‘{“x”: 2940078943461317278}’); alert(json[‘x’]);Insertar código desconocido en la ventana de la consola es una excelente manera de ser pirateado, pero el código era tan simple que pude descubrir que no era malicioso. En el informe de error, el autor indicó amablemente sus expectativas y resultados reales:
¿Cuál es el comportamiento esperado? Se debe devolver un valor entero de 2940078943461317278. ¿
Cuál es el error? En su lugar, se devuelve un número entero 2940078943461317000.
El "error" se encontró en Linux, y estoy trabajando en Chrome para Windows, pero este comportamiento es multiplataforma y tenía conocimiento de los números de coma flotante, así que lo investigué.
Este comportamiento de los enteros es potencialmente un error de punto flotante, porque en realidad no hay ningún tipo de entero en JavaScript. Y por la misma razón, esto no es un error.
El número ingresado es bastante grande, es aproximadamente igual a 2.9e18. Y ese es el problema. Dado que JavaScript no tiene un tipo de entero, utiliza la doble precisión de punto flotante IEEE-754 para los números . Este formato de punto flotante binario tiene un bit de signo, un exponente de 11 bits y una mantisa de 53 bits (sí, es de 65 bits, un bit está oculto por arte de magia). Este tipo doble es tan bueno para almacenar enteros que muchos programadores de JavaScript nunca se dieron cuenta de que no había ningún tipo de entero. Sin embargo, un gran número destruye esta ilusión.
El número de JavaScript puede almacenar cualquier valor entero hasta 2 ^ 53 con precisión. Después de eso, puede almacenar todos los números pares hasta 2 ^ 54. Después de eso, puede almacenar todos los múltiplos de cuatro números hasta 2 ^ 55, y así sucesivamente.
El número del problema se expresa en notación exponencial de base 2, que es aproximadamente 1.275 * 2 ^ 61. En este intervalo solo se puede expresar un número muy pequeño de números enteros; la distancia entre los números es 512. Aquí están los tres números correspondientes:
- 2940 07894 43461317278 es el número que el autor del informe de error quería conservar
- 2940 0789 43 461317120 - el doble más cercano a este número (menor que él)
- 2940 07894 461 317 632 - el siguiente más cercano al número doble (mayor que él)
El número que necesitamos está en el intervalo entre estos dos dobles y el módulo JSON (por ejemplo, JavaScript mismo o cualquier otra función implementada correctamente para convertir texto a doble) hizo su mejor esfuerzo y devolvió el doble más cercano. En pocas palabras, el número que el autor del informe quería guardar no se puede almacenar en el tipo numérico de JavaScript integrado .
Hasta ahora, todo está claro: si alcanzas los límites del idioma, entonces necesitas saber más sobre cómo funciona. Pero aún queda un misterio más. El informe de error dice que, de hecho, se devuelve el siguiente número:
2940 078943461317 000
La situación es curiosa, porque este no es un número ingresado, ni el doble más cercano y, de hecho, ¡ni siquiera un número que pueda representarse como un doble!
Este rompecabezas también se explica por la especificación de JavaScript. La especificación dice que cuando se imprime un número, una implementación debe generar una cantidad suficiente de dígitos para identificarlo de manera única, y nada más. Esto es útil para imprimir números como 0.1, que no se pueden representar con precisión como un doble. Por ejemplo, si JavaScript requiere que 0.1 se genere como un valor almacenado, entonces generaría:
0.1000000000000000055511151231257827021181583404541015625
Sería un resultado preciso , pero confundiría a las personas al no agregar nada útil. Las reglas específicas se pueden encontrar aquí (busque la línea "ToString aplicado al tipo de número"). No creo que la especificación requiera ceros finales, pero ciertamente lo hace.
Entonces, cuando se ejecuta el programa, JavaScript genera 2,940,078,943,461,317,000 porque:
- El valor del número original se perdió cuando se guardó como número de JavaScript
- El número mostrado está lo suficientemente cerca del valor almacenado para identificarlo de manera única
- El número mostrado es el número más simple que identifica de forma única el valor almacenado
Todo funciona como debería, esto no es un error, el problema está cerrado como WontFix ("irrecuperable"). El error original se puede encontrar aquí .
Parte 2: épsilon malo
Esta vez, de hecho, solucioné el error, primero en Chromium y luego en googletest, para evitar confusiones para las generaciones futuras de desarrolladores.
Este error fue un error de prueba no determinista que comenzó a ocurrir de repente. Odiamos estos errores de prueba borrosos. Son especialmente confusos cuando comienzan a ocurrir en una prueba que no ha cambiado en años. Unas semanas más tarde, me llevaron a investigar. Los mensajes de error (ligeramente modificados para la longitud de las líneas) comenzaron así:
La diferencia entre esperados_microsegundos y convertidos_microsegundos es 512, que supera 1,0 [La diferencia entre esperados_microsegundos y convertidos_microsegundos es 512, que supera 1,0]
Sí, eso suena mal. Este es un mensaje de error de Googletest que dice que dos valores de punto flotante que no deberían estar separados por más de 1.0 en realidad están separados por 512. La
primera evidencia fue la diferencia entre números de punto flotante. Parecía muy sospechoso que los dos números estuvieran separados exactamente por 2 ^ 9. ¿Coincidencia? No lo creo. El resto de la publicación, que indicaba los dos valores que se estaban comparando, me convenció aún más del motivo:
esperados_microsegundos se evalúa como 4.2934311416234112e + 18,
convertido_microsegundos se evalúa como 4.2934311416234107e + 18
Si ha luchado con IEEE 754 el tiempo suficiente , comprenderá inmediatamente lo que está sucediendo.
Has leído la primera parte, así que puedes sentir un déjà vu debido a los mismos números. Sin embargo, esto es pura coincidencia, solo uso los números que encontré. En esta ocasión se mostraron en formato exponencial, lo que hace que el artículo sea un poco diversificado.
El problema principal es una variación del problema de la primera parte: los números de coma flotante en las computadoras son diferentes de los números reales utilizados por los matemáticos. Se vuelven menos precisos a medida que aumentan, y todos los dobles eran necesariamente múltiplos de 512 en el rango de números fallidos. El doble tiene 53 bits de precisión, y estos números eran mucho mayores que 2 ^ 53, por lo que una reducción significativa en la precisión era inevitable. Y ahora podemos entender el problema.
La prueba calculó el mismo valor de dos formas diferentes. Luego verificó si los resultados estaban cerca, con "cercanía" significando una diferencia dentro de 1.0. Los métodos de cálculo dieron respuestas muy similares, por lo que en la mayoría de los casos los resultados se redondearon al mismo valor con doble precisión. Sin embargo , de vez en cuandola respuesta correcta está al lado de la inflexión, y un cálculo redondea en un sentido y el otro redondea en otro.
Más específicamente, como resultado, se compararon los siguientes números:
- 4293431141623410688
- 4293431141623411200
Sin exponentes, se nota más que están separados exactamente por 512.Los dos resultados infinitamente precisos generados por las funciones de prueba siempre diferían en menos de 1.0, es decir, cuando eran valores como 429 ... 10653.5 y 429 ... 10654.3, ambos se redondearon a 429 ... 10688. El problema se produjo cuando los resultados infinitamente precisos se acercaban a un valor como 4293431141623410944. Este valor está exactamente a la mitad entre dos dobles. Si una función genera 429 ... 10943,9 y la otra 429 ... 10944,1, entonces estos resultados, divididos por un valor de solo 0,2, se redondearon en diferentes direcciones y terminaron en una distancia de 512.
Ésta es la naturaleza de la inflexión o función escalonada. Puede obtener dos resultados, arbitrariamente cercanos entre sí, pero ubicados en lados opuestos de la inflexión, puntos exactamente en el medio entre los dos, y por lo tanto redondeados en diferentes direcciones. A menudo se recomienda cambiar el modo de redondeo, pero esto no ayuda, solo mueve el punto de inflexión.
Es como tener un bebé alrededor de la medianoche: una pequeña desviación puede cambiar permanentemente la fecha (tal vez un año, un siglo o un milenio) del registro del evento.
Quizás mi nota de compromiso fue demasiado dramática, pero infalible. Me sentí como un especialista único capaz de manejar esta situación:
commit 6c2427457b0c5ebaefa5c1a6003117ca8126e7bc
Autor: Bruce Dawson
Fecha: viernes 08 de diciembre 21:58:50 2017
Corregir el cálculo de epsilon para comparaciones grandes-dobles
Toda mi vida ha estado conduciendo a esta corrección de errores. [Toda mi vida me ha llevado a corregir este error].
De hecho, rara vez logro hacer un cambio en Chromium con una nota de confirmación que se vincule razonablemente a dos (2) de mis publicaciones .
La solución en este caso fue calcular la diferencia entre dos dobles vecinos con la magnitud de los valores calculados. Esto se hizo con la función nextafter raramente utilizada . Más o menos así:
epsilon = nextafter(expected, INFINITY) – expected;
if (epsilon < 1.0)
epsilon = 1.0;El nextafter función encuentra el siguiente doble (en este caso, en la dirección del infinito), y la resta (que se realiza exactamente, y esto es muy conveniente) a continuación, busca la diferencia entre los dobles en su valor. El algoritmo probado arrojó un error de 1.0, por lo que épsilon no debería ser mayor que este valor. Este cálculo de épsilon hace que sea muy fácil verificar si los valores están separados por menos de 1.0 o son dobles adyacentes.
No he investigado la razón por la que la prueba de repente comenzó a fallar, pero sospecho que es la frecuencia del temporizador o un cambio en el punto de inicio del temporizador lo que hizo que los números aumentaran.
. QueryPerformanceCounter (QPC), <int64>::max(), 2^63-1. , . , , QPC 2 148 . , QPC, , , , , 3 . QPC 2^63-1 , .
, , QueryPerformanceCounter.
googletest
Me molestó que la comprensión del problema requiriera un conocimiento esotérico de los detalles específicos del punto flotante, así que quería arreglar googletest . Mi primer intento terminó mal.
Originalmente intenté arreglar googletest haciendo que EXPECT_NEAR fallara al transmitir épsilon insignificantemente pequeño, sin embargo, parece que muchas pruebas dentro de Google, y probablemente muchas más fuera de Google, usan incorrectamente EXPECT_NEAR en valores dobles. Pasan un valor épsilon que es demasiado pequeño para ser útil, pero los números que comparan son los mismos, por lo que la prueba tiene éxito. Arreglé una docena de puntos de uso de EXPECT_NEAR sin acercarme a resolver el problema, así que me di por vencido.
No fue hasta que escribí esta publicación (¡casi tres años después de que apareció el error!) Que me di cuenta de lo seguro y fácil que era arreglar googletest. Si el código usa EXPECT_NEAR con muy poca épsilon y la prueba tiene éxito (es decir, los valores son realmente iguales), entonces esto no es un problema. Esto se convierte en un problema solo cuando la prueba falla, por lo que fue suficiente para mí buscar valores de épsilon demasiado pequeños solo en caso de falla y mostrar un mensaje informativo al mismo tiempo.
Hice este cambio y ahora el mensaje de error para este bloqueo de 2017 se ve así:
expected_microseconds converted_microseconds 512,
expected_microseconds 4.2934311416234112e+18,
converted_microseconds evaluates to 4.2934311416234107e+18.
abs_error 1.0, double , 512; EXPECT_NEAR EXPECT_EQUAL. EXPECT_DOUBLE_EQ.
Tenga en cuenta que EXPECT_DOUBLE_EQ en realidad no verifica la igualdad, verifica si los dobles son iguales a cuatro unidades en el último dígito (unidades en el último lugar, ULP). Puede leer más sobre este concepto en mi publicación Comparing Floating Point Numbers .
Espero que la mayoría de los desarrolladores de software vean este nuevo mensaje de error y tomen el camino correcto, y creo que, en última instancia, corregir Googletest es más importante que corregir la prueba de Chromium.
Parte 3: cuando x + y = x (y! = 0)
Esta es otra variación de los problemas de precisión al acercarme a los límites: ¿Quizás encuentro el mismo error de punto flotante una y otra vez?
En esta parte, también describiré las técnicas de depuración que puede aplicar si desea investigar el código fuente de Chromium o investigar la causa del bloqueo.
Cuando me encontré con este problema, publiqué un informe de error titulado " Crash with OOM (Out of Memory) error en chrome: // tracing when zoom in "; esto no es como un error de coma flotante.
Como de costumbre, no estaba buscando problemas por mí mismo, solo estaba estudiando chrome: // tracing, tratando de comprender algunos de los eventos; De repente apareció una pestaña triste: hubo una falla.
Puede ver y descargar los últimos bloqueos de Chrome en chrome: // bloqueos, pero quería cargar el volcado de errores en el depurador, así que miré dónde se almacenan localmente:
% localappdata% \ Google \ Chrome \ User Data \ Crashpad \ reports
Cargué el volcado de caída más reciente en windbg (Visual Studio también lo hará) y luego procedí a investigar. Como tenía configurados los servidores de símbolos de Chrome y Microsoft y habilitado el servidor de origen, el depurador descargó automáticamente el PDB (información de depuración) y los archivos de origen necesarios. Tenga en cuenta que este esquema está disponible para todos: no es necesario ser un empleado de Google o un desarrollador de Chromium para que esta magia funcione. Las instrucciones para configurar la depuración de Chrome / Chromium se pueden encontrar aquí . La descarga automática del código fuente requiere la instalación de Python.
El análisis de fallos mostró que el error de falta de memoria se debe al hecho de que la función v8 (motor JavaScript) NewFixedDoubleArrayintenta asignar una matriz con 75,209,227 elementos, y el tamaño máximo permitido en este contexto es 67,108,863 (0x3FFFFFF en hexadecimal).
Lo bueno de los fallos que yo mismo causé es que puedes intentar recrearlos con un seguimiento más cuidadoso. Los experimentos mostraron que cuando se hizo zoom, la memoria se mantuvo estable hasta que llegué al punto crítico, después de lo cual el uso de la memoria se disparó repentinamente y la pestaña se bloqueó incluso si no hice nada.
El problema aquí era que podía ver fácilmente la pila de llamadas para este error, pero solo en la parte C ++ del código de Chrome. Sin embargo, aparentemente, el error apareció en el código JavaScript de rastreo chrome: //. Intenté probarlo con una compilación canary de Chrome (diariamente) en el depurador y recibí el siguiente mensaje curioso:
==== Seguimiento de pila JS =====================================
Desafortunadamente, no había ningún rastro de pila detrás de esta interesante línea. Después de vagar un poco en la naturaleza de git , descubrí que la capacidad de generar pilas de llamadas JS a través de OOM se agregó en 2015 y luego se eliminó en diciembre de 2019 .
Investigué este error a principios de enero de 2020 (¿recuerdas esos buenos viejos tiempos cuando todo era inocente y más fácil?), Y significó que el código de seguimiento de pila OOM se eliminó de la compilación diaria, pero aún permaneció en un ensamblado estable ...
Por lo tanto, mi siguiente paso fue intentar recrear el error en la versión estable de Chrome. Esto me dio los siguientes resultados (los edité un poco para mayor claridad):
0: ExitFrame [pc: 00007FFDCD887FBD]
1: drawGrid_ [000016011D504859] [chrome: //tracing/tracing.js: ~ 4750]
2: draw [000016011D504821] [chrome: //tracing/tracing.js: 4750]
En resumen, el bloqueo de OOM fue causado por drawGrid_ , que encontré (usando la página de búsqueda de código de Chromium ) en x_axis_track.html. Habiendo modificado un poco este archivo, lo reduje a llamar a updateMajorMarkData . Esta función contiene un bucle que llama a la función majorMarkWorldPositions_.push , que es la culpable del problema.
Vale la pena mencionar aquí que aunque desarrollo un navegador, sigo siendo el peor programador de JavaScript del mundo. La habilidad en la programación de sistemas C ++ no me da la magia del "frontend". Hackear JavaScript para entender este error fue un proceso bastante doloroso para mí.
El bucle (que se puede ver aquí ) se veía así:
for (let curX = firstMajorMark;
curX < viewRWorld;
curX += majorMarkDistanceWorld) {
this.majorMarkWorldPositions_.push(
Math.floor(MAJOR_MARK_ROUNDING_FACTOR * curX) /
MAJOR_MARK_ROUNDING_FACTOR);
}Agregué declaraciones de salida de depuración antes del ciclo y obtuve los datos que se muestran a continuación. Cuando amplié la imagen, los números que eran críticos, pero no suficientes para causar un bloqueo, se veían así:
firstMajorMark: 885.0999999642371 majorMarkDistanceWorld
: 1e-13
Luego hice zoom para causar un bloqueo y obtuve números como este:
firstMajorMark: 885.0999999642371
majorMarkDistanceWorld: 5e-14
885 dividido por 5e-14 es 1.8e16, y la precisión de un número de coma flotante de doble precisión es 2 ^ 53, que es 9.0e15. Por lo tanto, se produce un error cuando majorMarkDistanceWorld (distancia entre puntos de la cuadrícula) es tan pequeño en relación con firstMajorMark (la ubicación de la primera marca de cuadrícula principal) que agregar un bucle ... no hace nada. Es decir, si agregamos un número pequeño a uno grande, entonces cuando el pequeño es "demasiado pequeño", el número grande (en el modo estándar / sano redondeo al modo más cercano) puede permanecer igual al mismo valor.
Debido a esto, el bucle se ejecuta indefinidamente y el comando push se ejecuta hasta que la matriz se limita a su tamaño. Si no hubiera límites de tamaño, el comando push continuaría ejecutándose hasta que toda la máquina se quedara sin memoria. Así que hurra, ¿problema resuelto?
La solución resultó ser bastante simple: no mostrar etiquetas de cuadrícula si no podemos:
if (firstMajorMark / majorMarkDistanceWorld > 1e15) return;
Como suele ser el caso con los cambios que hago, mi corrección de errores consistió en una línea de código y un comentario de seis líneas. Solo me sorprende que no hubiera notas de confirmación de pentámetro yámbico de 50 líneas, notación de notación y publicación de blog. Espere un minuto ...
Desafortunadamente, los marcos de pila de JavaScript todavía no se muestran en los bloqueos de OOM, porque se necesita memoria para escribir pilas de llamadas, lo que significa que no es seguro en esta etapa. No entiendo muy bien cómo investigaría este error hoy, cuando los marcos de pila OOM se eliminaron por completo, pero estoy seguro de que encontraré la manera.
Por lo tanto, si usted es un desarrollador de JavaScript que intenta usar números extremadamente grandes, un escritor de pruebas que intenta usar el valor entero más grande o implementa una interfaz de usuario con zoom ilimitado, entonces es importante recordar que a medida que se acerca a los límites de las matemáticas de punto flotante, esos límites se pueden romper.
Publicidad
Los servidores de desarrollo son épicos de Vdsina.
Usamos unidades NVMe extremadamente rápidas de Intel y no ahorramos en hardware , ¡solo equipos de marca y las soluciones más modernas del mercado!
