Ottimizzazione della ricerca hash e delle prestazioni della memoria in Go

Question

Ottimizzazione della ricerca hash e delle prestazioni della memoria in Go

#1 da (2 voti)

6

Come esercizio, sto implementando HashLife in Go.

In breve, HashLife funziona memorizzando i nodi in un quadrilatero in modo che, una volta calcolato il valore di un dato nodo in futuro, esso possa essere semplicemente controllato anziché essere ricalcolato. Quindi ad es. se hai un nodo al livello 8x8, lo ricordi per i suoi quattro figli (ciascuno al livello 2x2). Quindi la prossima volta che vedi un nodo 8x8, quando calcoli la prossima generazione, per prima cosa controlla se hai già visto un nodo con quegli stessi quattro figli. Questo è esteso a tutti i livelli del quadripeso, il che ti dà delle ottimizzazioni piuttosto sorprendenti se ad es. sei 10 livelli sopra le foglie.

Non sorprende, sembra che il punto di perfmance di questo è la ricerca di nodi per valori di nodo figlio. Attualmente ho una hashmap di

{&upper_left_node,&upper_right_node,&lower_left_node,&lower_right_node} -> node

Quindi la mia funzione di ricerca è questa:

func FindNode(ul, ur, ll, lr *Node) *Node {
        var node *Node
        var ok bool
        nc := NodeChildren{ul, ur, ll, lr}
        node, ok = NodeMap[nc]
        if ok {
                return node
        }
        node = &Node{ul, ur, ll, lr, 0, ul.Level + 1, nil}
        NodeMap[nc] = node
        return node
}

Quello che sto cercando di capire è se la riga "nc: = NodeChildren ..." causa un'allocazione di memoria ogni volta che viene chiamata la funzione. In caso affermativo, posso / devo spostare la dichiarazione nello scope globale e modificare semplicemente i valori ogni volta che viene chiamata questa funzione? O c'è un modo più efficiente per farlo?

Qualsiasi consiglio / feedback sarebbe il benvenuto. (anche la codifica degli style lits, questa è letteralmente la prima cosa che ho scritto in Go, quindi mi piacerebbe qualsiasi feedback)

performance go

posta Moishe 08.09.2012 - 15:35

fonte

1 risposta

Leggi altre domande sui tag performance go

REST: come memorizzare e riutilizzare le query di chiamata REST Aiuta a capire il modello astratto di fabbrica

score 2 · Accepted Answer

What I'm trying to figure out is if the "nc := NodeChildren..." line causes a >memory allocation each time the function is called?

Sì. Ogni volta che si chiama la funzione FindNode (), nc: = verrà assegnato a una nuova struttura che vive in un nuovo blocco di memoria rispetto alla struttura creata dalla chiamata della funzione precedente. Il modo in cui questo impatto influisce sulle prestazioni dipende dal numero di volte in cui si chiama tale funzione (in un ciclo stretto creerà un sacco di spazzatura da occuparsi di e richiede l'allocazione della memoria ogni volta che si raggiunge la quantità di memoria durante l'ultimo periodo di allocazione. 2mb - > 4mb - > 8mb- > 16mb, ect) Fino a quando il garbage collector viene eseguito, questi mbs possono sommarsi per oggetti che non sono più raggiungibili.

In caso affermativo, posso / devo spostare la dichiarazione nello scope globale e modificare semplicemente i valori ogni volta che viene chiamata questa funzione? O c'è un modo più efficiente per farlo?

Quello che vorrei fare è creare una sezione per contenere i puntatori del nodo

var nc [4]*Node

func FindNode(ul, ur, ll, lr *Node) *Node {
        var node *Node
        var ok bool
        nc[0] = ul; nc[1] = ur 
        nc[2] = ll; nc[3] = lr

        node, ok = NodeMap[nc] //change struct logic to slice logic
                               //i.e nc.ul -> nc[0], ect
        if ok {
                return node
        }
        node = &Node{ul, ur, ll, lr, 0, ul.Level + 1, nil}

        //why hash this with an index to a type that wont exist later?
        NodeMap[nc] = node
        return node
}