Wrong Algorithm for generating permutations.

[jazzshop111]

Please change the logic from:

for j := uint64(0); j < M; j++ {
p[j] = idx
idx += skip
if idx >= M {
idx -= M
}
}

To this one:

for j = 0; j < M; j++ {
p[j] = (offset + uint64(j)*skip) % M
}

You algorithum to generate permutations has mathematical Flaw. Please refer the original Google Maglev Hashing paper.
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf

The algorithm requires that p[j] is of size M, p[j] should not contain duplicates and should contain all numbers in range of 0 to M, which is only possible with following formula:
p[j] = (offset + uint64(j)*skip) % M

Your algorithm of generating permutations will contain duplicates in p[j] and will not have all numbers in range of 0 to M, this will create serious problems in "populate()" function.

[dgryski]

I'm fairly certain these two algorithms are equivalent. I optimized the one from the paper to reduce the number of operations that happen during regeneration of the table. Do you have an example where there is a mismatch?

[seebs]

Quick back of the envelope evaluation: Consider the value of idx for each iteration of the loop as distinct values idx[0], idx[1], and so on. (We don't actually need the values, but it's convenient to think of them that way.)

Assume for the sake of argument that, for some j, idx[j] is equal to the computed value from the other expression. If idx[j] == (offset + uint64(j) * skip) % M, then what about idx[j+1]? Well, it will be equal to idx[j]+skip, unless that exceeds M, in which case it will be equal to (idx[j]+skip) % M.

What's p[j+1] with the old formula? Well, it's (offset + uint64(j+1)*skip) % M, whereas p[j] is (offset + uint64(j)*skip) % M. So p[j+1] is (p[j]+skip)%M.

What that means is that if idx[j], computed with dgryski's method, is equal to p[j], computed with the multiplication expreession, then idx[j+1] will be equal to p[j+1].

It is reasonably obvious that idx0 = offset, because idx is initialized with offset. Since offset is (some value) mod M, offset is in [0,M). Thus, idx0 = (offset + 0 * skip) % M.

Therefore, by induction, idx[j] == p[j] for all j.

[jazzshop111]

Hello Dgryski, You are right, your algorithm is giving unique permutation value for each node p[j] in the range [0, M) p[j] = [0, M) where length(p) = M and all elements in p[j] are unique. Sample output for ( M = 11 ) and ( N = 8 ) according to your algorithm: p[0] = [8 0 3 6 9 1 4 7 10 2 5] p[1] = [8 7 6 5 4 3 2 1 0 10 9] p[2] = [5 6 7 8 9 10 0 1 2 3 4] p[3] = [5 3 1 10 8 6 4 2 0 9 7] p[4] = [8 3 9 4 10 5 0 6 1 7 2] p[5] = [8 10 1 3 5 7 9 0 2 4 6] p[6] = [8 7 6 5 4 3 2 1 0 10 9] p[7] = [4 1 9 6 3 0 8 5 2 10 7] Before testing your algorithm, I was expecting that p[j] will not contain all values in range of [0, M), but its working. 1. If we are storing all permutations p[j] in memory then your algorithm is better than p[j] = offset%M + (j * skip) % M 2. If we want to save memory and avoid storing all permutation p[j] in memory than we can generate permutation on the fly by using p[j] = offset%M + (j * skip) % M We can store "offset" and "skip" for each node, the values of j will be next[i] and M is already known. So we can compute permutation of p[j] on the fly. I guess google avoids allocation memory for permutations p[j] which is why they have mentioned above formula in the paper. Never the less, both the approach gives same result, its just a matter of choosing "permutation memory overhead" vs little "extra CPU computation" when the maglev table has to be populated again. Thanks & Regards, Aijaz

…

On Sat, May 18, 2019 at 11:08 AM seebs ***@***.***> wrote: Quick back of the envelope evaluation: Consider the value of idx for each iteration of the loop as distinct values idx[0], idx[1], and so on. (We don't actually need the values, but it's convenient to think of them that way.) Assume for the sake of argument that, for some j, idx[j] is equal to the computed value from the other expression. If idx[j] == (offset + uint64(j) * skip) % M, then what about idx[j+1]? Well, it will be equal to idx[j]+skip, unless that exceeds M, in which case it will be equal to (idx[j]+skip) % M. What's p[j+1] with the old formula? Well, it's (offset + uint64(j+1)*skip) % M, whereas p[j] is (offset + uint64(j)*skip) % M. So p[j+1] is (p[j]+skip)%M. What that means is that if idx[j], computed with dgryski's method, is equal to p[j], computed with the multiplication expreession, then idx[j+1] will be equal to p[j+1]. It is reasonably obvious that idx0 = offset, because idx is initialized with offset. Since offset is (some value) mod M, offset is in [0,M). Thus, idx0 = (offset + 0 * skip) % M. Therefore, by induction, idx[j] == p[j] for all j. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#2?email_source=notifications&email_token=AMDHGPHUTR5RPVIGDYNZJ33PV6I4ZA5CNFSM4HNYLMKKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVWIDGA#issuecomment-493650328>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AMDHGPGXHA65KVTJVQ7C35TPV6I4ZANCNFSM4HNYLMKA> .