Multicore Game Development: C++11 Practices

[00:00:01]so hello everybody thanks for coming had a few AV issues there so we're improvising a bit got my friend's laptop um so yeah hi my name is Jeff I work at Ubisoft Montreal we're a games company we make games such as Watchdogs Assassin's Creed Rainbow 6 and Far Cry and all of these games run on Multi and that's what we're here to talk about now multicore of course is when you have several CPU cores on a single processor each core understands the same instruction set runs in the same address space and you simply migrate existing threads from one core to the other this is the kind of multicore I'm going to be talking about so no gpus no spus going to talk about this kind which became mainstream around 20 5 when it became sort of the new popular way for CPU vendors to offer more power to programmers like us um and as you may know this power is difficult to exploit to its fullest but it has been almost 10 years and 10 years has been enough time to make some progress but I have noticed one thing on one hand you've got the games industry and multicores had a a pretty big impact on us but we're starting to settle a bit on our way of doing things on the other hand you've got the larger C++ Community where interest in multicore has really picked up in recent years with the arrival of the standard atomic Library proposals like parallel algorithms so we both have the same goal we all want to exploit multicore right but I've noticed that by and large neither groups really aware of the works that been done in the other so the goal of this talk is to try to bring the two communities closer together by talking a bit about things are done so part one of this talk is going to be about of course multi-core programming at Ubisoft Glimpse at how we do things part two is going to be a quick introduction to the C++ Atomic Library a lot of people in games have not really been exposed to it yet but uh compiler support is pretty mature now so I think it's ripe um you know that might we might start seeing code trickle in at least at Ubisoft Montreal so hope there'll be a little something for everybody all right so part one is the obligatory slide where I show you you know typical consoles that we develop for number of Hardware threads in each before 2005 you know it was pretty much just one general purpose Hardware thread all the time uh that all changed of course and now it's more usual to to see up to six a modest number of CPU cores or Hardware threads we don't really make a big distinction between the two when we develop for games Hardware Hardware threads are course so I'm going to use the words interchangeably one exception being PlayStation 3 had only two Hardware threads complemented by six spus which I won't be talking about so we had to make the most uh in this bra Brave New World now in the early days a single threaded main Loop of a game would look a lot like this first you would do a bunch of work we call these the engine tasks you know Gathering player input updating logic physics and animation then we'd perform a bunch of steps we consider the graphics tasks determining what's visible to the player issuing draw calls to the GPU and repeat of course this sequential approach became a dead end of on multicore right why limit ourselves to One Core don't leave the others leaving the others unused so we adapted by implementing the following three threading patterns every game you see in development at Ubisoft Montreal is pretty much a blend of the following three you know sometimes we pipeline work two threads working in lock step with each other uh the other pattern is you know a simple dedicated thread a thread that does one thing sequentially and then of course task schedulers now I'm pretty sure most of you know what I mean mean by these things but I'm going to talk briefly about each one of them there's just a couple things I want to point out and as I do keep an eye out for the concurrent objects these are objects that are modified concurrently mulle threads operate concurrently on the same object with that with at least one thread modifying its state because in order to implement those patterns we had to write such concurrent objects to synchronize the work between them and we could do that either on top of the available platform Primitives you know like new texes semaphor event objects or in cases where the object's under very heavy contention that's when we might use Atomic operations to make it more scalable so if maybe you're new to Atomic operations and you're learning about it and you're wondering where do these things fit in to a real application well here's one answer so the first pattern I'll talk about is pipelining work as you might spe this involves you know doing the same thing at the beginning run the engine tasks in one thread but kick off the graphics tasks in another and the advantage of doing that is you can go right ahead and begin performing the engine tasks for the next frame in parallel so on and so forth thus letting you achieve up to twice the work in the same amount of time one way to set this up is uh using a semaphore and just thread uh increments the the semaphor at the end of each iteration Graphics thread decrements it mind you you need a semaphor in the other direction to prevent the engine thread from getting too far ahead in its work so there's the first concurrent object of course you may look at this and wonder well how do you avoid race conditions right concur modifications because of course you got all these game objects in your engine engine threads modifying them in in one thread while the graphics thread is also trying to work with them well two real simple anwers to that question one approach is to double buffer any state that's relevant to both threads so an object's position Matrix you might have two two copies uh and each each frame each thread knows which copy it's working with and they alternate back and forth every frame next approach also real simple you have Graphics objects that are separate from the engine's objects and you just simply copy the needed State at the beginning of each frame so that's how that mystery is solved which brings us to our next pattern dedicated threads the example I'm going to use for this is content streaming because in today's open world games we never have the entire game World fully loaded in memory at one time um we tend to just load what's closest to the player at least in full and this actually lends itself quite well to multicore because now it's convenient for us to just have a dedicated thread floating around the system dedicated to loading so you know again you've got your engine thread iterating you got your loading thread which is initially asleep at some point you know the player might cross a threshold in the game route in the game world which uh you know that kicks off a loading request hey we're going to need to start loading this chunk of data over here because that's where they're going that request gets serviced in the loading thread and there is actually CPU work to do to be done here it's not entirely IO bound and when that's done of course the loading thread goes back to sleep now these two threads are not working in log steps so you need some way to coordinate the work between them simplest way to do that uh is you know with the concurrent q and any Q will do the job you know you can just throw a lock on top of it to make it thread safe not a very high contention on this object so that'll do just fine and it's very important to let that loading thread go to sleep when it has no work because you know we have only six cores six Hardware threads to work with and we really need to economize the available CPU time let that core work on something else so waking up threads is I think an interesting thing to to look at real quick um the most common way we do that in games uh at least at Ubisoft Montreal we don't use uh locks and and condition variables we tend to use these portable Primitives available on each platform called an event event real simple it can be in two states when it's signal that means other threads can pass through when it's reset or not signaled other threads will have have to wait on it um and then each time anybody submits work to the request queue submits a request you know they signal that event in case it wasn't signaled already the loading thread then Waits on that event at the beginning of each iteration of its outer loop when it gets that signal it resets it right away does as much work as it can exhausting the que and then repeats when the q's exhausted it's totally possible that this will do an extra iteration around the loop that it doesn't have to but that's harmless um the important thing is that as long as there's work to do it won't remain asleep so that's dedicated threads and how we manage them oh no it's not quite yet I wanted to mention you know a q's nice but often in games we can do better and we do because you know if the player starts heading out in One Direction triggers a request to load that stuff over there they might do a 180 go the other way before that stuff actually begins to get loaded so it might might not be the best candidate for loading anymore so now we want a way to cancel requests interrupt requests in Flight reprioritize requests as they're getting pulled out so that thing's not technically it's not a a queue anymore it's some other custom concurrent object this comes up often in game programming there are very few out of the box off the shelf uh you know concurrent objects that we can just plug in to solve a problem what that concurrent object does is usually very specific to the problem being solved which brings us to task schedulers task schedulers were born out of the desire to achieve more fine grained parallelism than what we've seen so far so if you look closely at the work that the engine thread does you know you find that the logic tasks themselves break into smaller pieces as do the other tasks and they're often safe to run in parallel of course right so with a task scheduler that's exactly what you do distribute the work across several worker threads each worker thread is a lot like that dedicated well it is a dedicated th thread really dedicated to the job of running tasks so just like in the case of the loading thread simplest way to set that up is with a concurrent que again anyone can push items into the queue we don't care which thread pulls it out as long as someone does like wise the the code for this very simple you know distillation of the idea uh looks very much the same only this time each worker thread has its own event to manage it going to sleep and waking back up and you know one one way you can make this system work is that anytime anyone submits a task uh it signals all the events wakes up all their threads you don't care which one deals with it but very similar to the other kind of dedicated FR thread in this case of course that might seem a bit naive and it is it's not exactly what we do in games one thing we do differently is organize those small tasks into groups so you might have a group for each of those categories logic physics and animation and each task group just keeps an array of items to update in parallel and then we allow multiple threads to work on that same task group at the same time so this little diagram on the right represents a concurrent task group object um we keep track of the next item to work on with this mcore index shared variable which we declare volatile because again this is before C++ 11 came along volatile was typically our way of you know indicating that this this variable might be changed at any time um yeah it's true that volatile disables certain optimizations but we don't worry about it it doesn't actually prevent us from generating efficient code so volatile it is and then you know say there's two threads there what they do is they just in their own Loop they're both in the Run function they just pick off the next itom of work to do using an atomic increment that go back and forth like that of course to manage these task groups it can't really be strictly speaking a a q anymore like we don't want the first thread to to uh retrieve the task group we don't want it to pop it off the que so once again it's kind of a more custom concurrent object right might be for example a queue with separate separate tails for each worker thread or you know we could give each worker thread its own Q push the same task group onto each one a lot of variations many ways to skin a cat point is like once again we got to implement these custom concurrent objects and strategies another nice result that you get out of task groups it gives you a way to manage dependencies for example might not be safe to run any of the physics tasks until all of the logic tasks complete and task groups give you a nice way to set this up and and we actually have a lot of dependencies like this in our game engines because now you can just establish a simple rule you know the last thread that finishes well the thread that finishes the last item in the the task group that's the one responsible for scheduling the next task group making it available for other threads to work on you can set that up with a separate shared counter remaining count first thread to decrement that to zero after actually doing work that's the one responsible and it has to be a separate counter right because determining the next item to work on is not the same thing as actually completing the work on that item and it doesn't stop there there's a lot of different features you can add to a task scheduler a lot of different tradeoffs you can make um I actually can count at least four different task schedulers in use on various projects at Ubisoft Montreal alone that's just fine it just means that each project is free to customize its concurrent objects as it sees fit and that brings us to Atomic operations um as I mentioned each time one of those concurrent objects is under heavy contention that's when we bust these things out and you know we want to ship our game on several platforms um so typically what we would do you know each platform has its own way of exposing Atomic operations and in any game game engine you're going to see an abstraction on top of that that we can just write to this abstract layer compile it for each platform much like C++ 11 atomics themselves and a game Atomic a game Atomic library is a low-level Library um typically consists of the following things you need some way to declare you know shared Atomic integers we tended to use VA volatile historically you know for for better for worse you need some way to do atomic loads in atomic stores well conveniently enough for us we happen to know that on the platforms we target a plane load in a plane store they're already Atomic uh you know they happen in one indivisible indivisible step for many data types integers pointers need some way to enforce memory ordering you know for that you usually see uh a macro or two two variations on the idea one being a lightweight fence the other being a full fence I'll I'll explain the difference in a sec and and then of course some way to some some portable set of read modify write operations we already saw an example of atomic increment I think this is what most people think of when they hear Atomic operations you know you read you modify you write the result back indivisibly so what's the difference between the lightweight fence and the false fence well what a lightweight fence does is it orders loads keeps loads ordered on their way in for memory and then it keeps stores ordered on their way out to memory and it actually does a little bit more than that but that doesn't matter um those are the main use things that make it useful a full fence does all of that but it also commits all previous stores to memory before even beginning the next load lightweight fence does the job of these things in C+ plus 11 Atomic thread fence it can do the job of either an acquire release or a chir release fence and a full fence translates to Atomic thread fence sequential consistent this is a defense you see a need for way more often in games at least from what I've seen so far I'm sorry the lightweight fence on the left that's the one comes up a lot more often in terms of needs as as I mentioned this API that we set up for ourselves this portable Atomic API it's a low-level API so each Macro each operation translates pretty conveniently to uh funny word rrap PA in there it's not my laptop um you know to Native instructions on each processor that we care about um a particular note that lightweight fence that comes up so often it can actually be implemented as a simple compiler barrier meaning no extra instructions are needed you just have to keep the neighboring instructions in the order they were written no compiler reordering well in fact all the fences are compiler barriers it's just that on some platforms you need an extra instruction but it's typically one instruction so it's a low-level Library I'm sorry I shouldn't I shouldn't say it's always one instruction because you know you've got these cach line Reserve store conditional Loops to do your read modify rights like you know that's the simplest way to do it on those platforms now programming with these atomics as you all know it's hard and we didn't really care to make our jobs harder you know we just wanted to implement these patterns which meant okay we got to coordinate the work with concurrent objects yeah okay well sometimes we observe a bottleneck and that's then it's time to get the Atomic operation tool box out so we're sort of forced into this problem from the top down before really any of us could claim to be experts and we probably still can't um so we had to learn and as we learned naturally we made plenty of mistakes along the way stubbed our toes from time to time I'll show you an example of one such mistake so this example is going to be a locked free Q Lock Free Q actually a Wade free que um it's the simplest I could make it uh only one thread can call Push at a time only one thread can call Pop at a time so single producer single consumer but it is allowed for both threads to call push and and pop concurrently we store the items in the queue using a simple static array there's a right position there's a read position um and the right position is shared between the two R so again we use volatile in this case and the Q is capped which means once that right position gets to the end that's it you can't you can't push any more elements into into this que obviously that's a big limitation but one nice thing about it is it simplifies the code a lot everything fits on one slide no memory management to worry about and I can just focus on the problem I want to show you all right so there on the left we've got the push implementation try push you know we check to see is there space Avail remaining in in our array of slots if there is okay go ahead and uh copy our item into one of those slots and then increment the right position and get out of there return uh for for the pop we check to see well is the read position less than the right position if so copy the next item out of the queue increment the read position and return not complicated so you write this code you you test it seems to work you check it in you go home uh but then the next day start getting crash reports on Xbox 360 uh you know weirdo issues glitches crashes fortunately we have you know a good team of testers they start sending us crash dumps it's like our safety net um maybe they'll narrow it down to an offending change list so this comes back to you and you say okay well gez you know the issues are happening on Xbox 360 Xbox 360 well that's a multi-core power PC and power PC is a weekly ordered architecture which means rights can be reordered on the way to memory and reads can be reordered on the way back from memory too well geez what can go wrong here one example is that this line where we store the item in one of the slots in the queue that might be delayed so that it doesn't happen until after the right position is incremented which means now you've incremented your right position but the data is not there you're exposing uninitialized memory well that's no good and even if that wasn't a problem you know theoretically you got a problem on the other side too this line where you read the item out of the queue could be reordered so it actually happens before the first load of the right position which is kind of confusing to think about the way I like to put it is that the second load it's seeing stale memory it's it's seeing a value of memory that that's not as up toate as the first load and these issues came up on on Xbox 360 but they very well could have happened on any other platform including x86 if the compiler had reordered the instructions you know we just got lucky that it didn't that's why this example is broken missing font anyway um so that's fixed with that uh lightweight fence that I explained keeps stores ordered on their way out and it ensures on the right that the second load gets a value that is at least as up to dat as the first that's it for that section um so the main takeaways I wanted to give you guys was that uh you know every game engine has some blend of those three threading patterns it's really more art than science um there's a need for a lot of custom concurrent objects and when those are in heavy contention that's when it's time for the atomic operations we learned very much by doing so I don't know if anyone has questions at this point actually made good progress if not I'll continue to part two which is all about C+ plus 11 Atomic Library well not really all about it yes if you want to use the mic technically I'm supposed to ask you right I've seen every other speaker doing it I have a question about the environment you're running in uh do you have like thread preemption and problems like that and if you have multiple thread pools with the different policy do they you know interact with each other in ways that you wouldn't expect yeah every platform that I've worked on at Ubisoft Montreal yes it is preemptive multi-threading so if another thread has higher priority wants to run in your core you can be kicked out of there and uh yeah naturally that is a problem especially if your task scheduler has set affinities and pinned each worker uh to a specific core and and actually on some consoles you didn't have a choice there was no way to let those threads migrate between cores so so yeah it was a problem and uh we had to get creative in solving it it was more art than science as I mentioned uh on one of the slides when you had the list of architectures you had x86 power PC and arm V7 you actually ship the same code base uh across the platforms I mean do you compile the same thing thing for power PC and for arm and just know expect it to work or do you have different code bases most of the code base is the same 90% of the code is is portable at least um 10% or less is probably specifically WR written for each platform uh but when it comes to implementing these concurrent objects that's the reason we have this abstraction layer so that we can write that concurrent object once and and yeah that code just gets compiled through the extra extraction layer onto each platform in which context do you find you need full sequential consistency so far off Montreal nobody even knows what it is yeah so it's it's mostly either acquire release or release consume yeah and not even release consume oh really cool thank you we're not there yet I suppose uh did you guys develop any static analysis tools or do you know of any that would detect those kind of like read write ordering issues like that would help you figure out where you need the fences and I mean in a in a compiler compiler could warnant on it but it would probably be in like specific to whatever native code was being generated as opposed to a front end warning but have you guys developed a tool or do you use any tool to help you detect those kinds of issues yeah so any any tools to help us catch problems like the one I described it would be cool if there were some static analys tools analysis tools that could do that um when we knew we were sort of venturing into you know Troublesome territory we'd probably write a special utility or small application to really stress tests that particular concurrent object like especially when writing a task schuer true you set up some some like artificial test to really stress that task schuer into so you you try to mistake proof that more with unit level testing or integration level kind of developer testing than static analysis I think you could say so okay yeah all right cool so let's go to part two this is going to be about as you know it's been on the slide for 5 minutes C++ 11 Atomic Library it's going to be you know a quick introduction so a lot of you here may already know this stuff um but I can tell you I'm pretty sure some people don't especially coming from games and uh yeah so C++ 11 the atomic Library it actually help us solve the same problem but it solves it in the other direction C++ 11's Atomic Library it's built on these portable principles um and those principles are exposed through the atomic Library API which you then use to implement concurrent objects for whatever purpose you have in mind and uh when I first heard of this Library I don't know three or four years ago it really interested me because it always seemed like ourway was a bit improvisational and I like the idea of having these formally spe specified principles you know brings a bit more discipline to the to the practice uh you know requirements and guarantees formally specified according to a specification and uh so I set out to make sense of it many ways I still am uh if anyone else is in the same position I find that the following points are probably the the most important points that you should know first uh in your journey to make sense of these things because with these things in mind I think it's going to Aid in the learning process would it for me I think rule number one the first rule to know about C++ 11 atomics is that it forbids data races which has to do with concurrent rights to the same variable multiple threads access the same variable concurrently and each and at least one thread modifies it all threads must useal plus 11 Atomic operations took me a while to really digest that one it's not the same thing as a race Condition it's its own specific rule kind of breaks down like this if you got a global variable plain integer X you got a bunch of threads reading from it that's just fine go right ahead nobody gets hurt but as soon as one of those threads the concurrent write and there are concurrent readers C++ says what are you doing you maniac this is a data race you got undefined Behavior you're on your own what C++ 11 wants you to do now is wrap that variable in an atomic type if you do that you're good to go read and write all you want concurrently of course you could you could just prevent the concurrency do some M Mutual exclusion between the threads um but when there is concurrent reads and wrs that's when you know you must use Atomic C++ 11 now why is this a rule one reason I'm aware of is that C++ 11 wants to support and C++ in general wants to support any kind of processor it possibly can including say say you got some archaic processor like in a dishwasher somewhere that can only write 16 bits of memory at a time uh but you're the variable you're working with is still 32bit obviously that's no good because now to do that store it's going to take two instructions it's no longer Atomic now we're talking about torn reads and torn rights C++ wants to support that machine so on that machine the compiler is going to compensate relying on the fact that you declared your variables in this case Atomic so it knows okay on this machine I got to implement some kind of lock around this variable now obviously since C++ 11 made that a rule well we got all this Legacy code that's breaking that rule Ru all the time of course you know and Rockets aren't launching out of our machine at as a result that's because like I said we we know that plane loads and stores to uh to an INT usually we declare it volatile they're already Atomic so the behavior might not be defined in terms of the standard but it's really implementation defined in our case like we know that about the pro the the platforms that we support and have to support but obviously that's not a portable assumption it's just why we get away with it next thing you should know about C++ 11 atomics is that it's actually two atomics libraries you might as well think about it that way two libraries kind of masquerading under the same API you've got sequentially consistent atomics which isn't really on everyone's radar in the game industry yet and you've got low-level atomics which kind of correspond more closely to the way we're used to working sequentially consistent atomics are really similar to the behavior you get when you define a variable volatile in Java in fact I think it's inspired by Java uh this is the style used in a lot of literature a lot of papers and books um lowlevel atomics on the other hand hand they're quite similar to volatile variables in C and C++ not strictly speaking identical there's some trivial differences technicalities between them but by and large we can kind of think of them behaving the same way so in games we're sort of used to the The Perils of of this low-level Atomic Library approach and it is perilous like uh when you use sequentially consistent as I think some of you here now they're easier to reason about but your code is potentially a little slower especially on today's processors low-level atomics much more difficult to use you can burn yourself like we showed at the end of the of part one but they translate more natively uh more directly to Native instructions on today's processors and thus are a bit more fast bit more scalable I'm calling them two libraries because like you could have almost have declared a separate template class you could have had Atomic standard atomic and standard low-level Atomic and you could actually just then delete either one of those template classes and you would still be left with a completely capable Atomic Library it's just two different programming models so good to be aware of because when you know which one you're working with you're going to make sense of the examples you see out there in the wild and what's actually the difference well sequentially consistent atomics is all about the ways that statements in your source code inter leave or can can interl with one another I'll illustrate this with an example so in this example we begin with two Atomic integers A and B both initially zero in thread one we set a to one then we load the value of B so store then load in thread two we set bet to one then load the value of a so store than load but in the opposite order now what are the possible ways our source code statements can inter leave well we could run both statements from thread one first if we do that we'll get an outcome where C equals z b equals 1 all right otherwise you know we could alternate statements between these two threads when that happens we might end up with one one we could run both statements from thread two first we do that we'll end up with one zero but there's no way to interl those statements and get the result z0 simply impossible because no matter how you inter leave them the first statement is always a storm and this is what sequential consistency promises you let's convert that same example to low-level atomics now to do that we got to use this slightly more verbose notation we got to say a. store memory order relaxed which is uh what we call an ordering constraint there's a few different possible enum values you could specify there relaxed is the lowest of the low-level ordering constraints so we're doing the same thing you know store followed by load store followed by load identical steps that were taken in the previous slide at this time because we're using lowlevel atomics the outcome of z0 is possible and this initially seems weird to a lot of people you can prevent it if if you want to by placing a full memory fence between the two statements in both threads full memory fence fence corresponds to Atomic thread fence memory order sequential consistent in the C++ 11 notation so that's to sort of illustrate the difference now let's take a look at the different ways of writing sequentially consistent atomics you know you can write it this way a. store I want to store one to the variable and I want it memory order sequentially consistent specify any other constraint there any other value for the second argument then you're no longer using sequential consistency you're using low-level atomics uh it's an optional argument so if you leave it out and you just say store one or you know load uh those are sequentially cons consistent operations too and in fact in C++ 11 atomics the assignment operator and the conversion operator are overloaded so if you just do loads and stores of plain values to and from an atomic variable those are going to be sequentially consistent Atomic operations let's take a look at a second example if you don't mind again two Atomic variables A and B integers both initially zero thread one we set a to one and then we store one in B so two stores in thread two we load B then we load a so now two loads but we're doing those loads in the opposite order so we can kind of reason that well if we got as far as b equals 1 a should equal one which means these is going to equal one let's look at the inter leavings you do both of the stores first you can end up with one one if you alternate instructions between the two threads can end up with the outcome 01 if you do both of the loads before any of the stores happen you're going to see the initial values 0 and then yeah in fact there is no possible interleaving which gives you one zero same example in low-level atomics using a. store memory order relaxed you know two stores two loads same thing we're doing in the previous slide just with low-level atomics now you guessed it the outcome 01 is possible and this example actually corresponds to that bug we saw at the end of section one doesn't it right like the one that had to do with stores becoming visible in an unexpected order on power PC this example illustrates that so just like we did in that case we can fix this example if we want to prevent that outcome using lightweight fences which uh which you know play the role of atomic thread fence memory order acquire or release in C++ 11 so yeah lowl atomics this programming model it's weird right um sequentially consistent it's kind of easier to reason about and uh yeah I'll go ahead and take your question go ahead hi Michael Wong IBM I was in fact one of the architects who put in the the the weak memory ordering all right um memory model in fact I remember having this exact discussion with Lawrence cwl Y at a barn Google arguing about whether we should have it and I was like it's got to go in it's got to go in okay this is the first time I've actually seen people actually show um make use I'm actually interested to see which which form does uh do the games people use do they use the weak one or do they use or is it just dependent on the platform we don't use C++ 11 Atomic Library operations yet at Ubisoft Montreal maybe other games companies do I'd be really interested to know so we're not using either of these but the game Library we do use it it's it's a low-level Library so in effect it's equivalent to the low level Atomic library that you helped put in MH obviously yeah easily yeah yeah so the comment the com there easy sell on that at that at that level you know because power PC was a platform that we had to support um we probably wouldn't have wanted sequentially consistent atomics even if they were available when we got busy with this stuff um thank you y you're welcome indic glad to hear it um now yeah because games this is the the the type of stuff we were dealing with when working with our game Atomic libraries our portable abstraction on top of what's available on each platform so we we were used to this weirdo stuff and one one useful way I found to to make sense of low-level atomics is simply imagine each thread has its own private copy of memory so you know thread one let's say it has its own copy of A and B thread two as well now that first example I showed you works like this like say you know we do a relaxed store in thread one to our own copy of a then we read from B we get zero thread two we store to B we read from a we get zero well in this way of thinking in this model obviously now this outcome of z0 is actually quite trivial so I find thinking about it this way each thread having its own copy of memory it gets pretty far I think it works because it kind of corresponds to the fact that uh you know of course each CPU core has its own cash and in general you can't really predict at any moment moment in time what's in the cash what's not in the cash so might as well just imagine heck the whole thing's in the cache and each core is working on its own copy and yeah as as the core makes changes to its copy to its local copy eventually those changes will propagate to the other cores next to cach coherency whatever stuff like that um but the timing is unpredictable I think that's kind of why the the analogy Works a little bit it's probably not a Perfect Analogy but uh it's helped me sort out some of the weird stuff so maybe it'll help someone else um so yeah I mean if if the low level Atomic behavior is really just exposing the behavior that's going on in our processors question might be well how how the heck are the sequentially consistent atomics able to work because that's not what the processors actually do they're not sequentially consistent uh if you're coming from a game background like I did it's actually at First the sequentially consistent atomics which are a little bit counterintuitive or at least unexpected well the answer is that when you do a sequentially consistent say load and store the compiler does all these gymnastics and converts that load in store to some set of instructions you know designed to enforce the guarantees of sequential consistency on each platform and as the gentleman commented here they're quite heavy to do a to do a a load a sequentially Atomic load on power PC five instructions some of which are pretty heavy um a particular note in the latest version of arm as many people know uh there's new instructions and there's new guarantees on existing qu uh instructions that are designed to translate more natively more directly uh to to sequentially consistent atomics so that's cool um so why does the low-level Library exist well we have Mr Wong to thank in part um well one reason besides the fact that they're actually faster on today's processors is that if we want to it actually gives us a way to migrate our game Atomic operations to C++ 11 Atomic operations you know so now instead of doing a instead of declaring a a variable volatile you know we would use Atomic uh we can't do technically we can't do plane loads and stores anymore so those become uh relaxed Atomic loads and stores fences have their equiv read modify wres have their equivalent rather than talk about it a lot uh I'll go ahead and show you let's go ahead and convert that lock free Q or weight free Q we saw at the uh end of the last section let's convert that to C+ plus 11 low-level atomics so first step is to get that volatile out of there now it's an atomic int right position the lightweight fence that was there in Tri push that becomes an atomic thread fence memory Order release the volatile store becomes a relaxed Atomic store to mcore right paw uh and then in tripop the volatile load of right Paws becomes a relaxed Atomic load and the second lightweight fence becomes Atomic thread fence memory order acquire this achieves the same thing uh interestingly this this line up here where we load the right PA that could even be non-atomic because we're guaranteed like we know at that moment that there's no other concurrent concurrent uh writers so that could be non-atomic because there would be no data race in that case but it's easier to just write this so we won't worry about it um and here's where those portable principles those guarantees that C++ 11 makes here's where they come in because now there's actually a a guarantee made in the standard that when this load uh of right position sees the value that was written by uh by that store when that happens it means that the fences synchronize with each other which means that every all the work that was done before the first fence the memory effects are guaranteed to be visible to everything that happens after the second fence and that's exactly what we want because we want that line that stores the item in the queue but we want that to be visible to the line that loads it and C++ guarantees by that section right there you can look it up if you're a lawyer uh that that's that's G to that's going to work on every you know every platform and every compiler that complies with the with the standard but yes go ahead well just because that was the direct translation from the original code right but you're exactly right we don't have to use Standalone fences anymore we can get rid of those and just specify specify the ordering constraints on the operations themselves this isn't exactly semantically equivalent to the first way we wrote it because those ordering constraints only apply to the operation on which they're specified but that's all we need in this case so it's just as good and again there's a there's a note there in the standard that says when this when the load right there sees the value written by the store then the store synchronizes with the load and therefore you know the item that we stored in that slot it's going to be there when the other thread loads it good to have so why not uh complete the circle go all the way and uh convert this example to sequentially consistent atomics we do that it looks it looks like that funny enough that looks identical we're actually typing the same code that we saw in the flaw implement ation in part one only this time it's not flood because we're not using a volatile int we're using we're using an atomic int for right position and because we're using this notation we're getting sequentially consistent behavior and guarantees and in sequential consistency well every Atomic store has release semantics and every Atomic load has acquire semantics which is good because it means that when the load reads from the store those synchronize with each other too and that's why this example is guaranteed to work using sequentially consistent atomics we don't even have to convert anything else to atomics just that one shared variable mcore right position everything else doesn't need to be Atomic because there's no data race never read and write it concurrently so I actually I actually uh compiled that code yesterday and ran it on my MacBook and my phone and uh compiled these benchmarks uh using a recent version of xcode um in release and I checked the assembly it looks pretty much as efficient as you can expect so after running you know push and pullup operations on on a queue with 10 million slots these were the average timings I got so you see the penalty being paid there for sequentially consistent atomics it's it's a bit more dramatic than I thought on Intel but keep in mind like this is a micro Benchmark you can't possibly get more contention than this um so that's sort of illustrates you know the price you pay uh for one approach or the other in terms of difficulty or efficiency so what were the key takeaways takeaways I wanted to give you guys for this section first thing to know C+ 11 forbids data races should be clear what that means it's effectively two Atomic libraries you might as well look at it that way and if you want to pass non-atomic information between threads make sure you've got this synchronizes with relationship somewhere very fundamental very important so I just want to acknowledge these names these are people I've worked with on the left that have implemented many of the stuff I showed you in part one list on the right is you know people I encountered work they've done uh and posted online either either articles or a talk or email exchanges so thanks to those guys any errors I made are entirely my own and if you want to get in touch discuss this stuff further you can find me on Twitter at pressing you can email me directly I don't mind Jeff pressing. comom uh and come check out my my blog pressing on programming so uh if there's any other questions we got a bit of time left take them now uh so your example that you just spent a lot of time on with the uh Q you had an implicit assumption that push can only be called on one thread but then you went in your timing and you actually broke that by doing concurrent pushes I saw um in your benchmarks I'm wondering um how do you enforce these implicit assumptions or do you at all well I was careful not to break that rule when when this slide says concurrent push and concurrent pop that means I I ran the the writer thread and the reader thread concurrently uh with each other but there wasn't more than one of either of them okay I understand um in general how do you prevent your co-workers from making small mistakes like that because it's easy to do you know call Push from two threads talk to them ask them not to when they break the rule and errors occur uh you know you got a test team that's going to help you find it's going to be your safety net uh so this slide uh why exactly do we have this huge performance hit when you use the sequentially consistent version of atomics yeah actually I think this example is benefiting a lot from the fact that the queue I showed you is single producer and single consumer which means that on Intel when we use the low-level Library it actually compiles to code that has uh no fence instructions and not even any read modify write operations and that's very rare uh you don't typically see that in lock free code so this is a very optimal case which kind of paints low-level atomics I don't think you can paint them in a better light than that but as soon as you have concurrent uh readers let's say now you got to use read modify write operations it's not going to be as cheap anymore okay so this is basically a contrive example that shows that it was uh needed to introduce these things to the standard sure basically that Mr W isn't basically Wrong by pushing this into the stand yeah and I think it also goes to show that if you can maybe it's a good idea to avoid concurrent uh like multiple presume producers and consumers at least At A fine grain level it kind of reflects that maybe what you want to do is do as much work as you can locally batch things up in your thread before interacting with other threads kind of hint that too I just wanted to know like when you um you try to avoid uh turn rights via using the atomic read and WR operations when actually it worked without Atomic reading in your volatile int example right if actually the compiler understands that the the sides of the of the value type will not have a turn right and it op optimizes it out like does that happen maybe Michael can help us clarify I was wondering if it's if you are required to call an atomic read operation but it since we can know at compile time that the size of the type will not incor in turnor right will it get optimized out that's my question um yes um will it get optimized out maybe it won't get optimized out but it will get optimized uh and a good implementation of C++ 11 atomics will do that we're just very recently getting those really refined implementations uh but there are you can find compilers which will generate very optimal code for Atomic ins let's say uh on Intel on arm uh armv7 and on power PC power PC I found when it was GCC the latest version um yeah if you do use an atomic int and you do an assignment or you do a fetch ad it'll use that single one instruction and not take a lock or you know call a function or do whatever else because it recognizes those are special cases okay thank you which if it didn't do that I wouldn't want to use them but supports getting there uh first of all I've been following your blogs and thank you so much for the detail information there I learned a lot um so um we exclusively work on x86 and we don't want to bring along lowlevel atomics when not needed um they are very portable they're great for you know lots of different platforms like you guys work on but if we just work on x86 is there a set of rules a subset of these rules that we should be following I try to read Intel manuals and try to put their guarantees together with the library guarantees and you know the Styles but somehow never got a subset of rules you know which I should the ones which I should just be using for x86 I don't want to bring along you know uh constructs from atomics which aren't really needed on x86 okay you see what I mean so did you guys have that kind of a conflict when you worked on different platforms and well when we work on different platforms at Ubisoft it's always low-level atomics and those are the rules thus far uh the only advice I can think of is start by using sequentially consistent atomics especially if you're doing funky stuff like herb Suter stuff talk that he showed two days ago was a very elaborate uh example actually dealing with memory management of these nodes and the que and stuff that'd be hard to write with relaxed atomics so start with sequential but if you have a a concurrent object that's really under very very very high contention that's when it's time to use low-l atomics okay can't really I don't know what else to suggest than that sure because I just came out of like Alexander's cu um presentation he talked about you know read always being you know Atomic on x86 um and then I read about standard toic and you know I'm always confused which of these really apply to me because I work just on x8x you know like but I see if you work just on x86 exactly you don't need to use C++ 11 at all that's a great advice too actually because because you know you have this imp impementation specific implementation defined behavior and you don't need that you know portable guarantee uh so you're not going to run it on on a dishwasher or something so maybe the last two questions so how do you feel about memory order consume and were you ever sad about not being able to create dependencies between different reads I thought I thought it was really really cool the first time I saw it to to not have that fence instruction on power PC and on arm uh on the reader side and because the reader side is the side you want to optimize for so to not have that there that's really nice um yeah today you can't use memory order consume yes if you use if you use memory order consume I think every compiler implementation I'm aware of treats it as if you had written uh AC choire this is actually the last blog post I wrote uh I was really interested in the idea and I took a lot of time to make sense of it I don't know if compilers ever will implement it efficiency efficiently it seems like it'll be hard to do um I also wonder for the kind of stuff we do in games would it really matter that much well now that you're on both both of your target platforms are TSO or the x86 plat I'm sorry x64 platforms it doesn't really matter so much anymore anyhow um yeah because it doesn't change the it doesn't change the comp code in that case anyway the point I was going to make there is that you know there are cases where we use uh a lightweight reader wrer lock and uh memory order consume is a nice way to eliminate some of the overhead from that uh but when I benchmarked it like there was some operation we were doing in a game we were doing like 10 10,000 times a frame and it just wouldn't have been that big a win because the price we were paying for that lock was uh uh yeah I forget but it was in the microsc neighborhood somewhere and not worth losing losing sleep about yes I just want to comment your original advice about use cs plus 11 toomics and use the default of memory order sequential consistency unless you're doing something under very high contention that still applies even if you target a single platform like do not try to roll it yourself let the library implementer handle that stuff it's really really hard like it's super hard yeah juggling razor blades so yes memory order consume we just had a meeting uhhuh we want to fix it we don't know how yet we think that we're going to change the current one to adapt whatever fixes we're going to do because no one implements it so we're not breaking anybody okay is it still useful in a general context yes um there are still some tech there techniques out there we looked at RCU yesterday that is probably um so some of these can still make use of some make use of memory order consume um it's not just platform dependent cool really interested let let me give a little warning there once you start going into the memory order consume that is the most difficult parallel task you can take on the software engineering effort per line of code is huge right so just keep that in mind yeah memory order consume is probably the most Niche subject in an already Niche subject of lowlevel atomic operations which itself is a niche subject so I agree with this gentleman right here all right thanks everyone for coming out