On Tue, Aug 28, 2007 at 11:03:22AM +0100, Johannes Schindelin wrote:

quoted text
> But then, we could spare even more space when not using an array, but a 
> linked list for the generation numbers...  It is a small performance 
> impact, but in reality it will not matter, methinks.

Hrm. I was puzzled at first by what you meant, and then I thought about
some more, and came up with this. Which is perhaps what you intended all
along, or maybe not.

We are going to store the same prefixes over and over again. For
example, when storing v2.6.22-rc1~1038^2~20^2~5, we can consider the
sequence (1/1038, 2/20, 2/5). There are likely to be many nearby commits
sharing 1/1038, and a few sharing 2/20.

We can't make a linked list in the forward direction, since the '1/1038'
will go to many suffixes. But if we start our list backwards, like:

 2/5 -> 2/20 -> 1/1038 -> v2.6.22-rc1

then I think we can get away with just allocating the head of the list,
and pointing to the rest.

I'm not sure if this would be a net win, though. We incur one pointer
per merge traversal. And moreover, when we come up with a better name
for a rev, we can't just deallocate the old one since it might be in use
by other revs.

Unless, perhaps, rather than allocating list pointers, each commit just
got a name and a 'next commit'. So if I have decided that a commit's
best name is foo~20, and another commit points to it with information
'parent 2, generation 10', then I know that it's foo~20^2~10. And if
foo~20 gets a better name, we will automatically pick that up.

Hmm. I think we could reduce memory usage quite a bit. But now rev_names
would be much more expensive (since we would have to follow the list to
its beginning just to see how two names compare!).

So perhaps this isn't worth it at all, and just a simple dynamic array
is a better bet.

-Peff
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html