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

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 9, 2013, 23:37 UTC
Message-ID: <7vehcan9e0.fsf@alter.siamese.dyndns.org>
In-Reply-To: <1370820277-30158-4-git-send-email-gitster@pobox.com>

Junio C Hamano <gitster@pobox.com> writes:

Show 11 quoted lines

> 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).