Re: [PATCH] Decrease hash table memory overhead

From: Andi Kleen (ak@muc.de)
Date: Mon Jul 31 2000 - 01:24:07 EST


On Mon, Jul 31, 2000 at 08:03:26AM +0200, Linus Torvalds wrote:
>
>
> On Mon, 31 Jul 2000, Andi Kleen wrote:
> >
> > Ok, it is worth about 13% for iget() on a K6-400 during cache trashing
> > with empty file system read_inode.
>
> I'm not interested in made-up benchmarks that cannot be reproduced under
> real load.

I don't think it is more made up than e.g. lmbench doing getpid() all
the time to test syscall latency. The other system is simulated by the
cache trashing. Doing it completely from user space would probably
add so many other variables and variances that the results would be hard
to interpret.
Instead I chose to benchmark the single function I care about directly.

>
> Can you make it show up on a real filesystem even with a contrieved
> user-mode benchmark?
>
> (Btw, even if you do convince me, please don't use a name like "hlist".
> "hlist WHAT?" What's the "h" for? "hash"? Why? Basically, it sounds
> nonsensical).

It stands for hash yes. single_pointer_head_list would be more accurate, but
I didn't like the sphlist name. Its most common use is probably hash tables,
so I chose the h- prefix instead.

>
> Btw, from past exprience I've found that it can be a lot more advantageous
> to just dynamically move the hash entries to the front of the list when
> accessed, rather than worry about how the list is set up. Hashes are bad
> on the caches by design, and whether the hash table takes up x or 2x of
> memory is pretty much immaterial for performance. But whether you find
> the entry on the first or the fifth try is noticeable.
>
> I suspect you'd find more of a performance advantage from trying something
> like that instead..

I'm not sure about that. Once you did the iget() the inode should be cached
in the dentry, so it is unlikely that LRU will do much good. For the dcache
hash it may be a better idea, but are there that many workloads that always
open/link/iget the same file ? If they do all the necessary cache lines
for hash head and inode list are probably in cache, so it'll go like smoke.
It'll get a lot slower when it falls out of CPU cache. The patch tries
to make this very slow case much more unlikely (50%)

-Andi

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/



This archive was generated by hypermail 2b29 : Mon Jul 31 2000 - 21:00:32 EST