Page Coloring Defines in vm_page.h

[Tim Kientzle]

Matthew Dillon wrote:
>     For example, prime number 3 an array size 8 will scan the array in
>     the following order  N = (N + PRIME) & (ARRAY_SIZE_MASK).
>     N = (N + 3) & 7:
> 
>     0 3 6 1 4 7 2 5 ... 0
> 
>     As you can see, all the array entries are covered before the sequence
>     repeats. ....  Only certain prime number / power-of-2-array size
>     combinations have this effect,   ....

Ummmm....  Actually, Matt, the property you've stated is much more
common than you seem to believe.  If you generate a sequence
    N = ( N + Stride ) % ArraySize
then you will visit every element of (0 ... ArraySize-1) as long as
the Stride and ArraySize are relatively prime (have no prime factors
in common).

In particular, if the ArraySize is a power of 2, then it
suffices for the stride to be odd.   Like 1, for example.  ;-)

The real motivation for a prime stride is avoiding hash table
collisions.  Many hash functions have cyclic properties;
for example, using a memory address as a hash code tends to
give multiples of 4, 8, and 16.  You want your stride to be
relatively prime to any cycles in the hash function.  Since
hash functions tend to be hard to analyze, you generally just
pick a number that's likely to be relatively prime to any
cycles in the hash function; a large prime is a good candidate.
For that reason, many hash table algorithms simply select the
largest prime less than the array size as the stride.

Tim Kientzle