linearizzazione incrementale di git DAG

Question

Sono l'autore di GitX . Una delle caratteristiche GitX ha è la visualizzazione di rami, come si può vedere qui .

Questa visualizzazione è attualmente fa leggendo commit che sono emessi da Git nell'ordine corretto. Per ogni commettono i genitori sono noti, quindi è abbastanza facile da costruire le corsie in modo corretto.

Mi piacerebbe accelerare questo processo utilizzando la mia commettere piscina e linearizzazione i commit me stesso. Questo mi permette di riutilizzare commit caricati esistente e consente git per emettere i commit più veloce perché non ha bisogno di emettere essi nel giusto ordine.

Tuttavia, io non sono sicuro di cosa algoritmo da utilizzare per raggiungere questo obiettivo. E 'importante che l'edificio è incrementale, come il caricamento di commit può richiedere molto tempo (> 5 secondi per 100.000 commit, che dovrebbero essere tutti visualizzati).

Gitk è andata allo stesso modo, e c'è una patch qui che mostra come è implementato, ma le mie capacità TCL sono deboli e la patch non è molto accuratamente commentato e un po 'difficile da seguire.

Mi piacerebbe anche questo algoritmo per essere efficiente, in quanto dovrà gestire centinaia di migliaia di commit. Ha anche essere visualizzati in una tabella, quindi è importante che l'accesso alle righe specifiche è veloce.

Descriverò l'input che ho finora, l'output che voglio e alcune osservazioni.

Input:

• Ho un pool corrente di commit, sotto forma di una tabella di hash che mappa impegnarsi id a commettere gli oggetti. Questa piscina non deve essere completa (hanno tutti i commit necessario)
• Ho un carico thread separato in nuovi impegna da git, con un callback che può essere chiamato ogni volta che un nuovo commit viene caricato. Non c'è un ordine garantito in cui i commit entrare, ma nella maggior parte dei casi il prossimo commit è un genitore del precedente commit.
• A commettere oggetto ha un proprio ID di revisione e gli ID di revisione di tutti i suoi genitori
• Ho una lista dei responsabili di filiali che dovrebbero essere elencati. Cioè, non c'è un unico 'top' del DAG che dovrebbe essere visualizzato. C'è, inoltre, non deve essere un singola radice grafico.

Output:

• Ho bisogno di linearizzare questi impegna in ordine topologico. Cioè, un commit non possono essere elencati dopo che i suoi genitori sono stati elencati.
• Ho anche bisogno le 'diramazioni' che si possono vedere nello screenshot qui sopra. Questi probabilmente bisogno di essere precalcolate come la maggior parte di essi dipendono i loro figli.

A poche osservazioni:

• E 'necessario spostare un elenco di commit. Ad esempio, potremmo avere a impegna (responsabili di filiali) che non sono collegati, fino a quando un commit rivela che lo rende una testa un antenato dell'altro.
• Più punte dei rami devono essere evidenziate
• È importante che questo processo è incrementale, in modo che almeno una vista parziale è disponibile, mentre i dati ancora carico. Ciò significa che i nuovi dati deve essere inserita a metà strada e che le diramazioni devono essere riadattato.

Answer 1

Il topologica sorta è O (n) (OK, O (V + E )), per esempio, si dovrebbe essere in grado di ordinare un milione impegna in memoria in una frazione di secondo. Non è necessario alcun mod incrementale come quelle di Tcl.

A proposito, io uso GitX (sembra molto meglio di Gitk su OS X) tutti i giorni e non ho alcun problema con esso (forse perché non ho quei folli fonde nei miei repository):)

Answer 2

OK, quindi sto avendo un momento simile difficoltà a leggere la totalità di quella patch, ma vediamo se riesco a piece insieme da quello che ho fatto capire.

Per cominciare, gitk semplifica le cose condensando una serie di commit in un arco, che contiene una serie di commit che hanno ciascuno un solo genitore e un bambino. A parte ogni altra cosa, a fare questo dovrebbe ridurre abbastanza drasticamente il numero di nodi si devono prendere in considerazione per l'ordinamento, che contribuirà a qualsiasi algoritmo che si usa. Come bonus, commit relativi finiranno raggruppati insieme.

Questo fa introdurre una certa complessità in termini di trovare un arco quando si legge un nuovo commit. Ci sono alcune situazioni:

• Il nuovo commit ha un solo genitore, o senza genitori. Si estende un arco (possibilmente vuoto). La maggior parte del tempo, ti basta estendere l'arco più recente. Ci sono alcuni sottocasi interessanti:
  • Può causare un arco esistente da dividere, se il suo genitore ha già un figlio (vale a dire la sua genitore si rivela essere un punto di diramazione, che mi sembra di capire che non sai in anticipo).
  • Potrebbe essere un "anello mancante" che collega due archi insieme.
  • Si può già sapere che questo commettono ha più figli
• Il nuovo impegno ha più i genitori (una fusione commit).

Si consiglia di includere il multi-figlio o multi-genitore impegna in archi, o può avere più senso per tenerli separati. In entrambi i casi, non dovrebbe essere troppo difficile da costruire questo insieme di archi in modo incrementale.

Una volta che avete questi archi, si sta ancora a sinistra con il tentativo di linearizzare loro. Nel tuo caso, il primo algoritmo descritto nella citata pagina di Wikipedia suona utile, come si avere un insieme noto di punti di diramazione da utilizzare come set iniziale S.

Altre note:

• commit Rilocazione dovrebbe essere gestibile. Prima di tutto, hai solo per la cura quando si collegano due archi, sia attraverso una nuova merge commit, un punto di diramazione scoperta di recente, o combinando due archi in una sola. Un dato arco può facilmente mantenere la sua gamma di numero di riga corrente (supponendo che si sta bene con la messa un arco su file sequenziali), in modo da attraversare l'albero di verificare che tutti i nuovi antenati mostrano più tardi dovrebbe essere abbastanza veloce.
• Non so abbastanza per dire molto su disegnare le linee del grafico, ma immagino che non sarà troppo diverso da quello che fai ora.

In ogni caso, spero che aiuta. E 'stato interessante a cui pensare, almeno.

Answer 3

Avete veramente bisogno di visualizzare 100k impegna in una volta? Che tipo di utente può assorbire questo tipo di informazioni?

Hai pensato di paging? Cioè solo calcolare per ~ 100 commit o qualcosa del genere. Se un ramo-line viene da lontano (off-page), si potrebbe usare qualcosa come freccia indietro che punta di Github per dimostrare che.

Answer 4

Non ho usato GitX, quindi forse mi manca qualcosa, ma sembra che si possa tornare indietro da bambino a genitore (s) dalla testa di ogni ramo corrente fino a quando è possibile disegnare un paio di schermate del grafico .

Non si potrebbe dare il layout visivo ottimale di rami che sono radicati in precedenza. Ma sembra che la risposta sarebbe più importante che in attesa di tracciare un grafico con gli incroci più basso dal momento che la maggior parte degli utenti sono suscettibili di essere interessati a recenti attività.