Oggetto JavaScript Big-O

Question

Proveniente da Java, l'oggetto Javascript mi ​​ricorda HashMap in Java.

Javascript:

var myObject = { 
    firstName: "Foo", 
    lastName: "Bar", 
    email: "foo@bar.com" 
}; 

Java:

HashMap<String, String> myHashMap = new HashMap<String, String>(); 
myHashMap.put("firstName", "Foo"); 
myHashMap.put("lastName", "Bar"); 
myHashMap.put("email", "foo@bar.com"); 

In Java HashMap, utilizza la funzione di codice hash() della chiave per determinare la posizione della benna (voci) per la memorizzazione e il recupero. Maggior parte del tempo, per operazioni di base come put() e get(), la performance è costante, fino a quando si verifica una collisione hash che diventa O (n) per queste operazioni di base perché forma un elenco collegato per archiviare il voci in conflitto.

La mia domanda è:

1. Come funziona negozi JavaScript Object?
2. Qual è la performance delle operazioni?
3. Ci sarà mai alcuna collisione o altri scenari che degrada le prestazioni come in Java

Grazie!

Answer 1

JavaScript sembra che memorizzi le cose in una mappa, ma in genere non è il caso. È possibile accedere alla maggior parte delle proprietà di un oggetto come se fossero un indice in una mappa e assegnare nuove proprietà in fase di esecuzione, ma il codice di backup è molto più rapido e complicato rispetto all'utilizzo di una mappa.

Non c'è nulla che richieda alle macchine virtuali di non usare una mappa, ma la maggior parte cerca di rilevare la struttura dell'oggetto e crea un'efficiente rappresentazione in memoria per quella struttura. Questo può portare a un sacco di ottimizzazioni (e deopzioni) mentre il programma è in esecuzione, ed è una situazione molto complicata.

This blog post, collegato nei commenti delle domande di @Zirak, presenta una discussione abbastanza buona sulle strutture comuni e quando le macchine virtuali possono passare da una struttura a una mappa. Può spesso sembrare imprevedibile, ma è in gran parte basato su un insieme di euristiche all'interno della VM e su quanti oggetti diversi ritiene di aver visto. Questo è in gran parte correlato alle proprietà (e ai loro tipi) dei valori di ritorno e tende a essere centrato attorno a ciascuna funzione (specialmente le funzioni di costruzione).

Ci sono un paio di domande e articoli che scavano nei dettagli (ma sono spera ancora comprensibile, senza una tonnellata di sfondo):

• slow function call in V8 when using the same key for the functions in different objects
• Why is getting a member faster than calling hasOwnProperty?
• http://mrale.ph/blog/2013/08/14/hidden-classes-vs-jsperf.html (e il resto di questo blog)

Le prestazioni variano notevolmente, in base a quanto sopra. Il caso peggiore dovrebbe essere un accesso alla mappa, il caso migliore è un accesso diretto alla memoria (forse anche un deref).

Ci sono un gran numero di scenari che possono avere impatti sulle prestazioni, specialmente considerando come JITter e VM creeranno e distruggeranno le classi nascoste in fase di runtime, poiché vedono nuove variazioni su un oggetto.Incontrare improvvisamente una nuova variante di un oggetto che si presumeva essere monomorfico prima può far sì che la VM ritorni ad una rappresentazione meno ottimale e smetta di trattare l'oggetto come una struttura in memoria, ma la logica attorno è piuttosto complicata e ben sviluppata - Rivestita in this blog post.

Puoi aiutare assicurandoti che gli oggetti creati dallo stesso costruttore tendano ad avere strutture molto simili e rendendo le cose il più prevedibili possibile (buono per te, manutenzione e VM). Avere le proprietà conosciute per ogni oggetto, impostare i tipi per queste proprietà e creare oggetti dai costruttori, quando è possibile, dovrebbe consentire di colpire la maggior parte delle ottimizzazioni disponibili e avere un codice terribilmente veloce.