Re: [PATCH] New dcache / inode hash tuning patch

Re: [PATCH] New dcache / inode hash tuning patch

[Andi Kleen]

torvalds@transmeta.com (Linus Torvalds) writes:

[please read the whole post before answering. thanks]

>    But quite frankly, if the hash list heads are actually noticeable
>    memory users, the hash is likely to be _way_ too big. The list heads
>    are _much_ smaller than the entries they point to, the hash list just
>    shouldn't be big enough that it really matters.

On big machines it is currently 1+MB. IMHO this is way too big.

> 
>  - hash list cache footprint
> 
>    Again: the hash head array itself is at least dense in the cache, and
>    each entry is _much_ smaller than the actual data structures it
>    points to.  So even if you improve the hash heads to be better from a
>    cache standpoint, you're only getting a very small percentage of the
>    real cache costs. 

It would be possible to cache line optimize the layout of struct dentry
in addition. May be an interesting add-on project for someone...
But for lookup walking even one cache line - the one containing d_hash -
should be needed. Unless d_hash is unlucky enough to cross a cache
line for its two members ... but I doubt that.

> 
>    So let's say that the cache costs of the dcache is 4% (according to
>    the oprofile run), then saving a few procent of that is not actually
>    going to be noticeable at a user level.
> 
> And the downsides of the hash list is that addition/removal is costlier
> due to the conditionals, and a non-conditional version (a common

But the list walking is faster.  Testing for NULL generates much better 
code on i386 than having to dedicate a register for storing the head
to test against. List walking happens more often than insertion/deletion.

I believe the conditionals are completely left in the noise compared
to the cache misses the two pointer head version causes. You can execute
a lot of conditionals in the time needed to serve one cache miss!

Please take a look at the x86 assembly generated by list_for_each
vs hlist_for_each. hlist_for_each looks much nicer, especially when you
can use the register normally wasted on the head for something else
in the loop body.

In case of dcache rcu it also made things simpler/faster because it didn't
require the complicated is_bucket race breaker check.

> In other words: it may be that our current dentry hashes are too big,
> and that is certainly worth fixing if so.  But the "hlist" approach very
> fundamentally cannot really help the _real_ problem very much, and it
> will (slightly) hurt the case where the hashes are actually cached. 

I admit it is a kind of micro optimization, but I believe it is an useful
one. Frankly wasting two pointers for a hash bucket in a potentially
big hash table is just s*d.

> 
> So I really think that the only longterm fix is to make the lookup data
> structures be "local" to the base of the lookup, in order to get away
> from the inherently non-local nature of the current hash lookups. 

Yes, that may be a good idea. I don't have time to work on this though.

Still even with local lookups single pointer buckets will likely help ;)

Also isn't it a bit late in the 2.5 cycle to think about such radical
changes like local lookup? It sounds more like a nice 2.7 project.  I
believe my patch with a bit more tweaking (my current 64K hash table
seems to be too small) is suitable even for an soon to be stable
kernel.

Also my patch had some other changes that I believe should be included
anyways because they're independent and improvement. It replaces the
max_dentries race break hack with a better algorithm to detect cycles on walk.

Also it does more prefetches while list walking which I believe to be 
useful.

-Andi

Re: [Lse-tech] Re: [PATCH] New dcache / inode hash tuning patch

[Paul Menage]

>
>It would be possible to cache line optimize the layout of struct dentry
>in addition. May be an interesting add-on project for someone...

I played with this a few months ago, and sent a preliminary patch to
linux-kernel, but in my (fairly brief) testing on a 4-way system I
wasn't able to produce a measurable benefit from it. I think part of
this may have been due to contention on dcache_lock, so maybe dcache_rcu
will help there.

The main changes were to bring together all the data needed for checking
a non-matching dcache hash entry (modulo hash collisions) into one
cacheline, and to separate out the mostly-read-only fields from the 
change-frequently fields.

The original patch is at 

http://marc.theaimsgroup.com/?l=linux-kernel&m=102650654002932&w=2

>But for lookup walking even one cache line - the one containing d_hash -
>should be needed. Unless d_hash is unlucky enough to cross a cache
>line for its two members ... but I doubt that.

No, but on a 32-byte cache line system, d_parent, d_hash and d_name are
all on different cache lines, and they're used when checking each entry.
On 64-byte systems, d_parent and d_hash will be on the same line, but
d_name is still on a separate line and d_name.hash gets checked before
d_parent. So bringing these three fields on to the same cacheline
would theoretically be a win.

Paul

Re: [Lse-tech] Re: [PATCH] New dcache / inode hash tuning patch

[Andi Kleen]

On Fri, Feb 28, 2003 at 02:27:27AM -0800, Paul Menage wrote:
> >But for lookup walking even one cache line - the one containing d_hash -
> >should be needed. Unless d_hash is unlucky enough to cross a cache
> >line for its two members ... but I doubt that.
> 
> No, but on a 32-byte cache line system, d_parent, d_hash and d_name are
> all on different cache lines, and they're used when checking each entry.

... and dcache RCU checks d_bucket and d_move_count too in the hash 
walking loop.


> On 64-byte systems, d_parent and d_hash will be on the same line, but
> d_name is still on a separate line and d_name.hash gets checked before
> d_parent. So bringing these three fields on to the same cacheline
> would theoretically be a win.

Ok you're right. Optimizing the layout a bit would be probably a good 
idea. I won't include it in the hash patchkit for now to not do too
many things with the same patch.

-Andi

Re: [PATCH] New dcache / inode hash tuning patch

[Linus Torvalds]

On 28 Feb 2003, Andi Kleen wrote:
>
> Also isn't it a bit late in the 2.5 cycle to think about such radical
> changes like local lookup?

Look again at my suggestion: forcing locality by just changing the hash
function to _intentionally_ bunch directory hashes together.

Yes, it's "pseudo-locality" (and my example hash was truly broken: we 
must _not_ use the directory dentry hash value as part of the hash, as the 
hash needs to be stable over the whole lifetime of the directory dentry), 
but the point is that by just changing the hashing algorithm you can 
potentially get a good portion of the locality we want.

Right now the dcache hash is often something like 17 bits - and we could
easily make it so that roughly "half" the bits would be based purely on
the directory. That would still give each directory ~8 bits worth of
"local hashing", which is fairly reasonable.

> It sounds more like a nice 2.7 project.

It sounds more like changing two lines of code to me.

> I believe my patch with a bit more tweaking (my current 64K hash table
> seems to be too small) is suitable even for an soon to be stable
> kernel.

Quite frankly, right now the only report I've seen about your patch is 
that it made things slightly _slower_.

For a patch that is supposed to speed stuff up, that's a damn bad track 
record. Sorry.

I'd suggest you drop the hash size changes, and try with _just_ the hlist 
stuff, and once that is verified to perform well, _then_ worry about 
hashing changes. Because quite frankly, I suspect my "local hash" thing 
performs better than "make the hashes smaller". And the hash algorithm and 
size is _totally_ independent from whether it uses the regular lists or 
the hlists..

			Linus

Re: [PATCH] New dcache / inode hash tuning patch

[Andi Kleen]

On Fri, Feb 28, 2003 at 10:47:38AM -0800, Linus Torvalds wrote:
> Right now the dcache hash is often something like 17 bits - and we could
> easily make it so that roughly "half" the bits would be based purely on
> the directory. That would still give each directory ~8 bits worth of
> "local hashing", which is fairly reasonable.

Ok I will see if that helps.
> 
> > I believe my patch with a bit more tweaking (my current 64K hash table
> > seems to be too small) is suitable even for an soon to be stable
> > kernel.
> 
> Quite frankly, right now the only report I've seen about your patch is 
> that it made things slightly _slower_.

Actually that's not quite true. The report had a completely different
profile (lots of other functions had different percentages), so it likely
wasn't a comparable workload. I also don't think the NUMAQs are a good test
platform for this because they have 2MB of fast cache per CPU, while
the typical linux multiprocessor machine has much less. Yes you can 
fit an 1MB hash table into a 2 MB cache....

I'll generate some new numbers here locally over the weekend on P4,
but I only have a dual to test on and see how it performs.

-Andi

Re: [PATCH] New dcache / inode hash tuning patch

[Jan Harkes]

On Fri, Feb 28, 2003 at 07:59:10PM +0100, Andi Kleen wrote:
> > Quite frankly, right now the only report I've seen about your patch is 
> > that it made things slightly _slower_.
> 
> Actually that's not quite true. The report had a completely different
> profile (lots of other functions had different percentages), so it likely
> wasn't a comparable workload. I also don't think the NUMAQs are a good test

Did you read any of the comments on your patch?

Look at slabinfo to see how much space those objects are actually using.

Dentry cache hash table entries: 131072 (order: 8, 1048576 bytes)
Inode cache hash table entries: 65536 (order: 7, 524288 bytes)
inode_cache        33977  82901    512 11810 11843    1 :  124   62
dentry_cache       14490  14490    128  483  483    1 :  252  126

So the actual amount of memory used by f.i. the inodes is about 47MB
(11810 * 4KB).

The dentry cache hashtable currently has a fill-rate of about 10%, but
I've been running a lot of compilations and updatedb hasn't been around
for a long time. The VM has already aggressivly pruned it, which is to be
expected. The inode cache hash table is at about 50%. So if the hash
function is good we can assume that most hash chains are either empty or
only contain a single object and any hit will give us either a pointer
to the likely candidate or we know that the object isn't cached.

Now from what I read of your patch, it limits the size of the inode hash
table to 64KB, but with single pointers it can still address about 16000
hash chains. Assuming the same perfect hash distribution, all chains
will contain about 2 objects. So although the hash table fits much
better, each time we are looking for an uncached object we need to walk
2 objects that are spread across that 47MB chunk of allocated inodes,
instead of basically having a 'yes or no' answer pretty much from
looking at the hash table.

> platform for this because they have 2MB of fast cache per CPU, while
> the typical linux multiprocessor machine has much less. Yes you can 
> fit an 1MB hash table into a 2 MB cache....

Yes but you will never fit 47MB worth of inodes into that same 2MB
cache. And I realize that you can align things so that you don't have
to pull in more than a few cache-lines per object, but traversing ~0.5
pointers versus 2 pointers for every L1/L2 cache miss will be felt
because each traversal will hit another L2 cache-line.

It is probably far more useful to restrain the sizes of the inode and
dentry caches. Why would my system need 2-3 times the number of inodes
compared to dentries, while you pretty much always need to go through
the dentry cache to find the inodes. So a lot of those inodes are likely
unreferenced and we already have to hit the disk for the dentry lookup
anyways.

Jan

Re: [PATCH] New dcache / inode hash tuning patch

[Andi Kleen]

> The dentry cache hashtable currently has a fill-rate of about 10%, but
> I've been running a lot of compilations and updatedb hasn't been around
> for a long time. The VM has already aggressivly pruned it, which is to be
> expected. The inode cache hash table is at about 50%. So if the hash
> function is good we can assume that most hash chains are either empty or

The hash function isn't good and the hash chains are far from evenly
distributed. There are typically 30-40% empty buckets, while some
others are rather long.

In addition I think only a small fraction of the dentries are actually hot.
(no numbers on that, sorry) 

Your 47MB number doesn't make much sense for lookup tuning because these 
are not walked all the time. Only a few cache lines of the dentry are accessed
for a lookup.

If you think you have a better concept than me to tune it then feel
free to post a patch. 


> Now from what I read of your patch, it limits the size of the inode hash
> table to 64KB, but with single pointers it can still address about 16000
> hash chains. Assuming the same perfect hash distribution, all chains
> will contain about 2 objects. So although the hash table fits much
> better, each time we are looking for an uncached object we need to walk
> 2 objects that are spread across that 47MB chunk of allocated inodes,
> instead of basically having a 'yes or no' answer pretty much from
> looking at the hash table.

Apply the latest hash patch  and run some statistics over the bucket
distributions from /proc/dcache. You'll quickly see that your ideal model 
does not match reality at all.

> Yes but you will never fit 47MB worth of inodes into that same 2MB
> cache. And I realize that you can align things so that you don't have

The overall cached inodes are not too interesting - it is a long known
problem of linux that it caches too many inodes. But it doesn't matter
here because the dcache does all the hard lookup work and it hash
direct pointers to the inodes (no inode hash lookup needed). Most of them
are just wasted memory, but luckily not wasted cache.

What's interesting is to make the dentry lookup as fast as possible.

> to pull in more than a few cache-lines per object, but traversing ~0.5
> pointers versus 2 pointers for every L1/L2 cache miss will be felt
> because each traversal will hit another L2 cache-line.

Sorry but the average 2 bucket length number is completely unrealistic.
It doesn't make any sense to use it in an argument.


> 
> It is probably far more useful to restrain the sizes of the inode and
> dentry caches. Why would my system need 2-3 times the number of inodes

Limiting inode caches is probably a good idea. It's a long standing known
bug. At least definitely do prune inodes not referenced by the dcache
I believe some 2.4 trees fixed that in fact, but these fixes have
likely not moved to 2.5 yet. But really, it makes no difference
for these benchmarks, which have enough memory.

Limiting dcache is probably a bad idea. Recreating the dcache is far 
slower than any hash lookup. And a lot of Linux's good interactive
performance comes from the aggressive dcache caching.

-Andi

Re: [PATCH] New dcache / inode hash tuning patch

[Ed Tomlinson]

Andi Kleen wrote:

> The hash function isn't good and the hash chains are far from evenly
> distributed. There are typically 30-40% empty buckets, while some
> others are rather long.
> 
> In addition I think only a small fraction of the dentries are actually
> hot. (no numbers on that, sorry)

I wonder what would happen if you reordered the chains moving a 'found'
dentry to the front of the chain?  If this could be done without 
excessive locking it might help keep hot entries quickly accessable.
This operation should be cheaper given you are using hlists.

Ed Tomlinson

Re: [PATCH] New dcache / inode hash tuning patch

[Andi Kleen]

> I wonder what would happen if you reordered the chains moving a 'found'
> dentry to the front of the chain?  If this could be done without 
> excessive locking it might help keep hot entries quickly accessable.
> This operation should be cheaper given you are using hlists.

You would need to fetch a spinlock for LRU, while the current lookup
runs completely lockless.

-Andi

Re: [PATCH] New dcache / inode hash tuning patch

[Ed Tomlinson]

On March 1, 2003 04:08 am, Andi Kleen wrote:
> > I wonder what would happen if you reordered the chains moving a 'found'
> > dentry to the front of the chain?  If this could be done without
> > excessive locking it might help keep hot entries quickly accessable.
> > This operation should be cheaper given you are using hlists.
>
> You would need to fetch a spinlock for LRU, while the current lookup
> runs completely lockless.

You would have to lock the chain IF the dentry was not at the head.  Would
be interesting to see if this locking would hurt much - since hot 
dentries would not require a lock...

Ed

Re: [PATCH] New dcache / inode hash tuning patch

[Linus Torvalds]

In article <20030301043131.7D5301058@oscar.casa.dyndns.org>,
Ed Tomlinson  <tomlins@cam.org> wrote:
>
>I wonder what would happen if you reordered the chains moving a 'found'
>dentry to the front of the chain?  If this could be done without 
>excessive locking it might help keep hot entries quickly accessable.

The original dentry code actually did that. It sucks.

The reason it sucks is not so much just the locking, but the fact that
you dirty the cache lines, which means that not only are you blowing
your cache on that CPU, you also caused the other CPU's to blow _their_
caches (the lines that are in the cache can no longer be shared) AND you
caused excessive bus traffic for the writeouts. 

In other words: it makes sense if there is one or two really hot
entries.  But it does not make sense in general.  But you might have
some heuristic that does it "every 1000 lookups" or something like that,
to avoid the problems but still statistically getting the really hot
entries closer to the top. 

This cache behaviour is, btw, something that rcu made worse - with the
pre-rcu stuff, we avoided taking the dcache locks and incrementing the
dcache counters for intermediate cached lookups, and we only did it for
the leaf entry (or misses). 

I hope that we can re-do that optimization _with_ rcu in 2.7.x.

		Linus