[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

tytso's readdir speedup patch - adoptable?


recently Theodory Tso posted a patch for the ext2fs driver, which
improves speed of find and similar programs. Background: the application
access all entries in the directory in the order they are stored on the
disk. The current ext2 (and apparently Ext3) run a lookup function for
each readdir call, starting with the first node! Theodore stores a
refference to the node which was accessed recently, so the next lookup
begins there and only one iteration is needed in best case. My own
test with "time ls -l" in a directory with 50000 files:

real    0m5.507s
user    0m1.880s
sys     0m0.940s
root zombie:/tmp/ext2patched>

real    0m4.341s
user    0m1.890s
sys     0m1.010s
root zombie:/tmp/reiser>

real    1m54.355s
user    0m2.060s
sys     1m50.370s
root zombie:/tmp/ext3>

I don't remember the result of ext2 before patching, it was about 1.45s
IIRC.  You see, ext3 is the looser and needs about 10000 percent more
CPU time.  I looked at the similar routines in ext3 code and it may be
optimised too, but I am not familiar with the code so I don't want to
start experimenting on the kernel. The ext2 patch is attached.

"Programmieren ist kalter Kaffee" (aus einer PC-Zeitschrift)
On Sat, Aug 18, 2001 at 01:52:56AM -0400, Matt Zimmerman wrote:
> On Tue, Aug 14, 2001 at 04:24:33PM +1000, Anthony Towns wrote:
> > That's not true: ext2 queries and directory lists are the problem here,
> > in that they're O(N) and O(N^2) rather than O(1)/O(N). Using reiser or
> > subdirectories would reduce those to O(lg(N)) and O(N lg(N)).
> Why on earth are directory lists O(N^2)?  I don't know much about ext2
> internals, but that should be an O(N) operation in any sane filesystem.  

Doing a directory list is indeed O(N) for ext2.  

However, iterating through the directory using readdir() and then
stating or opening each file in readdir order is O(N**2).  There's a
very obvious optimization which makes this O(N), which I thought ext2
was using, but as it turns out, we weren't.

Thanks for bringing this to my attention; here's the very simple
kernel patch which should speed up a du or find of very large
directories significantly.

						- Ted

Patch generated: on Sat Aug 18 08:41:38 EDT 2001 by tytso think
against Linux version 2.4.8
RCS file: fs/ext2/RCS/dir.c,v
retrieving revision 1.1
diff -u -r1.1 fs/ext2/dir.c
--- fs/ext2/dir.c	2001/08/18 11:11:30	1.1
+++ fs/ext2/dir.c	2001/08/18 12:41:10
@@ -303,7 +303,7 @@
 	const char *name = dentry->d_name.name;
 	int namelen = dentry->d_name.len;
 	unsigned reclen = EXT2_DIR_REC_LEN(namelen);
-	unsigned long n;
+	unsigned long start, n;
 	unsigned long npages = dir_pages(dir);
 	struct page *page = NULL;
 	ext2_dirent * de;
@@ -311,7 +311,11 @@
 	*res_page = NULL;
-	for (n = 0; n < npages; n++) {
+	start = dir->u.ext2_i.i_dir_start_lookup;
+	if (start >= npages)
+		start = 0;
+	n = start;
+	do {
 		char *kaddr;
 		page = ext2_get_page(dir, n);
 		if (IS_ERR(page))
@@ -324,11 +328,14 @@
 			if (ext2_match (namelen, name, de))
 				goto found;
-	}
+		if (++n >= npages)
+			n = 0;
+	} while (n != start);
 	return NULL;
 	*res_page = page;
+	dir->u.ext2_i.i_dir_start_lookup = n;
 	return de;
RCS file: include/linux/RCS/ext2_fs_i.h,v
retrieving revision 1.1
diff -u -r1.1 include/linux/ext2_fs_i.h
--- include/linux/ext2_fs_i.h	2001/08/18 11:10:48	1.1
+++ include/linux/ext2_fs_i.h	2001/08/18 11:11:18
@@ -34,6 +34,7 @@
 	__u32	i_next_alloc_goal;
 	__u32	i_prealloc_block;
 	__u32	i_prealloc_count;
+	__u32	i_dir_start_lookup;
 	int	i_new_inode:1;	/* Is a freshly allocated inode */

To UNSUBSCRIBE, email to debian-devel-request lists debian org
with a subject of "unsubscribe". Trouble? Contact listmaster lists debian org

Attachment: pgp00002.pgp
Description: PGP signature

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]