Re: git and larger trees, not so fast?

Linus Torvalds <torvalds@linux-foundation.org> writes:

[...]

Ok, preaching to the pope here, but: moving memory is bad. Make sure data can stay where it starts. In particular: don't use realloc. And if you do, grow the size _exponentially_ (like a factor of 1.5). If you grow the size exponentially, at least the movery hits the algorithm with O(n lg n). If data stays put, even in badly scattered linear lists, we have O(n). If you grow realloc _linearly_ (constant size increment), then the algorithm is hit with O(n^2).

Technically, basically _all_ operations of git can be done by doing list merges of presorted lists. The index can be kept sorted. All requests into the index can be collected in readdir order into one linear list, this gets sorted once using a merge sort with O(n lg n), then it gets merged with the index O(n+N). As long as the whole index is read in, it can't be done faster. It is not necessary to organize the read data into trees or more complicate structures: a single linear list is sufficient. One can use the hierarchical structure of a directory to shave off some part of the sorting cost, though, and it considerably will lessen memory impact (and copying costs) if a file/directory/tree entry can contain a relative file name and a "pointer to prefix" where the rest of the file path is to be found.

Anyway, so much for some theory. Now let's look at bad points in the code, judging from your benchmarks.

A grep for realloc is appaling. Let's see what is actually involved here.

attr.c:

struct git_attr *git_attr(const char *name, int len) {

	a->attr_nr = attr_nr++;
	git_attr_hash[pos] = a;

	check_all_attr = xrealloc(check_all_attr,
				  sizeof(*check_all_attr) * attr_nr);

[...]

Full O(n^2) behavior of the worst kind (increment 1!).

builtin-commit-tree.c:

static void add_buffer(char **bufp, unsigned int *sizep, const char *fmt, ...)
{
	size = *sizep;
	newsize = size + len + 1;
	alloc = (size + 32767) & ~32767;

[size rounded to next 32k (inconsistent! needs to be size+1 rounded up)]

	buf = *bufp;
	if (newsize > alloc) {
		alloc = (newsize + 32767) & ~32767;

[newsize rounded to next 32k]

		buf = xrealloc(buf, alloc);

[O(n^2): constant increment.  Important?  No idea.]

		*bufp = buf;
	}
	*sizep = newsize - 1;

	memcpy(buf + size, one_line, len);
}

[...]

int register_commit_graft(struct commit_graft *graft, int ignore_dups) {

[...]
	if (commit_graft_alloc <= ++commit_graft_nr) {
		commit_graft_alloc = alloc_nr(commit_graft_alloc);
		commit_graft = xrealloc(commit_graft,
					sizeof(*commit_graft) *
					commit_graft_alloc);
	}
	if (pos < commit_graft_nr)
		memmove(commit_graft + pos + 1,
			commit_graft + pos,
			(commit_graft_nr - pos - 1) *
			sizeof(*commit_graft));
	commit_graft[pos] = graft;
	return 0;
}

Eeek.  Start with a linear list, not an array.

objects.c:

void add_object_array_with_mode(struct object *obj, const char *name, struct object_array *array, unsigned mode)
{
	unsigned nr = array->nr;
	unsigned alloc = array->alloc;
	struct object_array_entry *objects = array->objects;

	if (nr >= alloc) {
		alloc = (alloc + 32) * 2;
		objects = xrealloc(objects, alloc * sizeof(*objects));
		array->alloc = alloc;

Constant increment, O(n^2).

pathlist.c:

static int add_entry(struct path_list *list, const char *path)
{
	int exact_match;
	int index = get_entry_index(list, path, &exact_match);

	if (exact_match)
		return -1 - index;

	if (list->nr + 1 >= list->alloc) {
		list->alloc += 32;
		list->items = xrealloc(list->items, list->alloc
				* sizeof(struct path_list_item));
	}

Constant increment, O(n^2).

That's just a cursory examination. In my opinion, pretty much every realloc should be replaced by some sort of list structure. That would be the nicest thing. I have sped up some awk scripts that built up argument lists by a factor of 100 by replacing a[index] = a[index] " " thenewstuff with a[index,nr[index]++] = thenewstuff and then never concatenating the strings, but just outputting them in a loop.

Anyway, short of that, don't realloc by fixed increments, always use alloc_nr as soon as multiple reallocs are to be expected.

And they certainly are in some of the above cited code passages.