buildBinaryFuse uses 0 as an empty-slot sentinel in reverseOrder even though mixsplit hash 0 is valid

[dain]

I noticed this while reading, so it is possible I'm missing something.

In buildBianryFuse, there is:

for _, key := range keys {
	hash := mixsplit(key, filter.Seed)
	segment_index := hash >> (64 - blockBits)
	for reverseOrder[startPos[segment_index]] != 0 {
		segment_index++
		segment_index &= (1 << blockBits) - 1
	}
	reverseOrder[startPos[segment_index]] = hash
	startPos[segment_index] += 1
}

so if reverseOrder[startPos[segment_index]] == 0 the slot is considered empty and is filled with the hash. But it seems that mixsplit(key, filter.Seed) can return zero, which would mark the slot as empty again.

A work around would be to not allow zero as a hash value or use a different reserved sentinel, or the code would need a sidecar "slot is empty" array.

[lemire]

@dain So you have a 64-bit random value. Can we agree that the probability of it being zero is not much of a worry?

[dain]

I think the odds of hitting this case are much greater than 2^64, as you need a hash of zero and you need to hit this exact code path. Also IIRC the mix uses a random number, so you can't even try to pollute input to trigger this. So likely never to happen in the life of the universe.

That said if you do hit it, it violates the assumptions of the data structure. An easy fix is to have a boolean array that tracks used. It should only be a few lines to patch, if someone wants to do that. I don't actually use this library, so it isn't a real concern for me.

[lemire]

So likely never to happen in the life of the universe.

Right.

That said if you do hit it, it violates the assumptions of the data structure.

The construction is probabilistic: it has a chance of failing, in which case we retry.

[dain]

@lemire does it fail or does it produce an invalid build? If it fails, then this is definately not a bug and should be fixed. My guess it the latter but I'm not sure. Basically, if we write 0, the slot is considered empty and I think it can be overwritten, so you would end up not having the zero hash. I only looked at that part in isolation so maybe there is another part that does validation, or maybe the zero reappears somewhere else.

If you aren't going to fix it, I would at least add a comment explaining why it is not a real issue, or that it doesn't matter in practice.

[lemire]

@dain If the construction succeeds, it succeeds. There is no possibility of generating an incorrect filter.