Re: [PATCH] NET : change layout of ehash table
On Friday 09 February 2007 10:43, David Miller wrote: > Current gcc does the right thing, even for weird sizes like 56 and 52 > which expands to many IALU operations. ... except if you use -Os, which at least on x86* is default and is what distros ship with. -Andi - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] NET : change layout of ehash table
From: Eric Dumazet <[EMAIL PROTECTED]> Date: Fri, 9 Feb 2007 10:36:58 +0100 > Thats strange, because pointer arithmetic is unsigned... > I dont know when gcc started to use reciprocal division, maybe your gcc was > very old ? Yep, it was only on older gcc's. And as the sparc gcc backend co-maintainer, I remember what the problem was. The insn costs for multiply and divide were not set properly on UltraSPARC, so it used the defaults, which made gcc think divides were very cheap :-) Current gcc does the right thing, even for weird sizes like 56 and 52 which expands to many IALU operations. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] NET : change layout of ehash table
On Friday 09 February 2007 10:15, David Miller wrote:
> From: Eric Dumazet <[EMAIL PROTECTED]>
> Date: Fri, 9 Feb 2007 10:06:24 +0100
>
> > Yes, but a decent C compiler for such targets should not use a
> > multiply instruction to perform a (idx * 12) operation... :)
>
> Good point.
>
> Actually, I could never get GCC to avoid a divide on sparc64 for
> certain kinds of pointer arithmetic when the elements were not
> a power of two. It probably has something to do with signedness.
>
> I think I narrowed is down to the fact that you can't legally replace
> a signed divide with shift/add/subtract. But I could be remembering
> things wrong.
Thats strange, because pointer arithmetic is unsigned...
I dont know when gcc started to use reciprocal division, maybe your gcc was
very old ?
$ cat div.c
struct s1 {int pad[3];};
unsigned long diffptr(struct s1 *a, struct s1 *b)
{
return a - b;
}
If compiled on i386 , gcc-4.1.1 :
$ gcc -O2 -fomit-frame-pointer -S div.c
diffptr:
movl4(%esp), %eax
subl8(%esp), %eax
sarl$2, %eax
imull $-1431655765, %eax, %eax
ret
If compiled on x86_64 , gcc-4.1.1:
diffptr:
subq%rsi, %rdi
movabsq $-6148914691236517205, %rax
sarq$2, %rdi
imulq %rax, %rdi
movq%rdi, %rax
ret
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] NET : change layout of ehash table
From: Eric Dumazet <[EMAIL PROTECTED]> Date: Fri, 9 Feb 2007 10:06:24 +0100 > Yes, but a decent C compiler for such targets should not use a > multiply instruction to perform a (idx * 12) operation... :) Good point. Actually, I could never get GCC to avoid a divide on sparc64 for certain kinds of pointer arithmetic when the elements were not a power of two. It probably has something to do with signedness. I think I narrowed is down to the fact that you can't legally replace a signed divide with shift/add/subtract. But I could be remembering things wrong. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] NET : change layout of ehash table
On Friday 09 February 2007 09:40, David Miller wrote: > From: Andi Kleen <[EMAIL PROTECTED]> > Date: 09 Feb 2007 10:18:03 +0100 > > > David Miller <[EMAIL PROTECTED]> writes: > > > I've applied this, but I _REALLY_ don't like the new multiply > > > instructions that are used now in the hash indexing paths when > > > CONFIG_SMP is set. > > > > > > I think that's a higher cost than the memory waste. > > > > You're serious? multiply on a modern CPU is _much_ cheaper than a cache > > miss e.g. a K8 can do a arbitary 64bit multiplication in 3-7 cycles. > > Any cache miss will be in the three to four digits at least. > > I'm not thinking of modern CPUs, I'm think of the little > guys :-) Yes, but a decent C compiler for such targets should not use a multiply instruction to perform a (idx * 12) operation... :) - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] NET : change layout of ehash table
On Friday 09 February 2007 09:40, David Miller wrote: > From: Andi Kleen <[EMAIL PROTECTED]> > Date: 09 Feb 2007 10:18:03 +0100 > > > David Miller <[EMAIL PROTECTED]> writes: > > > > > > I've applied this, but I _REALLY_ don't like the new multiply > > > instructions that are used now in the hash indexing paths when > > > CONFIG_SMP is set. > > > > > > I think that's a higher cost than the memory waste. > > > > You're serious? multiply on a modern CPU is _much_ cheaper than a cache miss > > e.g. a K8 can do a arbitary 64bit multiplication in 3-7 cycles. > > Any cache miss will be in the three to four digits at least. > > I'm not thinking of modern CPUs, I'm think of the little > guys :-) Even for them it's true, although the ratios are smaller (unless you go back to m68000 or VAX days) -Andi - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] NET : change layout of ehash table
From: Andi Kleen <[EMAIL PROTECTED]> Date: 09 Feb 2007 10:18:03 +0100 > David Miller <[EMAIL PROTECTED]> writes: > > > > I've applied this, but I _REALLY_ don't like the new multiply > > instructions that are used now in the hash indexing paths when > > CONFIG_SMP is set. > > > > I think that's a higher cost than the memory waste. > > You're serious? multiply on a modern CPU is _much_ cheaper than a cache miss > e.g. a K8 can do a arbitary 64bit multiplication in 3-7 cycles. > Any cache miss will be in the three to four digits at least. I'm not thinking of modern CPUs, I'm think of the little guys :-) - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] NET : change layout of ehash table
David Miller <[EMAIL PROTECTED]> writes: > > I've applied this, but I _REALLY_ don't like the new multiply > instructions that are used now in the hash indexing paths when > CONFIG_SMP is set. > > I think that's a higher cost than the memory waste. You're serious? multiply on a modern CPU is _much_ cheaper than a cache miss e.g. a K8 can do a arbitary 64bit multiplication in 3-7 cycles. Any cache miss will be in the three to four digits at least. -Andi - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] NET : change layout of ehash table
From: Eric Dumazet <[EMAIL PROTECTED]> Date: Wed, 7 Feb 2007 11:59:34 +0100 > ehash table layout is currently this one : > > First half of this table is used by sockets not in TIME_WAIT state > Second half of it is used by sockets in TIME_WAIT state. > > This is non optimal because of for a given hash or socket, the two chain > heads > are located in separate cache lines. > Moreover the locks of the second half are never used. > > If instead of this halving, we use two list heads in inet_ehash_bucket > instead > of only one, we probably can avoid one cache miss, and reduce ram usage, > particularly if sizeof(rwlock_t) is big (various CONFIG_DEBUG_SPINLOCK, > CONFIG_DEBUG_LOCK_ALLOC settings). So we still halves the table but we keep > together related chains to speedup lookups and socket state change. > > In this patch I did not try to align struct inet_ehash_bucket, but a future > patch could try to make this structure have a convenient size (a power of two > or a multiple of L1_CACHE_SIZE). > I guess rwlock will just vanish as soon as RCU is plugged into ehash :) , so > maybe we dont need to scratch our heads to align the bucket... > > Note : In case struct inet_ehash_bucket is not a power of two, we could > probably change alloc_large_system_hash() (in case it use __get_free_pages()) > to free the unused space. It currently allocates a big zone, but the last > quarter of it could be freed. Again, this should be a temporary 'problem'. > > Patch tested on ipv4 tcp only, but should be OK for IPV6 and DCCP. > > Signed-off-by: Eric Dumazet <[EMAIL PROTECTED]> I've applied this, but I _REALLY_ don't like the new multiply instructions that are used now in the hash indexing paths when CONFIG_SMP is set. I think that's a higher cost than the memory waste. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
