Hidden Dangers of Range-Based For Loops // Bug Hunting

[@TheCherno]

Been streaming a lot more often recently, follow my Twitch channel so you don't miss the next one! twitch.tv/thecherno

[@sharanappa.mudenursharanap2541]

A ]

[@sharanappa.mudenursharanap2541]

Q

[@rasmadrak]

I guess a different approach would be to gather/flag all entities to be deleted and at the very end (or at a convenient point) remove all flagged entities. Probably more work that way, but on the plus side you can avoid costly deletes and store objects in a pool to be repurposed and/or deleted during low periods of low CPU usage etc.

[@hawks3109]

that could still cause the same issue since all you change is that you flag the object. The issue is that the object was being moved out from under the iterator so he wasn't actually looking at what he thought he was looking at. Flagging it wouldn't fix that

[@rasmadrak]

@@hawks3109 What I meant was removing it outside the loop, so there would be no iterating at that time. But you're right - it will have to be iterated at one point regardless. But in the case of linked list you could relink it to a garbage list and simply pop/erase the first item until empty. :)

[@GreenFlame16]

What is the music in background @37:00 and in general? Would love more C++ tutorial videos. Though even here I ended up staying to the end instead of just checking out for 5 min, made my soul soar, felt really good. Even though I am a SW engineer myself, this feels so enlightening to watch someone so knowledgeable work Btw I think it's you who helped me to get my latest job xD

[@CreativeSteve69]

I miss haning out in the streams Cherno. Great to see you back at it. Will have to drop by for a visit someday.

[@FatalExceptionz]

The video was renamed while I was watching and it stopped buffering. Of all the vids that could've exhibited this behaviour it's pretty fitting that it was this one.

[@TuringTested01]

Jack harlow out here teaching how to fix bugs! What more can we ask for?

[@musdevfrog]

My man evolved from Ed Shreen to Jack Harlow.

[@badpotato]

hahaha..🤣🤣😂😅.. we need some swalla la la.

[@bigmistqke]

@@musdevfrog character development

[@Retrosen]

Hazel looking so clean damm, making me wanna create my own

[@lotusfish8632]

hi cherno i watched one of your code review videos and now i'm the world's leading expert in c++, big help, thanks

[@adheesh2secondsago630]

Really? Who artest' thou?

[@AntonioNoack]

Yes, you were correct with your guessed name for Java: it's a ConcurrentModificationException, because you modify it concurrently to iterating over the list.

[@Dustyy01]

Feels so good when you finally fix and thus understand those bugs😄

[@CGwatcher]

Actually most modern debuggers have a feature of setting breakpoints on memory change. So you could try to set a breakpoint on the vector pointer or size change and see where it happens.

[@CodAv123]

Not having watched the video to the end, I'm seeing "auto item : list" everywhere, which is kinda dangerous. If doesn't contain just (smart) pointers, the loop will always copy each object in the list using the copy constructor. This isn't just a (possibly huge) performance issue, but can also create issues with deep-copying whole structures and having unwanted leftovers. So better use "auto& item : list" instead, or "const auto& item : list" if you don't want to change anything (e.g. only reading values for displaying).

[@CodAv123]

If using "const auto& item : list", you should even use "const auto&& item : list" instead to always get a valid rvalue reference.

[@gracicot42]

@@CodAv123 not completely true. For integers, it's actually faster to copy the values in the for loop.

[@CodAv123]

@@gracicot42 totally correct, should have noted I was referring to complex types. Thanks for pointing it out!

[@gracicot42]

@@CodAv123 I think activating the `-Wrange-loop-construct` warning is a good option, it's easy to forget which types are cheap copy, and which types are not. It saved me many copies. I try to keep compatibility with GCC and MSVC these days.

[@CodAv123]

@@gracicot42 this, many other warnings plus using an IDE with a good clang-tidy/cppcheck integration helps a lot improving code quality, performance and compatibility.

[@N....]

The temporary value you pass to the for-each loop is lifetime-extended to initialize the internal iterators of the loop, so that function call to get the Children only happens once. Your issue appears to be an iterator invalidation issue, I'm surprised you weren't getting crashes if the Children list was being reallocated - maybe the old list was being re-purposed somehow so it was still valid memory? Either way, it sounds like a bug for that list relocation in memory to happen at all during this process, that's a definite point of optimization.

[@tolkienfan1972]

A standards compliant std::vector will not invalidate iterators except thru modification. Simply obtaining an iterator, or incrementing one will not modify the vector. The ranged for is equivalent to the old style calls to begin and end. There is more debugging needed here.

[@kenan2386]

this man goes deep to find why a bug happens while im just like: it works, it just works, idk why, it works

[@hawks3109]

That's the difference between good and great programmers haha, not trying to offend, but digging deep to understand why is how you advance your knowledge

[@samochreno]

wow thats funny (not)

[@kenan2386]

Just like all my jokes ;-;

[@Sebanisu]

Ranged based for loops have issues if the range passed in is a r-value. Sometimes it destructs the r-value range before the loop is complete. I'm not sure if this is the case with this code. There was a paper to get this fixed though it was rejected for c++23. It might come back later in another form.

[@TheCherno]

It’s an l-value, entity.Children() returns a std::vector&

[@simonfarre4907]

7 minutes in and I think I saw a for loop with (auto entity : ...)

[@TheCherno]

It’s not, an entity is a uint64_t which we would rather copy. auto written like that will always copy, but in this case it’s intentional

[@simonfarre4907]

@@TheCherno i came from Rust and has been bitten by the auto keyword myself. It also was an incredibly, astonishingly subtle bug that took me way too long to fix, to not be embarrassed by it 😅 but having watched the video i see what bug it is now, these things are easier to trip oneself up with, than one believes. However, this bug would never happen in Rust. But programming a game engine in Rust, and I love Rust, is probably a nightmare.

[@peremoyaserra2749]

21:41 Fun fact: Java DOES throw a ConcurrentModificationException if you tamper with what you are iterating upon or the iterator because it automatically makes for loops partially multithreaded.

[@Drillgon]

It doesn't make for loops automatically multithreaded, it throws that exception because you're modifying the iteratable at the same time as iterating over it, aka modifying it concurrently with iteration. Making for loops automatically multithreaded would be a horrible hidden danger. Loops over small data sets would become much slower because of the thread overhead, and that's not talking about the dangers of regular multithreading that it wouldn't tell you to watch out for.

[@ToothlessXDIn]

Cherno 3 days ago: Eggs 🥚 Cherno now : Bugs 🪲

[@markmuir7338]

I think the issue here is iterating over a temporary. entity.Children() returns a temporary. Temporaries are live only in the statement they were created in. Here that's the RHS of the range-based for-loop. It goes out of scope in the body of the loop, so is undefined. You solve it by copying the temporary into a variable in a scope enclosing the lifespan you need. This is usually ugly. I have no idea why C++ is designed this way - the lifespan of temporaries is the cause of maybe 90% of weird bugs I encounter.

[@TheCherno]

It doesn't return a temporary, it returns an l-value (std::vector&)

[@oblivionronin]

Depending on the datastructure, if you want to avoid copying your entire data structure (especially if its really massive) to modify it while looping over it. You can always itterate it backwards. This often solves the problem because, the issue with deleting a list that you itterate over is that is, lets say you are at index 5 and delete that index and then move on to the 6th element, it might no longer be there because it was moved to the 5th position or you might even skip over an entire element. So usually itterating backwards from the end of the array or vector helps in most cases.

[@hawks3109]

Okay cool but why would the vector be moved around? Is it to optimize access like what a splay tree does? This means you could have also accidentally been deleting objects from whatever was moved to where your vector was at.

[@yaboinachin7198]

43:13 Hey, there i am!

[@NPSJoker]

Could you do a video on unit testing?

[@JFF-space]

Welcome to the mirror dimension

[@CWunderA]

Can someone explain what the bug exactly was here? I know it's related to returning an iterator, but can someone explain why the iterator causes issues while the repeated calls don't?

[@sugg5719]

The bug was that the vector's position in memory was being changed during the loop. With a range based loop it was storing the memory address at the start then using it for the whole loop, so when the address changes it's still using the old one. But with a normal for loop it's getting the latest address for the vector on every iteration.

[@zvxcvxcz]

I was using an algorithm for which I need to remove things from the object I was iterating over... Java made that a giant pain the arse. Ended up doing it C++, and you cannot use iterators for it.

[@dominokos]

Awesome video!

[@juliushuck]

Where can i buy this pan?

[@ExplosiveLizard]

Had a similar bug when I was making a vdom in js... Took me 2 days to fix it properly

[@daantimmer]

What is the type returned by entity.Children()?

[@ax13h]

auto

[@daantimmer]

@@ax13h right. Useful. What are the value semantics? And what type is returned

[@TheCherno]

std::vector&

[@daantimmer]

@@TheCherno Hmm. Are you _really_ sure? If so, are you modifying the vector itself while iterating it?

[@CodAv123]

Not that this was an actual issue here, yet I'm always trying to avoid returning non-const references to any internal vectors of a class. Chances are just too high someone - and I'm including myself here - will use this to change the data somewhere else out of convenience. Depending on the use case, returning either a copy or a const reference will be sufficient in 99.9%, and for the rest the class managing the vector/object can provide a few insert/remove/change methods.

[@lithium]

I suspect your "fix" will break in release, since i'd expect the call to ::Children() to be hoisted outside of the loop.

[@TheCherno]

It works in release, as expected. The problem isn't Children() being inside or outside of the loop, the problem is we can't obtain an iterator ahead of time because the location of the Children() vector in memory will move as well delete entities from the ECS. The solution works because we continually query the ECS to give us the Children() vector, instead of trying to obtain a reference for the entire operation duration.

[@lithium]

@@TheCherno Right, but i would've assumed those constant queries would've been elided by any aggressively optimising compiler, I still think this might be lurking in the shadows on you but hey if it works, it works.

[@TheCherno]

@@lithium The compiler can't just decide to remove code because of "constant queries" (there are only 50 in the example we were debugging), the underlying code to retrieve the actual data is a little more complex than just fetching it from a constant memory address.

[@lithium]

@@TheCherno "the underlying code to retrieve the actual data is a little more complex than just fetching it from a constant memory address" ok well this is what makes the difference. If it was just a dumb getter and wasn't marked volatile the compiler absolute can, will and should cache that value.

[@TheCherno]

@@lithium Of course, but in that case calling the function repeatedly instead of just obtaining a reference once would not have made any difference :)

[@SanderVermeer]

Isn't it just better to iterate backwards when deleting items from an array? I know that in this case the actual array gets modified afterwards, but still.

[@TheCherno]

We’re not deleting any items from the array in this for loop

[@marcusrigonati7784]

I think the title should be "hidden dangers of for-each loops", no?! hahha Great video, I thought that you would fix it and then finish the video, so good that you went to the bottom of it :P

[@TheCherno]

Range-based for loops are what we call for-each loops in C++

[@marcusrigonati7784]

@@TheCherno ahhh, everything makes sense now 😅 thanks!

[@guywithknife]

@@TheCherno the bug in the end really had little to do with the range-based for loop, but rather that you were taking a reference to a field in an EnTT component that was being moved due to how EnTT's component deletion works. The fact that the foreach loop triggered it is really just coincidental.

[@real1cytv]

Is it really faster to look up the vector in the ecs every time instead of just copying it?

[@saphrone9749]

yes

[@nicobugs]

5:50 My condolences to declan_cd

[@danielflorez3762]

But in the end why the memory address is changing ?

[@TheCherno]

Because we’re removing entities from the ECS, and the vector we’re iterating over is also in the ECS data structure. As entities are removed, the ECS may want to rearrange memory to for eg. reduce fragmentation due to all the entities we’ve destroyed, and so it will move our data in memory

[@danielflorez3762]

@@TheCherno thanks men :)

[@calmchess2515]

I do a lot of range based for loops. You have to make it very easy to debug a large data set so you can make it compile the first time and future maintain it. I like centralized code. Custom OOP is pretty good but I rarely reuse custom methods and classes. I just write most of it fresh. I don't really care how much time I waste. I just like creating stuff. Even if it breaks after it's runtime environment changes or upgrades.

[@tobeypeters]

Kept wishing I was in the chat. Wanted to ask you, if you could just contact the developer of the engine & ask him how it works. :>

[@greywolf424]

Do you seriously have over 1,100 lines in one file?

[@phlfm]

What is that thing that is "frying"?

[@karmavil4034]

Maybe deep in your heart you're using a list

[@skywing221]

Reverse loop when destroying stuff

[@guywithknife]

That wouldn't fix this bug, the children array isn't being deleted from. The children array itself is moving around in memory due to the fact that its stored in an EnTT component and component pointers aren't, by default, stable when components are deleted in EnTT (and deleting an entity deletes all of its components). The video title is wrong, the bug was made visible due to how he used the children array in the loop, but the underlying cause has little to do with the loop itself other than that he is iterating through invalid memory because the vector moved behind the scenes.

[@FollowNdFeel]

Fire isn't a thing.... It's an event... Curious...

[@Faryuon]

heeeey, I'm here in video)

[@spudgossie]

Sorry but I don't like this method of bug fixing. I call it printf debugging. Who cares if startup is slow under the debugger when you only do it once or twice not every time you add a printf. Also writing code to fix code seems problematic, bit like unit testing but don't get me started ;-). You are a good programmer but to get to the point of actually uttering the words "could nested foreach loops be broken" was hilarious. +1 Subscriber

[@electrotsmishar]

helpful

[@ssfdf7751]

I am a bug bounty hunter btw

[@ssfdf7751]

I make millions

[@Volian0]

sure 🤣

[@miko007]

i do not think you can blame range based for loops for you getting your references messed up... this honestly is such a noob error ^^ you generally do not want to do what you initially did there.

[@TheCherno]

How am I getting my references mixed up? That’s not what’s happening here at all…

[@miko007]

@@TheCherno `getChildren()` returns a reference to a vector, is it not? if so, this should be the case of a standard problem when implementing ecs, even when hidden through an external api here. it is not much different from the reason, why in ecs most people reference entities by a simple id, so you do not run into null pointers when destroyed. in this vector, there should only be a `size_t` value, if i interpret the api of "entt" correctly, so copying comes basically without any big performance penalty. of course, the address of a vector might change if it is resized, thats why you probably are not supposed to to access it by reference in such a case... or maybe i got something totally wrong here, but from what i understand, i think you are not using an "entt" view inside of `getChildren`, as recommended, which actually would have returned a copy.

[@TheCherno]

@@miko007 From what I understand, you're half right. When dealing with an ECS, you're correct in saying that the data structure is abstracted through an API, and thus we should avoid trying to obtain "permanent" references to data that is owned by the ECS since its location is subject to change. However, the address of a vector does not change when it gets resized, the address of the data pointer within the vector is what changes. The reason we had the bug in this video was not because the vector was resized or something like that (elements were neither added nor removed during the for loop, the size remains constant), but because the ECS moved the vector itself in memory when it rearranged the component arrays.

[@DFPercush]

Seems like the way to avoid that would have been to expose a getChild(index) and a getChildCount() instead of returning a vector. Might be worth doing just so you don't have to clutter your mental space with making sure you don't use .children() when it could be moved. Could come up again.

[@ssfdf7751]

good

[@wal9745]

I use Arch btw

[@SuviTuuliAllan]

Did you use curl to post that comment?

[@ssfdf7751]

🤮🤮🤮🤮

[@wal9745]

@@SuviTuuliAllan I called Dani to post it, hehehe... Did you what Karlsson is?

[@SuviTuuliAllan]

@@wal9745 Sorry, I don't understand. I must be having a stroke.

[@minticedteaenjoyer]

@@SuviTuuliAllan He's the one having a stroke

[@SimonBuchanNz]

Why are you sure children isn't being modified when you're deleting the children? That sounds exactly like when it would be modifying the children.

[@TheCherno]

Yes, the Children() vector is not being modified. I explain the problem and solution towards the end of the video.

[@SimonBuchanNz]

@@TheCherno sure, but that wasn't what I asked.

[@TheCherno]

@@SimonBuchanNz I'm sure that the Children() vector isn't being modified because there's no code that modifies it, and also I've checked?

[@SimonBuchanNz]

@@TheCherno from what I saw, it looked like children was returned from ENTT, and you are modifying state in ENTT, was my confusion as to your confusion. But it seems like the issue is that ENTT doesn't know anything about Children, it's just moving your component around as an opaque block when other components of that type are deleted or added. I'd probably approach this as collecting all the ids first, especially if you can pass a list of components to remove ENTT, it might be faster but more importantly ids recursively and removing a list of ids seem generally useful.

[@guywithknife]

@@SimonBuchanNz Children is a vector field of a component Cherno created. EnTT sees the component, but doesn't know anything about its fields. That is, it just sees a bunch of bytes (EnTT makes heavy use of type erasure anyway), it does not know what is stored in those bytes (a vector of children id's in this case). Personally, I prefer to keep my components as POD types (no non-trivial constructors or destructors). The bug here is that he took a reference to this vector field, but when you delete a component in EnTT, it may move them around (internally, EnTT stores components in a sparse set, which is two vectors: a sparse vector where the index is the entity id and the value is the index of the second packed vector of component data, deleting from the packed vector is done by swapping it with the last item in the vector and popping -- actually you CAN request an in-place deletion policy which guarantees pointer stability and would fix Cherno's bug, but it comes with its own trade-offs, namely that iterating now has overhead to check whether a component is valid or deleted and that operations such as sorting require the vector to be compacted first, which would break pointer stability).

[@reganheath]

My guess @20 mins in.. iterating a collection and removing items from it at the same time.

[@Phroggster]

That was my guess from the title of the video. Iterating collections can be such a hassle.

[@KevinDay]

Obligatory "Rust would prevent this at compile time" comment

[@MrSandshadow]

TL;DR what's the bug?

[@aminebenhebba1891]

isnt a good simple way to solve this without messing with the undeleted items context, is to start deleting from the last one back to the first...

[@TheCherno]

No, because that’s not the problem - we’re not removing anything from the list while iterating over it

[@guywithknife]

The thing being deleted from is the EnTT sparse set and the order of items in this is out of the users control. So there's no easy way to delete them in reverse order. EnTT does let you reverse a sparse set and iterate in reverse, but that wouldn't help because we only want to delete items that are children of the deleted parent, which may still be in the middle of EnTT's internal vector of components.

[@Jkauppa]

be a wiz

[@Jkauppa]

what is knowing how to copy vs skill without knowing, memory copy

[@Jkauppa]

programmers spam effort copying things around, what would be the better way

[@Jkauppa]

idea programming, auto-generation of the spam

[@Jkauppa]

minimal input in "compressed" form

[@Jkauppa]

program language syntax is the enemy, effort consumer

[@TopConductor]

First

[@yabot5496]

2 minutes ago, damn im early for once

[@felixp535]

I just don't use foreach loops. Ever. I just don't need it, and it saves me lots of trouble

[@simonmaracine4721]

Next time write your engine in Rust and you will never have to debug these problems. 😉

[@godnyx117]

Man not to hate, but who uses C++ in 2021? Just use D with "BetterC" instead!

[@gracicot42]

What? You're not using haskell? Go back to your cave! /s

[@godnyx117]

@@gracicot42 I'm not Chad enough to use Haskell or anything with not regular functional programming syntax/style. Sorry...

[@SimonBuchanNz]

Who uses D? Honest question.

[@SimonBuchanNz]

Also the correct "better C" is probably Zig. But I really like that there is a wealth of new good languages now...

[@godnyx117]

@@SimonBuchanNz It's not world famous like C++ but some people do. I'm trying to build a system library on D to be used instead of libc for example. Tbh the language itself is better than C++