Re: [PATCH] [NET] Size listen hash tables using backlog hint

[Eric Dumazet <dada1@cosmosbay.com>]

David Miller a écrit :
> From: Eric Dumazet <dada1@cosmosbay.com>
> Date: Thu, 19 Oct 2006 07:12:58 +0200
> 
>> A 66 MHz 486 can perform 1.000.000 divisions per second. Is it a 'slow' cpu ?
> 
> Sparc and some other embedded chips have no division/modulus integer
> instruction and do it in software.

How many times this division will be done ? As I said, tcp session establishment.

Are you aware a division is done in slab code when you kfree() one network 
frames ? That is much more problematic than SYN packets.

> 
>> So... what do you prefer :
>>
>> 1) Keep the modulus
>> 2) allocate two blocks of ram (powser-of -two hash size, but one extra 
>> indirection)
>> 3) waste near half of ram because one block allocated, and power-of-two hash size.
> 
> I thought the problem was that you use a modulus and non-power-of-2
> hash table size because rounding up to the next power of 2 wastes
> a lot of space?  Given that, my suggestion is simply to not round
> up to the next power-of-2, or only do so when we are very very close
> to that next power-of-2.

My main problem is being able to use a large hash table on big servers.

With power-of two constraint, plus kmalloc max size constraint, we can use 
half the size we could.

Are you suggesting something like :

Allocation time:
----------------
if (cpu is very_very_slow or hash size small_enough) {
   ptr->size = power_of_too;
   ptr->size_mask = (power_of_two - 1);
} else {
   ptr->size = somevalue;
   ptr->size_mask = ~0;
}

Lookup time :
---------------
if (ptr->size_mask != ~0)
     slot = hash & ptr->size_mask;
else
     slot = hash % ptr->size;

The extra conditional branch may be more expensive than just doing division on 
99% of cpus...