Re: Why conf-split prime?
Ian Lance Taylor [EMAIL PROTECTED] wrote: Suppose the input numbers are 2 4 6 8 10 12. Suppose the hash size is 8. Then the buckets are 2 4 6 0 2 4. Note the bad distribution. Suppose the hash size is 7. Then the buckers are 2 4 6 1 3 5. Note the good distribution. OK, thanks, that finally clicked. Now you know why I'm not a mathematician or computer scientist. :-) -Dave
Re: Why conf-split prime?
On Fri, 22 Jun 2001, Dave Sill wrote: i = fmt_ulong(s,id % auto_split); len += i; if (s) s += i; I can't see that primality would do anything special here. I am going to give the secret away right here to save your time. :) It is obvious the distribution of B(i) = A(i) mod k will be very non-uniform (i.e. very suboptimal when the values of B(i) are used as hash values) when A(i) or its large subsequences can be expressed as A(i+1) = A(i) + p such that gcd(p, k) 1. Our A(i)'s are inode numbers assigned to files holding the contents of queued messages (queue/mess/*/*). An average implementation of a unix-like filesystem assigns inode numbers less or more sequentially, i.e. the next assigned number is often the last one plus 1. Of course, if we had A(i+1) = A(i) + 1, there would be no problem. Alas, there are 2, 3, or even 4 (or perhaps even more) files per a message in the qmail queue: there are files in mess, as well as files in info, local, and remote. This means A(i)'s are often incremented by 2, 3, or 4, and the risk of uneven distribution of B(i)'s is rather high. Using a prime number for k eliminates this risk for a very small price. After all the set of primes is quite dense for reasonable values (1000) and you can always find a prime close to the number you want to use. However, the default, 23, is prime, and in his only message to the list on the topic of conf-split, DJB suggested a value of 401, also prime, for a queue with 10 entries: 401 is quite close to sqrt(10). It means the sizes of the 1st and 2nd level are quite balanced. But I can only guess why DJB suggested 401 rather than any prime closer to that square root. Why would DJB use primes if they weren't necessary? He uses round numbers elsewhere (concurrencies, for example), so I don't think he just likes them. There is a notation based on the (unique) factorization of numbers. 1 is (0) (or ()), 2 is (1), 3 is (0,1), 6 is (1,1) etc. It has some interesting properties: like an incredible ease of multiplication (and an incredible difficulty of addition). Prime numbers are the *round* ones in this notation. :) On Fri, 22 Jun 2001, Dave Sill wrote: Charles Cazabon [EMAIL PROTECTED] wrote: It does -- a large series of random numbers, modulo some number I, will result in an even distribution of results if and only if I is prime. If I isn't prime, the results are skewed noticeably towards the low end. Hmm. On first reading that, I didn't believe it. I couldn't imagine how the primality of the divisor could magically guarantee an even distribution. Indeed. Given a source A(i) of natural numbers uniformly distributed in a given interval [0, N-1] (lrand48() is *supposed* to be such a source for N = 2^31), it is trivial to show that the distribution D_B(x) of B(i) = A(i) mod k for any natural k 0 is as follows: / ceil(N/k)/N if x N mod k D_B(x) =for each x \in [0, k-1] \ floor(N/k)/N if x = N mod k You can see the results are skewed but for k N, prime or not, the skew is negligible and the resulting distribution is almost uniform. A test showing anything different demonstrates nothing but an imperfection in your PRNG or a flaw in the test itself. Profiling may beat speculation but mathematical reasoning beats profiling anytime. :) On Fri, 22 Jun 2001, Dave Sill wrote: BTW, I modified my modhash program to read numbers from stdin, fed it lists of real, live inode numbers, and guess what? It still makes no difference whether you use a prime hash or not. What real, live inode numbers? Have you picked the inode numbers of messages stuffed in queue/mess/*? With all due respect, I doubt it. Any profiling is pointless when you test something different than you intented to. If you still feel the need, feed your qmail with a large number of messages that will get stuck in the queue (there are four important cases: 1. qmail-send is not running, 2. local deliveries keep failing temporarily, 3. remote deliveries keep failing, 4. both local and remote deliveries keep failing) and test the inode numbers of files in queue/mess/*. And of course, you should repeat the test for different supported unix-like systems. --Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ] Resistance is futile. Open your source code and prepare for assimilation.
Re: Why conf-split prime?
On Sun, 24 Jun 2001, Pavel Kankovsky wrote: Using a prime number for k eliminates this risk for a very small price. After all the set of primes is quite dense for reasonable values (1000) and you can always find a prime close to the number you want to use. If course I assume the prime number used is high enough to be different from 2, 3, or perhaps 5, because these small primes are likely to have gcd(k, p) 1. --Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ] Resistance is futile. Open your source code and prepare for assimilation.
Re: Why conf-split prime?
On Fri, Jun 22, 2001 at 12:01:05PM +, Jost Krieger wrote: On Thu, Jun 21, 2001 at 02:25:52PM -0400, Russell Nelson wrote: speed. However, why should this number be prime, why not have 12 or 16 directories? Because it's a hash. If your hash isn't prime, you fill your hash buckets unevenly. I think we are spreading urban legends here. AFAIK, the primality is for double hashing in conflict resolution. Nothing of that kind is going on here. The only way to minimize collisions is to test the function empirically. In general the hash function ''f(x)=x mod m'' seems to work well if m is a prime number and not close to a power of 2. Knuth discussed this in ''The Art of Computer Programming'' Vol.3: Sorting and Searching (Addison-Wesley) -- happy reading. Jörgen
Re: Why conf-split prime?
On Fri, Jun 22, 2001 at 04:04:27PM -0400, Dave Sill wrote: Dave Sill [EMAIL PROTECTED] wrote: If the input numbers are not fairly random, then a modulo hash is not a choice. Not a *good* choice. Unix file system inode numbers are not truly random. Therefore, it's wise to choose a prime conf-split. BTW, I modified my modhash program to read numbers from stdin, fed it lists of real, live inode numbers, and guess what? It still makes no difference whether you use a prime hash or not. You'll need local data to write the optimal hash function. The prime doesn't guarantee anything but it's usually a good compromise for the general case (see my earlier reply to Krieger). Jörgen
Re: Why conf-split prime?
On Thu, Jun 21, 2001 at 02:25:52PM -0400, Russell Nelson wrote: speed. However, why should this number be prime, why not have 12 or 16 directories? Because it's a hash. If your hash isn't prime, you fill your hash buckets unevenly. I think we are spreading urban legends here. AFAIK, the primality is for double hashing in conflict resolution. Nothing of that kind is going on here. Jost -- | [EMAIL PROTECTED] Please help stamp out spam! | | Postmaster, JAPH, resident answer machine am RZ der RUB | | Pluralitas non est ponenda sine necessitate | | William of Ockham (1285-1347/49) |
Re: Why conf-split prime?
Jost Krieger [EMAIL PROTECTED] wrote: I think we are spreading urban legends here. AFAIK, the primality is for double hashing in conflict resolution. Nothing of that kind is going on here. You're right. The hashing used here is a simple modulo. From fmtqfn.c: i = fmt_ulong(s,id % auto_split); len += i; if (s) s += i; I can't see that primality would do anything special here. However, the default, 23, is prime, and in his only message to the list on the topic of conf-split, DJB suggested a value of 401, also prime, for a queue with 10 entries: http://www.ornl.gov/its/archives/mailing-lists/qmail/1997/07/msg00295.html Why would DJB use primes if they weren't necessary? He uses round numbers elsewhere (concurrencies, for example), so I don't think he just likes them. So...anyone who still thinks conf-split must/should be prime... Could you explain why? -Dave
Re: Why conf-split prime?
Dave Sill [EMAIL PROTECTED] wrote: Jost Krieger [EMAIL PROTECTED] wrote: I think we are spreading urban legends here. AFAIK, the primality is for double hashing in conflict resolution. Nothing of that kind is going on here. You're right. The hashing used here is a simple modulo. [...] I can't see that primality would do anything special here. It does -- a large series of random numbers, modulo some number I, will result in an even distribution of results if and only if I is prime. If I isn't prime, the results are skewed noticeably towards the low end. Charles -- --- Charles Cazabon[EMAIL PROTECTED] GPL'ed software available at: http://www.qcc.sk.ca/~charlesc/software/ ---
Re: Why conf-split prime?
--IPiIw4QAe+ Content-Type: text/plain; charset=us-ascii Content-Description: message body text Content-Transfer-Encoding: 7bit Charles Cazabon [EMAIL PROTECTED] wrote: Dave Sill [EMAIL PROTECTED] wrote: You're right. The hashing used here is a simple modulo. [...] I can't see that primality would do anything special here. It does -- a large series of random numbers, modulo some number I, will result in an even distribution of results if and only if I is prime. If I isn't prime, the results are skewed noticeably towards the low end. Hmm. On first reading that, I didn't believe it. I couldn't imagine how the primality of the divisor could magically guarantee an even distribution. The first thing I did was Google for hash prime modulo even distribution. That turns up many repetitions of Charles' assertion, without proof or explanation. I did find one clue, though, at: http://www.cs.rpi.edu/courses/spring01/cs2/wksht22/wksht22.html Which says: Research has shown that you get a more even distribution of hash values, and thus fewer collisions, if you choose your table size to be a prime number. Being a ``Profile, don't speculate'' kind of guy, I decided to write a little program to test modulo hashes, which is attached to this message for your entertainment. The result is that I can't see any effect of primality of the hash table size on distribution. For example: $ ./hash 16 size=16, reps=1, seed=0 0: 6250114 1: 6250151 2: 6249941 3: 6249981 4: 6249971 5: 6250134 6: 6250221 7: 6250195 8: 6249542 9: 6249840 10: 6250200 11: 6249700 12: 6250055 13: 6250101 14: 6249832 15: 6250022 mean=625.00, variance=36840.00 stddev=191.937485 (0.003071%) The table size, 16, is about as non-prime as you can get, but the distribution is quite even. Repeating with a table size of 17 shows no improvement: $ ./hash 17 size=17, reps=1, seed=0 0: 5882787 1: 5880754 2: 5883273 3: 5880598 4: 5881230 5: 5880577 6: 5885196 7: 5878233 8: 5874942 9: 5887715 10: 5881680 11: 5889068 12: 5888613 13: 5879609 14: 5882129 15: 5882443 16: 5881153 mean=5882352.00, variance=13348593.00 stddev=3653.572754 (0.062111%) So, I'm not sure exactly what was determined in the research mentioned above, but it looks to me like everyone's heard the conclusion so many times that they just accept it. I suspect it's only applicable when the integers being hashed are fairly close to the size of the table. -Dave --IPiIw4QAe+ Content-Type: application/octet-stream Content-Description: modulo hash tester Content-Disposition: attachment; filename=hash.c Content-Transfer-Encoding: base64 I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPG1hdGgu aD4KCm1haW4oaW50IGFyZ2MsIGNoYXIgKiphcmd2KQp7CiAgaW50IGhhc2hbMTAwMDBdLCBp OwogIGludCBzaXplPTE2LCByZXBzPTEwMDAwMDAwMCwgc2VlZD0wOwogIGxvbmcgajsKICBm bG9hdCBtZWFuLCB2YXJpYW5jZT0wLCBzdGRkZXY7CgogIGlmIChhcmdjID49IDIpIHsKICAg IHNzY2FuZiAoYXJndlsxXSwgIiVkIiwgJnNpemUpOwogICAgaWYgKHNpemUgPiAxMDAwMCkK ICAgICAgZXhpdCAoMSk7CiAgfQogIGlmIChhcmdjID49IDMpCiAgICBzc2NhbmYgKGFyZ3Zb Ml0sICIlZCIsICZyZXBzKTsKICBpZiAoYXJnYyA+PSA0KQogICAgc3NjYW5mIChhcmd2WzNd LCAiJWQiLCAmc2VlZCk7CiAgbWVhbj1yZXBzL3NpemU7CiAgcHJpbnRmICgic2l6ZT0lZCwg cmVwcz0lZCwgc2VlZD0lZFxuIiwgc2l6ZSwgcmVwcywgc2VlZCk7CiAgZm9yIChpPTA7IGk8 c2l6ZTsgaSsrKSB7CiAgICBoYXNoW2ldPTA7CiAgfQogIHNyYW5kNDggKHNlZWQpOwogIGZv ciAoaT0wOyBpPHJlcHM7IGkrKykgewogICAgaj1scmFuZDQ4KCk7CiAgICBoYXNoW2olc2l6 ZV0rKzsKICB9CiAgZm9yIChpPTA7IGk8c2l6ZTsgaSsrKSB7CiAgICBwcmludGYgKCIlZDog JWRcbiIsIGksIGhhc2hbaV0pOwogICAgdmFyaWFuY2UgKz0gcG93KGhhc2hbaV0gLSBtZWFu LCAyLjApOwogIH0KICB2YXJpYW5jZSAvPSAoZmxvYXQpc2l6ZS0xOwogIHN0ZGRldj1zcXJ0 KHZhcmlhbmNlKTsKICBwcmludGYgKCJtZWFuPSVmLCB2YXJpYW5jZT0lZlxuIiwgbWVhbiwg dmFyaWFuY2UpOwogIHByaW50ZiAoInN0ZGRldj0lZiAoJWYlKVxuIiwgc3RkZGV2LCBzdGRk ZXYvbWVhbioxMDApOwp9Cg== --IPiIw4QAe+--
Re: Why conf-split prime?
Dave Sill [EMAIL PROTECTED] wrote:
--IPiIw4QAe+
Content-Type: text/plain; charset=us-ascii
Content-Description: message body text
Content-Transfer-Encoding: 7bit
etc.
Argh. Forgot about my Emacs' broken MIME. Here's the program:
#include stdio.h
#include stdlib.h
#include math.h
main(int argc, char **argv)
{
int hash[1], i;
int size=16, reps=1, seed=0;
long j;
float mean, variance=0, stddev;
if (argc = 2) {
sscanf (argv[1], %d, size);
if (size 1)
exit (1);
}
if (argc = 3)
sscanf (argv[2], %d, reps);
if (argc = 4)
sscanf (argv[3], %d, seed);
mean=reps/size;
printf (size=%d, reps=%d, seed=%d\n, size, reps, seed);
for (i=0; isize; i++) {
hash[i]=0;
}
srand48 (seed);
for (i=0; ireps; i++) {
j=lrand48();
hash[j%size]++;
}
for (i=0; isize; i++) {
printf (%d: %d\n, i, hash[i]);
variance += pow(hash[i] - mean, 2.0);
}
variance /= (float)size-1;
stddev=sqrt(variance);
printf (mean=%f, variance=%f\n, mean, variance);
printf (stddev=%f (%f%)\n, stddev, stddev/mean*100);
}
-Dave
Re: Why conf-split prime?
Ian Lance Taylor [EMAIL PROTECTED] wrote: If the input numbers are truly random, then a modulos hash will distribute well whether or not the hash size is prime. However, if the input numbers are not truly random, then a modulos hash may pick out some regularity in the input, and preferentially hash to a given set of buckets. If the input numbers are not fairly random, then a modulo hash is not a choice. For a trivial example, if the numbers tend to be even, then an even modulos hash will tend toward using the even numbered buckets. Which, unfortunately, wouldn't be helped by a prime table size. A prime modulos hash minimizes the types of regularity which will lead to a poor hash distribution. Exactly how does a prime modulus help? Can you give an example? Unix file system inode numbers are not truly random. Therefore, it's wise to choose a prime conf-split. I'm still not convinced. Has anyone ever seen a problem with a non-prime conf-split that was significantly helped by switching to a prime conf-split? -Dave
Re: Why conf-split prime?
Dave Sill [EMAIL PROTECTED] wrote:
The first thing I did was Google for hash prime modulo even
distribution. That turns up many repetitions of Charles' assertion,
without proof or explanation.
[...]
Being a ``Profile, don't speculate'' kind of guy, I decided to write a
little program to test modulo hashes, which is attached to this
message for your entertainment.
The result is that I can't see any effect of primality of the hash
table size on distribution.
Funny, I can reproduce it easily. Sure your random numbers are random?
With the attached Python script (it depends on the popular stats.py and
pstat.py modules), analyzing 25 15-bit random integers (read from a text
file, one per line), I get the following:
[charlesc@charon personal]$ ./buckets.py 12 13
A: 12 buckets
count: 25
mean: 20833.
std. dev.: 196.3153
B: 13 buckets
count: 25
mean: 19230.7692
std. dev.: 103.8646
The effect does appear to diminish significantly for large values, though.
Charles
--
---
Charles Cazabon[EMAIL PROTECTED]
GPL'ed software available at: http://www.qcc.sk.ca/~charlesc/software/
---
#!/usr/bin/python
import whrandom
import string
import stats
import sys
ints = map (int, map (string.strip, open ('randints.txt').readlines ()))
###
def fill_buckets (numbuckets):
buckets = [0] * numbuckets
for i in ints:
x = i % numbuckets
buckets[x] = buckets[x] + 1
return buckets
###
def main (a, b):
A = fill_buckets (a)
B = fill_buckets (b)
for L, name in ((A, 'A'), (B, 'B')):
sum = reduce (lambda a, b: a+b, L)
mean = stats.mean (L)
dev = stats.stdev (L)
print '%s: %i buckets' % (name, len (L))
print ' count: %10i' % sum
print ' mean: %7.04f' % mean
print ' std. dev.: %7.04f' % dev
print
###
if __name__ == '__main__':
a = int (sys.argv[1])
b = int (sys.argv[2])
main (a, b)
Re: Why conf-split prime?
Dave Sill [EMAIL PROTECTED] wrote: If the input numbers are not fairly random, then a modulo hash is not a choice. Not a *good* choice. Unix file system inode numbers are not truly random. Therefore, it's wise to choose a prime conf-split. BTW, I modified my modhash program to read numbers from stdin, fed it lists of real, live inode numbers, and guess what? It still makes no difference whether you use a prime hash or not. -Dave
Re: Why conf-split prime?
Dave Sill [EMAIL PROTECTED] writes:
Ian Lance Taylor [EMAIL PROTECTED] wrote:
If the input numbers are truly random, then a modulos hash will
distribute well whether or not the hash size is prime.
However, if the input numbers are not truly random, then a modulos
hash may pick out some regularity in the input, and preferentially
hash to a given set of buckets.
If the input numbers are not fairly random, then a modulo hash is not
a choice.
Sure it is. A modulos hash works fine if the input numbers are fairly
random with respect to the hash size. That doesn't imply that the
input numbers are random in any real size.
For a trivial example, if the numbers
tend to be even, then an even modulos hash will tend toward using the
even numbered buckets.
Which, unfortunately, wouldn't be helped by a prime table size.
I guess one of us misunderstands the other. My point is that if the
input numbers and the table size tend to have a divisor greater than
one, then the distribution will be skewed. Using a prime number
minimizes the number of divisors greater than one which may be shared
by the table size and the input numbers.
A prime modulos hash minimizes the types of
regularity which will lead to a poor hash distribution.
Exactly how does a prime modulus help? Can you give an example?
Suppose the input numbers are 2 4 6 8 10 12. Suppose the hash size is
8. Then the buckets are 2 4 6 0 2 4. Note the bad distribution.
Suppose the hash size is 7. Then the buckers are 2 4 6 1 3 5. Note
the good distribution.
Here's another way to say it. For any given hash size, call a series
of inputs which lead to a bad distribution B. Consider the set of all
bad inputs {B}. A prime hash size minimizes the number of elements in
{B}. Therefore, if you don't know anything about the inputs--in
particular, if you don't know if they are random--it is better to
choose a prime hash size.
Ian
Re: Why conf-split prime?
Dave Sill [EMAIL PROTECTED] writes: Unix file system inode numbers are not truly random. Therefore, it's wise to choose a prime conf-split. BTW, I modified my modhash program to read numbers from stdin, fed it lists of real, live inode numbers, and guess what? It still makes no difference whether you use a prime hash or not. That just proves that on your system it doesn't matter much. It doesn't prove much about the range of Unix filesystems out there. In my last message I tried to show that, all else being equal, a prime modulos is more likely to give a good result. That can be true even if in a particular case a prime modulos makes no difference. Ian
Re: Why conf-split prime?
Dave Sill [EMAIL PROTECTED] writes: You're right. The hashing used here is a simple modulo. From fmtqfn.c: i = fmt_ulong(s,id % auto_split); len += i; if (s) s += i; I can't see that primality would do anything special here. However, the default, 23, is prime, and in his only message to the list on the topic of conf-split, DJB suggested a value of 401, also prime, for a queue with 10 entries: http://www.ornl.gov/its/archives/mailing-lists/qmail/1997/07/msg00295.html Why would DJB use primes if they weren't necessary? He uses round numbers elsewhere (concurrencies, for example), so I don't think he just likes them. So...anyone who still thinks conf-split must/should be prime... Could you explain why? If the input numbers are truly random, then a modulos hash will distribute well whether or not the hash size is prime. However, if the input numbers are not truly random, then a modulos hash may pick out some regularity in the input, and preferentially hash to a given set of buckets. For a trivial example, if the numbers tend to be even, then an even modulos hash will tend toward using the even numbered buckets. A prime modulos hash minimizes the types of regularity which will lead to a poor hash distribution. Unix file system inode numbers are not truly random. Therefore, it's wise to choose a prime conf-split. Ian
Why conf-split prime?
Its not an issue for me as I have 10 users and don't expect queues larger than 2 or three messages (i.e. performance is not an issue). I wanted qmail for the security, though I am more than pleased to have the scalability and speed. However, why should this number be prime, why not have 12 or 16 directories? Just curious Thanks
Re: Why conf-split prime?
Stephen Froehlich writes: Its not an issue for me as I have 10 users and don't expect queues larger than 2 or three messages (i.e. performance is not an issue). I wanted qmail for the security, though I am more than pleased to have the scalability and speed. However, why should this number be prime, why not have 12 or 16 directories? Because it's a hash. If your hash isn't prime, you fill your hash buckets unevenly. The scary thing is people who know primes off the top of their heads. Hey Nick, do you know a prime that's about five hundred? Yeah. 521. Thanks. --- Real conversation at Xoom.com in 1998. -- -russ nelson [EMAIL PROTECTED] http://russnelson.com Crynwr sells support for free software | PGPok | 521 Pleasant Valley Rd. | +1 315 268 1925 voice | #exclude windows.h Potsdam, NY 13676-3213 | +1 315 268 9201 FAX |
Re: Why conf-split prime?
Russell Nelson([EMAIL PROTECTED])@2001.06.21 14:25:52 +: Because it's a hash. If your hash isn't prime, you fill your hash buckets unevenly. The scary thing is people who know primes off the top of their heads. Hey Nick, do you know a prime that's about five hundred? Yeah. 521. Thanks. --- Real conversation at Xoom.com in 1998. god bless the bsd people ;-) see primes(6) rohrbach@WM:datasink[~]24% /usr/games/primes 500 600 503 509 521 523 541 547 557 563 569 571 577 587 593 599 cheers, /k -- Dope will get you through times of no money better that money will get you through times of no dope. --Gilbert Shelton KR433/KR11-RIPE -- WebMonster Community Founder -- nGENn GmbH Senior Techie http://www.webmonster.de/ -- ftp://ftp.webmonster.de/ -- http://www.ngenn.net/ karstenrohrbach.de -- alphangenn.net -- alphascene.org -- [EMAIL PROTECTED] GnuPG 0x2964BF46 2001-03-15 42F9 9FFF 50D4 2F38 DBEE DF22 3340 4F4E 2964 BF46 Please do not remove my address from To: and Cc: fields in mailing lists. 10x PGP signature
Re: Why conf-split prime?
On Thu, Jun 21, 2001 at 09:21:20PM +0200, Karsten W. Rohrbach wrote: Russell Nelson([EMAIL PROTECTED])@2001.06.21 14:25:52 +: Because it's a hash. If your hash isn't prime, you fill your hash buckets unevenly. The scary thing is people who know primes off the top of their heads. Hey Nick, do you know a prime that's about five hundred? Yeah. 521. Thanks. --- Real conversation at Xoom.com in 1998. god bless the bsd people ;-) see primes(6) This program is also available in Debian in the bsdgames package. --Adam -- Adam McKenna [EMAIL PROTECTED] | No matter how much it changes, http://flounder.net/publickey.html | technology's just a bunch of wires GPG: 17A4 11F7 5E7E C2E7 08AA| connected to a bunch of other wires. 38B0 05D0 8BF7 2C6D 110A| Joe Rogan, _NewsRadio_ 12:30pm up 15 day(s), 12:33, 9 users, load average: 0.04, 0.05, 0.07
