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

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 10, 2013, 07:27 UTC
Message-ID: <7vsj0ql924.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20130610053059.GE3621@sigill.intra.peff.net>

Jeff King <peff@peff.net> 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.

Yes.

> 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 only affects the "sort the work queue in date order" before entering the main loop, and maintenance of work queue as we dig along still is "find the place to put this in the date-order sorted linked list", no?

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

I've been disturbed every time I saw the commit_list insertion function that does a small allocation which will be freed fairly often and have been wondering if we can rewrite it with custom slab allocator, but not using linked list where we do not have to feels like a better solution to that issue, and use of pqueue may be a right direction to go in.