gratis - habilitar javascript en chrome en windows
¿Qué hace que este sea el JavaScript más rápido para imprimir de 1 a 1,000,000(separados por espacios) en un navegador web? (4)
Estaba leyendo sobre el almacenamiento en búfer de salida en JavaScript aquí , y estaba tratando de entender el guión que el autor dice que fue el más rápido en la impresión de 1 a 1.000.000 en una página web. (Desplácese hacia abajo hasta el encabezado "El guion ganador de un millón de números".) Después de estudiarlo un poco, tengo algunas preguntas:
- ¿Qué hace que este script sea tan eficiente comparado con otros enfoques?
- ¿Por qué el almacenamiento en búfer acelera las cosas?
- ¿Cómo se determina el tamaño de búfer adecuado para usar?
- ¿Alguien aquí tiene algún truco en su manga que pueda optimizar aún más este guión?
(Me doy cuenta de que esto es probablemente CS101, pero soy uno de esos malditos hackers autodidactas y esperaba aprovechar la sabiduría del colectivo en este. ¡Gracias!)
¿Qué hace que este script sea tan eficiente comparado con otros enfoques?
Hay varias optimizaciones que el autor está haciendo para este algoritmo. Cada uno de estos requiere una comprensión bastante profunda de cómo se utilizan los mecanismos subyacentes (por ejemplo, Javascript, CPU, registros, caché, tarjeta de video, etc.). Creo que hay 2 optimizaciones clave que está haciendo (el resto son simplemente guinda):
- Buffering la salida
- Usar matemáticas enteras en lugar de manipulación de cadenas
Discutiré el almacenamiento en búfer en breve ya que lo preguntas explícitamente. La matemática entera que está utilizando tiene dos ventajas de rendimiento: la suma entera es más económica por operación que la manipulación de cadena y utiliza menos memoria.
No sé cómo JavaScript y los navegadores web manejan la conversión de un entero a un glifo de visualización en el navegador, por lo que puede haber una penalización asociada con pasar un entero a document.write en comparación con una cadena. Sin embargo, está realizando (1,000,000 / 1000) llamadas a document.write contra 1,000,000 - 1,000 adiciones enteras. Esto significa que está realizando operaciones de aproximadamente 3 órdenes de magnitud más para formar el mensaje que él para enviarlo a la pantalla. Por lo tanto, la penalización por enviar un entero frente a una cadena a document.write debería exceder 3 órdenes de magnitud para compensar la ventaja de rendimiento de la manipulación de enteros.
¿Por qué el almacenamiento en búfer acelera las cosas?
Los detalles de por qué funciona varían según la plataforma, el hardware y la implementación que esté utilizando. En cualquier caso, se trata de equilibrar su algoritmo con sus recursos que inducen cuellos de botella.
Por ejemplo, en el caso de E / S de archivos, el búfer es útil porque aprovecha el hecho de que un disco rotativo solo puede escribir una cierta cantidad a la vez. Déle muy poco trabajo y no usará todos los bits disponibles que pasan debajo de la cabeza del husillo a medida que gira el disco. Déle demasiado, y su aplicación tendrá que esperar (o quedarse dormida) mientras el disco finaliza su tiempo de escritura, lo que podría emplearse para preparar el siguiente registro para la escritura. Algunos de los factores clave que determinan el tamaño de búfer ideal para E / S de archivo incluyen: tamaño de sector, tamaño de fragmento de sistema de archivos, entrelazado, número de cabezales, velocidad de rotación y densidad de área, entre otros.
En el caso de la CPU, se trata de mantener la tubería llena. Si le da muy poco trabajo a la CPU, perderá tiempo girando NO OP mientras espera que lo haga. Si le da demasiado a la CPU, no puede enviar solicitudes a otros recursos, como el disco o la tarjeta de video, que podrían ejecutarse en paralelo. Esto significa que más tarde la CPU tendrá que esperar a que vuelvan sin nada que hacer. El factor principal para almacenar en la CPU es mantener todo lo que necesita (para la CPU) lo más cerca posible de la FPU / ALU. En una arquitectura típica, esto es (en orden de proximidad decreciente): registros, caché L1, caché L2, caché L3, RAM.
En el caso de escribir un millón de números en la pantalla, se trata de dibujar polígonos en su pantalla con su tarjeta de video. Piénsalo así. Digamos que por cada nuevo número que se agrega, la tarjeta de video debe hacer 100,000,000 operaciones para dibujar los polígonos en su pantalla. En un extremo, si colocas 1 número en la página a la vez y luego haces que tu tarjeta de video lo escriba y lo haces por 1,000,000 de números, la tarjeta de video tendrá que hacer 10 ^ 14 operaciones: ¡100 billones de operaciones! En el otro extremo, si tomas el millón completo de números y lo envías a la tarjeta de video de una sola vez, solo necesitarás 100,000,000 operaciones. El punto óptimo es en algún lugar en el medio. Si lo haces una vez, la CPU realiza una unidad de trabajo y espera mucho tiempo mientras la GPU actualiza la pantalla. Si primero escribe la cadena de elementos de 1M, la GPU no hace nada mientras la CPU se agita.
¿Cómo se determina qué tamaño de buffer usar?
A menos que esté apuntando a una plataforma muy específica y bien definida con un algoritmo específico (por ejemplo, escribir el enrutamiento de paquetes para un enrutamiento de Internet), normalmente no puede determinar esto matemáticamente. Por lo general, lo encuentras empíricamente. Adivina un valor, pruébalo, registra los resultados y luego elige otro. Puede hacer algunas conjeturas sobre dónde comenzar y qué rango investigar según los cuellos de botella que está administrando.
¿Alguien aquí tiene algún truco en su manga que pueda optimizar aún más este guión?
No sé si esto funcionaría y no lo he probado, sin embargo, los tamaños de los búfers suelen venir en múltiplos de 2, ya que las anotaciones de las computadoras son binarias y los tamaños de las palabras suelen ser múltiplos de dos (pero esto no siempre es ¡caso!). Por ejemplo, 64 bytes es más probable que sea óptimo que 60 bytes y 1024 es más probable que sea óptimo que 1000. Uno de los cuellos de botella específicos para este problema es que la mayoría de los navegadores hasta la fecha (Google Chrome es la primera excepción que soy consciente de) que javascript se ejecute en serie dentro del mismo hilo que el resto de la mecánica de representación de la página web. Esto significa que el javascript hace algo de trabajo llenando el búfer y luego espera mucho tiempo hasta que regrese la llamada a document.write. Si el javascript se ejecutó como un proceso separado, asincrónicamente, como en Chrome, es probable que obtenga una mayor velocidad. Esto, por supuesto, está atacando la fuente del cuello de botella, no el algoritmo que lo utiliza, pero a veces esa es la mejor opción.
No es tan breve como me gustaría, pero espero que sea un buen punto de partida. El almacenamiento en búfer es un concepto importante para todo tipo de problemas de rendimiento en la informática. Tener una buena comprensión de los mecanismos subyacentes que usa el código (tanto hardware como software) es extremadamente útil para evitar o abordar problemas de rendimiento.
Apuesto a que lo más lento en la impresión de números de 1m es que el navegador redibuja la página, por lo que cuantas menos veces llame a document.write (), mejor. Por supuesto, esto se debe equilibrar con las grandes concatenaciones de cadenas (porque implican asignar y copiar).
La determinación del tamaño de búfer correcto se encuentra a través de la experimentación.
En otros ejemplos, el almacenamiento en búfer ayuda a alinearse a lo largo de los límites naturales. Aquí hay unos ejemplos
- Las CPU de 32 bits pueden transferir 32 bits de manera más eficiente.
- Los paquetes TCP / IP tienen tamaños máximos.
- Las clases de E / S de archivos tienen búferes internos.
- Las imágenes, como TIFF, se pueden almacenar con sus datos en tiras.
Alinearse con los límites naturales de otros sistemas a menudo puede tener beneficios de rendimiento.
Así que este me ha estado volviendo loco porque no creo que realmente sea el más rápido. Así que aquí está mi experimento con el que cualquiera puede jugar. Tal vez lo escribí mal o algo así, pero parece que hacerlo de una vez en vez de usar un buffer es en realidad una operación más rápida. O al menos en mis experimentos.
<html>
<head>
<script type="text/javascript">
function printAllNumberBuffered(n, bufferSize)
{
var startTime = new Date();
var oRuntime = document.getElementById("divRuntime");
var oNumbers = document.getElementById("divNumbers");
var i = 0;
var currentNumber;
var pass = 0;
var numArray = new Array(bufferSize);
for(currentNumber = 1; currentNumber <= n; currentNumber++)
{
numArray[i] = currentNumber;
if(currentNumber % bufferSize == 0 && currentNumber > 0)
{
oNumbers.textContent += numArray.join('' '');
i = 0;
}
else
{
i++;
}
}
if(i > 0)
{
numArray.splice(i - 1, bufferSize - 1);
oNumbers.textContent += numArray.join('' '');
}
var endTime = new Date();
oRuntime.innerHTML += "<div>Number: " + n + " Buffer Size: " + bufferSize + " Runtime: " + (endTime - startTime) + "</div>";
}
function PrintNumbers()
{
var oNumbers = document.getElementById("divNumbers");
var tbNumber = document.getElementById("tbNumber");
var tbBufferSize = document.getElementById("tbBufferSize");
var n = parseInt(tbNumber.value);
var bufferSize = parseInt(tbBufferSize.value);
oNumbers.textContent = "";
printAllNumberBuffered(n, bufferSize);
}
</script>
</head>
<body>
<table border="1">
<tr>
<td colspan="2">
<div>Number: <input id="tbNumber" type="text" />Buffer Size: <input id="tbBufferSize" type="text" /><input type="button" value="Run" onclick="PrintNumbers();" /></div>
</td>
</tr>
<tr>
<td style="vertical-align:top" width="30%">
<div id="divRuntime"></div>
</td>
<td width="90%">
<div id="divNumbers"></div>
</td>
</tr>
</table>
</body>
</html>
Una forma de pensarlo es considerar que una sola llamada a document.write () es muy costosa. Sin embargo, construir una matriz y unir esa matriz a una cadena no lo es. Por lo tanto, la reducción del número de llamadas a document.write () reduce efectivamente el tiempo computacional total necesario para escribir los números.
Los búferes son una forma de intentar y unir dos piezas de trabajo de costos diferentes.
La computación y el llenado de matrices tiene un costo pequeño para matrices pequeñas, un gran costo de errores para matrices de gran tamaño. document.write tiene un gran costo constante independientemente del tamaño de la escritura, pero escalas menores que o (n) para entradas más grandes.
Así que poner en cola cadenas más grandes para escribir, o almacenarlas en búfer, acelera el rendimiento general.
Buen hallazgo en el artículo por cierto.