Re: [PATCH 1/3] commit: convert pop_most_recent_commit() to prio_queue

> 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/

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

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

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