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

From: Jeff King <peff@peff.net>
Date: Jun 10, 2013, 05:31 UTC
Message-ID: <20130610053059.GE3621@sigill.intra.peff.net>
In-Reply-To: <7vehcan9e0.fsf@alter.siamese.dyndns.org>

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

Show 31 quoted lines

> Junio C Hamano <gitster@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 <gitster@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).

-Peff