Thanks to you and to Junio for your replies,
Linus Torvalds [off-list ref] writes:
No, no. The fastest way to store a bunch of files is to basically:
- make the filenames as small as possible
This improves density, and thus performance. You'll get more files to
fit in a smaller directory, and filename compares etc will be faster
too.
If you don't need hashes, but can do with smaller names (for example,
your names are really just sequential, and you can use some base-64
encoding to make them smaller than numbers), you'll always be better
off.
This is really interesting and I would not have suspected it. But it
begs the question: why does Git use the base-16 hash instead of the
base-64 hash?
After your replies I took a serious look at Git's storage and there is
indeed not that many loose objects in a typical repo: most is kept
into packs. So I guess Git doesn't need that much density and keeping
the filename in the format that is used in the UI probably helps power
users.
- store them in a good final order. This is debatable, but depending on
your load and the filesystem, it can be better to make sure that you
create all files in order, because performance can plummet if you start
removing files later.
I suspect your benchmark *only* tested this case,
That is true.
but if you want to check odder cases, try creating a huge
directory, and then deleting most files, and then adding a few
new ones. Some filesystems will take a huge hit because they'll
still scan the whole directory, even though it's mostly empty!
(Also, a "readdir() + stat()" loop will often get *much* worse access
patterns if you've mixed deletions and creations)
This is something that will be interesting to benchmark later on. So,
an application with a lot of turnaround, say a mail server, should
delete and re-create the directories from time to time? I assume this
is specific to some file system types.
- it's generally *much* more efficient to have one large file that you
read and seek in than having many small ones, so if you can change your
load so that you don't have tons of files at all, you'll probably be
better off.
That makes a lot of sense.
Thanks again for those clarifications.
--
Yannick Gingras
On Mon, 31 Dec 2007, Yannick Gingras wrote:
This is really interesting and I would not have suspected it. But it
begs the question: why does Git use the base-16 hash instead of the
base-64 hash?
Because I was stupid, and I'ma lot more used to hex numbers than to
base-64.
Also, the way the original encoding worked, the SHA1 of the object was
actually the SHA1 of the *compressed* object, so you could verify the
integrity of the object writing by just doing a
sha1sum .git/objects/4f/a7491b073032b57c7fcf28c9222a5fa7b3a6b9
and it would return 4fa7491b073032b57c7fcf28c9222a5fa7b3a6b9 if everything
was good. That was a nice bonus in the first few days of git development,
when it all was a set of very low-level object routines hung together with
prayers and duct-tape.
So consider it historical. It wasn't worth fixing, since it became obvious
that the real fix would never be to try to make the individual files or
filenames smaller.
quoted
(Also, a "readdir() + stat()" loop will often get *much* worse access
patterns if you've mixed deletions and creations)
This is something that will be interesting to benchmark later on. So,
an application with a lot of turnaround, say a mail server, should
delete and re-create the directories from time to time? I assume this
is specific to some file system types.
This is an issue only for certain filesystems, and it's also an issue only
for certain access patterns.
A mail server, for example, will seldom *scan* the directory. It will just
open individual files by name. So it won't be hit by the "readdir+stat"
issue, unless you actually do a "ls -l".
(There are exceptions. Some mailbox formats use a file per email in a
directory. And yes, they tend to suck from a performance angle).
And you can avoid it. For example, on most unixish filesystems, you can
get better IO access patterns by doing the readdir() into an array, then
sorting it by inode number, and then doing the stat() in that order: that
*often* (but not always - there's no guarantee what the inode number
actually means) gives you better disk access patterns.
Linus
On Dec 31, 2007 11:13 PM, Yannick Gingras [off-list ref] wrote:
quoted
but if you want to check odder cases, try creating a huge
directory, and then deleting most files, and then adding a few
new ones. Some filesystems will take a huge hit because they'll
still scan the whole directory, even though it's mostly empty!
(Also, a "readdir() + stat()" loop will often get *much* worse access
patterns if you've mixed deletions and creations)
This is something that will be interesting to benchmark later on. So,
an application with a lot of turnaround, say a mail server, should
delete and re-create the directories from time to time? I assume this
is specific to some file system types.
This is indeed the case. Directories with a lot of movement get
fragmented on most FSs -- ext3 is a very bad case for this -- and
there are no "directory defrag" tools other than regenarating them.
The "Maildir" storage used for many IMAP servers these days shows the
problem.
This (longish) threads has some interesting tidbits on getdents() and
directory fragmentation.
http://kerneltrap.org/mailarchive/git/2007/1/7/235215
cheers,
m