Measurements Indicate that this is “Faster than the Speed of Light”

[rdeits]

@GpuCoder

The implication is that the underlying data structure must be significantly richer than assumed. There must be something like a hidden queue. The queue structure must point to elements in the bit array and there must be an index for finding elements in the queue when they are removed from the set, so they can also be removed from the queue.

Nope, definitely not. Here’s the full definition of the type, which you can find by doing @edit BitSet():

mutable struct BitSet <: AbstractSet{Int}
    bits::Vector{UInt64}
    # 1st stored Int equals 64*offset
    offset::Int

    BitSet() = new(sizehint!(zeros(UInt64, 0), 4), NO_OFFSET)
end