[PATCH 1/2] describe: use prio_queue

[PATCH 1/2] describe: use prio_queue

[René Scharfe]

Replace the use a list-based priority queue whose order is maintained by
commit_list_insert_by_date() with a prio_queue.  This avoids quadratic
worst-case complexity.  And in the somewhat contrived example of
describing the 4751 commits from v2.41.0 to v2.47.0 in one go (to get a
sizable chunk of describe work with minimal ref loading overhead) it's
significantly faster:

Benchmark 1: ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):      1.558 s ±  0.002 s    [User: 1.492 s, System: 0.051 s]
  Range (min … max):    1.557 s …  1.562 s    10 runs

Benchmark 2: ./git describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):      1.209 s ±  0.006 s    [User: 1.143 s, System: 0.051 s]
  Range (min … max):    1.201 s …  1.219 s    10 runs

Summary
  ./git describe $(git rev-list v2.41.0..v2.47.0) ran
    1.29 ± 0.01 times faster than ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/describe.c | 51 ++++++++++++++++++++++++----------------------
 1 file changed, 27 insertions(+), 24 deletions(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index fbf305d762..80722ae0c0 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -23,6 +23,7 @@
 #include "list-objects.h"
 #include "commit-slab.h"
 #include "wildmatch.h"
+#include "prio-queue.h"
 
 #define MAX_TAGS	(FLAG_BITS - 1)
 #define DEFAULT_CANDIDATES 10
@@ -249,24 +250,26 @@ static int compare_pt(const void *a_, const void *b_)
 	return 0;
 }
 
-static unsigned long finish_depth_computation(
-	struct commit_list **list,
-	struct possible_tag *best)
+static bool all_have_flag(const struct prio_queue *queue, unsigned flag)
+{
+	for (size_t i = 0; i < queue->nr; i++) {
+		struct commit *commit = queue->array[i].data;
+		if (!(commit->object.flags & flag))
+			return false;
+	}
+	return true;
+}
+
+static unsigned long finish_depth_computation(struct prio_queue *queue,
+					      struct possible_tag *best)
 {
 	unsigned long seen_commits = 0;
-	while (*list) {
-		struct commit *c = pop_commit(list);
+	while (queue->nr) {
+		struct commit *c = prio_queue_get(queue);
 		struct commit_list *parents = c->parents;
 		seen_commits++;
 		if (c->object.flags & best->flag_within) {
-			struct commit_list *a = *list;
-			while (a) {
-				struct commit *i = a->item;
-				if (!(i->object.flags & best->flag_within))
-					break;
-				a = a->next;
-			}
-			if (!a)
+			if (all_have_flag(queue, best->flag_within))
 				break;
 		} else
 			best->depth++;
@@ -274,7 +277,7 @@ static unsigned long finish_depth_computation(
 			struct commit *p = parents->item;
 			repo_parse_commit(the_repository, p);
 			if (!(p->object.flags & SEEN))
-				commit_list_insert_by_date(p, list);
+				prio_queue_put(queue, p);
 			p->object.flags |= c->object.flags;
 			parents = parents->next;
 		}
@@ -316,7 +319,7 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf
 static void describe_commit(struct object_id *oid, struct strbuf *dst)
 {
 	struct commit *cmit, *gave_up_on = NULL;
-	struct commit_list *list;
+	struct prio_queue queue = { compare_commits_by_commit_date };
 	struct commit_name *n;
 	struct possible_tag all_matches[MAX_TAGS];
 	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
@@ -359,11 +362,10 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 		have_util = 1;
 	}
 
-	list = NULL;
 	cmit->object.flags = SEEN;
-	commit_list_insert(cmit, &list);
-	while (list) {
-		struct commit *c = pop_commit(&list);
+	prio_queue_put(&queue, cmit);
+	while (queue.nr) {
+		struct commit *c = prio_queue_get(&queue);
 		struct commit_list *parents = c->parents;
 		struct commit_name **slot;
 
@@ -397,7 +399,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 				t->depth++;
 		}
 		/* Stop if last remaining path already covered by best candidate(s) */
-		if (annotated_cnt && !list) {
+		if (annotated_cnt && !queue.nr) {
 			int best_depth = INT_MAX;
 			unsigned best_within = 0;
 			for (cur_match = 0; cur_match < match_cnt; cur_match++) {
@@ -420,7 +422,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 			struct commit *p = parents->item;
 			repo_parse_commit(the_repository, p);
 			if (!(p->object.flags & SEEN))
-				commit_list_insert_by_date(p, &list);
+				prio_queue_put(&queue, p);
 			p->object.flags |= c->object.flags;
 			parents = parents->next;
 
@@ -435,6 +437,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 			strbuf_add_unique_abbrev(dst, cmit_oid, abbrev);
 			if (suffix)
 				strbuf_addstr(dst, suffix);
+			clear_prio_queue(&queue);
 			return;
 		}
 		if (unannotated_cnt)
@@ -450,11 +453,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 	QSORT(all_matches, match_cnt, compare_pt);
 
 	if (gave_up_on) {
-		commit_list_insert_by_date(gave_up_on, &list);
+		prio_queue_put(&queue, gave_up_on);
 		seen_commits--;
 	}
-	seen_commits += finish_depth_computation(&list, &all_matches[0]);
-	free_commit_list(list);
+	seen_commits += finish_depth_computation(&queue, &all_matches[0]);
+	clear_prio_queue(&queue);
 
 	if (debug) {
 		static int label_width = -1;
-- 
2.50.1

[PATCH 2/2] describe: use prio_queue_replace()

[René Scharfe]

Optimize the sequence get+put to peek+replace to avoid one unnecessary
heap rebalance.

Do that by tracking partial get operations in a prio_queue wrapper,
struct lazy_queue, and using wrapper functions that turn get into peek
and put into replace as needed.  This is simpler than tracking the
state explicitly in the calling code.

We get a nice speedup on top of the previous patch's conversion to
prio_queue:

Benchmark 1: ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):      1.559 s ±  0.002 s    [User: 1.493 s, System: 0.051 s]
  Range (min … max):    1.556 s …  1.563 s    10 runs

Benchmark 2: ./git_describe_pq describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):      1.204 s ±  0.001 s    [User: 1.138 s, System: 0.051 s]
  Range (min … max):    1.202 s …  1.205 s    10 runs

Benchmark 3: ./git describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     850.9 ms ±   1.6 ms    [User: 786.6 ms, System: 49.8 ms]
  Range (min … max):   849.1 ms … 854.1 ms    10 runs

Summary
  ./git describe $(git rev-list v2.41.0..v2.47.0) ran
    1.41 ± 0.00 times faster than ./git_describe_pq describe $(git rev-list v2.41.0..v2.47.0)
    1.83 ± 0.00 times faster than ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)

Signed-off-by: René Scharfe <l.s.r@web.de>
---
A more convincing showcase for that optimization than a79e3519d6
(commit: use prio_queue_replace() in pop_most_recent_commit(),
2025-07-18).

 builtin/describe.c | 68 +++++++++++++++++++++++++++++++++++-----------
 1 file changed, 52 insertions(+), 16 deletions(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index 80722ae0c0..c18e4b3e4b 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -250,22 +250,58 @@ static int compare_pt(const void *a_, const void *b_)
 	return 0;
 }
 
-static bool all_have_flag(const struct prio_queue *queue, unsigned flag)
+struct lazy_queue {
+	struct prio_queue queue;
+	bool get_pending;
+};
+
+#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false }
+
+static void *lazy_queue_get(struct lazy_queue *queue)
+{
+	if (queue->get_pending)
+		prio_queue_get(&queue->queue);
+	else
+		queue->get_pending = true;
+	return prio_queue_peek(&queue->queue);
+}
+
+static void lazy_queue_put(struct lazy_queue *queue, void *thing)
+{
+	if (queue->get_pending)
+		prio_queue_replace(&queue->queue, thing);
+	else
+		prio_queue_put(&queue->queue, thing);
+	queue->get_pending = false;
+}
+
+static bool lazy_queue_empty(const struct lazy_queue *queue)
+{
+	return queue->queue.nr == (queue->get_pending ? 1 : 0);
+}
+
+static void lazy_queue_clear(struct lazy_queue *queue)
+{
+	clear_prio_queue(&queue->queue);
+	queue->get_pending = false;
+}
+
+static bool all_have_flag(const struct lazy_queue *queue, unsigned flag)
 {
-	for (size_t i = 0; i < queue->nr; i++) {
-		struct commit *commit = queue->array[i].data;
+	for (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {
+		struct commit *commit = queue->queue.array[i].data;
 		if (!(commit->object.flags & flag))
 			return false;
 	}
 	return true;
 }
 
-static unsigned long finish_depth_computation(struct prio_queue *queue,
+static unsigned long finish_depth_computation(struct lazy_queue *queue,
 					      struct possible_tag *best)
 {
 	unsigned long seen_commits = 0;
-	while (queue->nr) {
-		struct commit *c = prio_queue_get(queue);
+	while (!lazy_queue_empty(queue)) {
+		struct commit *c = lazy_queue_get(queue);
 		struct commit_list *parents = c->parents;
 		seen_commits++;
 		if (c->object.flags & best->flag_within) {
@@ -277,7 +313,7 @@ static unsigned long finish_depth_computation(struct prio_queue *queue,
 			struct commit *p = parents->item;
 			repo_parse_commit(the_repository, p);
 			if (!(p->object.flags & SEEN))
-				prio_queue_put(queue, p);
+				lazy_queue_put(queue, p);
 			p->object.flags |= c->object.flags;
 			parents = parents->next;
 		}
@@ -319,7 +355,7 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf
 static void describe_commit(struct object_id *oid, struct strbuf *dst)
 {
 	struct commit *cmit, *gave_up_on = NULL;
-	struct prio_queue queue = { compare_commits_by_commit_date };
+	struct lazy_queue queue = LAZY_QUEUE_INIT;
 	struct commit_name *n;
 	struct possible_tag all_matches[MAX_TAGS];
 	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
@@ -363,9 +399,9 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 	}
 
 	cmit->object.flags = SEEN;
-	prio_queue_put(&queue, cmit);
-	while (queue.nr) {
-		struct commit *c = prio_queue_get(&queue);
+	lazy_queue_put(&queue, cmit);
+	while (!lazy_queue_empty(&queue)) {
+		struct commit *c = lazy_queue_get(&queue);
 		struct commit_list *parents = c->parents;
 		struct commit_name **slot;
 
@@ -399,7 +435,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 				t->depth++;
 		}
 		/* Stop if last remaining path already covered by best candidate(s) */
-		if (annotated_cnt && !queue.nr) {
+		if (annotated_cnt && lazy_queue_empty(&queue)) {
 			int best_depth = INT_MAX;
 			unsigned best_within = 0;
 			for (cur_match = 0; cur_match < match_cnt; cur_match++) {
@@ -422,7 +458,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 			struct commit *p = parents->item;
 			repo_parse_commit(the_repository, p);
 			if (!(p->object.flags & SEEN))
-				prio_queue_put(&queue, p);
+				lazy_queue_put(&queue, p);
 			p->object.flags |= c->object.flags;
 			parents = parents->next;
 
@@ -437,7 +473,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 			strbuf_add_unique_abbrev(dst, cmit_oid, abbrev);
 			if (suffix)
 				strbuf_addstr(dst, suffix);
-			clear_prio_queue(&queue);
+			lazy_queue_clear(&queue);
 			return;
 		}
 		if (unannotated_cnt)
@@ -453,11 +489,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 	QSORT(all_matches, match_cnt, compare_pt);
 
 	if (gave_up_on) {
-		prio_queue_put(&queue, gave_up_on);
+		lazy_queue_put(&queue, gave_up_on);
 		seen_commits--;
 	}
 	seen_commits += finish_depth_computation(&queue, &all_matches[0]);
-	clear_prio_queue(&queue);
+	lazy_queue_clear(&queue);
 
 	if (debug) {
 		static int label_width = -1;
-- 
2.50.1