Any more information about `src/cuckoo/mean.hpp`?

[xiongyw]

It turns out that the edge-trimming process in mean.cpp is much more difficult for me to understand, as compared to the simple and lean version... It's even hard for me to make a list of questions, since I am a sort of totally lost... I watched at least 3 youtube videos about cuckoo cycle, but not in-depth discussion about mean algorithm so far...so I am wondering if there are any more information on the web discussing details about mean.hpp?

For example, I am confused about what's the data structure is used to store "edges", and how (where) the "edges" are trimmed with regard to the corresponding data structure...also it seems a zbucket elment is of BIGSIZE (5) bytes, which is 40 bits, and an an edge's two node (UYZ, VYZ) is 22*2=44(bit). How 44-bit info fits into 40-bit space...

Many thanks!

[tromp]

The complexity in mean.hpp is due to the complicated variable size bit packing of edges. In most rounds, 5 bytes are used to store relevant parts of the endpoints UXYZ and VXYZ. We need not store bits that are implied by the bucket index, and we also need not store the most significant bits that can be recovered by ordering assumptions. Comments like https://github.com/tromp/cuckoo/blob/master/src/cuckoo/mean.hpp#L694-L695 show the layout of bits in for the case XBITS=YBITS=8. For the case where XBITS=YBITS=7 this looks like // bit 39..37 36..22 21..15 14..0 // write UYYYYY UZZZZZ VYYYYY VZZZZ within VX partition In this case, all 7 UX bits and 4 of the 7 UY bits must be recovered by ordering, which is done in with uxyz += ((u32)(e >> YZBITS) - uxyz) & SRCPREFMASK; whenever the most significant 18 of 40 bits in e (corresponding to least significant 18 bits of UXYZ) is less than in the previous e, a carry is generated into the upper 11 bits of UXYZ. This works because, within a bucket, the UXYZ entries are in ascending order, and the successive differences between them are small enough (less than 2^18).

[xiongyw]

Thanks for your replay, Tromp!

Can you also explain a bit about the purpose of genUnodes() and genVnodes()? It seems that these two steps are not regarded as trimming rounds.

It seems that genUnodes() fills the buckets with zz=edge<<YZBITS|(node & YZMASK), looping through all edges, so the function name can be interpreted as "generate all Unodes and store them in the buckets[NX][NY].bytes[]", where NX is "node>>YZBITS" but NY is "edge>>YZBITS". I have difficulty to match this behavior with the comments at the beginning of mean.hpp saying that "Edge i between nodes ui and vi resides in the bucket at (uiX, viX)" since vi is not involved yet.

And if genUnodes() already filled the buckets, where genVnodes() is supposed to store V nodes info?

Apparently I am still confused...

Thanks again!

[tromp]

genUnodes, fills buckets with 22-bit UYZ of an edge plus lower 10 or 18 bits of the edge index:

// bit 39/31..22 21..15 14..0 // read edge UYYYYY UZZZZ within UX partition

genVnodes then does trimming on U nodes while also generating UVYZ from the (fully recovered) edge index and storing

// bit 39..37 36..22 21..15 14..0 // write UYYYYY UZZZZZ VYYYYY VZZZZ within VX partition

Edges (ui,vi) are stored in bucket[uiX][viX] at the end of genVnodes and trimedges.

[xiongyw]

Thank you very much, Tromp! I guess I am now back on the right track :)

[xiongyw]

Hi, Tromp,

Regarding "recovering bits by ordering assumptions", I have a question about edge bits recovery in genVnodes().

In genUnodes(), the least significant 10 bits of edge index are stored in the most significant 10 bits of each bucket element:

bit      31..22  21..15  14..0
write    ELLLLL  UYYYYY  UZZZZ

and the most significant 7 bits of edge index are bucket row index, so what's missing (to be recovered) is the middle 12 bits of the edge index.

As you described above, the recovery process based on:

1. the fact that edge index are in ascending order in each bucket
2. the assumption that the index difference between two successive edges are small enough (i.e, < 2^10).

My question is about the 2nd point (the assumption): what's the possibility that this assumption is not true (for example, for any 1024 consecutive edges falling into a column of 128 buckets, if any of the bucket contains 0 edge, it's a false case of the assumption)? I am not sure how to model it formally, so I just did a simple test using the following program:

#include <stdio.h>
#include <stdlib.h>

#define N 128     // nr of boxes (buckets in a column)
#define R 1024    // nr of balls (edges)
unsigned int g_count[N];

/*
 * return 0 if if there is any empty box,
 * otherwise 1;
 */
int one_put()
{
    for (int i = 0; i < N; i ++)
        g_count[i] = 0;

    for (int i = 0; i < R; i ++) {
        int n = random() % N;
        g_count[n] ++;
    }

    for (int i = 0; i < N; i ++) {
        if (g_count[i] == 0)
            return 0;
    }

    return 1;
}

int main(void)
{
    int total = 0, empty = 0;
    for (int i = 0; ; i ++) {
        if (one_put()) {
            total ++;
        } else {
            empty ++;
        }
        printf("%d/%d\n", empty, total);
    }

    return 0;
}

It shows that the ratio is more than 0.04, which is close to 128*(127/128)^1024. To me, 0.04 is a bit high, but I don't know if I missed some thing in my reasoning above.

Thanks!

[tromp]

The bucket row index is msb of nodeU, not the edge index. There is indeed a non-negligible probability of consecutive edges being more than 1024 apart, which is handled with extra syncing codes. See NEEDSYNC in the code...

On Sat, 15 Jun 2019, 02:23 bruin, notifications@github.com wrote:

Hi, Tromp,

Regarding "recovering bits by ordering assumptions", I have a question about edge bits recovery in genVnodes().

In genUnodes(), the least significant 10 bits of edge index are stored in the most significant 10 bits of each bucket element:

bit 31..22 21..15 14..0 write ELLLLL UYYYYY UZZZZ

and the most significant 7 bits of edge index are bucket row index, so what's missing (to be recovered) is the middle 12 bits of the edge index.

As you described above, the recovery process based on:

1. the fact that edge index are in ascending order in each bucket
2. the assumption that the index difference between two successive edges are small enough (i.e, < 2^10).

My question is about the 2nd point (the assumption): what's the possibility that this assumption is not true (for example, for any 1024 consecutive edges falling into a column of 128 buckets, if any of the bucket contains 0 edge, it's a false case of the assumption)? I am not sure how to model it formally, so I just did a simple test using the following program:

include

include

define N 128 // nr of boxes (buckets in a column)

define R 1024 // nr of balls (edges)

unsigned int g_count[N];

/*

• return 0 if if there is any empty box,

• otherwise 1; */ int one_put() { for (int i = 0; i < N; i ++) g_count[i] = 0;

  for (int i = 0; i < R; i ++) { int n = random() % N; g_count[n] ++; }

  for (int i = 0; i < N; i ++) { if (g_count[i] == 0) return 0; }

  return 1; }

int main(void) { int total = 0, empty = 0; for (int i = 0; ; i ++) { if (one_put()) { total ++; } else { empty ++; } printf("%d/%d\n", empty, total); }

return 0;

}

It shows that the ratio is more than 0.04, which is close to 128*(127/128)^1024. To me, 0.04 is a bit high, but I don't know if I missed some thing in my reasoning above.

Thanks!

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/tromp/cuckoo/issues/93?email_source=notifications&email_token=AAR5BW7DLVESD6LAYIHLEFDP2QY6JA5CNFSM4HDH6TEKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXYMCEQ#issuecomment-502317330, or mute the thread https://github.com/notifications/unsubscribe-auth/AAR5BW7NFJK4DSOANXS3VRTP2QY6JANCNFSM4HDH6TEA .

[xiongyw]

Thank you, Tromp.