[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

**To**:**Sad Clouds <cryintothebluesky%googlemail.com@localhost>****Subject**:**Re: radix tree implementation for quota ?****From**:**David Laight <david%l8s.co.uk@localhost>**- Date: Mon, 29 Nov 2010 17:33:48 +0000

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

**Follow-Ups**:**Re: radix tree implementation for quota ?***From:*Matthias Drochner

**References**:**radix tree implementation for quota ?***From:*Manuel Bouyer

**Re: radix tree implementation for quota ?***From:*Sad Clouds

**Re: radix tree implementation for quota ?***From:*Manuel Bouyer

**Re: radix tree implementation for quota ?***From:*David Laight

**Re: radix tree implementation for quota ?***From:*Sad Clouds

**Re: radix tree implementation for quota ?***From:*Joerg Sonnenberger

**Re: radix tree implementation for quota ?***From:*Sad Clouds

**Re: radix tree implementation for quota ?***From:*David Laight

**Re: radix tree implementation for quota ?***From:*Sad Clouds

- Prev by Date:
**Re: radix tree implementation for quota ?** - Next by Date:
**Re: radix tree implementation for quota ?** - Previous by Thread:
**Re: radix tree implementation for quota ?** - Next by Thread:
**Re: radix tree implementation for quota ?** - Indexes: