Oggetto Java allocazione overhead

Question

Sto scrivendo un immutabile albero del DOM in Java, per semplificare l'accesso da più thread.*

Tuttavia, non è necessario che il supporto inserisce e aggiorna il più velocemente possibile.E dal momento che è immutabile, se faccio una modifica ad un nodo sulla N-esimo livello dell'albero, ho bisogno di assegnare almeno N nuovi nodi per l'albero.

La mia domanda è, sarebbe notevolmente più veloce pre-allocare i nodi piuttosto che crearne di nuove, ogni volta che l'albero è modificato?Sarebbe abbastanza facile da fare, mantenere un pool di diverse centinaia di nodi non utilizzati, e tirare fuori la piscina, piuttosto che creare uno ogni volta che era necessario per un'operazione di modifica.Posso riempire il nodo piscina quando non c'è nient'altro.(nel caso in cui non è evidente, il tempo di esecuzione è intenzione di essere molto di più ad un premio in questa applicazione di spazio heap è)

Vale la pena di fare questo?Altri suggerimenti su rendendola?

In alternativa, qualcuno sa se è un immutabile DOM libreria già?Ho cercato, ma non ho trovato nulla.

*Nota:Per quelli di voi che non hanno familiarità con il concetto di immutabilità, fondamentalmente, significa che su ogni operazione per un oggetto che cambia, il metodo restituisce una copia dell'oggetto con i cambiamenti in atto, piuttosto che l'oggetto modificato.Così, se un altro thread è ancora leggendo l'oggetto continuerà a felicemente operare sulla "vecchia" versione, inconsapevole del fatto che le modifiche sono state fatte, piuttosto che schiantarsi orribilmente.Vedere http://www.javapractices.com/topic/TopicAction.do?Id=29

Answer 1

In questi giorni, la creazione di oggetti è piuttosto dang veloce, e il concetto di pool di oggetti è un po obsoleto (almeno in generale;il pool di connessioni è naturalmente ancora valido).

Evitare un prematuro di ottimizzazione.Crea il tuo nodi quando hai bisogno di loro quando fare le copie, e poi vedere se diventa troppo lenta.Se è così, allora guardare in tecniche per la velocità.Ma a meno che non sai già che quello che hai non è abbastanza veloce, non vorrei andare a introdurre tutte le complessità che si sta andando ad avere bisogno di ottenere il pool di andare.

Answer 2

Odio dare una risposta, ma credo che l'unico modo definitivo per rispondere a una domanda di prestazioni come questa potrebbe essere per voi il codice di entrambi gli approcci, benchmark i due, e confrontare i risultati.

Answer 3

Non so se si può evitare in modo esplicito la sincronizzazione di alcuni metodi per assicurarsi che tutto è thread-safe.

Un caso specifico è necessario sincronizzare uno o l'altro lato di rendere la creazione di un nuovo nodo a disposizione altri thread, altrimenti si rischia la VM/CPU ri-ordinare le scritture dei campi passato la scrittura di riferimento condivisi, il nodo, l'esposizione di una parte oggetto costruito.

Provate a pensare a un livello superiore.Si dispone di un IMMUTABILE albero (che è fondamentalmente un insieme di nodi di puntamento per i suoi figli).Si desidera inserire un nodo in esso.Quindi, non c'è via d'uscita:è necessario creare un nuovo albero.

Se si sceglie di implementare la struttura come un insieme di nodi di puntamento per i bambini, quindi si dovrebbe creare nuovi nodi lungo il percorso del cambiamento di nodo alla radice.Gli altri hanno lo stesso valore di prima, e normalmente sono in comune.Quindi è necessario creare un parziale nuova struttura, che di solito significa (profondità di cura nodo dei nodi padre.

Se si può far fronte con una forma meno diretta di attuazione, si dovrebbe essere in grado di cavarsela con solo la creazione di parti di nodi, utilizzando tecniche simili a quelle descritte in Puramente Funzionale Di Strutture Di Dati per ridurre il costo medio della creazione, o si può by-pass utilizzando semi-approcci funzionali (come la creazione di un iteratore che avvolge esistente iteratore, ma restituisce il nodo nuovo al posto del vecchio, insieme con un meccanismo per la riparazione di tali patch nella struttura con il passare del tempo).XPath stile di api potrebbe essere meglio di un DOM api in quel caso si potrebbe scindere i nodi dell'albero un po ' di più, e trattare il mutato albero in modo più intelligente.

Answer 4

Io sono un po ' confuso su ciò che si sta cercando di fare, in primo luogo.Si desidera che tutti i nodi siano immutabili E si desidera piscina di loro?Non sono queste 2 idee si escludono a vicenda?Quando si tira un oggetto fuori dalla piscina, non è necessario richiamare un setter di collegamento dei bambini?

Penso che l'utilizzo di immutabile nodi probabilmente non sta per darvi il tipo di filo di sicurezza è necessario, in primo luogo.Cosa succede se 1 thread sta scorrendo i nodi (una ricerca o qualcosa del genere), mentre un altro thread è aggiunta/rimozione di nodi?Non i risultati di ricerca essere valido?Non so se si può evitare in modo esplicito la sincronizzazione di alcuni metodi per assicurarsi che tutto è thread-safe.

Answer 5

@Fuorilegge Programmatore

Quando si tira un oggetto fuori piscina, non è necessario richiamare un setter link ai bambini?

Ogni nodo non deve essere immutabile all'interno del pacchetto, solo per l'andata fronte di interfaccia. node.addChild() sarebbe un immutabile funzione pubblica visibilità e ritorno di un Documento, mentre node.addChildInternal() sarebbe una normale, mutevole funzione con il pacchetto di visibilità.Ma dal momento che è interno al pacchetto, si può solo essere chiamato come un discendente di addChild() e la struttura nel suo complesso è garantita per essere thread-safe (fornito sincronizzare l'accesso all'oggetto piscina).Non si vede un difetto in questo...?Se è così, si prega di dire a me!

Penso che l'utilizzo di immutabile nodi probabilmente non sta per darvi il tipo di filo di sicurezza è necessario, in primo luogo.Cosa succede se 1 thread sta scorrendo i nodi (una ricerca o qualcosa del genere), mentre un altro thread è aggiunta/rimozione di nodi?

L'albero verrà immutabile.Dire che ho Thread1 e Thread2, e albero dom1.Thread1 inizia un'operazione di lettura su dom1, mentre, contemporaneamente, Thread2 inizia un'operazione di scrittura su dom1.Tuttavia, tutte le modifiche Thread2 rende effettivamente verrà fatto un nuovo oggetto, dom2, e dom1 sarà immutabile.È vero che i valori letti da Thread1 sarà (pochi microsecondi) al di fuori di data, ma non bloccarsi su un IndexOutOfBounds o NullPointer exception o qualcosa di simile, farebbe se fosse la lettura di un mutevole oggetto che è stato scritto.Quindi, Thread2 può generare un evento contenente dom2 per Thread1 in modo che possa fare il suo letto di nuovo e aggiornare i propri risultati, se necessario.

Edit:chiarito

Answer 6

Penso che @Fuorilegge ha un punto.La struttura dell'albero DOM, risiede nei nodi stesso, avendo un nodo di puntamento per i suoi figli.Per modificare la struttura di un albero, è necessario modificare il nodo, in modo che non si può avere il pool, è necessario crearne uno nuovo.

Provate a pensare a un livello superiore.Si dispone di un IMMUTABILE albero (che è fondamentalmente un insieme di nodi di puntamento per i suoi figli).Si desidera inserire un nodo in esso.Quindi, non c'è via d'uscita:è necessario creare un nuovo albero.

Sì, l'immutabile, l'albero è thread-safe, ma con un impatto sulle prestazioni.Creazione di un oggetto può essere veloce, ma non più veloce quindi NON la creazione di oggetti.:)