Re: [PATCH 0/2] History replay support

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Nov 3, 2007, 01:40 UTC
Message-ID: <alpine.LFD.0.999.0711021809060.3342@woody.linux-foundation.org>
In-Reply-To: <alpine.LFD.0.999.0711021301200.3342@woody.linux-foundation.org>

On Fri, 2 Nov 2007, Linus Torvalds wrote:

> 
> The bad news is that it doesn't work well in this simplistic form, because 
> there is a O(n**2) behaviour when replays *do* happen, ie we end up having 
> replays within replays [..]

Gaah. the more I look at this, the more I think the topo sort should be done at the visualization side.

It's really quite cheap to do the topo sort, *and* it's really quite cheap to do the tests that trigger the topo sort, but what's expensive is to re-output all the data again!

The silly thing is, I think I've come up with an "almost optimal" solution, but it's so ugly that I'm a bit ashamed of it.

That almost optimal solution is simply:
 - get the first <n> (say: 100) commits, and topo-sort just them. Feed it 
   to the visualizer.
 - the visualizer will now have enough to work with in order to show the 
   starting screen and set the cursor to the hourglass or whatever the 
   "wait for it" thing is.
 - get the rest of the commits at our normal leisurely pace (whether it 
   is one second of 17).
 - output the total number of commits (so that the visualizer can re-size 
   the slider and/or allocate some big array just once), topo-sort it all, 
   and output the full thing.

It's disgusting. But it avoids the unnecessary data transfer - except for just the first 100 commits that get sent twice. And it gets what *I* look for, namely that "immediate" feel to the initial pop-up of the history.

			Linus