Perché la concatenazione delle stringhe è più veloce di un join matrice?

Question

Oggi ho letto this thread sulla velocità della concatenazione delle stringhe.

Sorprendentemente, concatenazione di stringhe è stato il vincitore:

http://jsben.ch/#/OJ3vo

Il risultato è stato opposto a quello che ho pensato. Inoltre, ci sono molti articoli su questo che spiega in modo opposto come this o this.

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

Answer 1

ottimizzazioni stringa Browser hanno cambiato la concatenazione di stringhe immagine.

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.

- Writing Efficient JavaScript: Chapter 7 – Even Faster Websites

Il V8 motore JavaScript (utilizzato in Google Chrome) utilizza this code fare concatenazione 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, ""); 
} 

Così, internamente hanno ottimizzarlo creando un (la variabile InternalArray parts), che viene quindi riempito. La funzione StringBuilderConcat viene chiamata con queste parti. È veloce perché la funzione StringBuilderConcat è un codice C++ fortemente ottimizzato. È troppo lungo per citare qui, ma cerca nel file runtime.cc per RUNTIME_FUNCTION(MaybeObject*, Runtime_StringBuilderConcat) per vedere il codice.

Answer 2

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

Answer 3

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

Se si tenta di aggiungere un for(j=0;j<1000;j++) prima di ogni for vedrete che (sotto il cromo) 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 oggetto JS.

Essere consapevoli del fatto che non v'è la possibilità che molte implementazioni di motori JS hanno un'ottimizzazione per gli array singolo tipo che avrebbe fatto tutto quello che ho scritto inutile :-)

Answer 4

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

Quindi, ad esempio, se si dovesse fare a = 'abc'.concat('def'), l'oggetto appena creato sarà 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 ha a che 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('') di solito allocava semplicemente memoria per disporre la nuova stringa piatta in memoria. (Forse dovrebbe essere ottimizzato)

Answer 5

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

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

Answer 6

This test mostra la penalità dell'utilizzo effettivo di una stringa eseguita con concatenazione di incarichi o con 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.

Answer 7

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!