Skip to contentSkip to conversation

Horrible L2 cache effects from kernel compile

DISCUSSION Dave Hansen 7 participants 10 messages Feb 25, 2003

lore
Share & tools
lore
#0 lore raw

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

#2 lore raw
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]
#8 lore raw
In reply to Dave Hansen

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_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.

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

#3 lore raw
In reply to William Lee Irwin III
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

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

#5 lore raw
In reply to John Levon
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.

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

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