On Thu, Aug 02, 2007 at 03:41:23PM -0500, Will Schmidt wrote: > Hi Paul, > just a few questions. [snip] > > +#define VSID_MULTIPLIER_256M ASM_CONST(200730139) /* 28-bit prime > > */ > > > +#define VSID_MULTIPLIER_1T ASM_CONST(12538073) /* 24-bit prime */ > > Anything special in how this 24-bit prime value was selected? (same > question could be for the 28-bit prime, though I see that value was > updated at least once a few years back)
I can't speak to the 24-bit value specifically, but I can speak to the 28-bit one: I did the rewrite of the SLB miss handler to use that multiplicative hash, and changed the prime value when a bug report showed problems in the original choice. Afaict, the value of the prime doesn't matter all that much - in fact it doesn't strictly even need to be prime, just co-prime to (2^36-1). Originally, I picked the largest 28-bit prime, on the basis that a large multiplier should give better scattering/folding. That turned out to cause problems on some iSeries machines (which couldn't do 16M pages) - we were filling up hash buckets with the linear mapping. I figured out that that was because a very large 28-bit number was in the relevant modulus, sort of equivalent to a small negative number. For a big linear mapping, the hash bucket selected strided gradually backwards through the table - there were also differences in the high bits of the hash, but they were lost because of the limited size of the hash table. So, I changed the multiplier to the median 28-bit prime, in the hopes that that would give better hash scattering across as many bits of the VSID as possible. I don't have much in the way of theoretical justification for that, but it fixed the iSeries problem and I've never heard of any regressions, so apparently it's not too bad. -- David Gibson | I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ | _way_ _around_! http://www.ozlabs.org/~dgibson _______________________________________________ Linuxppc-dev mailing list Linuxppc-dev@ozlabs.org https://ozlabs.org/mailman/listinfo/linuxppc-dev