On 7/15/25 10:47 PM, Justin Tobler wrote: > On 25/07/15 04:51PM, René Scharfe wrote: >> pop_most_recent_commit() calls commit_list_insert_by_date(), which and > > Did you mean? > > s/which and/which/ Oh, yes. >> is itself called in a loop, which can lead to quadratic complexity. >> Replace the commit_list with a prio_queue to ensure logarithmic worst >> case complexity and convert all three users. > > If I understand correctly, `pop_most_recent_commit()` removes the most > recent commit from a list of commits sorted by date and then inserts > each of the removed commit's parents into the list while maintaining > date order. Iterating through `struct commit_list` every time to find > where to insert each parent parent leads to quadratic complexity. For > repositories with many merge commits, this could scale poorly. Right. >> Add a performance test that exercises one of them using a pathological >> history that consists of 50% merges and 50% root commits to demonstrate >> the speedup: >> >> Test v2.50.1 HEAD >> ---------------------------------------------------------------------- >> 1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9% >> >> Alas, sane histories don't benefit from the conversion much, and >> traversing Git's own history takes a 1% performance hit on my machine: > > As "normal" repositories don't benefit here, it might be nice to more > explicitly mention the the types of repositories that do benefit. Good idea. >> diff --git a/commit.h b/commit.h >> index 70c870dae4..9630c076d6 100644 >> --- a/commit.h >> +++ b/commit.h >> @@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r, >> >> const char *skip_blank_lines(const char *msg); >> >> -/** Removes the first commit from a list sorted by date, and adds all >> - * of its parents. >> - **/ >> -struct commit *pop_most_recent_commit(struct commit_list **list, >> +struct prio_queue; >> + >> +/* Removes the first commit from a prio_queue and adds its parents. */ >> +struct commit *pop_most_recent_commit(struct prio_queue *queue, >> unsigned int mark); > > Previously, `pop_most_recent_commit()` would ensure commits inserted in > the list were done it date order. Now this depends on how the caller has > configured the `struct prio_queue`. This is fine though as previously > the caller was required to ensure the list was sorted to begin with > otherwise it wouldn't work properly. Indeed. René
