On Mar 15, 2011, at 7:23 AM, Ric Wheeler wrote: > > I have tested both sorting techniques with very large directories. > > Most of the gain came with the simple sorting by inode number, but of course this relies on the file system allocation policy having a correlation between the inode numbers and layout (i.e., higher inode number correspond to higher block numbers). That's not just a matter of file system allocation policy, but how fragmented the free space is as far as inode numbers and block numbers might be. (Especially in the block group where /var/lib/dpkg/info lives, on Debian systems. That's because that directory is (ab)used as a database, with lots of files added and deleted, so over time it's pretty much inevitable that any link between directory order, inode numbers, and block numbers, would become weaker and weaker over time. Fortunately the overall database tends to fit into the dentry, inode, and page caches after the first dpkg operation...) > Note that you can get the inode number used in this sorting without doing any stat calls. Sure. And in the worst case, you would sort based on the inode number so that when you call open/FI[BE]MAP, the disk isn't seeking all over the place when you read in the inode structure... Then you need to sort by block numbers, and assuming that you have enough memory that all of /var/lib/dpkg/info/* fits in the inode cache, you will minimize seeking while you read the blocks into memory. -- Ted -- To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
