amdcomputelibraries / morton_filter Goto Github PK

When using Morton3_8 with random long keys as below, and using a load factor of >= 0.5, often I get false negatives (meaning: for an entry previously added, the method likely_contains returns false). My usage:

filter = new Morton3_8((size_t) (size / 0.50) + 64);
// in a loop, do this
uint64_t key = ...
filter->insert(key);
// in a loop, do this
uint64_t key = ...
filter->likely_contains(key);

the same key is only ever added once, and keys are random, generated using mix64, as follows:

uint64_t x = index++;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9L;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebL;
x = x ^ (x >> 31);
return x;

Could you tell me what could be wrong?

The following static assertion triggers even when it shouldn't because it is evaluated even when the alternate bucket selection method isn't TABLE_BASED_OFFSET, causing Morton1_8 to fail to compile (it uses FUNCTION_BASED_OFFSET, and the assertion shouldn't trigger).

context:

Since _alternate_bucket_selection_method is known at compile time, the inverse of the case taken should be added to the assertion, something like this:

static_assert(offsets[0] > _buckets_per_block ||
              _alternate_bucket_selection_method != AlternateBucketSelectionMethodEnum::TABLE_BASED_OFFSET,
  "Cannot use TABLE_BASED_OFFSET with so many buckets per block");

The readme mentions self-resizing and the code has a resize function. However I could not find reference to this in the paper. Is this mechanism (and potential trade-offs) described somewhere?