Re: radix tree implementation for quota ?

[David Laight <david%l8s.co.uk@localhost>]

On Mon, Nov 29, 2010 at 10:44:11AM +0000, Sad Clouds wrote:
> 
> If you are hashing integer values, you can tune the hash table so that every 
> bucket will have no more than 1 entry. Usually you simply make hash table 
> size a prime number.

I very much doubt that is possible in the general case.
Of course, if your hash table is many, many times larger than the number
of hashed items, then it will tend to truthness.

> As for calculating the hash, modern hardware has fast modulo instructions. A 
> very simple test on Intel Atom D510 processor, seems to indicate a single 
> 'interger % prime' is roughly equal to two integer operations.

Erm, I'm not running a system with a divide instruction.
Division has to be done by software.
So, whereas integer multiply is a small number of clock, divide is 100s.

More generally, integer multiply can easily be executed in a short
pipeline with one multiply per clock, often in multiple execution units
and in parallel with other instructions.
(You can do multiple using 'full adders' in the time it takes a bit to
ripple a double length word - provided you throw enough silicon at it.)
Integer divide (effectively) need a compare/subtract loop, although you
can do more than one bit per interation, you can't start the next stage
until the previous on is complete.

The 57 clocks quoted for divide (on the Atom) seems reasonable, and it is
probably a full pipeline stall. Whereas the chip can probably do at
least one multiply per clock - pipelined as any other integer op.

        David

-- 
David Laight: david%l8s.co.uk@localhost