InsertOnlyHashSet in C++

Short-circuiting behavior

You have a number of places where you run a loop over some collection of data, checking for a condition on each iteration, and return false or true, short-circuiting the loop.

E.g.

            for (size_t i = 0; i < K; i++) {
                if (item == values[i]) {
                    return false;
                }
            }
            auto spillStartIndex = bucket.spillIndex;
            for (size_t offset = 0; K + offset < bucketSize; offset++) {
                if (item == spill[spillStartIndex + offset]) {
                    return false;
                }
            }

These are opportunities to use something like std::any_of or std::all_of, or since you're using a range of integers, you may wish to use std::views::iota and std::views::take or std::views::take_while with std::ranges::all_of.

            if (std::ranges::any_of(
                    std::views::iota(0) | 
                    std::views::take(K), 
                    [](auto i) { return item == values[i]; }
                )
            ) {
               return false;
            }

            auto spillStartIndex = bucket.spillIndex;

            if (std::ranges::any_of(
                    std::views::iota(0) |
                    std::views::take_while([](auto offset) { return offset + K < bucketSize; }),
                    [](auto offset) { return item == spill[spillStartIndex + offset]; }
               )
            ) {
                return false;
            }

I note also:

• The reasoning for these loops and checks is not documented in comments.
• That they may be better factored out into private member functions.

This opportunity for range-based iteration can also be seen in a simple loop like:

                for (size_t i = 0; i < bucketSize; i++) {
                    newHashSet.insert(std::move(bucketValues[i]));
                }

Which might be:

                for (auto &bucket : buckets) {
                    newHashSet.insert(std::move(bucket));
                }

Indentation style

In the following you have a lot of indentation going on.

            // move all other spills
            for (size_t i = 0; i < nBuckets(); i++)
            {
                if (i != bucketIndex) {
                    if (auto& otherBucket = buckets[i]; otherBucket.size > K) {
                        if constexpr (std::is_trivially_copyable_v<T>) {
                            std::memcpy(&newSpill[newHead], &spill[otherBucket.spillIndex], (otherBucket.size - K) * sizeof(T));
                        } else {
                            for (size_t offset = 0; K + offset < otherBucket.size; offset++) {
                                newSpill[newHead + offset] = std::move(spill[otherBucket.spillIndex + offset]);
                            }
                        }
                        otherBucket.spillIndex = newHead;
                        newHead += otherBucket.size - K;
                    }
                }
            }

We can reduce this using continue.

            // move all other spills
            for (size_t i = 0; i < nBuckets(); i++)
            {
                if (i == bucketIndex) {
                    continue;
                }

                if (auto& otherBucket = buckets[i]; otherBucket.size > K) {
                    if constexpr (std::is_trivially_copyable_v<T>) {
                        std::memcpy(&newSpill[newHead], &spill[otherBucket.spillIndex], (otherBucket.size - K) * sizeof(T));
                    } else {
                        for (size_t offset = 0; K + offset < otherBucket.size; offset++) {
                            newSpill[newHead + offset] = std::move(spill[otherBucket.spillIndex + offset]);
                        }
                    }
                    otherBucket.spillIndex = newHead;
                    newHead += otherBucket.size - K;
                }
                
            }

Further to this piece of code, the if (auto& otherBucket = buckets[i]; otherBucket.size > K) feels a bit excessively clever, given there is no need for otherBucket to be limited in scope to the conditional, since nothing else follows.

            // move all other spills
            for (size_t i = 0; i < nBuckets(); i++)
            {
                if (i == bucketIndex) {
                    continue;
                }

                auto& otherBucket = buckets[i]; 

                if (otherBucket.size > K) {
                    if constexpr (std::is_trivially_copyable_v<T>) {
                        std::memcpy(&newSpill[newHead], &spill[otherBucket.spillIndex], (otherBucket.size - K) * sizeof(T));
                    } else {
                        for (size_t offset = 0; K + offset < otherBucket.size; offset++) {
                            newSpill[newHead + offset] = std::move(spill[otherBucket.spillIndex + offset]);
                        }
                    }
                    otherBucket.spillIndex = newHead;
                    newHead += otherBucket.size - K;
                }
                
            }

We might further reduce indentation levels with:

            // move all other spills
            for (size_t i = 0; i < nBuckets(); i++)
            {
                if (i == bucketIndex) {
                    continue;
                }

                auto& otherBucket = buckets[i]; 

                if (otherBucket.size <= K) {
                    continue;
                }

                if constexpr (std::is_trivially_copyable_v<T>) {
                    std::memcpy(&newSpill[newHead], &spill[otherBucket.spillIndex], (otherBucket.size - K) * sizeof(T));
                } else {
                    for (size_t offset = 0; K + offset < otherBucket.size; offset++) {
                        newSpill[newHead + offset] = std::move(spill[otherBucket.spillIndex + offset]);
                    }
                }
                otherBucket.spillIndex = newHead;
                newHead += otherBucket.size - K;
            }

size_t index = thisHash % nBuckets();

Since you apply an avalanche function to the hash, it is safe to force the number of buckets to be a power of two and then you can use a bitwise truncation here (eg bitwise AND, or right shift if you prefer, doesn't really matter hashes that have gone through an avalanche function) instead of a more expensive remainder. Some hash sets & maps do this without applying an avalanche function to the hash, which can cause problems if the hashes have poorly distributed lower bits (if using bitwise AND) or poorly distributed upper bits (if using right shift), but after putting the raw hash through the MurmurHash3 finalizer it should be fine to take some subset of its bits as the index. When you can get away with it, skipping the avalanche function but still using a bitwise AND for the range reduction can be the fastest option (that's why some hash sets & maps do it), this only gets slow due to not being able to get away with it and generating too many collisions.

Or if you don't want to force the number of buckets to be a power of two, you could use multiply-high (at the assembly level it's as easy as a multiplication, unfortunately it takes some effort to express it in C++, hopefully multiply-high makes it into the standard library at some point), essentially that treats the avalanced hash as a fixed-point number in the range [0 .. 1) and multiplies that by the number of buckets, giving a number in the range [0 .. nBuckets). This relies on the hashes being properly distributed throughout the whole 64-bit range, which they should be after going through avalanche function, but otherwise for example if the hashes tend to be low values then the resulting indices similarly bunch up near zero.

How much avoiding a remainder operation matters depends on the CPU you test the code on. For example on Intel x64 processors like Kaby Lake and older a 64-bit remainder takes dozens of cycles to compute, while on more recent processors it may only take around a single dozen of cycles, which is still not great but noticably less than it used to be.

Given the results from various hash map benchmarks (usually it's maps, not sets, but they're pretty similar..), such as https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ , it may be worth comparing not just to std::unordered_set but to some alternatives as well.

A pity there is no well documented abstract class e.g. std::unordered_set is patterned after.
But given the lack of intersection and union there, I don't see how to do without iteration.

With hindsight, I think it would have merit to proceed in stages:
a) special case K == 1, no spills (just grow table & rehash) - private?
b) special case K == 1
c) general K (see question)
d) elaborate "free" management for spill? May well prove not worth it

To have spelled out in an answer what indy's comment highlights:
Keeping Ts instead of (shared(?)) pointers(/references?) uses a lot of space, especially where items are significantly bigger than their keys. And it initialises a lot of Ts.
Having table size exceed nominal capacity is conventional, their quotient designated load factor. M looks the latter's reciprocal, but even 2 is a lot: conventionally, a floating point value is used here. Likewise, a spill area the size of nominal capacity is anything but shy.

There are six sections of source code searching for an item:
two functions times (two places to search + one for when the bucket didn't spill).
The + one is easy to consolidate: search up to the min of K and bucket size.

thisHash is unused but for computing bucketIndex. Depending on the cost of establishing item equivalence, it may be useful to keep the hash values and use them to establish not equivalent cheaply.

To further reduce searching code, I shy from consolidating bucket & spill.
So how about a consolidated function?
I tried to code it (bottom of post - I find myself way out of my depth with C++, more so with modern C++.)

In reserveBucketSpill(), there are three instances of "std::is_trivially_copyable_v-optimised copy": factor out a procedure.
Calling that, it seems "this spill" gets copied twice?!

// just hacked in to eyeball feasibility
    /// search for an item.
    /// return is_contained when dont_insert;
    /// otherwise false if is_contained,
    /// else insert & return true
    bool checkInsertIf(const T& item, bool dont_insert) {
        auto thisHash = myHash(item);
        size_t index = thisHash % nBuckets();
        auto& bucket = buckets[index];
        auto bucketSize = bucket.size;
        auto& values = bucket.values;
        auto range = std::min(bucketSize, K);
        auto begin = values.begin(),
             beyond = begin + range,
             found = std::find(begin, beyond, item);
        
        if (found != beyond)  // item found in bucket
            return dont_insert;

        if (bucketSize <= K) {
            if (!dont_insert && bucketSize < K)
                values[bucketSize] = item;
        }
        else /* (K < bucketSize): handle spilled */ {
            begin = spill.begin() + bucket.spillIndex;
            range = bucketSize - K;
            beyond = begin + range;  // given references this calls for factoring out
            found = std::find(begin, beyond, item);
            if (found != beyond)  // item found in spill
                return dont_insert;
        }
        // not found anywhere
        if (dont_insert)
            return false;
        if (K <= bucketSize) {
            reserveBucketSpill(index, bucketSize + 1);
            spill[bucket.spillIndex + bucketSize - K] = item;
        }
        bucket.size = bucketSize + 1;
        numElements++;
        return true;
    }

    bool contains(const T& item) const {
        return checkInsertIf(item, true);
    }
    
    bool insert(const T& item) {
        if (capacity <= numElements) {
            reserve(capacity <= 1 ? 2 : (capacity * 5) / 3);
        }
        return checkInsertIf(item, false);
    }

1. Don't put static asserts in constructor, since it limits of the whole class. Instead:

template <typename T, std::size_t K, std::size_t M>
class InsertOnlyHashSet {
        static_assert(M > 0, "Template parameter M must positive");

2. initialize member variables in the initializer's list:

explicit InsertOnlyHashSet(const size_t capacity)
     : numElements(0),
       capacity(capacity),
       spillHead(0),
       buckets( M*capacity ),
       spill(capacity),
       spillHead( 0 )
    {
        assert(capacity > 0);
    }

3. instead of using indexing, use iterators. For example, in the reserve() method, instead of this:

                for (size_t i = 0; i < K; i++) {
                    newHashSet.insert(std::move(bucketValues[i]));
                }

do this:

                auto it = std::begin( bucketValues );
                while( std::end( bucketValues) != it ) {
                    newHashSet.insert(std::move( *it++ ) );
                }

Once you make such changes to all places, you should see a huge improvement.

4. don't mix methods and variables

...
    size_t nBuckets() const { return buckets.size(); };
    size_t nTotalSpill() const { return spill.size(); };


    std::vector<BucketEntry> buckets;
    std::vector<T> spill;
    size_t spillHead;

5. a function (method) should do one thing and it should do it good. Also, it should fit the screen, because if you read long functions, when you get to the end, you forgot what was at the beginning. Your method reserveBucketSpill() goes over pages and is too long.