[RESEND][PATCH 1/3] PPPoE: improved hashing routine

[RESEND][PATCH 1/3] PPPoE: improved hashing routine

[Florian Zumbiehl]

Hi,

I'm not sure whether this is really worth it, but it looked so
extremely inefficient that I couldn't resist - so let's hope providers
will keep PPPoE around for a while, at least until terabit dsl ;-)

The new code produces the same results as the old version and is
~ 3 to 6 times faster for 4-bit hashes on the CPUs I tested.

Florian

---------------------------------------------------------------------------
Signed-off-by: Florian Zumbiehl <florz@florz.de>

diff --git a/drivers/net/pppoe.c b/drivers/net/pppoe.c
index 9e51fcc..954328c 100644
--- a/drivers/net/pppoe.c
+++ b/drivers/net/pppoe.c
@@ -108,19 +108,24 @@ static inline int cmp_addr(struct pppoe_addr *a, unsigned long sid, char *addr)
 		(memcmp(a->remote,addr,ETH_ALEN) == 0));
 }
 
-static int hash_item(unsigned long sid, unsigned char *addr)
+#if 8%PPPOE_HASH_BITS
+#error 8 must be a multiple of PPPOE_HASH_BITS
+#endif
+
+static int hash_item(unsigned int sid, unsigned char *addr)
 {
-	char hash = 0;
-	int i, j;
+	unsigned char hash = 0;
+	unsigned int i;
 
-	for (i = 0; i < ETH_ALEN ; ++i) {
-		for (j = 0; j < 8/PPPOE_HASH_BITS ; ++j) {
-			hash ^= addr[i] >> ( j * PPPOE_HASH_BITS );
-		}
+	for (i = 0 ; i < ETH_ALEN ; i++) {
+		hash ^= addr[i];
+	}
+	for (i = 0 ; i < sizeof(sid_t)*8 ; i += 8 ){
+		hash ^= sid>>i;
+	}
+	for (i = 8 ; (i>>=1) >= PPPOE_HASH_BITS ; ) {
+		hash ^= hash>>i;
 	}
-
-	for (i = 0; i < (sizeof(unsigned long)*8) / PPPOE_HASH_BITS ; ++i)
-		hash ^= sid >> (i*PPPOE_HASH_BITS);
 
 	return hash & ( PPPOE_HASH_SIZE - 1 );
 }

Re: [RESEND][PATCH 1/3] PPPoE: improved hashing routine

[David Miller]

From: Florian Zumbiehl <florz@florz.de>
Date: Sun, 29 Jul 2007 08:04:23 +0200

> Hi,
> 
> I'm not sure whether this is really worth it, but it looked so
> extremely inefficient that I couldn't resist - so let's hope providers
> will keep PPPoE around for a while, at least until terabit dsl ;-)
> 
> The new code produces the same results as the old version and is
> ~ 3 to 6 times faster for 4-bit hashes on the CPUs I tested.
> 
> Florian
> 
> ---------------------------------------------------------------------------
> Signed-off-by: Florian Zumbiehl <florz@florz.de>
> 
> diff --git a/drivers/net/pppoe.c b/drivers/net/pppoe.c
> index 9e51fcc..954328c 100644
> --- a/drivers/net/pppoe.c
> +++ b/drivers/net/pppoe.c
> @@ -108,19 +108,24 @@ static inline int cmp_addr(struct pppoe_addr *a, unsigned long sid, char *addr)
>  		(memcmp(a->remote,addr,ETH_ALEN) == 0));
>  }
>  
> -static int hash_item(unsigned long sid, unsigned char *addr)
> +#if 8%PPPOE_HASH_BITS
> +#error 8 must be a multiple of PPPOE_HASH_BITS
> +#endif

Since PPPOE_HASH_BITS is "4" I would think this check will break the
build. :-)

Anyways, I looked at this myself and half of the problem comes from
the fact that "sid" is passed around as an "unsigned long" throughout
this entire file yet the thing is just a "__u16".

So the first thing to fix is to use __u16 consistently for sid values.
Then the sid hash looks obviously wrong and is easy to fix.

Then you end up with a hash_item() that simply looks like:

static unsigned int hash_item(__u16 sid, unsigned char *addr)
{
	unsigned int hash;

	hash = (((unsigned int)addr[0] << 24) |
		((unsigned int)addr[1] << 16) |
		((unsigned int)addr[2] <<  8) |
		((unsigned int)addr[3] <<  0));

	hash ^= (((unsigned int)addr[4] << 8) |
		 ((unsigned int)addr[5] << 0));

	hash ^= sid;

	return ((hash ^ (hash >> 8) ^ (hash >> 16)) &
		(PPPOE_HASH_SIZE - 1));
}

which is what I've checked into my tree.

Thanks!

Re: [RESEND][PATCH 1/3] PPPoE: improved hashing routine

[Florian Zumbiehl]

Hi,

> > -static int hash_item(unsigned long sid, unsigned char *addr)
> > +#if 8%PPPOE_HASH_BITS
> > +#error 8 must be a multiple of PPPOE_HASH_BITS
> > +#endif
> 
> Since PPPOE_HASH_BITS is "4" I would think this check will break the
> build. :-)

Erm, I thought that 8 was 4*2, but maybe I didn't quite understand that
natural numbers business ;-)

> Anyways, I looked at this myself and half of the problem comes from
> the fact that "sid" is passed around as an "unsigned long" throughout
> this entire file yet the thing is just a "__u16".
> 
> So the first thing to fix is to use __u16 consistently for sid values.
> Then the sid hash looks obviously wrong and is easy to fix.
> 
> Then you end up with a hash_item() that simply looks like:
> 
> static unsigned int hash_item(__u16 sid, unsigned char *addr)
> {
> 	unsigned int hash;
> 
> 	hash = (((unsigned int)addr[0] << 24) |
> 		((unsigned int)addr[1] << 16) |
> 		((unsigned int)addr[2] <<  8) |
> 		((unsigned int)addr[3] <<  0));
> 
> 	hash ^= (((unsigned int)addr[4] << 8) |
> 		 ((unsigned int)addr[5] << 0));
> 
> 	hash ^= sid;
> 
> 	return ((hash ^ (hash >> 8) ^ (hash >> 16)) &
> 		(PPPOE_HASH_SIZE - 1));
> }
> 
> which is what I've checked into my tree.

Erm, I'd say this not only produces different results than the old
version, but it also produces "wrong" results, in that it ignores quite
a bit of the data that's supposed to be hashed. If I didn't overlook
something, it only considers addr&0x0f0f0f0f0f00 and sid&0x0f0f, given
the right endianness of addr and that PPPOE_HASH_SIZE stays 16.

Florian

Re: [RESEND][PATCH 1/3] PPPoE: improved hashing routine

[David Miller]

From: Florian Zumbiehl <florz@florz.de>
Date: Tue, 31 Jul 2007 10:07:19 +0200

> Erm, I'd say this not only produces different results than the old
> version, but it also produces "wrong" results, in that it ignores quite
> a bit of the data that's supposed to be hashed. If I didn't overlook
> something, it only considers addr&0x0f0f0f0f0f00 and sid&0x0f0f, given
> the right endianness of addr and that PPPOE_HASH_SIZE stays 16.

You're right, I need to fix the shifts up.  How does this version
look?

	hash ^= (hash >> 4) ^ (hash >> 12) ^ (hash >> 20);
	return (head ^ (hash >> 8) ^ (hash >> 24)) &
		(PPPOE_HASH_SIZE - 1);

Actually it might be simpler and more efficient to just make
PPPOE_HASH_SHIFT be 8.

Re: [RESEND][PATCH 1/3] PPPoE: improved hashing routine

[Florian Zumbiehl]

Hi,

> > Erm, I'd say this not only produces different results than the old
> > version, but it also produces "wrong" results, in that it ignores quite
> > a bit of the data that's supposed to be hashed. If I didn't overlook
> > something, it only considers addr&0x0f0f0f0f0f00 and sid&0x0f0f, given
> > the right endianness of addr and that PPPOE_HASH_SIZE stays 16.
> 
> You're right, I need to fix the shifts up.  How does this version
> look?
> 
> 	hash ^= (hash >> 4) ^ (hash >> 12) ^ (hash >> 20);
> 	return (head ^ (hash >> 8) ^ (hash >> 24)) &
> 		(PPPOE_HASH_SIZE - 1);

Assuming that it was supposed to read s/head/hash/: Same disclaimers
apply, but I'd say this considers only addr&0xff0fff0f000f and
sid&0x0fff, so, well, yes, it's better, but still not quite what I
think it should be ;-)

> Actually it might be simpler and more efficient to just make
> PPPOE_HASH_SHIFT be 8.

SHIFT? SIZE? BITS?

Florian

Re: [RESEND][PATCH 1/3] PPPoE: improved hashing routine

[David Miller]

From: Florian Zumbiehl <florz@florz.de>
Date: Tue, 31 Jul 2007 11:01:59 +0200

> Assuming that it was supposed to read s/head/hash/: Same disclaimers
> apply, but I'd say this considers only addr&0xff0fff0f000f and
> sid&0x0fff, so, well, yes, it's better, but still not quite what I
> think it should be ;-)

Indeed it's still bogus.

> > Actually it might be simpler and more efficient to just make
> > PPPOE_HASH_SHIFT be 8.
> 
> SHIFT? SIZE? BITS?

You know what I meant :-)

PPPOE_HASH_BITS.

I guess otherwise we degenerate back to your original patch :)

Re: [RESEND][PATCH 1/3] PPPoE: improved hashing routine

[Florian Zumbiehl]

Hi,

> > > Actually it might be simpler and more efficient to just make
> > > PPPOE_HASH_SHIFT be 8.
> > 
> > SHIFT? SIZE? BITS?
> 
> You know what I meant :-)
> 
> PPPOE_HASH_BITS.

Actually, I wasn't sure, for "SHIFT" looks more similar to "SIZE"
than to "BITS", plus numbers are somewhat same order of magnitude
anyway, and I didn't quite see what you were up to, so ... whatever ;-)

> I guess otherwise we degenerate back to your original patch :)

Well, as I don't quite see what you were up to and as my patch doesn't
change anything about the semantics of the code, I'd at least prefer
that over your other suggestions so far ;-)

A few variations I tried back when I created the patch, using larger
things than a char for accumulating the pieces and then folding down
from that, turned out to be slower than what I finally submitted, at
least on the machines I tested it on. I didn't do comprehensive testing,
as it really doesn't matter, after all, but I think the version I
submitted is pretty fast, plus it's quite readable, and it keeps the
flexibility of different hash sizes, but still should allow the
compiler to optimize away the loops that allow for this flexibility.

Florian

Re: [RESEND][PATCH 1/3] PPPoE: improved hashing routine

[David Miller]

From: Florian Zumbiehl <florz@florz.de>
Date: Tue, 31 Jul 2007 13:05:47 +0200

> A few variations I tried back when I created the patch, using larger
> things than a char for accumulating the pieces and then folding down
> from that, turned out to be slower than what I finally submitted, at
> least on the machines I tested it on. I didn't do comprehensive testing,
> as it really doesn't matter, after all, but I think the version I
> submitted is pretty fast, plus it's quite readable, and it keeps the
> flexibility of different hash sizes, but still should allow the
> compiler to optimize away the loops that allow for this flexibility.

Therefore, I've put your original patch into the tree :-)

Thanks.