Re: [PATCH v2 3/4] sort-in-topological-order: use commit-queue

2013-06-10 Thread Jeff King
On Mon, Jun 10, 2013 at 12:27:31AM -0700, Junio C Hamano wrote: > > Around the same time, though, René wrote the linked-list merge sort that > > powers commit_list_sort_by_date. And topo-sort learned to do O(1) > > insertions into the unsorted list, and then one O(n log n) sort. > > Yes, but that

Re: [PATCH v2 3/4] sort-in-topological-order: use commit-queue

2013-06-10 Thread Junio C Hamano
Jeff King writes: > The performance enhancement of the priority queue came from replacing > "commit_list_insert_by_date" calls with insertion into a queue. That > drops O(n^2) behavior on the linked-list down to O(n log n), as we have > "n" insertions, each causing an O(log n) heapify operation.

Re: [PATCH v2 3/4] sort-in-topological-order: use commit-queue

2013-06-09 Thread Jeff King
On Sun, Jun 09, 2013 at 04:37:27PM -0700, Junio C Hamano wrote: > Junio C Hamano writes: > > > Use the commit-queue data structure to implement a priority queue > > of commits sorted by committer date, when handling --date-order. > > The commit-queue structure can also be used as a simple LIFO s

Re: [PATCH v2 3/4] sort-in-topological-order: use commit-queue

2013-06-09 Thread Junio C Hamano
Junio C Hamano writes: > Use the commit-queue data structure to implement a priority queue > of commits sorted by committer date, when handling --date-order. > The commit-queue structure can also be used as a simple LIFO stack, > which is a good match for --topo-order processing. > > Signed-off-b

[PATCH v2 3/4] sort-in-topological-order: use commit-queue

2013-06-09 Thread Junio C Hamano
Use the commit-queue data structure to implement a priority queue of commits sorted by committer date, when handling --date-order. The commit-queue structure can also be used as a simple LIFO stack, which is a good match for --topo-order processing. Signed-off-by: Junio C Hamano --- commit-queue