Re: [PATCH] binary-tree-based objects.

From: Linus Torvalds <torvalds@osdl.org>
Date: Feb 12, 2006, 05:22 UTC
Message-ID: <Pine.LNX.4.64.0602112117560.3691@g5.osdl.org>
In-Reply-To: <Pine.LNX.4.64.0602112045340.3691@g5.osdl.org>

On Sat, 11 Feb 2006, Linus Torvalds wrote:

Show 10 quoted lines

> 
> Before:
> 	real    0m41.322s	user    0m40.612s	sys     0m0.492s
> 	real    0m40.797s	user    0m40.140s	sys     0m0.468s
> 	real    0m40.433s	user    0m40.016s	sys     0m0.412s
> 
> After:
> 	real    0m22.542s	user    0m22.080s	sys     0m0.448s
> 	real    0m22.660s	user    0m22.336s	sys     0m0.312s
> 	real    0m22.671s	user    0m22.236s	sys     0m0.292s

And just so you wouldn't think that all my machines are slow..

Before:
	real    0m28.645s	user    0m28.366s	sys     0m0.280s
	real    0m28.700s	user    0m28.486s	sys     0m0.212s

After:
	real    0m16.566s	user    0m16.373s	sys     0m0.196s
	real    0m16.512s	user    0m16.277s	sys     0m0.236s

so there (that's all with current kernel HEAD, mostly packed).

Now, I haven't compared it to the other suggested fixes (hashing, and the 256-way bucket-sorting), but I obviously prefer the tree approach because it's my idea (and my ideas are _always_ superior) and because it's so dang simple.

If somebody shows that the other approaches are faster, then I guess I'll just have to sulk in a corner and grown quietly at people.

		Linus