Perché la concatenazione delle stringhe è più veloce rispetto all’array join?

Oggi leggo questo thread sulla velocità della concatenazione delle stringhe.

Sorprendentemente, il concatenamento delle stringhe è stato il vincitore:

http://jsben.ch/#/OJ3vo

Il risultato era opposto a quello che pensavo. Inoltre, ci sono molti articoli su questo che spiegano in modo opposto come questo .

Posso indovinare che i browser sono ottimizzati per string concat sull’ultima versione, ma come fanno? Possiamo dire che è meglio usare + quando si concatenano le stringhe?

Aggiornare

Quindi, nei moderni browser la concatenazione delle stringhe è ottimizzata, quindi l’utilizzo dei segni + è più rapido rispetto all’utilizzo di join quando si desidera concatenare le stringhe.

Ma @Arthur ha sottolineato che join è più veloce se si desidera effettivamente unire le stringhe con un separatore.

Le ottimizzazioni della stringa del browser hanno cambiato l’immagine di concatenazione della stringa.

Firefox è stato il primo browser ad ottimizzare la concatenazione delle stringhe. A partire dalla versione 1.0, la tecnica dell’array è in realtà più lenta rispetto all’utilizzo dell’operatore più in tutti i casi. Altri browser hanno anche ottimizzato la concatenazione di stringhe, quindi Safari, Opera, Chrome e Internet Explorer 8 mostrano anche prestazioni migliori usando l’operatore plus. Internet Explorer precedente alla versione 8 non aveva tale ottimizzazione e quindi la tecnica dell’array è sempre più veloce dell’operatore plus.

– Scrittura di JavaScript efficiente: Capitolo 7 – Anche siti Web più veloci

Il motore javascript V8 (utilizzato in Google Chrome) utilizza questo codice per eseguire concatenazioni di stringhe:

 // ECMA-262, section 15.5.4.6 function StringConcat() { if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) { throw MakeTypeError("called_on_null_or_undefined", ["String.prototype.concat"]); } var len = %_ArgumentsLength(); var this_as_string = TO_STRING_INLINE(this); if (len === 1) { return this_as_string + %_Arguments(0); } var parts = new InternalArray(len + 1); parts[0] = this_as_string; for (var i = 0; i < len; i++) { var part = %_Arguments(i); parts[i + 1] = TO_STRING_INLINE(part); } return %StringBuilderConcat(parts, len + 1, ""); } 

Quindi, internamente, lo ottimizzano creando un InternalArray (la variabile delle parts ), che viene poi riempito. La funzione StringBuilderConcat viene chiamata con queste parti. È veloce perché la funzione StringBuilderConcat è un codice C ++ fortemente ottimizzato. È troppo lungo per essere citato qui, ma cerca nel file runtime.cc per RUNTIME_FUNCTION(MaybeObject*, Runtime_StringBuilderConcat) per vedere il codice.

Firefox è veloce perché usa qualcosa chiamato Ropes ( Ropes: an Alternative to Strings ). Una corda è fondamentalmente solo un DAG, in cui ogni nodo è una stringa.

Ad esempio, se si a = 'abc'.concat('def') , l’object appena creato sarebbe simile a questo. Ovviamente questo non è esattamente come appare in memoria, perché è ancora necessario avere un campo per il tipo di stringa, la lunghezza e forse altro.

 a = { nodeA: 'abc', nodeB: 'def' } 

E b = a.concat('123')

 b = { nodeA: a, /* { nodeA: 'abc', nodeB: 'def' } */ nodeB: '123' } 

Quindi nel caso più semplice la VM deve fare quasi nessun lavoro. L’unico problema è che questo rallenta un po ‘le altre operazioni sulla stringa risultante. Anche questo naturalmente riduce il sovraccarico della memoria.

D’altra parte ['abc', 'def'].join('') solito allocano semplicemente memoria per disporre la nuova stringa piatta in memoria. (Forse questo dovrebbe essere ottimizzato)

I parametri di riferimento sono banali. Concatenando ripetutamente gli stessi tre elementi, i risultati si dimostreranno deterministici e memoizzati, il gestore dei rifiuti si limiterà a buttare via gli oggetti array (che non avranno quasi nulla in termini di dimensioni) e probabilmente li spingeranno e rimbalzeranno dallo stack a causa di no riferimenti esterni e perché le stringhe non cambiano mai. Sarei più impressionato se il test fosse un numero elevato di stringhe generate casualmente. Come in un concerto o due di archi.

Array.join FTW!

Direi che con le stringhe è più semplice preallocare un buffer più grande. Ogni elemento è solo 2 byte (se UNICODE), quindi anche se si è prudenti, è ansible preallocare un buffer piuttosto grande per la stringa. Con gli arrays ogni elemento è più “complesso”, poiché ogni elemento è un Object , quindi un’implementazione conservativa prealloca lo spazio per meno elementi.

Se provi ad aggiungere un for(j=0;j<1000;j++) prima di ciascuno, vedrai che (sotto chrome) la differenza di velocità si riduce. Alla fine era ancora 1.5x per la concatenazione di stringhe, ma inferiore alla 2.6 che era prima.

E dovendo copiare gli elementi, un carattere Unicode è probabilmente più piccolo di un riferimento a un object JS.

Siate consapevoli che esiste la possibilità che molte implementazioni di motori JS abbiano un'ottimizzazione per array di tipo singolo che renderebbero tutto inutile scritto :-)

So che questo è un thread vecchio, ma il tuo test non è corretto. Stai facendo output += myarray[i]; mentre dovrebbe essere più simile output += "" + myarray[i]; perché hai dimenticato che devi incollare oggetti insieme a qualcosa. Il codice concat dovrebbe essere qualcosa del tipo:

 var output = myarray[0]; for (var i = 1, len = myarray.length; i 

In questo modo, stai facendo due operazioni invece di una a causa di elementi di incollaggio insieme.

Array.join() è più veloce.

Questo test mostra la penalità di utilizzare effettivamente una stringa creata con concatenazione di assegnazione e realizzata con il metodo array.join. Mentre la velocità complessiva di assegnazione è ancora due volte più veloce in Chrome v31, ma non è più così grande come quando non si utilizza la stringa risultante.

Ciò dipende chiaramente dall’implementazione del motore javascript. Anche per versioni diverse di un motore è ansible ottenere risultati significativamente diversi. Dovresti fare il tuo benchmark per verificarlo.

Direi che String.concat ha prestazioni migliori nelle versioni recenti di V8. Ma per Firefox e Opera, Array.join è un vincitore.

La mia ipotesi è che, mentre ogni versione sta portando il costo di molte concatenazioni, le versioni di join stanno costruendo matrici in aggiunta a questo.