Re: [GSoC] Designing a faster index format

From: Junio C Hamano <gitster@pobox.com>
Date: Mar 26, 2012, 21:14 UTC
Message-ID: <7vd37znjyo.fsf@alter.siamese.dyndns.org>
In-Reply-To: <2A61C352-5C71-4EDF-9DBE-01CC09AE03A5@gmail.com>

Thomas Gummerer <t.gummerer@gmail.com> writes:

Show 7 quoted lines

> The proposed solution is to rework the index, in order to make it possible to
> have a complexity of O(log(n)), where n is the number of index entries, for 
> simple operations like adding files. More complex operations shall also
> benefit from the new index format, although a complexity of O(log(n)) might not
> be reached, while keeping the index format easy enough to parse for .git reading
> programs. The amount of data for which that the hash will be computed however
> shall be log(n). N is the number of entries in the index.

Where does log(N) come from, and is that a hard requirement?

Rephrasing your problem description, you want to address the inefficiency that we have to write the full 1m entries to a new file in order to update only one file when the index tracks 1m paths.

Wouldn't the goal be more in line with that problem statement if you instead aim to make the cost proportional to the number of entries that are updated, regardless of how many entries exist in the index?

Show 6 quoted lines

> In phase one the pysical index format shall be replaced with the new index 
> format, which does neither require a full recalculation of the sha-1 hash nor a
> full rewrite of the index to the disk. The new index format will be mapped to 
> the current in-memory structure, which will only be changed in phase two. For 
> further optimization the cache-tree sha-1 hashes shall be mapped to the new 
> index format, which should avoid cache-tree invalidations.

It is unclear what you meant by the last sentence. The cache-tree invalidation is a critical part of the machinery that allows later write-tree to reuse the already computed subtree object names, without having to recompute subtree object names until they are really necessary (i.e. when writing a tree out). By "avoiding" it, are you going to make write-tree always recompute all the subtree object names? Or are you planning to keep the cached tree information always up to date by recomputing subtree object names and keeping them in the index even when they are not yet needed? If the latter, how would you handle when a part of the index contains unmerged entries?

Right now, the code that updates the in-core index records "Is the in-core index clean, or modified?" bit and nothing else. Without updating the in-core structure and the codepaths that access it, how is it possible for your phase I to selectively write out only the modified (either added, updated or removed) part of it? In other words, I do not think it is realistic to expect that the core parts to stay oblivious to the new index semantics during the "phase one".

> -- Timeline --
> 24/04 - 12/05: Getting familiar with the old index

It might make more sense to write the "proposed solution" *after* this step is done; otherwise you wouldn't even know the problems you are trying to solve. That may mean that this part of the schedule may need to be shortened or started way before the beginning of GSoC.