Re: [PATCH] improvement on net/sched/cls_fw.c's hash function

[Wang Jian <lark@linux.net.cn>]

[-- Attachment #1: Type: text/plain, Size: 1502 bytes --]

Hi jamal,


On 05 Apr 2005 12:11:35 -0400, jamal <hadi@cyberus.ca> wrote:

> Hi Wang,
> 
> On Tue, 2005-04-05 at 10:18, Wang Jian wrote:
> 
> > I am not saying that we must use jenkins. We may use a less expensive
> > hash function than jenkins, but better than & 0xFF.
> > 
> 
> Sure; point is as long as it doesnt destroy the common use in place.
> 
> >Anyway, I have done userspace test for jhash. The following test 
> > is done in a AMD Athlon 800MHz without other CPU load.
> > 
> 
> No, the test i was asking for is to show distribution of the
> hash not how long it took (which is also an ok test).

Sorry, the test is not on the AMD Athlon 800MHz, but a 2.4G Pentium4! I
didn't notice that. So the jhash's performance is not fast enough.

On AMD 800Mhz

line speed @ 1000Mbps

[root@home ~]# time ./a.out 
0.31user 0.00system 0:00.32elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+83minor)pagefaults 0swaps

line speed @ 100Mbps

[root@home ~]# time ./a.out 
0.03user 0.00system 0:00.03elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+83minor)pagefaults 0swaps


> 
> i.e if you fed the jenkins hash with 256 buckets - lets pick the number 1024 
> samples of the data you showed earlier for how fwmark looks like,
> how well would the result look like. 
> And what if you fed it with something like 1024 incremental fwmark from 
> say 1..1024?
> 

The test result looks not good. See attached file.

So let's find a better way.



-- 
  lark

[-- Attachment #2: jhash-dist.txt --]
[-- Type: application/octet-stream, Size: 5499 bytes --]

$VAR1 = {
          '32' => 1,
          '127' => 3,
          '90' => 6,
          '118' => 3,
          '206' => 2,
          '71' => 2,
          '102' => 7,
          '200' => 4,
          '18' => 7,
          '125' => 4,
          '16' => 8,
          '44' => 2,
          '55' => 4,
          '84' => 6,
          '27' => 4,
          '190' => 5,
          '233' => 4,
          '161' => 9,
          '57' => 2,
          '194' => 3,
          '95' => 5,
          '220' => 2,
          '20' => 2,
          '163' => 2,
          '231' => 1,
          '109' => 4,
          '243' => 3,
          '151' => 3,
          '89' => 3,
          '175' => 3,
          '148' => 7,
          '31' => 2,
          '35' => 2,
          '11' => 5,
          '208' => 5,
          '78' => 4,
          '93' => 2,
          '106' => 1,
          '157' => 5,
          '65' => 3,
          '29' => 5,
          '197' => 7,
          '203' => 2,
          '138' => 1,
          '114' => 4,
          '199' => 6,
          '226' => 2,
          '58' => 7,
          '15' => 3,
          '153' => 1,
          '211' => 5,
          '137' => 1,
          '81' => 5,
          '60' => 3,
          '73' => 2,
          '101' => 5,
          '76' => 5,
          '86' => 6,
          '62' => 6,
          '247' => 2,
          '67' => 4,
          '204' => 3,
          '241' => 3,
          '165' => 7,
          '139' => 6,
          '198' => 6,
          '129' => 7,
          '2' => 3,
          '17' => 5,
          '186' => 4,
          '82' => 6,
          '110' => 2,
          '147' => 9,
          '228' => 2,
          '236' => 4,
          '249' => 3,
          '202' => 6,
          '168' => 3,
          '218' => 1,
          '14' => 1,
          '135' => 3,
          '184' => 5,
          '69' => 5,
          '112' => 7,
          '172' => 3,
          '145' => 4,
          '49' => 4,
          '178' => 3,
          '24' => 5,
          '224' => 3,
          '140' => 7,
          '187' => 4,
          '223' => 5,
          '124' => 1,
          '104' => 3,
          '131' => 5,
          '181' => 2,
          '234' => 4,
          '79' => 3,
          '121' => 4,
          '212' => 3,
          '154' => 6,
          '0' => 5,
          '23' => 1,
          '96' => 7,
          '126' => 3,
          '238' => 3,
          '159' => 6,
          '251' => 3,
          '253' => 2,
          '160' => 6,
          '176' => 2,
          '47' => 7,
          '8' => 6,
          '98' => 4,
          '209' => 4,
          '216' => 4,
          '37' => 4,
          '117' => 2,
          '43' => 4,
          '195' => 7,
          '5' => 4,
          '170' => 4,
          '33' => 5,
          '63' => 5,
          '21' => 6,
          '7' => 5,
          '227' => 3,
          '80' => 4,
          '26' => 4,
          '193' => 1,
          '119' => 3,
          '99' => 1,
          '180' => 3,
          '244' => 4,
          '162' => 2,
          '72' => 4,
          '179' => 3,
          '255' => 3,
          '246' => 3,
          '74' => 4,
          '240' => 5,
          '182' => 2,
          '61' => 5,
          '230' => 4,
          '108' => 2,
          '115' => 6,
          '92' => 5,
          '103' => 5,
          '201' => 2,
          '232' => 4,
          '10' => 3,
          '113' => 6,
          '152' => 2,
          '189' => 6,
          '225' => 3,
          '207' => 2,
          '142' => 5,
          '91' => 1,
          '167' => 5,
          '48' => 6,
          '107' => 4,
          '87' => 3,
          '77' => 2,
          '174' => 6,
          '214' => 4,
          '133' => 4,
          '149' => 3,
          '123' => 4,
          '221' => 2,
          '50' => 7,
          '39' => 1,
          '210' => 2,
          '64' => 2,
          '97' => 5,
          '41' => 4,
          '12' => 4,
          '52' => 4,
          '173' => 1,
          '56' => 3,
          '229' => 2,
          '66' => 4,
          '45' => 6,
          '19' => 4,
          '54' => 4,
          '237' => 2,
          '70' => 4,
          '188' => 4,
          '68' => 4,
          '166' => 2,
          '1' => 2,
          '136' => 6,
          '116' => 8,
          '88' => 2,
          '30' => 2,
          '141' => 4,
          '144' => 5,
          '100' => 4,
          '222' => 6,
          '128' => 3,
          '25' => 5,
          '252' => 3,
          '28' => 5,
          '120' => 2,
          '75' => 2,
          '83' => 5,
          '40' => 2,
          '134' => 5,
          '156' => 5,
          '192' => 6,
          '250' => 8,
          '59' => 7,
          '215' => 4,
          '254' => 3,
          '177' => 2,
          '150' => 3,
          '130' => 3,
          '155' => 4,
          '53' => 4,
          '217' => 6,
          '245' => 4,
          '239' => 4,
          '122' => 1,
          '143' => 6,
          '205' => 2,
          '42' => 3,
          '158' => 5,
          '22' => 4,
          '46' => 9,
          '219' => 5,
          '13' => 2,
          '105' => 3,
          '235' => 9,
          '6' => 1,
          '85' => 4,
          '185' => 5,
          '3' => 5,
          '36' => 5,
          '183' => 6,
          '94' => 7,
          '213' => 5,
          '248' => 5,
          '146' => 4,
          '111' => 5,
          '9' => 6,
          '38' => 5,
          '4' => 6,
          '34' => 9,
          '132' => 3,
          '169' => 7,
          '164' => 6,
          '196' => 5,
          '171' => 4,
          '242' => 5
        };