Cosa rende questo il JavaScript più veloce per la stampa da 1 a 1.000.000 (separati da spazi) in un browser Web?

Question

Stavo leggendo del buffering dell'output in JavaScript qui , e stavo cercando di orientarmi nella sceneggiatura, secondo l'autore, è stato il più veloce a stampare da 1 a 1.000.000 di pagine Web. (Scorri verso il basso fino all'intestazione " Lo script vincente da un milione di numeri " ;.) Dopo averlo studiato un po ', ho alcune domande:

• Cosa rende questo script così efficiente rispetto ad altri approcci?
• Perché il buffering accelera le cose?
• Come si determina la dimensione del buffer corretta da utilizzare?
• Qualcuno qui ha qualche asso nella manica che potrebbe ottimizzare ulteriormente questo script?

(Mi rendo conto che questo è probabilmente CS101, ma sono uno di quegli hacker esplosivi e autodidatti e speravo di beneficiare della saggezza del collettivo su questo. Grazie!)

Answer 1

Cosa rende questo script così efficiente rispetto ad altri approcci?

Esistono diverse ottimizzazioni che l'autore sta apportando a questo algoritmo. Ognuno di questi richiede una comprensione abbastanza profonda di come sono utilizzati i meccanismi sottostanti (ad esempio Javascript, CPU, registri, cache, scheda video, ecc.). Penso che ci siano 2 ottimizzazioni chiave che sta facendo (il resto è solo una ciliegina sulla torta):

• Buffering dell'output
• Uso della matematica dei numeri interi anziché della manipolazione delle stringhe

Discuterò a breve il buffering poiché lo chiedi esplicitamente. La matematica dei numeri interi che sta utilizzando ha due vantaggi in termini di prestazioni: l'aggiunta di numeri interi è più economica per operazione rispetto alla manipolazione di stringhe e utilizza meno memoria.

Non so come JavaScript e i browser web gestiscano la conversione di un numero intero in un glifo di visualizzazione nel browser, quindi potrebbe esserci una penalità associata al passaggio di un numero intero a document.write rispetto a una stringa. Tuttavia, sta eseguendo (1.000.000 / 1000) document.write chiamate contro 1.000.000 - 1.000 integrazioni intere. Ciò significa che sta eseguendo circa 3 ordini di grandezza in più operazioni per formare il messaggio di quanto non lo debba inviare al display. Pertanto, la penalità per l'invio di un numero intero rispetto a una stringa a document.write dovrebbe superare 3 ordini di grandezza per compensare il vantaggio prestazionale della manipolazione di numeri interi.

Perché il buffering accelera le cose?

Le specifiche del motivo per cui funziona variano a seconda della piattaforma, dell'hardware e dell'implementazione che stai utilizzando. In ogni caso, si tratta di bilanciare l'algoritmo con il collo di bottiglia, inducendo risorse.

Ad esempio, nel caso dell'I / O dei file, il buffer è utile perché sfrutta il fatto che un disco rotante può scrivere solo un determinato importo alla volta. Dagli troppo poco lavoro e non utilizzerà tutti i bit disponibili che passano sotto la testa del mandrino mentre il disco ruota. Dagli troppo e la tua applicazione dovrà attendere (o essere messa in sospensione) mentre il disco termina la tua scrittura - tempo che potrebbe essere impiegato per preparare il prossimo record pronto per la scrittura! Alcuni dei fattori chiave che determinano la dimensione del buffer ideale per l'I / O dei file includono: dimensione del settore, dimensione del blocco del file system, interleaving, numero di teste, velocità di rotazione e densità areale, tra gli altri.

Nel caso della CPU, si tratta di mantenere la pipeline piena. Se si dà alla CPU troppo poco lavoro, passerà il tempo a girare NO OP mentre attende che tu lo assegni. Se si dà troppo alla CPU, non è possibile inviare richieste ad altre risorse, come il disco o la scheda video, che potrebbero essere eseguite in parallelo. Ciò significa che in seguito la CPU dovrà attendere che ritornino senza nulla da fare. Il fattore principale per il buffering nella CPU è mantenere tutto il necessario (per la CPU) il più vicino possibile all'FPU / ALU. In un'architettura tipica questo è (in ordine decrescente di prossimità): registri, cache L1, cache L2, cache L3, RAM.

Nel caso di scrivere un milione di numeri sullo schermo, si tratta di disegnare poligoni sullo schermo con la scheda video. Pensala in questo modo. Diciamo che per ogni nuovo numero aggiunto, la scheda video deve eseguire 100.000.000 di operazioni per disegnare i poligoni sullo schermo. Ad un estremo, se metti 1 numero alla pagina alla volta e poi la tua scheda video lo scrive e lo fai per 1.000.000 di numeri, la scheda video dovrà fare 10 ^ 14 operazioni - 100 trilioni di operazioni! All'altro estremo, se prendessi l'intero 1 milione di numeri e lo avessi inviato alla scheda video tutto in una volta, sarebbero necessarie solo 100.000.000 di operazioni. Il punto ottimale è un po 'nel mezzo. Se lo fai una volta, la CPU esegue un'unità di lavoro e attende a lungo mentre la GPU aggiorna il display. Se scrivi prima l'intera stringa di elementi 1M, la GPU non sta facendo nulla mentre la CPU si sposta.

Come si determina quale dimensione del buffer utilizzare?

A meno che non si stia prendendo di mira una piattaforma molto specifica e ben definita con un algoritmo specifico (ad esempio, la scrittura del routing di pacchetti per un routing di Internet) in genere non è possibile determinarlo matematicamente. In genere, lo trovi empiricamente. Indovina un valore, provalo, registra i risultati, quindi scegline un altro. Puoi fare alcune ipotesi plausibili su dove iniziare e su quale intervallo indagare in base alle strozzature che stai gestendo.

Qualcuno qui ha qualche asso nella manica che potrebbe ottimizzare ulteriormente questo script?

Non so se questo funzionerebbe e non l'ho ancora testato, le dimensioni del buffer sono generalmente in multipli di 2 poiché i pin di sotto dei computer sono binari e le dimensioni delle parole sono in genere in multipli di due (ma non è sempre così!). Ad esempio, 64 byte hanno maggiori probabilità di essere ottimali rispetto a 60 byte e 1024 hanno maggiori probabilità di essere ottimali rispetto a 1000. Uno dei colli di bottiglia specifici per questo problema è che la maggior parte dei browser fino ad oggi (Google Chrome è la prima eccezione che sto a conoscenza di) avere javascript eseguito in serie all'interno dello stesso thread del resto della meccanica di rendering della pagina web. Ciò significa che javascript fa un po 'di lavoro riempiendo il buffer e quindi attende a lungo fino al ritorno della chiamata document.write. Se il javascript fosse eseguito come processo separato, in modo asincrono, come in Chrome, probabilmente otterresti una maggiore velocità. Questo ovviamente attacca l'origine del collo di bottiglia non l'algoritmo che lo utilizza, ma a volte questa è l'opzione migliore.

Non è così succinto come vorrei, ma spero sia un buon punto di partenza. Il buffering è un concetto importante per tutti i tipi di problemi di prestazioni nell'informatica. Avere una buona conoscenza dei meccanismi sottostanti utilizzati dal codice (sia hardware che software) è estremamente utile per evitare o affrontare i problemi di prestazioni.

Answer 2

Scommetto che la cosa più lenta nella stampa di numeri di 1m è il browser che ridisegna la pagina, quindi meno volte chiami document.write (), meglio è. Ovviamente questo deve essere bilanciato con grandi concatenazioni di stringhe (perché implicano allocazione e copia).

La determinazione della giusta dimensione del buffer si trova attraverso la sperimentazione.

In altri esempi, il buffering aiuta ad allinearsi lungo i confini naturali. Ecco alcuni esempi

• Le CPU a 32 bit possono trasferire 32 bit in modo più efficiente.
• I pacchetti TCP / IP hanno dimensioni massime.
• Le classi I / O dei file hanno buffer interni.
• Le immagini, come i TIFF, possono essere archiviate con i loro dati in strisce.

L'allineamento con i confini naturali di altri sistemi può spesso avere vantaggi in termini di prestazioni.

Answer 3

Un modo per pensarci è considerare che una singola chiamata a document.write () è molto costosa. Tuttavia, la creazione di un array e l'unione di tale array in una stringa non lo è. Quindi ridurre il numero di chiamate a document.write () riduce efficacemente il tempo di calcolo complessivo necessario per scrivere i numeri.

I buffer sono un modo per provare a collegare due diversi pezzi di lavoro a costo.

Il calcolo e il riempimento di array ha un costo ridotto per array di piccole dimensioni, bug per costi elevati per array di grandi dimensioni. document.write ha un costo costante elevato, indipendentemente dalle dimensioni della scrittura, ma si ridimensiona di o (n) per input più grandi.

Quindi accodare stringhe più grandi per scrivere o memorizzarle in buffering, accelera le prestazioni complessive.

Bella trovata sull'articolo tra l'altro.

Answer 4

Quindi questo mi sta facendo impazzire perché non penso che sia davvero il più veloce. Quindi ecco il mio esperimento con cui chiunque può giocare. Forse l'ho scritto male o qualcosa del genere, ma sembrerebbe che farlo tutto in una volta invece di usare un buffer sia in realtà un'operazione più veloce. O almeno nei miei esperimenti.

<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:&nbsp;<input id="tbNumber" type="text" />Buffer Size:&nbsp;<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>