News for hackers. Stuff that matters.
Re:My favourite C++ footgun by 2bitencryption on Tuesday June 22, 2021 @05:05PM (#27597206)
My favorite C++ footgun is creating a Vector with some items, taking a reference to, say, &vec[3], then adding another item to the vec, then trying to use the reference from the previous step.

If you write C++ it might be obvious what the problem is.

If you don't, this will absolutely ruin your entire day.

The worst part is, 95% of the time, it will probably work without issue.

But eventually, pushing a new item to the Vector will trigger a relocation of the whole vector, which will invalidate your reference and bring down production. Have fun debugging that.

Re:My favourite C++ footgun by nicoburns on Tuesday June 22, 2021 @05:34PM (#27597519)
Yep. I learnt about this when I was learning Rust (which makes this a compile-time error). I was very glad I didn't have to learn this and the 100 other things like that seem to exist in C++ the hard way!
Re:My favourite C++ footgun by failwhaleshark on Tuesday June 22, 2021 @08:39PM (#27599292)
Footguns might keep you prepared for the zombie apocalypse, but they'll inevitably make it difficult to walk. I'm glad I don't currently use C++ in production, but that may change soon. ):
Re:My favourite C++ footgun by kaik on Tuesday June 22, 2021 @06:21PM (#27597984)
I kid you not, I spent a full working day debugging this exact same issue (taking a pointer to a vector element, before adding more elements). Very obvious if you understand how C++ and vectors work, yet it took me forever to realize, and it was miserable…
Re:My favourite C++ footgun by saagarjha on Tuesday June 22, 2021 @08:04PM (#27599030)
Heh, you can run into this even if you understand how iterator invalidation works. Once you see the bug it's easy to understand, but finding it might not be…
Re:My favourite C++ footgun by account42 on Wednesday June 23, 2021 @06:45AM (#27602957)
> finding it might not be…

Valgrind memcheck is your friend.

Re:My favourite C++ footgun by gpderetta on Wednesday June 23, 2021 @07:15AM (#27603123)
also asan.
Re:My favourite C++ footgun by duped on Tuesday June 22, 2021 @06:03PM (#27597794)
This, and the entire class of iterator invalidation bugs that force you to memorize which collections are ok for which applications.
Re:My favourite C++ footgun by nyanpasu64 on Tuesday June 22, 2021 @06:18PM (#27597953)
Rust takes the approach of flat-out not letting you mutate any collection while you have any references to its contents. It eliminates all dangling pointer bugs... I don't know if it rules out any useful use cases of collections with iterator stability. I think any C++ collection holding unique_ptr is stable (pushing to the collection doesn't invalidate the target of the unique_ptr), and Rust doesn't have an safe ergonomic way to achieve that (perhaps Pin<Box<MagicCell<T>>>, but we don't yet have a MagicCell that makes &mut MagicCell<T> not noalias).
Re:My favourite C++ footgun by Animats on Tuesday June 22, 2021 @08:18PM (#27599151)
Rust takes the approach of flat-out not letting you mutate any collection while you have any references to its contents. It eliminates all dangling pointer bugs... I don't know if it rules out any useful use cases of collections with iterator stability.

It does. Some collections have a "collection.retain" method.

   collection.retain(|v| true_if_we_want_to_keep(v))
which goes through the collection in linear time and deletes any items for which the test is false. This is O(N).

Some collections ("multi_map", which isn't used much, comes to mind) don't have that. You have to make a read pass over the collection, construct a list of things to delete, then go through the delete list and delete those items. Can't read and change with the same iterator. That's slower. But sound.

I'm OK with that. It avoids subtle bugs.

Re:My favourite C++ footgun by ridiculous_fish on Tuesday June 22, 2021 @08:51PM (#27599361)
An illustrative example is a string set which remembers its insertion order. In C++ you may write:

    struct OrderedSet {
        deque<string> storage;
        set<string_view> vals;
    }
The deque holds the string contents, and the set holds views of those contents. This is safe because the deque has iterator stability, and it's pleasant because the `vals` set can just be a regular set.

As you say Rust does not allow this; its answer is IndexSet, and it is implemented differently, like:

    struct OrderedSet {
       Vec<String> buckets;
       RawTable<usize> hashToBucketIndex;
    }
RawTable is a hash table that doesn't know how to compute a hash or determine equality. Instead, you provide it with closures to do those tasks, but at the call site (not construction time).

Basically Rust achieves the same thing through a layer of indirection involving indexes, which is a common pattern.

Re:My favourite C++ footgun by duped on Tuesday June 22, 2021 @06:56PM (#27598376)
The underlying pointer to a unique_ptr won't be invalidated but the iterator might. Consider if you had a vector of unique_ptrs and inserted into it within a for loop. Depending on the implementation of the iterator this may not be sound (if it's an index, you're probably ok, if it's a pointer, you're screwed).

If you wanted to do the same in Rust it would be Vec<Box<T>>. Mutating the collection won't invalidate the pointers.

Re:My favourite C++ footgun by nyanpasu64 on Tuesday June 22, 2021 @09:51PM (#27599851)
> Mutating the collection won't invalidate the pointers.

Rust still won't let you mutate a Vec<Box<T>> while you hold a &T or &mut T borrowed from the Vec.

Perhaps it would be sound to do so unsafely; Rust would let you mutate a Vec<Rc<T>> while you hold a Rc<T> cloned from the Vec. But I'm not clear on whether Stacked Borrows allows moving the Box while you have a &mut T pointing to the same memory as the Box points to. It definitely does not allow dereferencing the Box. (I heard Stacked Borrows will be updated to make self-referential types sound, and I don't know if it will affect this situation.)

Re:My favourite C++ footgun by Measter on Wednesday June 23, 2021 @07:15AM (#27603122)
In the case of a Vec<Box<T>> the Vec owns the box, so the only thing you could link the reference lifetime to is the Vec itself because if the lifetime isn't bound to the Vec, mutating the Vec might drop that item which in the case of Box<T> will also deallocate the memory. If any references point directly to that memory, then it would be dangling.

In the case of Rc<T>, cloning the Rc creates a second owner of the heap allocation, so the Vec dropping its copy won't deallocate. Though I believe one complication to this would be that the lifetime any references created through the Vec's copy of the Rc will be linked specifically to that copy, so would result in a borrow check error when it's dropped.

If the Vec is storing references, you can borrow the thing behind the reference and still mutate the Vec because that reference stays valid even if mutating the Vec drops its reference to the item.

    let (a, b, c, d) = (1, 2, 3, 4);
    let mut v = vec![&a, &b, &c, &d];
    
    // If you change the type here to &&u32, or let the compiler infer the type
    // then you'll get a borrow check error because the outer reference 
    // borrows the Vec.
    let borrowed_b: &u32 = &v[1];
    v.remove(1);
    
    println!("{}", borrowed_b);
    println!("{:?}", v);
https://play.rust-lang.org/?version=stable&mode=debug&editio...

[1]

Re:My favourite C++ footgun by pjmlp on Wednesday June 23, 2021 @03:33AM (#27601824)
If you use a proper C++ compiler, the debug builds throw a runtime exception or abort on invalidation misuse, and it can be enabled for release build as well.
Re:My favourite C++ footgun by pizza234 on Tuesday June 22, 2021 @06:11PM (#27597878)
Interestingly, AFAIK also Golang suffers from something similar: creating a slice from an array, then performing an operation on the array, that causes resizing - the slice will keep pointing to the old array data.
Re:My favourite C++ footgun by krylon on Tuesday June 22, 2021 @05:36PM (#27597538)
You can run into the same problem in C, using malloc/realloc. realloc, in fact, makes for a nasty footgun, too (and remains, of course, available in C++).
Re:My favourite C++ footgun by flohofwoe on Wednesday June 23, 2021 @06:18AM (#27602807)
An important difference is that in C it is usually obvious that a reallocation is happening while in the C++ stdlib, memory management is usually hidden (important to note that this isn't a design fault of the C++ language, but of the C++ stdlib, unfortunately the two are more and more entangled in newer C++ versions). Because of the fact that memory management is hidden in C++, I find claims that C++ is more memory-safe than C quite hilarious. If it works, it works fine, but if anything goes wrong (which is quite easy to achieve) it's much harder to find the actual problem in C++ than in C.
Re:My favourite C++ footgun by turminal on Tuesday June 22, 2021 @06:00PM (#27597764)
Yes, but unlike with realloc and a custom dynamic array, C++ references and smart pointers and containers are half-smart and do all sorts of things on their own. Knowing when they will and when they will not be "smart" makes writing C++ really difficult sometimes.
Re:My favourite C++ footgun by flyingswift on Tuesday June 22, 2021 @05:51PM (#27597678)
What is the safe way to achieve the same result?
Re:My favourite C++ footgun by Kranar on Tuesday June 22, 2021 @05:54PM (#27597703)
The concept behind this is reference stability, and if you need a collection that has stable references, you must introduce a level of indirection, that is, instead of a vector<T>, you use a vector<unique_ptr<T>> and then you can take references as follows:

    auto& r = *some_vector[0];
Re:My favourite C++ footgun by owl57 on Tuesday June 22, 2021 @08:58PM (#27599422)
Or std::deque. It's conceptually similar, but additional allocations are hidden under the hood and batched.
Re:My favourite C++ footgun by MauranKilom on Wednesday June 23, 2021 @02:35AM (#27601469)
std::dequeue is as good as useless. The defaults for "batch size" in different compilers are at extreme opposites of the tradeoff spectrum. So unless you really don't care about performance, memory or portability, it's not a datastructure you can rely on.

From memory:

In MSVC, dequeue will allocate memory for every single element if your elements are > 8 bytes. This will never be changed, due to ABI compatibility.

Clang and gcc have batching sizes of 1K and 4K (i.e. you throw out a whole page of memory even if your dequeue contains only 1 element).

Re:My favourite C++ footgun by owl57 on Wednesday June 23, 2021 @03:53AM (#27601944)
I had a vague feeling that std::deque is a "heavy" thing which you shouldn't have a million of, but iterating through a couple big ones is pretty fast. 1–4K batches wouldn't hurt my feelings. Looked up GCC, it's actually slightly less heavy at 512 bytes per node[1]. But the MSVC part — that caught me completely off guard.

https://github.com/gcc-mirror/gcc/blob/47749c43acb460ac8f410...

Re:My favourite C++ footgun by jcelerier on Wednesday June 23, 2021 @03:31AM (#27601805)
In general it's better to use the same standard library everywhere - discrepancies like that occur for almost every type so if you care about having the same performance on every platform... Either use libc++ or boost
Re:My favourite C++ footgun by gpderetta on Wednesday June 23, 2021 @07:19AM (#27603152)
IIRC boost.containers has a standard conforming deque with configurable batch size.
Re:My favourite C++ footgun by flyingswift on Tuesday June 22, 2021 @05:58PM (#27597730)
Thanks! I am just learning C++ for a new gig, and coming from Javascript land, it is a lot to take in :)
Re:My favourite C++ footgun by layoutIfNeeded on Wednesday June 23, 2021 @02:29AM (#27601425)
Yikes. I feel sorry for your client in advance. One does not learn C++ “for a gig”, especially when coming from JS…
Re:My favourite C++ footgun by Karsteski on Wednesday June 23, 2021 @06:52AM (#27603004)
For all you know, this person is simply talking about a new job. Is it necessary to be so condescending..? Sigh
Re:My favourite C++ footgun by saagarjha on Tuesday June 22, 2021 @08:08PM (#27599065)
I would generally suggest avoiding reference stability here (extra heap allocations) and going with the offset-based approach mentioned in the other responses.
Re:My favourite C++ footgun by Kranar on Tuesday June 22, 2021 @08:17PM (#27599147)
I would generally suggest going for correctness over performance and the solution I provided is correct in the general case. Using an offset is only correct in the special case where objects will not be inserted or removed at an index less than the offset, otherwise you will end up with bugs as the offset becomes invalid upon such operations.

Furthermore, depending on the size of T, the performance penalty of the extra heap allocations is amortized over the cost of resizing the vector. That is vector reallocation is significantly faster for a unique_ptr<T> than it is for T when T is large and almost all memory allocators are tuned to allocate objects close together in space when they are allocated close together in time, so you don't lose the cache locality or need to worry about memory fragmentation.

Re:My favourite C++ footgun by yongjik on Tuesday June 22, 2021 @06:51PM (#27598325)
In addition to other answers, sometimes you do know the final/max length of the vector when you construct it. In that case reserve() can reserve the necessary space, and as long as you stay under the limit all the addresses will remain valid.

(Though it's still pretty brittle, so you may want to add a ton of comments to warn yourself in the future...)

Re:My favourite C++ footgun by TylerGlaiel on Tuesday June 22, 2021 @06:13PM (#27597899)
store the index 3 as an int instead of &vec[3]
Re:My favourite C++ footgun by bentcorner on Tuesday June 22, 2021 @06:36PM (#27598142)
I can understand people used to a HLL running into this. It's useful to read the documentation: https://en.cppreference.com/w/cpp/container/vector/insert mentions that references/iterators may be invalidated.

I'm not going to pretend that I understand everything on that site (particularly anything about complex templates and things like SFINAE) but often there's comprehensible stuff in there. It can be really helpful.