Skip to contentSkip to conversation

Horrible L2 cache effects from kernel compile

DISCUSSION Manfred Spraul 9 participants 12 messages Feb 25, 2003 – Mar 5, 2003

lore
Share & tools
lore
#0 lore raw
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

#1 lore raw
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

#3 lore raw
In reply to Manfred Spraul
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 in d_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 ;-)

#4 lore raw
In reply to Manfred Spraul

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 in d_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

#5 lore raw
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>
#6 lore raw
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

#7 lore raw
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 ?

#8 lore raw
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>
#9 lore raw
In reply to Alan Cox
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.

#10 lore raw
In reply to Alan Cox
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

#11 lore raw
In reply to Alan Cox
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