Perché in questa situazione v8 esaurisce la memoria?

Question

In base al file node.js, un nodo ha un limite di 512 meg sulla versione a 32 bit e un limite di 1,4 gig sulla versione a 64 bit. I limiti sono simili per Chrome AFAICT. (+/- 25%)

Quindi, perché questo codice esaurisce la memoria quando non utilizza mai più di ~ 424meg di memoria?

Ecco il codice (Il codice non ha senso. Questa domanda non riguarda ciò che il codice sta facendo, riguarda il motivo per cui il codice non funziona).

var lookup = 'superCaliFragilisticExpialidosiousThispartdoesnotrealllymattersd'; 
function encode (num) { 
    return lookup[num]; 
} 

function makeString(uint8) { 
    var output = ''; 

    for (var i = 0, length = uint8.length; i < length; i += 3) { 
    var temp = (uint8[i] << 16) + (uint8[i + 1] << 8) + (uint8[i + 2]); 
    output += encode(temp >> 18 & 0x3F) + encode(temp >> 12 & 0x3F) + encode(temp >> 6 & 0x3F) + encode(temp & 0x3F); 
    } 

    return output; 
} 

function test() { 
    var big = new Uint8Array(64 * 1024 * 1024 + 2); // multiple of 3 
    var str = makeString(big); 
    console.log("big:", big.length); 
    console.log("str:", str.length); 
} 

test(); 

Come si può vedere makeString costruisce una stringa aggiungendo 4 caratteri alla volta. In questo caso costruirà una stringa 89478988 di lunghezza (180meg) grande. Poiché output viene aggiunto, l'ultima volta che i caratteri vengono aggiunti, ci saranno 2 stringhe in memoria. Il vecchio con 89478984 caratteri e l'ultimo con 89478988. GC dovrebbe raccogliere qualsiasi altra memoria utilizzata.

Quindi, 64 meg (l'array originale) + 180meg * 2 = 424meg. Bene sotto i limiti del v8.

Ma, se si esegue l'esempio fallirà con la memoria

<--- Last few GCs ---> 

    3992 ms: Scavenge 1397.9 (1458.1) -> 1397.9 (1458.1) MB, 0.2/0 ms (+ 1.5 ms in 1 steps since last GC) [allocation failure] [incremental marking delaying mark-sweep]. 
    4450 ms: Mark-sweep 1397.9 (1458.1) -> 1397.9 (1458.1) MB, 458.0/0 ms (+ 2.9 ms in 2 steps since start of marking, biggest step 1.5 ms) [last resort gc]. 
    4909 ms: Mark-sweep 1397.9 (1458.1) -> 1397.9 (1458.1) MB, 458.7/0 ms [last resort gc]. 

$ node foo.js  
<--- JS stacktrace ---> 

==== JS stack trace ========================================= 

Security context: 0x3a8521e3ac1 <JS Object> 
    2: makeString(aka makeString) [/Users/gregg/src/foo.js:~6] [pc=0x1f83baf53a3b] (this=0x3a852104189 <undefined>,uint8=0x2ce813b51709 <an Uint8Array with map 0x32f492c0a039>) 
    3: test(aka test) [/Users/gregg/src/foo.js:19] [pc=0x1f83baf4df7a] (this=0x3a852104189 <undefined>) 
    4: /* anonymous */ [/Users/gregg/src/foo.js:24] [pc=0x1f83baf4d9e5] (this=0x2ce813b... 

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memory 
Abort trap: 6 

provato sia il nodo 4.2.4 e 5.6.0

Quindi, la domanda è perché è esaurendo di memoria?

Alcune cose che ho provato.

1. Ho provato unendo pezzi

   invece di aggiungerlo ai output indefinitamente Ho provato controllare se è maggiore di una certa dimensione (come 8k). Se è così, lo metto in un array e ripristina l'output sulla stringa vuota.

   In tal modo, output non è mai più di 8 k grande. L'array contiene 180meg + contabilità. Quindi 180meg + 8k è molto meno di 180meg + 180meg. Funziona ancora a corto di memoria. Ora, alla fine di quel processo, io unisco l'array, a quel punto userà più memoria (180meg + 180meg + bookeeping). Ma, v8 si blocca prima che arrivi alla linea .

2. Ho provato a cambiare la codifica a poco

   function encode(num) { 
       return 'X'; 
   } 
   

   In questo caso si esegue effettivamente a compimento !! Così ho pensato, "A-ha! la questione deve essere qualcosa legato al lookup[num] generare una nuova stringa a tutte le chiamate? Così ho provato ...

3. Modificato lookup di array di stringhe

   var lookup = Array.prototype.map.call(
       'superCaliFragilisticExpialidosiousThispartdoesnotrealllymattersd', 
       function(c) { 
        return c; 
       }); 
   

   Ancora esaurito la memoria

Questo sembra un bug in v8?Non è in grado di interpretare le stringhe inutilizzate di GC in un modo strano a causa di questo codice, sebbene il # 2 rispetto al # 3 sia strano in quanto sembrano equivalenti in termini di utilizzo della memoria.

Perché in queste situazioni la memoria è esaurita? (e c'è una soluzione alternativa)

Answer 1

TL; DR: l'esempio è un caso patologico per una delle rappresentazioni di stringa interne di v8. È possibile risolvere il problema indicizzando in output una volta ogni tanto (informazioni sul perché di seguito).

In primo luogo, possiamo usare heapdump per vedere ciò che il garbage collector è fino a:

L'istantanea sopra è stata presa poco prima del nodo esaurisce la memoria. Come puoi vedere, la maggior parte delle cose sembra normale: vediamo due stringhe (il grandissimo output e il piccolo pezzo da aggiungere), tre riferimenti allo stesso array big (di circa 64 MB, simile a quello che ci aspetteremmo), e molti oggetti più piccoli che non sembrano insoliti.

Ma, una cosa spicca: output è un enorme 1.4+ GB. Nel momento in cui è stata scattata l'istantanea, era lunga circa 80 milioni di caratteri, quindi ~ 160 MB assumendo 2 byte per carattere. Com'è possibile?

Forse questo ha a che fare con la rappresentazione stringa interna di v8. Citando mraleph:

Ci sono due tipi [di stringhe V8] (in realtà di più, ma per il problema in esame solo questi due sono importanti):

• stringhe piatte sono array immutabili di personaggi
• le stringhe sono coppie di stringhe, risultato della concatenazione.

Se si concatena a e b si ottiene una stringa di controllo (a, b) che rappresenta il risultato della concatenazione. Se in seguito concatri a ciò ottieni un'altra stringa di controllo ((a, b), d).

L'indicizzazione in una stringa "ad albero" non è O (1), quindi per rendere più veloce V8 appiattisce la stringa quando si indice: copia tutti i caratteri in una stringa piatta.

Quindi potrebbe essere che v8 rappresenti output come un albero gigante? Un modo per controllare è quello di forzare v8 per appiattire la stringa (come suggerito da mraleph sopra), ad esempio, indicizzando in output a intervalli regolari all'interno del ciclo for:

if (i % 10000000 === 0) { 
    // We don't do it at each iteration since it's relatively expensive. 
    output[0]; 
} 

E in effetti, il programma viene eseguito con successo!

Una domanda rimane ancora: perché è stata eseguita la versione 2 sopra? Sembra che in tal caso v8 sia in grado di ottimizzare la maggior parte delle concatenazioni di stringhe (tutte quelle sul lato destro, che vengono convertite in operazioni bit a bit su un array di 4 elementi).