On Tue, Aug 28, 2007 at 11:03:22AM +0100, Johannes Schindelin wrote: > 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@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
