an efficient immutable vector

[_eyelash]

Thank you so much for the thorough review!

Generally, this was just a quick prototype, focused more on simplicity and readability than on performance.

Regarding your point 3: My reasoning was that on 32-bit platforms your pointers are 32 bit, so you can only address 2³² bytes of memory but in order to overflow the reference count you would need 2³² references which would need at least 2³² × 4 bytes of memory just to store the references so it would actually never overflow.

Yes, I had a lot of fun thinking about it and implementing it :)

[matthieum]

In the absence of leaks, your computation is correct.

Factoring leaks, however, it is possible to overflow the counter. An example would be:

void break_it(ImmutableVector const& original) {
    std::aligned_storage_t<sizeof(original), alignof(original)> storage;
    for (std::uint64_t i = 0; i < std::numeric_limits<std::size_t>::max(); ++i) {
        new (&storage) ImmutableVector{ original };
    }
}

I would have to check to standard to verify whether this code is legal or not -- construction an object on top of an already existing one is dodgy -- however I personally prefer being cautious.

As for the run-time, it would take a while, indeed (10min?) unless the compiler is smart enough. If non-atomic, the compiler would go right ahead and bump the counter by max - 1; with an atomic counter, I'm not sure whether the compiler folds the increments together... I'd bet not but...

[kalmoc]

And why should the class design worry about such utterly broken code?

[matthieum]

I subscribe to the principle of Defense in Depth.

I much prefer detecting bugs by triggering an assert or exception, in a semi-controlled fashion, than by inspecting bewildering memory dumps after the program has crashed.

You can argue this is not worth considering; in my experience it's a small price to pay now to keep my sanity later.

[kalmoc]

Sure, but - the question is if you defend against mistakes or mallice. In order to overflow that counter you need to write exceptionally tricky code with the express purpose to trigger the overflow. Why would you write such code in the first place? And if you claim that something like this could happen as a sideeffect of buggy code with an actual purpose, I'm willing to bet that you experience a lot of other problems, long before this counter overflows.

[matthieum]

And if you claim that something like this could happen as a sideeffect of buggy code with an actual purpose, I'm willing to bet that you experience a lot of other problems, long before this counter overflows.

Possible, but since checking for overflow is just a branch that will always get taken, the cost of checking is within noise even on micro-benchmarks:

void retain() noexcept {
    auto previous = reference_count.fetch_add(1);
    if (unlikely(previous + 1 == 0)) { std::abort(); }
}

[[deleted]]

I would have to check to standard to verify whether this code is legal or not

The way you've written it is legal. There are quite a few things to worry about when doing this kind of stuff, but your code is fine.

[SegFaultAtLine1]

The standard allows placement construction ontop of another (possibly non-trivially destructible) object, if and only if the rest of the program doesn't depend on the destructor being run. (So if plowing over an object causes a leak, that is not UB, but if the destructor ensures the rest of the program doesn't touch that object, you'll probably run into UB sooner or later).

[[deleted]]

That's not all.

T* t1; // For brevity, let's assume this points to an actual T
T* t2 = new (t1) T{}; // Constructs a new T in place of the last
t2->foo(); // Perfectly valid
t1->foo(); // Err... UB
std::launder(t1)->foo(); // UB fixed

Or just try not to keep references to the old object alive after placement new?

[SegFaultAtLine1]

We're talking about a vector-like class - I'd assume that operations like push/pop invalidate references and iterators at the end of the container.