Horrible L2 cache effects from kernel compile
I was testing Martin Bligh's kernbench (a kernel compile with -j(2*NR_CPUS)) and using DCU_MISS_OUTSTANDING as the counter event.
The surprising thing? d_lookup() accounts for 8% of the time spent waiting for an L2 miss.
__copy_to_user_ll should be trashing a lot of cachelines, but d_lookup() is strange.
Counter 0 counted DCU_MISS_OUTSTANDING events (number of cycles while DCU miss outstanding) with a unit mask of 0x00 (Not set) count 10000
c017d78c 72929 1.92175 start_this_handle c0139b60 75317 1.98468 vm_enough_memory c0138cd4 75367 1.986 do_no_page c01ccae0 79475 2.09425 atomic_dec_and_lock c0117320 80918 2.13227 scheduler_tick c0176338 90851 2.39402 ext3_dirty_inode c013cc38 132228 3.48434 page_remove_rmap c0176557 148116 3.90301 .text.lock.inode c013cae0 156345 4.11985 page_add_rmap c012c964 157716 4.15598 find_get_page c015797c 314165 8.27857 d_lookup c01cc948 334779 8.82177 __copy_to_user_ll
a snippet from d_lookup(), annotated. I've seen oprofile be off by a line here, but we can be pretty sure it is in this area.
... smp_read_barrier_depends(); /* 106 0.002793% */ dentry = list_entry(tmp, struct dentry, d_hash); /* if lookup ends up in a different bucket * due to concurrent rename, fail it */ /* 154991 4.084% */ if (unlikely(dentry->d_bucket != head)) break; /* to avoid race if dentry keep coming back to original * bucket due to double moves */ /* 634 0.01671% */ if (unlikely(++lookup_count > max_dentries)) break; ...
Signature · 2 lines
Dave Hansen [email protected]
Quoted 4 lines · Dave Hansen
c01cc948 334779 8.82177 __copy_to_user_ll c015797c 314165 8.27857 d_lookup c012c964 157716 4.15598 find_get_page c013cae0 156345 4.11985 page_add_rmap
Quoted 8 lines
c0176557 148116 3.90301 .text.lock.inode c013cc38 132228 3.48434 page_remove_rmap c0176338 90851 2.39402 ext3_dirty_inode c0117320 80918 2.13227 scheduler_tick c01ccae0 79475 2.09425 atomic_dec_and_lock c0138cd4 75367 1.986 do_no_page c0139b60 75317 1.98468 vm_enough_memory c017d78c 72929 1.92175 start_this_handle
Your profile was upside down. I've re-sorted it.
It probably confused people who were wondering why the numbers at the top of the profile were lower than the ones below them.
Quoted 18 lines · Dave Hansen
a snippet from
d_lookup(), annotated. I've seen oprofile be off by a line here, but we can be pretty sure it is in this area.smp_read_barrier_depends(); /* 106 0.002793% */ dentry = list_entry(tmp, struct dentry, d_hash); /* if lookup ends up in a different bucket * due to concurrent rename, fail it */ /* 154991 4.084% */ if (unlikely(dentry->d_bucket != head)) break; /* to avoid race if dentry keep coming back to original * bucket due to double moves */ /* 634 0.01671% */ if (unlikely(++lookup_count > max_dentries)) break; ...
Well, you're walking hash chains, you're going to get a lot of cache misses, about the whole length of the chain's worth. You could try changing the dcache to use something like a B+ tree or some such nonsense to reduce its cache footprint.
I'd collect statistics to see if the dcache hash function is badly distributing things. That's relatively easily fixable if so.
-- wli
Quoted 3 lines · William Lee Irwin III
Your profile was upside down. I've re-sorted it.
It probably confused people who were wondering why the numbers at the top of the profile were lower than the ones below them.
Thanks, Bill. oprofile's default output is useful when you're viewing it from the cmdline, but it looks bad in email.
Signature · 2 lines
Dave Hansen [email protected]
In article <[email protected]>,
Quoted 8 lines · Dave Hansen
I was testing Martin Bligh's kernbench (a kernel compile with -j(2*NR_CPUS)) and using
DCU_MISS_OUTSTANDINGas the counter event.The surprising thing?
d_lookup()accounts for 8% of the time spent waiting for an L2 miss.
__copy_to_user_llshould be trashing a lot of cachelines, butd_lookup()is strange.
I wouldn't call it that strange. It _is_ one of the most critical areas of the FS code, and hashes (which it uses) are inherently bad for caches.
The instruction you point to as being the most likely suspect:
if (unlikely(dentry->d_bucket != head))
is the first instruction that actually looks at the dentry chain information, so sure as hell, that's the one you'd expect to show up as the cache miss.
There's no question that the dcache is very effective at caching, but I also think it's pretty clear that especially since we allow it to grow pretty much as big as we have memory, it _is_ going to cause cache misses.
I don't know what to even suggest doing about it - it may be one of those things where we just have to live with it. I don't see any alternate good data structures that would be more cache-friendly. Unlike some of our other data structures (the page cache, for example) which have been converted to more cache-friendly RB-trees, the name lookup is fundamentally not very well-behaved.
(Ie with the page cache there is a lot of locality within one file, while with name lookup the indexing is a string, which pretty much implies that we have to hash it and thus lose all locality)
Linus
Quoted 3 lines · William Lee Irwin III
Your profile was upside down. I've re-sorted it.
It probably confused people who were wondering why the numbers at the top of the profile were lower than the ones below them.
Would people generally prefer things to be sorted so the most important stuff was at the top ? We're considering such a change ...
regards
john
Quoted 3 lines · William Lee Irwin III
Quoted 3 lines
Your profile was upside down. I've re-sorted it.
It probably confused people who were wondering why the numbers at the top of the profile were lower than the ones below them.
Quoted 2 lines · John Levon
Would people generally prefer things to be sorted so the most important stuff was at the top ? We're considering such a change ...
I would, I have to do a double take to catch it.
-- wli
Quoted 10 lines · John Levon
Quoted 3 lines · William Lee Irwin III
Your profile was upside down. I've re-sorted it.
It probably confused people who were wondering why the numbers at the top of the profile were lower than the ones below them.Would people generally prefer things to be sorted so the most important stuff was at the top ? We're considering such a change ...
I prefer it the way it is, so unimportant stuff can scroll away.
Bill can just turn his monitor upside down.
Quoted 11 lines
Quoted 7 lines
Quoted 3 lines
Your profile was upside down. I've re-sorted it.
It probably confused people who were wondering why the numbers at the top of the profile were lower than the ones below them.Would people generally prefer things to be sorted so the most important stuff was at the top ? We're considering such a change ...
I prefer it the way it is, so unimportant stuff can scroll away.
Bill can just turn his monitor upside down.
You're Australian though, so you get that by default ;-)
John, how about a "-r" flag or something to sort the output biggest first? Might keep the dissenting masses happy ;-)
M.
Quoted 1 line · Martin J. Bligh
John, how about a "-r" flag or something to sort the output biggest first?
[moz@lambent src]$ oprofpp --help | grep -- reverse
-r, --reverse reverse sort order
[moz@lambent src]$ op_time --help | grep -- reverse
-r, --reverse reverse sort order
Requests like this are my favourite ;)
john