Message-ID: <4AE68E23.20205@gmail.com>
Date: Tue, 27 Oct 2009 07:07:31 +0100
From: Eric Dumazet <eric.dumazet@gmail.com>
User-Agent: Thunderbird 2.0.0.23 (Windows/20090812)
MIME-Version: 1.0
To: Stephen Hemminger <stephen.hemminger@vyatta.com>
CC: Andrew Morton <akpm@linux-foundation.org>,
       Linus Torvalds <torvalds@linux-foundation.org>,
       Octavian Purdila <opurdila@ixiacom.com>, netdev@vger.kernel.org,
       linux-kernel@vger.kernel.org, Al Viro <viro@zeniv.linux.org.uk>
Subject: Re: [PATCH] dcache: better name hash function
References: <19864844.24581256620784317.JavaMail.root@tahiti.vyatta.com>
In-Reply-To: <19864844.24581256620784317.JavaMail.root@tahiti.vyatta.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1391
Lines: 55

Stephen Hemminger a écrit :
> One of the root causes of slowness in network usage
> was my original choice of power of 2 for hash size, to avoid
> a mod operation. It turns out if size is not a power of 2
> the original algorithm works fairly well.

Interesting, but I suspect all users have power of 2 tables :(

> 
> On slow cpu; with 10million entries and 211 hash size
> 
>
> 
> How important is saving the one division, versus getting better
> distribution.


unsigned int fold1(unsigned hash)
{
	return hash % 211;
}

Compiler uses a reciprocal divide because of 211 being a constant.

And you also could try following that contains one multiply only,
and check if hash distribution properties are still OK

unsigned int fold2(unsigned hash)
{
	return ((unsigned long long)hash * 211) >> 32;
}

fold1:
        movl    4(%esp), %ecx
        movl    $-1689489505, %edx
        movl    %ecx, %eax
        mull    %edx
        shrl    $7, %edx
        imull   $211, %edx, %edx
        subl    %edx, %ecx
        movl    %ecx, %eax
        ret

fold2:
        movl    $211, %eax
        mull    4(%esp)
        movl    %edx, %eax
        ret


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