Re: [PATCH 1/2] blame: large-scale performance rewrite

> Shawn Pearce <spearce@spearce.org> writes:
>
>> On Fri, Apr 25, 2014 at 4:56 PM, David Kastrup <dak@gnu.org> wrote:
>>> The previous implementation used a single sorted linear list of blame
>>> entries for organizing all partial or completed work.  Every subtask had
>>> to scan the whole list, with most entries not being relevant to the
>>> task.  The resulting run-time was quadratic to the number of separate
>>> chunks.
>>>
>>> This change gives every subtask its own data to work with.  Subtasks are
>>> organized into "struct origin" chains hanging off particular commits.
>>> Commits are organized into a priority queue, processing them in commit
>>> date order in order to keep most of the work affecting a particular blob
>>> collated even in the presence of an extensive merge history.
>>
>> Without reading the code, this sounds like how JGit runs blame.
>>
>>> For large files with a diversified history, a speedup by a factor of 3
>>> or more is not unusual.
>>
>> And JGit was already usually slower than git-core. Now it will be even
>> slower! :-)
>
> If your statement about JGit is accurate, it should likely have beat Git
> for large use cases (where the performance improvements are most
> important) as O(n) beats O(n^2) in the long run.

> Apart from the objective measurement of "total time", the more
> subjective impression of interactive/incremental response (like in git
> gui blame) where the order of results will significantly differ (current
> git-blame --incremental focuses on getting blames resolved in
> first-lines-first manner, the proposed git-blame rather works on a
> newest-commits-first basis which might better match typical use cases)
> might be worth reporting.