diff mbox

[next-next-2.6] netdev: better dev_name_hash

Message ID 4AE53382.8020308@gmail.com
State Changes Requested, archived
Delegated to: David Miller
Headers show

Commit Message

Eric Dumazet Oct. 26, 2009, 5:28 a.m. UTC 
Hagen Paul Pfeifer a écrit :
> * Octavian Purdila | 2009-10-25 23:55:32 [+0200]:
> 
>> My results shows that new17 is better or very close to jhash2. And I think its 
>> lighter then jhash too.
> 
> If new17 is very close to jhash/jhash2 then the cycles comes into play.
> Anyway, there is already a very potent hash interface in form of jhash{,2}.
> 
> +1 for jhash2
> 

In fact, new10 should be the 'perfect' hash for the "eth%d"
netdev use, not jhash (way more expensive in cpu cycles BTW)

Most linux machines in the world have less than 10 interfaces, jhash
would be really overkill.


Thanks


[PATCH net-next-2.6] netdev: better dev_name_hash

Octavian Purdila pointed out that the current dev_name_hash is 
not very good at spreading entries when a large number of interfaces
of the same type (e.g. ethXXXXX) are used.

Here is hash distribution of 16000 "dummy%d" devices :

full_name_hash[] = {
0, 0, 0, 375, 0, 0, 562, 0, 0, 0, 6, 0, 0, 0, 0, 56,
0, 0, 0, 374, 0, 0, 562, 0, 0, 0, 5, 0, 0, 0, 0, 57,
0, 0, 0, 375, 0, 0, 562, 0, 0, 0, 6, 1, 0, 0, 0, 56,
0, 0, 0, 375, 0, 0, 563, 0, 0, 0, 5, 1, 0, 0, 0, 56,
0, 0, 0, 375, 0, 0, 563, 0, 0, 0, 6, 1, 0, 0, 0, 56,
0, 0, 0, 375, 0, 0, 562, 0, 0, 0, 6, 0, 0, 0, 0, 57,
0, 0, 0, 375, 0, 0, 563, 0, 0, 0, 5, 0, 0, 0, 0, 56,
0, 0, 0, 376, 0, 0, 563, 0, 0, 0, 6, 1, 0, 0, 0, 56,
0, 0, 0, 375, 0, 0, 562, 0, 0, 0, 5, 1, 0, 0, 0, 57,
0, 0, 0, 374, 0, 0, 563, 0, 0, 0, 6, 1, 0, 0, 0, 56,
0, 0, 0, 375, 0, 0, 563, 0, 0, 0, 6, 1, 0, 0, 0, 56,
0, 0, 0, 376, 0, 0, 562, 0, 0, 0, 6, 0, 0, 0, 0, 56,
0, 0, 0, 375, 0, 0, 562, 0, 0, 0, 5, 0, 0, 0, 0, 56,
0, 0, 0, 375, 0, 0, 562, 0, 0, 0, 5, 1, 0, 0, 0, 56,
0, 0, 0, 375, 0, 0, 563, 0, 0, 0, 6, 1, 0, 0, 0, 57,
0, 0, 0, 375, 0, 0, 563, 0, 0, 0, 6, 1, 0, 0, 0, 56,
};

Instead of using full_name_hash(), netdev should use a hash suited
to its typical uses, which are a common substring followed by a base 10 number.

new hash distribution :

string_hash10[] = {
62, 63, 61, 60, 61, 63, 61, 62, 64, 62, 61, 62, 62, 60, 60, 61,
61, 59, 60, 63, 61, 60, 62, 63, 62, 60, 60, 60, 59, 60, 61, 59,
58, 61, 61, 60, 60, 61, 61, 58, 58, 59, 58, 57, 58, 59, 58, 59,
60, 60, 59, 61, 63, 61, 60, 60, 62, 61, 60, 61, 61, 60, 61, 62,
61, 62, 63, 63, 62, 62, 64, 64, 61, 62, 63, 62, 62, 63, 64, 64,
64, 64, 64, 62, 64, 65, 62, 62, 63, 63, 62, 62, 63, 64, 62, 62,
64, 62, 63, 65, 64, 63, 63, 64, 64, 63, 63, 67, 65, 64, 66, 66,
66, 66, 66, 65, 64, 63, 65, 63, 63, 66, 66, 64, 64, 65, 65, 64,
63, 66, 64, 64, 65, 65, 63, 64, 65, 63, 62, 61, 64, 61, 61, 63,
65, 64, 63, 64, 62, 62, 62, 64, 61, 61, 63, 63, 63, 63, 65, 64,
62, 61, 63, 61, 61, 62, 61, 61, 62, 63, 62, 62, 63, 66, 62, 61,
62, 62, 62, 61, 62, 61, 61, 61, 64, 62, 63, 65, 63, 63, 63, 64,
62, 60, 60, 63, 61, 61, 63, 62, 63, 65, 65, 63, 62, 63, 65, 62,
62, 64, 63, 63, 65, 66, 65, 64, 64, 65, 63, 64, 66, 63, 63, 65,
66, 64, 63, 64, 66, 64, 63, 65, 63, 64, 66, 66, 64, 63, 64, 64,
62, 62, 64, 61, 60, 62, 63, 62, 61, 62, 63, 61, 62, 63, 60, 59,
}; 


Based on a previous patch from Octavian Purdila

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
---
 net/core/dev.c |   15 ++++++++++++++-
 1 files changed, 14 insertions(+), 1 deletion(-)

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Comments

Krishna Kumar Oct. 26, 2009, 1:07 p.m. UTC | #1 
Eric Dumazet wrote on 10/26/2009 10:58:34 AM:

> In fact, new10 should be the 'perfect' hash for the "eth%d"
> netdev use, not jhash (way more expensive in cpu cycles BTW)
>
> Most linux machines in the world have less than 10 interfaces, jhash
> would be really overkill.
>
>
> Thanks
>
>
> [PATCH net-next-2.6] netdev: better dev_name_hash

Changing Eric's test program to pass a multiplier to string_hash()
and calling string_hash with multipler=<2 - 63> confirms that 10
is almost always the best number for varying netdev names. I print
the number of times perfect 64 was scored, and for most passed
device names, the best is for n=10, followed by n=5 and others.
Almost the worst was n=31, slightly better was n=17.

But other variables matter too, like fewer entries (4K or 1K) but
above values for are still better compared to n=31.

Thanks,

- KK

#include <stdio.h>
#include <string.h>

#define NUM_ENTRIES 1024

static inline unsigned int
string_hash_n(const unsigned char *name, unsigned int len, int n)
{
        unsigned hash = 0;
        int i;

        for (i = 0; i < len; ++i)
                hash = n * hash + name[i];
        return hash;
}

int best_n = -1, best_n_val = -1;

void print_dist(unsigned int *dist, int n)
{
        unsigned int i;
        int perfect = 0;


printf("-----------------------------------------------------------\n");
        printf("n=%d[] = {\n", n);
        for (i = 0; i < 256; i++) {
                if (dist[i] == NUM_ENTRIES/256)
                        perfect++;
                printf("%d, ", dist[i]);
                if ((i & 15) == 15) putchar('\n');
        }
        if (perfect > best_n_val) {
                best_n_val = perfect;
                best_n = n;
        }
        printf("}; (PERFECT = %d (n=%d))\n", perfect, n);
}

int main(int argc, char *argv[])
{
        int n, i;
        char *str, name[16];
        unsigned int hash, hashdist[256];

        if (argc == 1)
                str="eth";
        else
                str=argv[1];

        for (n = 2; n < 63; n++) {
                memset(hashdist, 0, 256*sizeof(int));
                for (i = 0; i < NUM_ENTRIES; i++) {
                        unsigned int len = sprintf(name, "%s%d", str, i);

                        hash = string_hash_n(name, len, n);
                        hashdist[hash & 255]++;
                }
                print_dist(hashdist, n);
        }
        printf("Best N was %d, and perfect entries: %d\n",
                best_n, best_n_val);
        return 0;
}

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Octavian Purdila Oct. 26, 2009, 2:31 p.m. UTC | #2 
On Monday 26 October 2009 15:07:31 you wrote:
> Eric Dumazet wrote on 10/26/2009 10:58:34 AM:
> > In fact, new10 should be the 'perfect' hash for the "eth%d"
> > netdev use, not jhash (way more expensive in cpu cycles BTW)
> >
> > Most linux machines in the world have less than 10 interfaces, jhash
> > would be really overkill.
> >
> >
> > Thanks
> >
> >
> > [PATCH net-next-2.6] netdev: better dev_name_hash
> 
> Changing Eric's test program to pass a multiplier to string_hash()
> and calling string_hash with multipler=<2 - 63> confirms that 10
> is almost always the best number for varying netdev names. I print
> the number of times perfect 64 was scored, and for most passed
> device names, the best is for n=10, followed by n=5 and others.
> Almost the worst was n=31, slightly better was n=17.
> 
> But other variables matter too, like fewer entries (4K or 1K) but
> above values for are still better compared to n=31.
> 

Hmm, I've found out that it very much depends on the name as well:

0 - orig, 1 - jhash, 2 - new10, 3 - new17, 4 - new31

$ ./dev_name_hash ixint 16000 0 16
score 24741
$ ./dev_name_hash ixint 16000 1 16
score 17949
$ ./dev_name_hash ixint 16000 2 16
score 16000
$ ./dev_name_hash ixint 16000 3 16
score 16715
$ ./dev_name_hash ixint 16000 4 16
score 18125


$ ./dev_name_hash ixunc 16000 0 16
score 24741
$ ./dev_name_hash ixunc 16000 1 16
score 17904
$ ./dev_name_hash ixunc 16000 2 16
score 22180
$ ./dev_name_hash ixunc 16000 3 16
score 17065
$ ./dev_name_hash ixunc 16000 4 16
score 18038
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Eric Dumazet Oct. 26, 2009, 2:55 p.m. UTC | #3 
Octavian Purdila a écrit :
> On Monday 26 October 2009 15:07:31 you wrote:
>> Eric Dumazet wrote on 10/26/2009 10:58:34 AM:
>>> In fact, new10 should be the 'perfect' hash for the "eth%d"
>>> netdev use, not jhash (way more expensive in cpu cycles BTW)
>>>
>>> Most linux machines in the world have less than 10 interfaces, jhash
>>> would be really overkill.
>>>
>>>
>>> Thanks
>>>
>>>
>>> [PATCH net-next-2.6] netdev: better dev_name_hash
>> Changing Eric's test program to pass a multiplier to string_hash()
>> and calling string_hash with multipler=<2 - 63> confirms that 10
>> is almost always the best number for varying netdev names. I print
>> the number of times perfect 64 was scored, and for most passed
>> device names, the best is for n=10, followed by n=5 and others.
>> Almost the worst was n=31, slightly better was n=17.
>>
>> But other variables matter too, like fewer entries (4K or 1K) but
>> above values for are still better compared to n=31.
>>
> 
> Hmm, I've found out that it very much depends on the name as well:
> 
> 0 - orig, 1 - jhash, 2 - new10, 3 - new17, 4 - new31
> 
> $ ./dev_name_hash ixint 16000 0 16
> score 24741
> $ ./dev_name_hash ixint 16000 1 16
> score 17949
> $ ./dev_name_hash ixint 16000 2 16
> score 16000
> $ ./dev_name_hash ixint 16000 3 16
> score 16715
> $ ./dev_name_hash ixint 16000 4 16
> score 18125
> 
> 
> $ ./dev_name_hash ixunc 16000 0 16
> score 24741
> $ ./dev_name_hash ixunc 16000 1 16
> score 17904
> $ ./dev_name_hash ixunc 16000 2 16
> score 22180
> $ ./dev_name_hash ixunc 16000 3 16
> score 17065

> $ ./dev_name_hash ixunc 16000 4 16
> score 18038

This is because you chose a 65536 slots hash table, to store 16000 elements

The ideal function should be :

$ ./dev_name_hash ixunc 16000 5 16
score 16000

unsigned int dev_name_hash_new10bis(const char *name)
{
	unsigned hash = 0;
	int len = strnlen(name, IFNAMSIZ);
	int i;

	for (i = 0; i < len; ++i)
		hash = 10 * hash + (name[i] - '0');
	return hash;
}

But should we really care ?


--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Octavian Purdila Oct. 26, 2009, 3:52 p.m. UTC | #4 
On Monday 26 October 2009 16:55:10 you wrote:
> 
> This is because you chose a 65536 slots hash table, to store 16000 elements
> 
> The ideal function should be :
> 
> $ ./dev_name_hash ixunc 16000 5 16
> score 16000
> 
> unsigned int dev_name_hash_new10bis(const char *name)
> {
> 	unsigned hash = 0;
> 	int len = strnlen(name, IFNAMSIZ);
> 	int i;
> 
> 	for (i = 0; i < len; ++i)
> 		hash = 10 * hash + (name[i] - '0');
> 	return hash;
> }
> 

Eric, thanks a lot for your help. This is turning into a very instructive 
thread for me :)

10bis performs better for ixunc but interestingly performs worse for ixint 
now. I also get mixed results for the two when using other names like ppp or 
gtp.

2 - new10, 3 - new10bis

score 49852
$ ./dev_name_hash ixint 32000 3 14
score 53194
$ ./dev_name_hash ixunc 32000 2 14
score 55232
$ ./dev_name_hash ixunc 32000 3 14
score 48168

> But should we really care ?

I'm just testing various common cases we use here ({ixint,ixunc,gtp,ppp,gre} 
{1000,16000,32000,128000} {14,16}). 

Ideally we want a hash function that performs better in all cases  - but I 
understand that it may not be possible.

I will play more with it and see if I can come up with something better, but 
in any case the new{10,10bis,17,31} performs much better than full_name_hash 
and most of the time better that jhash .
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
stephen hemminger Oct. 26, 2009, 4:55 p.m. UTC | #5 
Added more algorithms to test...

Time is in seconds for 10000000 entries with hashbits = 8
Ratio is number of probes / ideal hash probes

Result sorted by distribution:

Algorithm             Time       Ratio       Max   StdDev
string10             1.434087       1.00     39064   0.01
SuperFastHash        1.469511       1.00     40497   2.17
string_hash17        1.472544       1.00     39497   1.50
jhash_string         1.501508       1.00     39669   1.04
crc                  2.826795       1.00     39088   0.07
md5_string           3.608253       1.00     39605   0.98
djb2                 1.462722       1.15     60681  76.16
string_hash31        1.457253       1.21     64950  91.12
sdbm                 1.566174       2.38    129900 232.22
pjw                  1.527306       2.45     99990 237.86
elf                  1.576096       2.45     99990 237.86
kr_hash              1.400072       7.80    468451 515.52
fletcher             1.449671       7.80    468451 515.52
full_name_hash       1.487707      13.09    562501 687.24
xor                  1.400403      13.36    583189 694.98
lastchar             1.348798      25.60   1000000 980.27

Another run sorted by speed:
Algorithm             Time       Ratio       Max   StdDev
lastchar             1.338545      25.60   1000000 980.27
kr_hash              1.398453       7.80    468451 515.52
xor                  1.398843      13.36    583189 694.98
string10             1.432756       1.00     39064   0.01
fletcher             1.448499       7.80    468451 515.52
string_hash31        1.457524       1.21     64950  91.12
string_hash17        1.462548       1.00     39497   1.50
djb2                 1.462956       1.15     60681  76.16
SuperFastHash        1.469907       1.00     40497   2.17
full_name_hash       1.486465      13.09    562501 687.24
jhash_string         1.500959       1.00     39669   1.04
pjw                  1.526097       2.45     99990 237.86
sdbm                 1.566533       2.38    129900 232.22
elf                  1.576470       2.45     99990 237.86
crc                  2.811210       1.00     39088   0.07
md5_string           3.604675       1.00     39605   0.98

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
stephen hemminger Oct. 26, 2009, 5:45 p.m. UTC | #6 
Another algorithm that scores well in my tests.

http://isthe.com/chongo/tech/comp/fnv/

Algorithm             Time       Ratio       Max   StdDev
string10             1.433267       1.00     39064   0.01
string_hash17        1.461422       1.00     39497   1.50
fnv1a                1.472216       1.00     39895   2.25
jhash_string         1.482494       1.00     39669   1.04


static unsigned int fnv32(const unsigned char *key, unsigned int len)
{
	uint32_t hval = 2166136261;
	unsigned int i;

	for (i = 0; i < len; i++) {
		hval ^= key[i];
		/* optimized multiply by 0x01000193 */
		hval += (hval<<1) + (hval<<4) + (hval<<7)
			+ (hval<<8) + (hval<<24);
	}

	return hval;
}
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
David Miller Oct. 27, 2009, 1:24 a.m. UTC | #7 
From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Mon, 26 Oct 2009 15:55:10 +0100

> But should we really care ?

The only thing I see consistently in this thread is that
jhash performs consistently well and without any tweaking.

And without any assumptions about the characteristics of
the device names.  I've seen everything from the traditional
"eth%d" to things like "davem_is_a_prick%d" so you really cannot
optimize for anything in particular.

Jenkins is ~50 cycles per round of 4 bytes last time I checked, give
or take, and that was on crappy sparc. :-) So the execution cost is
really not that bad, contrary to what I've seen claimed as an argument
against using jhash here.

And if I-cache footprint is really an issue, we can have one
out-of-line expansion of jhash somewhere under lib/ since we use jhash
in so many places these days.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Eric Dumazet Oct. 27, 2009, 1:40 a.m. UTC | #8 
David Miller a écrit :
> From: Eric Dumazet <eric.dumazet@gmail.com>
> Date: Mon, 26 Oct 2009 15:55:10 +0100
> 
>> But should we really care ?
> 
> The only thing I see consistently in this thread is that
> jhash performs consistently well and without any tweaking.
> 
> And without any assumptions about the characteristics of
> the device names.  I've seen everything from the traditional
> "eth%d" to things like "davem_is_a_prick%d" so you really cannot
> optimize for anything in particular.
> 
> Jenkins is ~50 cycles per round of 4 bytes last time I checked, give
> or take, and that was on crappy sparc. :-) So the execution cost is
> really not that bad, contrary to what I've seen claimed as an argument
> against using jhash here.
> 
> And if I-cache footprint is really an issue, we can have one
> out-of-line expansion of jhash somewhere under lib/ since we use jhash
> in so many places these days.

Well, since Stephen posted a generic patch on lkml, I suspect we'll take
the dcache hash anyway ?

But yes, last time I checked, jhash was pretty big, so an out-of-line
version is welcome :)
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
diff mbox

Patch

diff --git a/net/core/dev.c b/net/core/dev.c
index fa88dcd..e192068 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -196,9 +196,22 @@  EXPORT_SYMBOL(dev_base_lock);
 #define NETDEV_HASHBITS	8
 #define NETDEV_HASHENTRIES (1 << NETDEV_HASHBITS)
 
+/*
+ * Because of "eth%d" patterns, following hash is giving good distribution
+ */
+static inline unsigned int string_hash10(const char *name, unsigned int len)
+{
+	unsigned int i, hash = 0;
+
+	for (i = 0; i < len; i++)
+		hash = hash * 10 + name[i];
+
+	return hash;
+}
+
 static inline struct hlist_head *dev_name_hash(struct net *net, const char *name)
 {
-	unsigned hash = full_name_hash(name, strnlen(name, IFNAMSIZ));
+	unsigned hash = string_hash10(name, strnlen(name, IFNAMSIZ));
 	return &net->dev_name_head[hash & ((1 << NETDEV_HASHBITS) - 1)];
 }