Re: [RFC PATCH] Fix quadratic performance in rewrite_one.

From: Alexander Gavrilov <angavrilov@gmail.com>
Date: Jul 13, 2008, 00:37 UTC
Message-ID: <200807130437.59141.angavrilov@gmail.com>
In-Reply-To: <alpine.LFD.1.10.0807121550320.2959@woody.linux-foundation.org>

On Sunday 13 July 2008 02:55:27 Linus Torvalds wrote:

Show 8 quoted lines

> On Sat, 12 Jul 2008, Alexander N. Gavrilov wrote:
> > Parent commits are usually older than their children. Thus,
> > on each iteration of the loop in rewrite_one, add_parents_to_list
> > traverses all commits previously processed by the loop.
> > It performs very poorly in case of very long rewrite chains.
>
> Good call, but you don't seem to invalidate the cache when we remove
> things from the list.

The cache is local to rewrite_one, and is invalidated by exiting from that function. Other users of add_parents_to_list just pass NULL as cache_ptr, thus causing insert_by_date_cached to degenerate into a simple insert_by_date.

> The top of the limit_list() loop does that "get top entry from list, an
> free it", and I'm not seeing you invalidating the cache if that entry that
> just got free'd happened to be the cache entry?

This type of workflow can be expected to keep the list relatively short (roughly limited by the number of simultaneously existing branches); and if it is already long, new entries will probably be added near the beginning anyway, so there doesn't seem to be any need to use caching.

rewrite_one() is special in that it can sometimes walk through thousands of commits at once and put them all into the list -- i.e. it is bound not by the width of the history, but by its length.

Alexander