Re: [PATCH 0/3] Remove more parsers

From: Linus Torvalds <torvalds@osdl.org>
Date: Jan 31, 2006, 17:16 UTC
Message-ID: <Pine.LNX.4.64.0601310905000.7301@g5.osdl.org>
In-Reply-To: <Pine.LNX.4.64.0601291645060.25300@iabervon.org>

On Sun, 29 Jan 2006, Daniel Barkalow wrote:

Show 5 quoted lines

> 
> I'll look into discarding the struct trees after use (since we're not 
> keeping flags on them, or storing references to them long-term), so we can 
> use the same parser without worse memory behavior. It does seem to take a 
> bunch more memory (and, oddly, be very slow) as I currently have it.

Really, trying to use "struct tree" just is _broken_.

Even if you start freeing the memory, performance will absolutely _suck_. You'll be using a "malloc()" (and eventually, a "free()") and copying the tree entries around for absolutely zero gain. You'll make things follow pointers and have indirection, instead of just walking the data structure directly.

IOW, it will be about ten times more expensive in CPU time, in the most performance-critical part of git.

I would actually argue that if you want to use a common structure, try to convert existing users of "struct tree" to the "struct tree_desc" iterators. Yes, their use is a little awkward, but there's really no way you can use anything but the fast ones for tree diffing.

The "struct tree_desc" can only be used for traversing a tree linearly in one order, but I bet that nobody really ever does anything else.

To make "struct tree_desc" more generic, you'd obviously have to export the "update_tree_entry()" and "extract()" functions (and the latter would probably need to be re-named to "extract_tree_entry()").

Oh, and to make freeign the tree entry a bit simpler, you'd probably want to replace

	void *buf
	unsigned int size;

with a

	const void *const tree_base;
	const unsigned int tree_size;
	unsigned int offset;

so that you'd just update "offset" and leave tree_base/size untouched (to make freeing easier - right now the person who populates the "struct tree_desc" has to free the thing by hand).

		Linus