Horrible L2 cache effects from kernel compile
Quoted 8 lines · Andi
The reason:
Dentry cache hash table entries: 131072 (order: 8, 1048576 bytes) Inode cache hash table entries: 65536 (order: 7, 524288 bytes)
(1GB) I bet on your big memory box it is even worse. No cache in the world can cache that.
[snip]
Quoted 4 lines
Try the appended experimental patch. It replaces the hash table madness with relatively small fixed tables.
Are you sure that this will help?
With a smaller table, you might cause fewer cache misses for the table lookup. Instead you get longer hash chains. Walking linked lists probably causes more cache line misses than the single array lookup.
Dave, how many entries are in the dcache?
Btw, has anyone tried to replaced the global dcache with something local, perhaps a tree instead of d_child, and then lookup in d_child_tree?
--
Manfred
Quoted 4 lines
Are you sure that this will help?
With a smaller table, you might cause fewer cache misses for the table lookup. Instead you get longer hash chains. Walking linked lists probably causes more cache line misses than the single array lookup.
That's true when the hash table has a reasonable size. But with 1MB and bigger hash tables you are guaranteed to get a cache miss for most head bucket access, no matter how many dentries you have. The hash function is actively working against your cache here.
The dentries are actually more likely to fit into dcache because they don't get artificially spread out over the cache space.
-Andi
Quoted 1 line · Manfred Spraul
Dave, how many entries are in the dcache?
from slabinfo:dentry_cache 35157 35352 160 1473 1473 1 : 248 124
The full result set:
http://www.sr71.net/prof/kernbench/run-kernbench-2.5.62.13/
Signature · 2 lines
Dave Hansen [email protected]
Quoted 2 lines
Btw, has anyone tried to replaced the global dcache with something local, perhaps a tree instead of
d_child, and then lookup ind_child_tree?
I don't think anyone does this, but I've been considering doing this for over a year now ... I just feel there's bound to be some inherent problem, or someone would have done it already. But there's only one real way to find that out ;-)
In article <[email protected]>,
Quoted 2 lines · Manfred Spraul
Are you sure that this will help?
It might, under some loads.
However, I don't think it's a long-term solution, since the hashing will mean that for any reasonably spread out load you _will_ always walk all dentries.
So the long-term solution is to either use a local lookup (which we ended up doing for the page cache) _or_ to limit the number of dentries themselves some way. The latter sounds like a bad idea.
Quoted 2 lines
Btw, has anyone tried to replaced the global dcache with something local, perhaps a tree instead of
d_child, and then lookup ind_child_tree?
I'd love to see somebody try. The main worry is the overhead required per directory dentry and keeping it scalable. The dentry tree _will_ be quickly populated and one common case is a few huge directories, yet at the same time for most dentries there won't be any children at all or very few of them).
Right now the "child" list is just a simple linked list, and changing that to something more complex might make it possible to get rid of the hash entirely. But increasing the size of individual dentries is a bad idea, so it would have to be something fairly smart.
Linus
Quoted 4 lines · Linus Torvalds
Right now the "child" list is just a simple linked list, and changing that to something more complex might make it possible to get rid of the hash entirely. But increasing the size of individual dentries is a bad idea, so it would have to be something fairly smart.
Part of it is that some of the dentry is simply just too bloated. At 160 bytes, there must be something we can prune:
qstr.len - if anyone cares about 4GB long dentries, they
probably have other problems. could be a short
d_lock - 1 bit out of 4 bytes
d_vfs_flags - 2 bits out of 4 bytes
d_flags - 3 bits out of 4 bytes
d_move_count - rcu -- is it ever used on UP?
d_time - only used by network filesystems
*d_sb - rarely used, accessible via inode
*d_fsdata - mostly used by exotic/network filesystems
*d_cookie - only used when o_profile is active
In short, almost a third can be configured out of existence for some setups, and others are candidates for being moved into filesystem specific data.
-ben
Signature · 1 line
Junk email? <a href=mailto:"[email protected]">[email protected]</a>
Quoted 3 lines · Benjamin LaHaise
Part of it is that some of the dentry is simply just too bloated. At 160 bytes, there must be something we can prune:
The thing is, the size of it doesn't really matter. The bad effects come not from the size, but from the bad behaviour of the lookup algorithm, which would be exactly the same even if the dentry was _half_ the size it is now.
In other words, the size of the dentry only matters from a memory usage standpoint, and I don't think we have any cause to believe that dentries really hurt our global memory usage (we've _often_ had the bug that we don't shrink the dentry cache quickly enough, which is a different problem, though - keeping too many of them around. That should be largely fixed in current kernels).
So I don't think there is any real reason to worry about the size of the dentry itself. Yes, you could make it smaller (you could remove the inline string from it, for example, and you could avoid allocating it at cacheline boundaries - both of which makes it a _lot_ smaller than just trying to save few bits), but both of those bigger decisions look like they are worthwhile tradeoffs.
Linus
Quoted 2 lines · Linus Torvalds
dentry itself. Yes, you could make it smaller (you could remove the inline string from it, for example, and you could avoid allocating it at
How about at least making the inline string align to the slab alignment so we dont waste space ?
Quoted 6 lines · Alan Cox
Quoted 2 lines · Linus Torvalds
dentry itself. Yes, you could make it smaller (you could remove the inline string from it, for example, and you could avoid allocating it at
How about at least making the inline string align to the slab alignment so we dont waste space ?
Also, making the qstr length an unsigned short or u8 would increase the length of the string by 2 or 3 bytes quite for free.
-ben
Signature · 1 line
Junk email? <a href=mailto:"[email protected]">[email protected]</a>
Quoted 7 lines · Alan Cox
Quoted 2 lines · Linus Torvalds
dentry itself. Yes, you could make it smaller (you could remove the inline string from it, for example, and you could avoid allocating it at
How about at least making the inline string align to the slab alignment so we dont waste space ?
That change was made a couple of months back.
Quoted 6 lines · Alan Cox
Quoted 2 lines · Linus Torvalds
dentry itself. Yes, you could make it smaller (you could remove the inline string from it, for example, and you could avoid allocating it at
How about at least making the inline string align to the slab alignment so we dont waste space ?
2.5.x does that already:
#define DNAME_INLINE_LEN \ (sizeof(struct dentry)-offsetof(struct dentry,d_iname))
with the DNAME_INLINE_LEN_MIN just being exactly what the name says: the minimum size.
Linus
Quoted 6 lines · Alan Cox
Quoted 2 lines · Linus Torvalds
dentry itself. Yes, you could make it smaller (you could remove the inline string from it, for example, and you could avoid allocating it at
How about at least making the inline string align to the slab alignment so we dont waste space ?
what what be best is the hash chaining pointers and the first N bytes of the inline name in the same cacheline. for 32B cache lines it looks like it's at least two misses per chain now. (er, well i'm looking at 2.4 source.)
-dean