On Thu, 14 Apr 2005, H. Peter Anvin wrote:
Linus Torvalds wrote:
Even something as simple as "ls -l" has been known to have O(n**2) behaviour for big directories.
For filesystems with linear directories, sure. For sane filesystems, it should have O(n log n).
note that default configs of ext2 and ext3 don't qualify as sane filesystems by this definition.
ext3 does have an extention that you can enable to have it hash the directory access, but even if you enable that on a filesystem you aren't guaranteed that it will be active (if the directory existed before it was turned on, or has been accessed by a kernel that didn't understand the extention then the htree functionality won't be used until you manually tell the system to generate the tree)
David Lang
-- There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies. -- C.A.R. Hoare - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
