Messages in this thread | | | Date | Mon, 31 May 1999 17:05:46 +0200 | From | Jamie Lokier <> | Subject | Re: large directory handling speed |
| |
Alexander V. Lukyanov wrote: > Cyclic search looks good. At least it would make better the common > case of readdir/stat. But what if a stupid program sort file name list > before stat's :) (fortunately it is not common)
For small/medium ext2 directories and cold caches, the fastest way to stat all the entries is to sort by inode number, d_ino. This orders the disk I/O optimally, and the saving from that is greater than the loss due to directory search time.
I haven't tested this on very large directories -- but I'd expect the quadratic directory search time to be more significant than I/O time for ext2, fat etc.
The cyclic search suggestion
- wouldn't help for randomly ordered directories, but wouldn't make things any worse either (on ext2, this tends to be directories containing other directories)
- would help a lot for directories whose entries are mostly in inode order (on ext2, this tends to be most directories containing files)
-- Jamie
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |