From: Junio C Hamano <gitster@pobox.com>
Date: Mon, 09 Apr 2012 19:46:50 GMT
Subject: Re: rs/commit-list-sort-in-batch
Message-ID: <7vty0svgb9.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20120407073232.GA13076@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

> I'm not sure if that vindicates the patches, or implies that these
> things are lurking everywhere and that we should really move to a better
> data structure so we don't have to fix them all manually. :)

;-).

I do not know offhand how widespread the assumption of "list"-ness of the
commit_list is in the codebase.  The last time I looked at it was when I
was wondering if we could give a custom allocator to "struct commit_list",
as we seemed to liberally malloc()/free() quite many of them, with the
hope to reduce memory footprint, but I didn't finish it, so...

But at least inside revision walking machinery, your earlier heap based
implementation to optimize for time based priority queue access pattern
looked a very sensible approach to me.