{"action":"created","issue":{"url":"https://api.github.com/repos/borgbackup/borg/issues/905","repository_url":"https://api.github.com/repos/borgbackup/borg","labels_url":"https://api.github.com/repos/borgbackup/borg/issues/905/labels{/name}","comments_url":"https://api.github.com/repos/borgbackup/borg/issues/905/comments","events_url":"https://api.github.com/repos/borgbackup/borg/issues/905/events","html_url":"https://github.com/borgbackup/borg/issues/905","id":148384686,"number":905,"title":"Order of traversing files in a directory","user":{"login":"verygreen","id":625925,"avatar_url":"https://avatars.githubusercontent.com/u/625925?v=3","gravatar_id":"","url":"https://api.github.com/users/verygreen","html_url":"https://github.com/verygreen","followers_url":"https://api.github.com/users/verygreen/followers","following_url":"https://api.github.com/users/verygreen/following{/other_user}","gists_url":"https://api.github.com/users/verygreen/gists{/gist_id}","starred_url":"https://api.github.com/users/verygreen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/verygreen/subscriptions","organizations_url":"https://api.github.com/users/verygreen/orgs","repos_url":"https://api.github.com/users/verygreen/repos","events_url":"https://api.github.com/users/verygreen/events{/privacy}","received_events_url":"https://api.github.com/users/verygreen/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":7,"created_at":"2016-04-14T14:45:14Z","updated_at":"2016-04-14T16:13:54Z","closed_at":null,"body":"Moving from #325 in a ticket of its own.\r\n\r\nWhile looking around Archiver::_process I noticed that:\r\n```\r\n            if not dry_run:\r\n                status = archive.process_dir(path, st)\r\n            try:\r\n                entries = os.listdir(path)\r\n            except OSError as e:\r\n                status = 'E'\r\n                self.print_warning('%s: %s', path, e)\r\n            else:\r\n                for filename in sorted(entries):\r\n                    entry_path = os.path.normpath(os.path.join(path, filename))\r\n                    self._process(archive, cache, matcher, exclude_caches, exclude_if_present,\r\n                                  keep_tag_files, skip_inodes, entry_path, restrict_dev,\r\n                                  read_special=read_special, dry_run=dry_run)\r\n```\r\n\r\nI imagine the `sort(entries)` just sorts stuff alphabetically? If so, this is a pretty bad idea on a bunch of filesystems for large directories on spinning media. Affected filesystems include reiserfs, ext4 and probably many more that have static inode allocation.\r\nThe problem at hand is when you sort this list in an order different than inode numbers, every lstat that you do seeks the disk to a different inode table block somewhere which is really slow.\r\nNot sorting the output is also not an option since then you get some \"random\" underlying hash sorting that also might not correspond to creation order. The most optimal strategy here for things with fixed inode tables is to sort by inode number (available in readdir output).\r\nFor filesystems with no static inode tables (like reiserfs) I imagine that would also lead to desired effect because it still is a good proxy for create time that leads to ondisk location (earlier created files get closer to start of disk in a chunk if they were written together).\r\nMore advanced COW filesystems like zfs and bttrfs - I am less sure, those might be all over the place depending on a bunch of stuff, though. I assume sort ordering would not matter there all that much.\r\n\r\nA question was also raised if this makes any practical difference. And it certainly does for large directories (with millions of entries) that are not cached.\r\nHere are some links to ext3 discussions about when htree code became popular and discussion arose. You'll see that performance impact is quite high:\r\nhttps://bugzilla.kernel.org/show_bug.cgi?id=417\r\nhttps://lkml.org/lkml/2008/2/18/263\r\n\r\nThere are tons more and the same issue is present in other filesystems with hashed names. I know about this because I am a Linux fs developer on my day job (and we met this when I was still working on reiserfs).\r\n\r\nAdditionally as we look outside of Linux (which is really optimized in these areas), other systems caches are (in some cases? in many cases) a lot more suboptimal or even non-exstent (e.g. in BSD where every fs driver used to need to implement their own cache).\r\nI had a big confirmation of this yesterday. So I had a ~2M structure of files in on my Linux server, all on rotating media. find / -perm 0 (to cause stat calls) took 15 seconds there.\r\nNow I also have this macbook I am working on, it has ssd and about 2.5M files on it, same find takes 2m50s. Quite a difference thanks to many-many variables I am sure."},"comment":{"url":"https://api.github.com/repos/borgbackup/borg/issues/comments/210027862","html_url":"https://github.com/borgbackup/borg/issues/905#issuecomment-210027862","issue_url":"https://api.github.com/repos/borgbackup/borg/issues/905","id":210027862,"user":{"login":"enkore","id":1330164,"avatar_url":"https://avatars.githubusercontent.com/u/1330164?v=3","gravatar_id":"","url":"https://api.github.com/users/enkore","html_url":"https://github.com/enkore","followers_url":"https://api.github.com/users/enkore/followers","following_url":"https://api.github.com/users/enkore/following{/other_user}","gists_url":"https://api.github.com/users/enkore/gists{/gist_id}","starred_url":"https://api.github.com/users/enkore/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/enkore/subscriptions","organizations_url":"https://api.github.com/users/enkore/orgs","repos_url":"https://api.github.com/users/enkore/repos","events_url":"https://api.github.com/users/enkore/events{/privacy}","received_events_url":"https://api.github.com/users/enkore/received_events","type":"User","site_admin":false},"created_at":"2016-04-14T16:13:54Z","updated_at":"2016-04-14T16:13:54Z","body":"Yes, I noticed now, too. I pushed a new version which uses Pythons scandir instead, which from the looks of it is a quite thin wrapper around readdir. This should now sort-then-stat."}}