[lkml]   [2000]   [Jul]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [PATCH] Decrease hash table memory overhead
On Mon, Jul 31, 2000 at 08:00:28PM +0200, Linus Torvalds wrote:
> > 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.
> Yes.
> The other way to say the same thing is
> "Doing it from user space might show that it's not a performance
> optimization that cna be noticed".

Or it might. It is just too much work for me, because it is takes too long
to do right.

I believe when you manage to save 200K of active L2 cache lines from kernel
use, then a user with a 512K L2 cache will notice it. The hlists are
hopefully good for 20-40K. It would be a beginning at least.

> > 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.
> If it makes you feel any better, I would have hated "sphlist" even more.
> Basically, I think it's the wrong level of abstraction. If it is
> abstracted like a list, then I like the current lists more that do not
> need conditionals in many of the common operations. If it were to be
> abstraced as a hash thing, then I might like it.

Less jump, but they need more registers on x86, which is IMHO worse (or at
similarly bad). This one would be probably hard to benchmark for though.

Anyways, hlists are already used all over the kernel (e.g. try grep pprev
net/ipv4/*), just everybody is reinventing the wheel on them all the
time. I did that myself several times. It would be nicer to use list_*()
macros the time, just without the bloat of the list_* list heads.

To solve your abstraction problems they could be renamed slists, but then
people would confuse them with single linked lists.

> Something like "hash_insert()" and "hash_remove()" etc would be
> acceptable, but then you'd need to really make the abstraction layer
> higher (ie implement some form of generic "hash_find()" etc). This might
> well be worthwhile - I suspect there is quite a lot of common code in
> inode/page/dentry hashing, and at that point the interface would be _more_
> than "just another list implementation".

I suspect that would either end up with lots of pseudo functional function
pointer (do_foo(hash_list, void (*foo_functor)(void *, void *)) and other slow
horrors) or a disgusting macro mess like the older lists.h that was
recently removed.

-Andi (who goes back to code pprev lists by hand)

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:57    [W:0.065 / U:9.500 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site