lkml.org 
[lkml]   [1999]   [May]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: 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/

\
 
 \ /
  Last update: 2005-03-22 13:52    [W:0.039 / U:0.024 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site