On Sun, Jun 09, 2013 at 04:37:27PM -0700, Junio C Hamano wrote:

> Junio C Hamano <gits...@pobox.com> 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-by: Junio C Hamano <gits...@pobox.com>
> > ---
> >  commit-queue.c | 13 +++++++++++
> >  commit-queue.h |  3 +++
> >  commit.c       | 74 
> > ++++++++++++++++++++++++++++++++++------------------------
> >  3 files changed, 59 insertions(+), 31 deletions(-)
> Peff, I think you were the one who did a priority queue previously,
> primarily for performance.  The primary reason for this round was so
> that I didn't have to touch the revision.c and struct commit in
> order to sort by keys in commit-info-slabs and I was not aiming for
> performance but a quick and rough benchmarking seems to indicate
> that
>  - for a small repository like git.git, there is not much difference
>    in runtime;
>  - but it does seem to cut down the memory pressure (less minor
>    faults).
> Representative runs of "rev-list --date-order v0.99..v1.8.3" on my
> box with 'master' and with these patches spend 0.47user/0.04system
> with 0.50elapsed (no time change), with 13450 vs 13108 minor faults
> (smaller memory use).

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.

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.

So your results are exactly what I would expect: the time should be
about the same (due to the same complexity), but the memory is used more
compactly (array of pointers instead of linked list of pointers).

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to