PTRHash fails to build on 10^12 keys

[vigna]

This is with the parameters in many_keys.rs, just changing the number of keys:

[...]
part    507 bucket  0.01%  chain:   8388608
Too many displacements. Aborting!
Possible causes:
- Too many elements in part.
- Not enough empty slots => lower alpha.
- Not enough buckets     => increase c.
- Not enough entropy     => fix algorithm.

part   1350 bucket  0.03%  chain:   8388608
Too many displacements. Aborting!
Possible causes:
- Too many elements in part.
- Not enough empty slots => lower alpha.
- Not enough buckets     => increase c.
- Not enough entropy     => fix algorithm.

thread 'main' panicked at /home/vigna/git/PTRHash/src/lib.rs:369:13:
Failed to find a global seed after 3 tries for 262144 keys.
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

I can send the whole log if that's useful.

[vigna]

BTW, somewhat unrelated, but this comment

    // Since running all queries is super slow, we only check a subset of them.
    // Although this doesn't completely check that there are no duplicate
    // mappings, by the birthday paradox we can be quite sure there are none
    // since we check way more than sqrt(n) of them.

has no mathematical basis. It would be correct if the output of the function was random, but it is not. If there are exactly two keys colliding the probability of hitting them is the probability of having exactly those two keys in the subset you test, and this has nothing to do with the birthday paradox.

[RagnarGrootKoerkamp]

Yeah so as the error says, the algorithm only works well if there are sufficiently many buckets and slots. You probably want to run with c=11 to have more buckets and significantly increase the probability that displacing finds a solution.

I still have to work out the math at some point. Currently the number of buckets scales as c * n / lg(n) (as does PTHash), but in practice it seems that the default c=9 fails for larger n, so it's needed to compensate manually for the /lg(n) by increasing c.

Ah yeah I did realize at some point that the comment doesn't really make sense indeed. will fix it at some point.

It would be cool to be able to efficiently check all 10^12 keys using multiple threads. Maybe each thread could store a buffer of 10^6 to 10^9 keys, and then flush/write that once full. But still there is so much writing going on it's bound to be slow I suspect.

[vigna]

That was 10, I'll try 11.

…

On November 18, 2023 10:13:21 AM GMT+01:00, Ragnar Groot Koerkamp ***@***.***> wrote: Yeah so as the error says, the algorithm only works well if there are sufficiently many buckets and slots. You probably want to run with `c=10` or `c=11` to have more buckets and significantly increase the probability that displacing finds a solution. I still have to work out the math at some point. Currently the number of buckets scales as c * n / lg(n) (as does PTHash), but in practice it seems that the default c=9 fails for larger n, so it's needed to compensate manually for the /lg(n) by increasing c. -- Reply to this email directly or view it on GitHub: #6 (comment) You are receiving this because you authored the thread. Message ID: ***@***.***>

[RagnarGrootKoerkamp]

Did this end up working?

[vigna]

I tried with c=11 and a single shard but I got

        keys: 1000000000000
      shards:          1
       parts:    3892549
   slots/prt:     262144
   slots tot: 1020408365056
 buckets/prt:      72285
 buckets tot: 281372904465
 keys/bucket:          3.55
memory allocation of 2147483648 bytes failed

Now trying with more shards.

[RagnarGrootKoerkamp]

It will store n/s hashes per shard. Do you have 10^12 / 1 * 16byte = 16TB of RAM? 😅

Probably you want ~1000 shards to get ~16GB memory per shard.

[vigna]

With c=11 the first round failed. I'll make it do another couple of rounds. I'm using 1000 shards.

[RagnarGrootKoerkamp]

Then c=12 maybe?

[RagnarGrootKoerkamp]

Or maybe try alpha=0.97 or a bit lower. Its hard to know exactly where is the bottleneck.

[vigna]

It didn't stop, but it is still at 800/1000 chunks after three days. Hardly usable in practice. If it finishes I'll try with a smaller alpha.

[RagnarGrootKoerkamp]

Hmm. That's weird. Did you enable sharding to disk? Without it it will hash all keys once for each shard which is quite a bit slower probably.

[vigna]

Oh no. Well, from my experience, it is better that default options offer a reasonable behavior. People won't always come to you for explanations—they'll just move elsewhere.

[vigna]

On a better note: it completed! But it didn't print any stats about space, unless " keys/bucket: 3.26" it is. That's where serialization is really useful—you can measure the file to double check.

[vigna]

Will it obey to TMPDIR? I can't find where it's creating the shards...

[RagnarGrootKoerkamp]

Yeah well... People using this for up to 10^9 elements probably don't want sharding to disk and this program writing disk unexpectedly.
Maybe I'll make a separate function build_on_disk for visibility and clarity.
TMPDIR env var should work yes.

It should normally print a bits/element stat at the end, but at some point I broke that and it was printing 0 instead. I think that's fixed now.