Lock-Free Programming in Modern C++ | ACCU 2017

[00:00:09]hello everyone thanks for coming my name is Kim or I'm C++ developer and I'm specializing in audio and music technology and I work for a company called Rolly base in London and we do a lot of different music technologies and one of the things we do is juice which is the logo in my t-shirt here which is a cross-platform C++ framework which you can use to build any kinds of apps but there it has focused on audio app so this is sort of my background and first of all disclaimer as you can probably hear English is not my native language and also I'm the jet lag so I apologize for that so I hope you can still understand me and another disclaimer this is an introduction talk so I'm going to be talking about lock reprogramming but a deeper stuff and this is a basic introduction talk so if you are already an experienced developer and you've already done some blocks with programming before you're probably not going to hear anything new apart from maybe a few bits about C++ 17 so sorry for that can I just get a show of hands who has done some lucky programming before okay so well maybe it's going to be a few new bits but mostly it's going to be really a basic introduction talk so that's what it is about then also I'm not going to mention any platform specific things so this is really about standard C++ so I'm not going to go into any details about specific hardware architectures or anything like that so all the code I'm going to be showing it's going to work on every platform as long as you have a compliant compiler so here's the overview what we're going to do I'm going to start with a little bit of motivation why you would even do lucky programming in the first place define a few useful things like what does it is mean log freeze a few useful definitions that I'm going to look at the interface of atomic because this is really the most important tool that people stuff gives you for lucky programming so we're going to go through the whole interface and make sure that we're all on the same level of how it works then I'm going to talk a little bit about how we can use to exchange values between different thread and then we're going to get to the really fun part of the talk which is implementing a Locksley queue what I'm going to do is I'm going to implement with you I'm going to implement the whole thing from scratch so this is really the fun bit and I hope you're going to stay awake until then yes so let's dive in so what's the fundamental problem that we're trying to solve here it's really we have multiple threads exchanging data as they keep running so I'm not going to talk about things like futures and promises which is basically if your thread finish to get that back into another thread it's all about tricks that keep running and have to exchange data while they do so and if you have multi multiple threads as you will know you have to synchronize the data access you know as long as threads are reading data is usually the problem that as soon as one opposite is writing you can have raised conditions so you need to synchronize that so I'm sure everyone's familiar with the concept of race condition but we're going to have like the exact definition of it in C++ so yeah so if you want to do this then the main tool really the main approach to fix race conditions are things like locks critical sections semaphores and condition variables and of course some higher-level facilities that are built on top of those and modern c++ really has a lot of those facilities so in typical 2011 we have the mutex you have said recursive mutex you have time mutex we have a lock guard which is useful to make it a bit safer you have a unique lock which is a bit more flexible and you have the good condition variable which is another way of exchanging data between threads and then this keep getting added to it so it keeps getting better since we possess 14 we have the shared lock and then c++ 17 as Nico was describing and his wonderful workshop yesterday we're going to get the shared mutex and we're going to get scope lock which is basically the very attic version of the guard so that's great and I think most programmers really should focus on mastering those things however if you want to do lottery programming they're going to take a different approach and I think the simplest definition of local programming is really don't you don't use any of those stuff instead any of those things and certainly going to achieve our synchronization in a different way now the question is why you would even why you would even bother doing lock-free programming because most people agree that it's it's very hard to do hopefully I can convince you that it's actually not that hard most of the time it's hard to write it's hard to maintain and often the overall performance that you get is actually not better sometimes it is sometimes it's not three depends on your use case so why would you even bother doing that and the answer is that if you if you have mutexes locks basically you have something like this yeah so actually if you're in England so I should have flipped the image around sorry we're not doing that but yeah we take a crazy something like this you have like different threads so it's like an intersection and then mutex it's like a traffic light which says you know if it's green you're good to go if it's red you have to wait for the other one and at some point it's going to turn green and then you can continue and you know a lot of the time this is good sometimes you're waiting on a red light even if there's actually no other cars on D on the other street so that could be a performance problem but really the main reason why you want to do lots of programming is if you can't afford to wait on a traffic red traffic light like for example the ambulance car don't hear the ambulance car really has to get as fast as possible to its destination because human lives that depend on it right so it just has it can't afford to just stop in the red traffic light and wait until all the other cars are done and the traffic light turns green so you can't really afford that and where does it happen in code typically whenever you have something like a real-time environment which basically means one or more of your threads are on the strict time constraints they're doing some work which has to be finished as fast as possible or it has to be finished in a certain amount of time and blocking and waiting for mutex is not possible because you simply don't have time for it so it means in a third like this you can't use any locks you can't do things like allocating dedicated memory because there's also a blocking operation and you can't really call into any third party code either because you know you don't know you don't know if it's locked free you don't know how long it's going to take if you have a third party API people don't document things like well this function is going teach to finish within X milliseconds or whatever actually C++ does it doesn't even have a way to express that some languages do but C++ is not one of them and why can't you do any of those things well because if you're blocking and waiting on something then there's no guarantee how long you will be waiting because maybe you don't know what what code waiting for also if you do that if you're waiting for the threads you're at the mercy of the stretch scheduler if your operating system and you don't want to rely on that maybe and this also brings with it some other problems like priority inversion which basically means if you have a high priority thread and it's waiting on a mutex our that is owned by another thread which is low priority then you know that other thread you waiting for has low priority so the operating system can decide hey let's just you know instead of executing that threat let's execute some third thread which you have nothing to do with and then you're going to be waiting for that so your high priority thread is going to turn into a low priority thread effectively and then you're going to suffer from a lot of problems and you're not going to finish your work and time and that could result into a consistent failure so this is the kind of cases that we're talking about and typically this happens so these we do some environments they come up in all kinds of different fields they come up in all your processing which I only put first because this is my field but you also have problems like this and finance in embedded systems and lots of science and engineering problems so let me just give you the example for example in all your processing what we have is you have a sound card and the sound card has a little crystal in it which is like a timer and it's going to call you with a callback on a higher priority system thread regularly so maybe every millisecond or so we're going to get a call back from the sound card and you're going to get like a buffer of floats and the soft that's going to say fill that buffer of it with floats and then it's going to send those floats to to the speaker and that cool bag is going to get called armed regularly and if you're not finished with filling the bottle with numbers in that millisecond or like by the time the next callback hits you then the data is going to be sent to the speakers it's going to be garbage data and then what you're going to hear is you're going to get an audible like audio glitch so you're going to get something like in your speakers right and this is bad for example if you is this guy and you're playing something in front of a thousand people and you have some audio code going on on your laptop and then you're going to get you're going to get into the situation then first of all you can blow the speakers and second of all everyone's going to turn death so that's something that you never want to happen if you're interested in audio processing I gave another tour a couple years ago at CBP Korn about specifically that it's called C++ in the audio industry so if you're interested check that out but this is not an audio talk so of course the same situation or similar situations also occur in other industries for example in finance and the most extreme example of that is I guess high-frequency trading where typically you have some kind of hot path where you need to take a decision very quickly like what are you going to do with the given trade for example and if you in that thread you have to make an immediate decision and every microsecond counts and if you late for a few microseconds it's going to cost you a lot of money so you can't really afford to wait on a mutex and if in that hot pocket I'm going to need some data that's shared with another thread well at some point you're probably going to look into local programming at some point another area of science and engineering for example if you have those robot workers here and imagine your C++ code controls you know the motors in those legs and then they're going to need to know what to do with the very high frequency they need to get some updates on how to move around and you know if the motor in the left leg is not going to get an update what to do for too long because you're waiting on the mutex then no this is going to happen and I'm pretty sure the person sitting in the cockpit is not gonna appreciate it very much so really what you want to be doing is instead of doing this you're going to have to arrange a traffic and something like that where instead of traffic lights you're going to have ways of you know the traffic lane sort of like merging into one another so that all the cars can keep going and none of the cars have to slow down by the way it shamelessly stole this picture from a talk by herb Sutter thanks herb it's a great talk where he talks about his talk is called juggling razor blades it's a great talk I really recommend you watch it he has some very deep explanations and he implements in that talk alakh Rafi a linked list which is I'm not I'm not going to do here but yeah watch this talk it's a great talk coming back to this I think that's a great analogy because this setup can guarantee that you can always keep moving well then of course you have different ways of like how do you merge traffic into one another and what does it actually mean the cars always keep moving so here we can make an important distinction there's actually two different kinds of you know laksa guarantees one of them is block 3 which means at least one threat would always make progress which you can imagine like if you have a traffic plane and traffic is merging in there then either this car it's going to wait a little bit until the next slot is free or this class that's going to go and then you know there's going to be another one but you always have to go into use at least one trade will always make progress and then the stronger version of that is the weight free which means that every thread at every point of time will keep making progress and no thread is ever going to wait for any other thread and the good thing regardless of whether you have lost your way to see the other good thing about this that you can never deadlock so actually even if you're not in a real time environment if you have one of those two guarantees it can be good way to reduce contention to get better concurrency and scalability even a non real real-time systems but the fact the use case I think you should really bench mark the code before you put lock-free algorithms on production code because it might turn out it may turn out that it actually is actually not having better performance okay so before C++ 11 C both didn't actually have any notion of threads right but now we do see tickets at 11 we have a memory model in a standard and I'm just going to display quote from the standard this quote mentions bit fields those are those weird things where you say like int X colon 5 or whatever anyone here using the fields okay two people so I think it's a bit of an obscure feature that most people don't really need so we're going to just grade that out so the standard says a memory location is an object of scalar type which by the way means one of the built-in numeric types or a pointer or an enum that's a memory location and two or more threads of execution can update and access separate memory locations without interfering with each other so that's really like the main the main sentence from from the standard on the memory model and what's important about this is what happens if you inverse the statement if two or more threads can update and access the same memory location that's called the data race and then you get undefined behavior and that means if you're modifying a value from 1 to it and the other thread can see value before the right after the right some garbage value which represent something in between or actually your code can do something completely different and your computer can blow up and catch fire and that's going to be consistent with the standard and the reason the reason is undefined behavior is because optimizers can rearrange your code right it can reorder instructions they can optimize variables out of existence that can optimize memory access the way they can reuse one memory location for two different variables and optimizers can do all kinds of crazy stuff and the way they do it is the optimizer is always going to assume while then doing these optimizations is that you don't have a data race in your code and if you do then no one knows what the optimizer is going to come up with a gobble your code and you can get really weird behavior by the way declaring something is volatile is not a way to fix this it's something completely different people have done that in the past maybe people still doing that I don't know but volatile has nothing to do with this is a very different thing and it's still going to be undefined behavior so one way to fix this are so there's actually just two ways to fix this you can have either lock so we can have Atomics and now we can count with another definition of lock reprogramming if you have let's say you have a chunk of code doesn't matter what that is and there's a race condition in there you know normally what you can do is you can you can put a lock there and then it's safe now probably all of you know that now here's the lock is protecting the whole function and I guess all of you know is that this is not really good programming practice and what you really want to do is you want to put the lock just around the piece of code that actually accesses the data yet you want to make the scope of that lock as small as possible because then you get better concurrency and better performance and now lock your programming or like one way of looking at this is you would use the scope of that lock even further until it protects just a single instruction and when you get to that point you just replace the lock and that's one thing an instruction with an atomic instruction which means and you can get rid of the lock and atomic instructions means that it's going to be memory access that's supported on the hardware level so your processor has special instructions that can do that you can do to read or write on memory with a single instruction and that instruction is going to be raised free even without a lock so that's the hardware feature and every other thread is going to see either the value before the right or the value after the right but nothing in between and it's defined behavior even without a lock and doing this kind of stuff needs to be really hard because you know you have Intel arm power if you see all these different platforms and they all have different instructions with different rules and actually those different processes also have different memory models so you know there's cases where an arm you would need to insert a memory sense and an Intel you don't have to do that and things like that and really scary stuff so in order to do that you need to be basically an expert for your hardware architecture if you want to know more there's another 12 perhaps latter which is called atomic weapons I think that's a great talk when he goes like it's a 3-hour talk where he goes through like all these hardware differences from different hardware so if you're interested in that watch this talk but of course what we do is library developers is you want to hide all that complexity between behind a cross-platform interface so you know people started writing some records for this stuff so huge has Hugh atomic in then one of my previous jobs that was working for another music tech company called Native Instruments in Berlin and I was maintaining their application framework and they also had a wrapper for it as I'm sure dozens of other companies had and actually induce you also have rapper deuce atomic but since C++ 11 this is all obsolete because now we have a wrapper in the standard which goes to the atomic and still atomic is the type in the standards that is inherently raised free which means that you can read and write from an atomic variable without me lost and it's defiant behavior and guaranteed rates to be and actually it's the only type and super stuff that has this property and I'm going to in the next minutes I'm going to go through the whole interface of this class because it's so important for the rest of the talk just to make sure that we recover everything we need so if you only know if you already know sted atomic very well you can have a little break so this is just a screenshot from cpp reference so what we have is we have a generic template which is the first one which is going to compile for any class T which is to really copyable and now we have a specialization for integrals and for bulls and then we have another specialization for pointers note that there was no specialization for float and double I'm going to come back to that a bit later so first of all of course we have a default constructor for that it's a bit nasty because it's actually not going to initialize so atomic is like an atomic wrapper around the type T so for example in and this is not going to initialize the value so it's going to leave it uninitialized yeah you have to know that so maybe it's better to use to use this other constructor to just initialize the value immediately and there's no other constructor so atomic is not copyable not moveable and then basically it has these five member functions so you have store which means you can write a value into into the atomic you have load which means you can read it then there's exchange which basically means you're going to let you swap the current value with a new value so it's going to set it to the new value it's going to return the old value so it's like an atomic swap and then the last one is compare exchange which basically means you're going to compare it so you have an expected value and if the current value is equal to the expected value you're going to set it to the desired value and then it's going to return true and if it's not the expected value it's going to do nothing and it's going to return false and it comes in two flavors are strong and weak and basically the difference between them is that if the current value is the expected value then strong is guaranteed to succeed whereas weak can spurious lis fail and basically the coding rule here is that whenever you just want to do it once you should use a strong one and whenever you have to do it in the loop anyway so you're going to like keep checking repeatedly anyway then you should use weak because then it gives you better performance on some architectures one more thing about this so store has a shorthand notation where you can just use an overloaded assignment operator and equally loads there's a shorthand notation for that of wealth where it has an overloaded operator T but I actually actually discourage using those shorthand because I really like readable clear code that expresses the intent of the author to the reader and so I prefer to always use store and loads instead of the shorthand because then it makes it obvious that you're dealing with an atomic value here so I'm actually discouraging using the shorthand is just for clarity but they're doing the same thing so one more thing about the compare exchange ones so basically I think those are really the most important ones because those allow you to the compare exchange allows you to write all these locks the other ones and and the reason why they're so powerful is that in Locksley code a lot of the time you run into this problem where for example here it's like a piece of some lock the algorithm where maybe you have an atomic pointer like a reposition that points somewhere you want to check if you're allowed to read and if so you want to increment that thing and the problem with this code is this gap right so you check am I allowed to to do something to that thing and then you do it but in this like gap in between everything can happen you don't know what's going to happen there and you can't put a lock around it right so by the time you get to the second line maybe the condition would would have changed and you don't know and you can't be thankful to look around it so compare exchange gives you a way to solve this and then you would write the code like this so basically you you load the current position and then you check if the current positions of a is okay and then if not you just return and if it is okay then you calculate the new value and then you say okay if it's still okay if I'm still the threat that gets to modify this thing then do the compare exchange right so if it's still the old value which basically means no other thread has changed the value in the meantime I am the threat who's going to change this value then do the compare exchange if it's expected change it to the new one and and this is this is really a very important pattern that you're going to see over and over again and then we have an atomic we have the template specializations for integers and pointers and basically what they give you is those additional functions where you can the increment and decrement the value that's example use if you look into the implementation of the share pointer it has a reference count so that's going to be an atomic reference count and it's going to use the atomic increment to increment that reference count in a nice red tape way and then it has these plus equals minus equals operators which are all atomic and then it has these fetch add fetch subtract month where you can add and subtract and and on or the current value and the cool thing about them is it's going to also return the previous value so again it's useful if you're if you're using that and Mochrie algo so that's only for integer and pointer arm specializations so it already said there's no spacers Asians for floats and doubles actually are at the last standard committee meeting in Kona we discussed the proposal in the library evolution group like this one po2 0 where they're proposing an atomic float crystallization it didn't get into C++ 17 but I think there's a good chance it's going to be in C++ 20 so I hope it's going to add kind of a reasonable clean way of dealing with this but as long as it's not understand that we don't have that so basically if you're dealing with atomic floats you don't have operators plus minus plus equals minus equals and so on you do have store in load which you can use which is fine and you do also have compare exchange but it's not really meaningful for floats and I would discourage using compare exchange for float and the reason is first of all floating-point comparison that you all know it's not really meaningful anyway but actually compare exchange is even worse because the definition of the atomic and the standard says that the comparison is always going to be bitwise and it's also what's happening in the hardware it's always going to be a bit weird comparison because that's how these atomic compare exchange of operations work and this means if you have a float yes situations like if you look at the bit representation of a float you have for example plus and minus zero right which is it's the same value if you compare plus or minus zero with normal flows it's going to compare equal but they have different representations like if you multiply minus one by zero you're going to get the minus zero one and if you do a computer exchange plus zero minus zero are going to compare as not equal so it's a three nasty and I don't really have a use case for compare exchange for float but as long as you just use I'm storing load you're fine and basically we're going to be going to do that later as well yes there's a question I'm sure they repeat questions for the recording so the question was if you only use compare exchange for floats in this pattern where you only read the store like the old value and then you're going to check if it changed if is that fine I guess it's fine but I would probably not do it just because if you see a compare exchange for floats then maybe people can start using it for different things for other things and then it's going to blow up so I guess it would be fine and that specific use case but I think it's safer to say just don't use it because you might then change your code and then do something else and then it's going to break it's just dangerous so the question was why we have complexions weak and strong and why don't we let the optimizer decide which one to pick I don't really have a good answer I think like a lot of frameworks they don't actually have this distinction the standard has so it's going to be different instructions on some hardware I think on Intel is probably going to be the same instruction anyway yeah that's like hardware details I'm not sure um I guess it's to give you a little bit of flexibility where you can tell the compiler basically now I really don't care if it fails in this particular algorithm so it can generate faster code on some architectures secondly it's like it may be like a hint to the optimizer learn away well it does not just do the same thing because weak is allowed to spurious ly fail even if the value is the expected one so they actually do have different behavior in practice is going to be the same thing and most platforms I'm aware of strong yes exactly so strong is always going to do what it says it has to do and weak does not have that guarantee but it might be faster on some platforms and I'm pretty sure Intel is not one of those platforms yeah yeah exactly so that's exactly how we use it so whenever you don't care if it fails this one time around which typically happens if you call this thing in a loop then you expect it to fail several times because of the way your algorithm is designed you expects to face we call it in the loop until it doesn't fail anymore and then you continue and this situation is weak because you expect it to fail so you say okay now let's be allow it to fail even seriously and then you can get a little bit out of performance out of it so it depends on your algorithm like if your algorithm says it's okay to fail because we're going to repeatedly check it anyway then use the weak one and if you really want to know it now is it like expected or not and you're doing it only once then you should and you just make take like a different code path depending on that one call then you use the strong one does that does it answer the question okay one more thing what Atomics is there's actually people confuse the term atomic and lock free and those actually don't mean the same thing so what atomic means is it's an operation that thread-safe where every other threat is going to see the result either before it or after it there's nothing it's never going to see like anything in between and it's thread safe you don't have to put a lock around it that's what atomic means it does not mean that the operation itself is lock free so lock 3 means that it's atomic and also inside the operation it's not going to block so it's a stronger it's a stronger term and actually is this important because remember that you can initialize split atomic with any type that is trivially copyable but your hardware might not support atomic lock the operations for that type so for example typically on yeah I actually have a slide about this so atomic might not be lock free and that we depends on whether your hardware architecture supports lock the operations for that type so most platforms like you know laptops and phones they support atomic clock preparations for eight-byte types like an inter a pointer or size key some of them support operations for 16 bytes as well some don't I'm not aware of any architecture that supports atomic clock preparations for larger types so if we depends on on the type of lookup a parameter of T and this is why it said atomic has a member function to check for that so it's called is lock free and if you just call that thing for different different parameter different template parameters then you're going to see that on typical you know Intel platform or like an arm platform like a phone it's going to be lovely for bool in double dicey pointer because your hardware supports atomic lock preparations for all of those types if you have something like stood complex double it depends for example my MacBook on my macbook this is going to be true so apparently it supports 16 byte compare exchange on a PC that I tested it said false so we depends and if you have anything bigger than that then pretty much all the time it's not going to be locked free and what's atomic is going to do is it's going to if you instantiate the template with with some types that's not supported it's going to silently insert locks inside the store and load and all these other member function and you're not going to even know it if you don't check so it's going to slightly support locks and your your Atomics actually going to not be lock free and you won't be aware of it if you don't know and if you don't check and the really annoying thing about this is that this member function is per instance and this has a really a few reason I think on some platforms on some obscure hardware there's like certain pieces in memory where these atomic things go and if you run out of that space then all other instances are going to be put elsewhere and then it's not going to be locked free I don't know in what platform that's the case certainly not on any platform I'm familiar with but it's a possibility therefore in the standards of this thing is instance which is really annoying three tickets are 17 it got much better now because finally we have this one which is is always lock free and that's going to tell you whether you know that's going to be locked before every instance and this function is not only static but it also comes to expert so I'm really happy we got that into the super stuff 17 standard very very last bit about atomic is that there is this memory order thing which is basically another parameter at the end of all these operations like straw and load you have like an extra parameter which is the memory order that's the other part of the C++ memory model that didn't show well if you just omit that which is what I'm going to do for the rest of the talk it's going to use this one by default which is sequentially consistent memory order which basically means if you execute different atomic instructions in a certain order then all the yellow threads are going to see them to be executed in that order which is basically what everyone would expect anyway right the reason they exist is that if you you can sort of relax those guarantees if you use any of the other memory orders and it's going to achieve two things on some platforms you can squeeze a little bit more performance or if you lock the algorithms and the other thing is that it's going to become extremely hard to reason about your code I think 99% of the time people don't need to worry about any of this stuff but if you do want to know more about this I think just after this talk is going to be a talk by going to a buffer who's going to talk about atomic memory orders so if you know if you want to know I'm really looking forward to this talk and if you wanna know more about memory order to stay in the room but you're not going to worry about this here right let's let's unlock the code very simple example we have a float which is some kind of parameter and you want to exchange that parameter between two different threads and the simple example I'm going to give an example from audio processing but you can easily come up with an equivalent example in any other kind of industry so what we have here is we have a GUI thread on the right which is controlling your user interface and you have some kind of knob there and which you can control the volume of the sound and that's just going to be like a floating-point number and then you have another thread which is a real-time thread where it's going to use that number in a computation that actually computes the sound so here's the code you know don't worry too much about it the point is that you have to float level parameter and then you have one thread which so whenever the user turns out not they're going to get a callback here you're going to change the value and then and the other thread which is the view template you using that value in this loop to computer your audio signal and if you write it like this of course you have a data rate here and the easiest way to fix this is to make this atomic and so basically you store the value in one thread and you load it in another thread and you typically have these pairs of like store and one thread and load in another thread and there's a very common pattern if you if you have this in your code you probably got it right and we will see this again later when we implement the lock free queue however that's one thing here if you just replace the the float with the atomic float that's one thing that you need to be careful with so with this code this load is going to be probably very inefficient and perhaps you even get a different result and the reason for that is remember an optimizer always assumes that you don't have a data rate in your code so if you go back to the to the racy version so you have this level down here in the real time thread and the the optimizer views that you don't have a data race so the optimizer can assume that this level is not going to change while you're in that loop so what it's going to do is it's going to probably optimize it in such a way that it's going to load the value of the level one into a register and then it's going to use that value inside the loop so you're going to have only one memory access and then the value is going to be in a register it's not going to change and the optimizer is allowed to do that because the optimizer always assumes you don't have any data races now if you if you if you do it with Atomics then the situation changes because every load is going to be actually like a hardware load from that memory location so first of all you're going to get 100 loads instead of one load which is going to be much slower especially since er their atomic loads and then also actually the value can change in between while you're in the loop so you're probably going to get a different result so you have to do this optimization manually where you load the atomic value once you put it in a local variable then you use that inside the loop so these are just the kind of things that you really need to be careful with but as soon as long as you're dealing with explodes or in this three straightforward but what happens if you want to exchange an object between threads then it gets a little bit more nasty because of course you can if you have like any kind of struct or class widget and if it happens to be true really copyable then you can instantiate it like this but that's not going to be lock free because atomic is going to insert locks inside so the thing that you can do is you can instead have an atomic pointer to that object now we have a rule pointer that it should already make you a bit suspicious so let's see where this goes so first of all of course you have to initialize it and now let's say we have one thread and we want to modify that object but if you just modify the object and there's another very easing it you immediately going to have a race condition and you can't put blocks around it so what you have to do if you want to modify the widget if you have to allocate a new object on the heap and then you have to do all the setup for that object and then once you're done then you have to Tom eclis swap the pointer to the old object with the pointer to the new object and that's going to publish the change to the other thread and then what exchange is going to do is exchange is going to return the point is the old object and then you have to sum dispose of it and then the other thread if you want to use that object you need to get appointed to it but the problem is if you just get the point and start using it again you have a race condition so what you need to do is you need to again swap the pointers and you can you can for example swap a null pointer in there and that's going to indicate to the other thread that okay this is this object like another site is using that object so there's no object in the atomic at the moment and then you can do your work with current widget and then you can again has to have to dispose of it so there are several problems with that one problem is that obviously you have to add some kind of lifetime management to this for your object so inside the circle so you can for example use a shared pointers in 2011 we have special atomic load and some extra functions for um take a pointer to a shape shared pointer so that's that's an interface you can use it's a bit ugly in the concurrency TS we actually have a class called split atomic shared for inter we're just going to make it nicer so I really hope that this one's going to get into C Buster's 20 and the other problem is that if one of those threads is the real time thread you don't really want to deal with allocating and deallocating memory anyway because that's going to be a blocking operation so there's all kinds of techniques for that for example instead of D allocating an object you can throw the pointer in some kind of garbage collect to a bucket and then that's going to be allocated in another thread there's all kinds of techniques to sort of manage the lifetime and I'm not going to talk about this here I have to defer you to this other talk I gave a couple years ago because that's where I'm discussing all these techniques in detail and I'm actually showing some code to deal with that stuff and I don't want to do this here because I think the problem of lifetime management is very important but we an independent problem and what I'm going to I want to talk here about now is the actual like lock free algorithms yes yes yes what yeah as long as you're just reading you're fine but if you can't write to it so you have to write into another object and anatomically swap the pointers if no thread is writing to the object then you're fine but that's like trivial anyway what you want to do is you want to modify the object and you can't do that you have to set up a new object and then sort the pointers but the whole point of this is actually that this whole idea is not actually very as much as useful as you might think because you can't just share an object between between threads in a lock free way if one of them is right into it because you have to sort of like swap it in and out all the time so it'd have to sort of like push and pop it right you can't just keep it you can't keep a pointer to the object in the in the atomic variable because that's going to that's going to race right so at this point it's actually better to introduce the proper data structure that deals with it which is which is much more much more flexible and yeah this brings me to the to the lock free queue because this is a very very useful data structures of solving all those problems and there's many many use cases for this so if you have a lovely queue you can pass jobs to another thread you can post parameter changes if you have like a stream of incoming data then you can you can pass that on to the other thread and you can get it out again it's really like it's kind of Swiss Army knife as well for programming this structure it keeps coming up over and over again in many many different use cases so so yeah the rest of the talk I want to implement the structure because first of all it's very useful and second of all it shows a lot of the typical kind of problems that you want into if you do write lock the algorithms so actually one thing I want to say about this is I don't actually encourage anyone to write their own log 3qs or lock free structures because it's you're going to BCC it's a complicated business so you should always use of course if you can third-party solutions like boost has a boost luxury library with several containers in it now in juice we have we have an atomic Q atomic 5 4 class as well so of course you should prefer third-party implementations but the reason I want to do this year is because it is very useful to learn about how to how to build those things so it's really useful if you want to see the typical problems that come up with you deal with lovely code any questions at this point ok let's let's dive in because it's really the fun part so lock BQ so what's the Q you have a writer thread and the reader thread so they're going to point to some some memory and then the writer can push items into the Q and then the little XS are actually valid objects that are in the Q and then you have a reader and you can pop them off again right and so the whole thing sort of moves to memory like a like an or a swarm maybe and the simplest case is single producer single consumer which means that you always have one thread that's pushing and another thread that's popping so we're going to start with this and I think we're going to have enough time to discuss the Multi multi consumer cases later as well so the complexity increases quite rapidly if you do this so let's start with the single produced a single consumer case right so let's write a let's write a lock free Q so this is the simplest interface you can possibly come up with you have a push method and you have a pop method so for the pop one I use an out parameter that's really arbitrary and C++ 17 I could probably use a that optional instead so basically and the bool is whether the pop succeeded or not so if the queue is empty it's kind of return false its accuse not empty it's going to return true is going to put the element in there and then the push adds an element to the queue of course you can't just use a good queue right we have specific requirements so our requirements is no data races no allocations and no locks so first of all let's talk about data races so if you have single producing a consumer that's actually quite simple because on if the queue is empty then the writer and reader point to the same object but there's nothing to read so there's not going to be erased because no one's going to try to read something that's not there and whenever the queue is non-empty the right-hand reader point to different points in memory so you're not going to have a raise there because you're not going to write and read to the same location so no data race is easy no location that means our queue is going to be of limited capacity so it's not going to be like a vector where if you keep adding items that's going to just allocate new memory we can't do that because if you're in a real-time environment you want to have to allocate in order to push something we don't have time for that so we're going to have a fixed capacity and it turns out that the best way to implement this and to the way it's implemented most of the time is by using a pre-allocated fixed size ring buffer or circular buffer as people call it so this is the reason why the structure goes by all these different names people call it locks EQ lofty FIFO atomic circular buffer atomic wing buffer whatever but it all means the same thing basically you have a ring buffer like this and again you have a writer and reader and if they point to the same position memory it means that the queues empty and then the writer keeps pushing things to it and then it's going to move and the reader pops them off again and it's going to move as well and it sort of wraps around like this and you just use this fixed amount of memory and it's we are important to notice that whenever the queue is empty they're going to point to the same location and now we have different choices design choices how you want to implement this and the way I'm going to implement it here is that it's akyüz full it's going to be like this so basically we need to allocate one more Allen and then we actually need so that we can use reader equals writer as a condition for is the Q empty and if the queue is full we're going to be in this state where the writer sort has sort of caught up with the reader but there's like this one space in between so we have you need to have this like extra extra slop in there there are other strategies to do this in instead of allocating this additional one you can have like reader equals writer to mean either empty or full and you can keep like an extra loop count to distinguish those those cases so there's all kinds of ways different ways to implement this but this is this is the simplest way to do it because you can just say we do equals writer means the queue is empty it's going to make things much simpler okay any questions on what we're trying to implement here okay cool so let's dive in let's go these are the two methods we need to implement and I'm using the because the size of six anyway I'm going to use the size as a non type template parameter up there you don't have to do that but that's just the way I do it here so first of all we need to have the actual size of the membrane now already said it's going to be one element more than we need so we have this ring buffer size we're going to be size plus one and then we need to have some actual storage by the way it's going to be a lot of code now so if you have any questions at any point feel free to interrupt me so you're going to allocate some storage for it I'm going to use this to the right so that's going to be our ring buffer and then we need to have a weak position and a right position to be sure if those pointers and I'm going to use because they're going to be accessed from the two different threads so I'm going to use an atomic for it and instead of pointers to the actual memory I'm just going to use indices into the array and we're initializing them with zero so that's the initial state everything points at the beginning there equals the queue is empty so that's all fine right cool let's implement the the pot so first of all if you want to pop an element what we need to do is we need to figure out where the reader and writer positions so we're going to load them from the atomic values the read and write a position and then if the queue is empty there's nothing to pull so you're going to see if they're equal and if they're equal we just return false there's nothing to do for out there if they're not equal we have to actually pop the element which means that we can go into the ring buffer move the move the object out of it and then move it into the reference that is given here is the in all parameters and then we're going to do is you're going to store you have to increment so because you read just read an element so we need to increment the read pointer by one so we're going to increment it and store that value there's one problem with this we have a circular buffer right so at some point if it reaches the the end of the array it has to wrap around so we can't just keep incrementing it so our what I'm going to do instead instead of increment I have to sketch position after method which checks if we reach the end and yes that's a question well well hang on so we have one one reader here that's the that's the first step the singer we have a single reader so it's not really only spread who's going to change that so we're fine you just have to see where the reader is at the moment and then we're the only traders get gets to advance it so you're fine so yeah instead of just incrementing it we do this kind of checks it maybe to the end and then we're going to wrap around back to zero again there's different strategies held to do this there's a way to implement this where instead of doing this thing if your buffer is the size of your buffer as a power of two we can just keep incrementing the pointer and not using the higher bits so that's a little bit of optimization that some people do but it's just unnecessary complexity here so let's just use this yeah and we're done so that's the pop method it's all fine right let's implement a push method again we need to load the right position so we're going to load the current right position and then you're going to see okay we need to advance this so what's the new right position so it's like increment or maybe wrap around so we have the old and a new position which is just the next one and if the new position what hits the the reader right it's like this kind of thing where the writer would sort of like overtake the reader and they would become equal and we'll we can't have that because it would mean that we would exceed the capacity of our queue so if the next week is the next right position would be equal to the reader it means that we can't actually push anything like the queues full which means that if that happens we just return false and we don't do anything everything clear now if the new right position is not reader it means that we have some space so we can actually push a new item into the queue so let's do that let's copy the new element into the queue or maybe you can move it and restore the atomic restore the new right position and they're done and that's it that's the lock PQ that's not really hard is it okay that's cool by the way the the assumption here is that the copy and move constructors of the element I'm not going to do any funky stuff like allocating memory or anything like that because if they're going to block in size and there's really no point doing this because it's not going to be locked for you so the assumption is that this is some kind of type that it's not going to allocate memory if you try to move a copy it or anything like that now this might look like a raise here right because you're reading and writing to the buffer but actually it's not a race because you're never going to read from a position and then write into the same position simultaneously just because of the way the point of work it's never going to happen so that's not the race so um this is great and it's actually not only lock-free it's actually wait for you as well because if you look at this at no point would you have to sort of like say okay I can't do this right now I have to like try again or whatever there's no such thing in the code so if the queue is full or secure empty you're just going to fail immediately and if the queue is not full and you can Porter if the queue is not empty and you can pop you just do it immediately it's like basically one one operation and it's never going to fail so it's wait free that's like the best case you can have unlock the code cool easy you can there's a question reading and writing at least objects there will not be some kind of cash lying with issue where you think your item and lights there is a bother and actually all over I think view your item 16 bytes the do over I could six bytes of that next slot with a range so with something that was there before has been changed by other threat already so maybe the question was can you run into problems with the cache lines yeah so this is another problem which I'm not talking about but of course if you so the way data is shared between threads is in cache lines so if you're going to write to a piece of memory and you're going to read from an adjacent one so the right is going to invalidate the whole cache line and then you're going to have something like locks on a hardware level where before you can read from the same cache line you have to actually fetch it from memory again so it's going to invalidate the copy in the cache from the other if it's on another core is going to invalidate that cache and it has to read the whole cache line again so yes it would have it can happen but that's like a whole other problem oh yeah it's just the old divorced thing that can happen is you can get a cache miss on the other core and then you're going to have to research that cache line so yes that can happen if there's ways of getting around that as well and which I'm not going to show but in this very very simple example yes it can happen that you're going to get a cache miss because the other spread modified in Jason piece of memory and then you're going to get a performance it but that's the worst thing that can happen unless you have some really weird stuff with like misaligned memory or whatever which we also don't have here so yeah no problem another question if you're on the question was what happens if your reader is slower than your writer and then you cue it getting full and you can't you can't pop items anymore because the pushes you can push items anymore because the pop is too slow the answer is in practice there's different ways to deal with this the simplest ways to increase the buffer size which is what we do in practice another way is to do like a slight modification of the structure where the degree depends on what you want to do so you can modify the structure in such a way that if you keep pushing instead of failing you just keep overriding the oldest so you keep overwriting the oldest element so it just keeps going around around around 80 pop you're just going to get in the newest one and be like the oldest ones just getting slightly overwritten that's another thing that you can do in practice it's just it's very easy to modify this code to do that so that's another strategy really depends on whether you can discard the old values or whether you cannot discard the old values because you have some kind of stream of data where you need to get like every single element that has ever been pushed and then you should instead increase the buffer size but there's different strategies to deal with that I should say that this is like the most simple case there's like if you encounter these structures and practice there's like hundreds of variations of how you actually implement them but like how do you add to this code depending on your use case to deal with all these kind of cases okay so you continue so we have this yeah so we now have just this interface here and of course if you want to do this if you want to like if you're writing like a library class here there's a lot of things that you can add for example you can add a push to take certain our very reference so you don't have to copy it you can add on utility functions to it like size and clear like the usual container stuff and then another really useful addition is to push a whole range of elements or to pop the whole range of elements and like get a pair of iterator thing I push the whole range into the queue or you can pop all the elements and put them into into an output iterator yes question oh no reason okay you know the start yeah the question was why do I pass the input iterators as a pointer forget about it I think the original version I was passing rule pointers and then I replaced them with iterators and I forgot to remove these star so just ignore the star yeah sorry for the type of there so anyway so you can add these utility functions and like push range is really useful if your elements are like integers or floats and you have like a whole chunk of them just going to yes another question so the comment was you should if you push the range you should return some kind of value that indicates how many elements you have actually pushed great that's that's great idea yes you should do that basically the whole point of the slide is you can keep adding those utilities and those useful things and eventually if you keep doing this you end up with the interface that looks like a proper library implementation if you do all those things so this is this is now almost like the interface of boost boost has the boost Luffy has the SPS EQ which is good at structure and if you add these kind of methods then that's going to look very much like that structure so yeah you can sort of refine that interface and add all those things and it's going to become a proper library class but you're not going to do that here but yes so yeah we're done the single producer singer consumer case is completed and we do have a lot of time left so we can actually talk about multiple producers and multiple consumers and this is where it gets really really fun the first question is again why would you even bother doing this and I think my opinion is that if you can write code with single produces single consumer Q's or if you can rewrite your code so that you only have one thread reading and one-third writing should always do that because it's going to save you a lot of pain but sometimes you can't do that because obviously we have multi-core platforms and you want to use those course so you want to distribute your work among those course and one of the situations you might end up with is that you have different processing threads that do some number crunching on different cores and you want to get all this data into your views hemp thread and then you want to get it out again and so either one direction or both of them depending on your use case and you want to push data from multiple threads into a real-time thread and you want to push it from there to multiple threads as well so in those cases you need a multi producer queue or multi consumer queue or queue that does box so we don't have time for the multi producer queue because it's a bit more complicated so in this talk I'm going to just talk about the multi consumer queue but maybe I can do the module for ducek you next time so fun but yeah let's let's talk about the multi consumer queue so let's talk let's have the code that we already have and let's see if we can just modify it a little bit to allow for multiple consumers or multiple readers so what do we have to modify there it's actually it's going to turn out that it's actually not not as bad as you would think so first of all this line is a problem right because another threat might also be reading it and if you're moving it out then the other set is going to read garbage so you can't move it you have to copy it but again like reading from the same location from multiple threats okay so if you copy it you're fine as long as the copy is not going to do any funky stuff the next problem is this gap here because what you're doing here is if you read the element then you're updating the weak pointer if another threat is also reading it it's going to be finished it may be finished before you and it's going to update the read pointer while you're still somewhere before that red line and then you're going to run into a problem because you're going to so the by the time you get to so after you've copied the element you want to update the read pointer but by the time you get there another reader has already updated it so he to fix that and the way to fix that is as you already saw earlier compare exchange as we useful to do that so we can do this and you can say okay I've read this value so I'm fine I want to advance the read pointer so I'm going to ask is the read pointer still the same as when I was reading it or in other words am I the thread that's going to get to update the read pointer now that's too updated to the new value and return right and if not you have to read again if not if that fails basically then Oh someone else changed the reader position so you have to load it again right because it has changed and then the element you read another thread has already read it before you so you have to actually try the whole thing again so you're going to put all the stuff in a while loop yeah so you read an element and you try to advance the read pointer but Oh someone else has all you read it and already incremented the weak pointer so discard it and try again okay is that code correct yeah you don't think so okay I'm going to give you a hint there's a there's a bug here okay so this is a great example for how it it becomes really difficult to spot those race conditions actually this room's really good because a lot of hands went up yes yeah yeah you're going to come to that okay so here's the bug and the bug is okay let's say we have one reader which is reading this element and then another leader which is also reading the same element and then the other reader gets to do the computer exchange now the case no there's like one case that can occur here which is basically you're trying to read a value another thread has already read this value so you're you in this loop and it has failed and then why you did that so the thing here is if you want to spot those things we choose Hume that oh baby imagine that any line of code can be simultaneous with any other line of code and any line of code can take any amount of time and also your whole thing can be in any any state and so it's a bit tricky sometimes so if you fail to read this value another another one has read the value and then while it was doing that actually are the the writer has pushed a lot of new items into the queue it's gone all the way around and it's going to try to so the writer has a little filled up the whole key why you were stuck in this one line and now it's going to write into the same piece of memory from which you're trying still trying to read here if your reader one and then you're going to have a rate here where the writers writing and the readers reading from the same memory location yeah so congratulations you've just opened the gates of hell this is the kind of stuff that's need to deal with so how do we fix that it turns out um well some people say it's actually not that bad because if you have in this case where the writer writes and you're still reading from the same memory location it's actually fine it means you're going to read some junk but then the next line here you're going to realize that you have read some junk so you're going to anyway discarded and fly again so yeah you're going to read some junk at it's actually fine because you're not going to use that which is true on certain platforms like Intel probably because you know that's the way Intel works it's going to be atomic anyway maybe or maybe not what about arm I don't know what about if T is like not a float it's like a big object and is it still going to be fine to read some okay so actually it's undefined behavior so you can't you can't do that and yeah if you if you care about a portable code you wouldn't rely on the fact that if you if you read kind of junk and then you discard it then that's okay because it is actually on the same behavior so we need to fix that and unfortunately in this case there's no easy way to fix this because you can't sort of lock around the memory access so what you need to do is you need to make the memory access itself atomic now like to the actual data so instead of having a ring buffer full of T's we need to have a ring buffer full-width Atomics so that the actual access of the data is going to be atomic as well which means again that if you want to store something that's not an int or a float but you're going to store objects in your queue then you have to store pointers to them and you have to deal with a lifetime you have to write some code around to deal for lifetime because the only way you can access data simultaneously reading and reading without locks is atomic right so that's me to do here so you need to instead of just reading and writing you need to have atomic stores and loads into the actual data which fixes the problem very good so we don't really have to modify this code at all we just need to make sure that the access into the actual data is now also atomic yes that's a question yes the question is whether the reader is going to read elements out of order if the writer overtakes it or no why would it do that yeah but then you're going to realize that and then you're going to try again yeah so if something went wrong then this is going to reach on false and then you're going to discard the whole thing and load the read position again and just try it try it try that again but actually there is another bug here which I think you've sort of spotted yeah very good you discovered one more bug in this code so yeah you want to say yes so this you describe the same bug in different ways so there's one last budget that we need to fix and the case here what can happen is that if you're in this situation for example where we have one item left and both readers try to read it and then obviously one of them finishes first and then the queue is empty and but then the second reader is still still trying to read it right so both readers are in the green line of code here and then one reader succeeds that the other readers still there and what happens is it's going to read it it's going to realize it's going to realize that the other reader was faster and it's going to load the new read position and try again but the problem is that the queue is now empty and there's nothing to read but it's going to keep just keep trying to do it even though there's nothing to read and that's the other rate condition here which means that our dragon just grew like a new head and we need to deal with that so how do we fix that well basically the bug here is that the compare exchange is going to correctly tell us the read position has changed and then we load the new one but we don't check if the queue is actually empty now so this is the code that checks if the queue is empty and what we need to do is we need to move it into the loop right and if you do that then actually this one becomes obsolete you can get rid of that and now we're done and that's not correct code and actually it's shorter than the first buggy version it's almost as short as the single produced a single consumer line so that's going to work now and it looks like this large while loop it looks a bit scary because it looks like the pop could get stuck in this loop for for a while a bit like as if it was blocking but actually it's not blocking because if the loop if the loop fails once and you have to do it again it means that another reader succeeded in reading so it means that the other readers have made progress so it's this case where it's lock free but not weight free but it's still lock free and you could imagine a theoretical case where like one of the readers is just going to be very very unfortunate every time I'm just going to be stuck in that loop while all the other readers make progress but it's a practice that's very unlikely case and actually the probability for that to happen goes down exponentially so yeah so that's that's the lock for your multi consumer queue one question in the back I'm not sure I understand the question you want to you want to come up here and show me the line of code you have a cute couple villains in it yeah and then you arrive at this line yeah and you capture the right position yeah and then your thread stop acute executing yeah and some others quit keep on working for the queue read all the elements writer clicks going yes and then it's your turn again and you get the resolution yes and then it happens to be the same as the old right position but the right position has yeah this is why this is this is why and then you put on Oh to cue them please let's not do anything but actually relevant did it I'm not sure that's the problem but I think we need to sit down and work it out yeah interesting it's a it's not really easy to reason about this stuff I'm not sure we can fix this in one minute or like figure out if that action actually happened I don't really see it but let's sit down off of the talk and and like go through it properly is that okay I appreciate that you say it's hard to do yeah so basically the takeaway message from the store because it's really hard you shouldn't be doing it just use a library implementation well how old library care and yeah um any more questions yes the question was why don't I replace the East which is loading because you're going to use it again later no we don't yeah we could do that so we can't replace this one because you're going to use it again there yeah we could instead of writing this you could do load here yeah it's just cleaner this way I like having our loads and comparisons because they're different things I like to have them on different lines yes ah are you referring to the feature in sequence of 17 we can initialize path under if thanks for that comment I love that feature yeah in C++ 17 you can if and then you can initialize the right pause here and the repose and whatever you want and then do the comparison and one is can you hang on hang on hang on you can't initialize stuff in the while loop this feature works with if and a switch as far as I know it doesn't work with while yeah okay yeah so there's ways of writing this code in different ways I think it's reasonably clean but obviously we can yeah you can massage this code to make it look different but I think it's reasonably clean to sort of get the message across but yeah you can yeah you can write for semicolon semicolon if you prefer that yeah yeah sure yeah okay but it's not changing the algorithm right so it's just a coding style cool um any other questions yes the question is an excellent question is there any way to prove this is correct and I assume you mean mathematically prove not that I'm aware of so this code is complicated enough that I wouldn't know for like rigid logical framework where you could sort of like prove it mathematically or something like that I don't think that's possible sorry okay that's a great comment do we have a mic fall here so you can you can say that again and going to be on the video because I'm not able to repeat what you just said but yeah you're going to be saying there was a framework which you can use to prove these kind of things okay sorry okay cool I'd love to hear about that stuff let's talk about it later can you can you please repeat into the mic we have a mic now okay so the first answer was can you prove is that I can't but I know there are mechanisms and the colleague told about communication sequential processes CSP it's an old model by Tony Hoare and you might end up finding something and I didn't understand the other thing process calculus okay so there might be means to prove things let's say I love conference until my comment was if you add memory order that's not sequential consistent with the loads and stores things get much more interesting and much harder to put oh yes yes and this is why I'm looking forward to the next talk so I completely ignored the issue of the memory ordering because this is all just sequentially consistent but you can get much more interesting if you want to optimize it further and you use like relaxed memory order and things like that it's going to get even harder to reason about the code which is really I didn't have time for that stuff in the talk but I'm really looking forward to the to the talk that's just going to be off just after this so yeah it gets much more interesting if you do that more comments can you please all use the mic from now on because we haven't mic now is that okay if you just bring it pass it around thank you very much and I have a question about the atomic ring buffer which is atomic now but not only singer producer singer consumer scenario why is it not required to store atomic teeth in the singer consumer case because we have atomic access to the right position and the read position but is there any guarantee that the reader actually also reads the correct value of the writer inserted into the cue basically the question is why is this not a race condition yes why is this not a problem because there is no state in which the object can end up where read and write position would be equal and he would also be executing top but isn't the optimizer allowed to swap the assignment into the ring buffer and the store into the position well we have atomic operations here that you have load and store and we use sequentially consistent memory so it's not allowed to move everything so whatever is under the load the optimize is not allowed to move it above the load and the same for the other one like it's there are some restrict its again this kind of memory all the stuff there's certain restrictions on the optimizer what it's allowed to swap and if you have an atomic load it's not allowed to put things that are under it and put it in front of it okay so the divi important thing is to help to store after the right into the buffer otherwise we will get a break that you if you if you swap around and don't want to fall in there if you have a laser pointer yeah yeah I just bought it yesterday so I'm not familiar with it yet but it has a laser pointer so if you put this in front of that line you don't have that guarantee anymore and then yeah you're going to have a potential recondition that's going to screw it up yeah so the whole point is that yeah because because yeah exactly right one last question here sorry can you speak into the microwave no I mean I have a suggestion for next time throughout the line of codes and you're the code people can refer to the lines without filling down that's a great suggestion I'm going to do that from now on I'm going to have line codes yeah number line numbers yeah thanks I'm going to adopt that thank you hi it's a practical question because you'll advise it from the beginning of that talk is essentially don't do it yourself what fine and I see why wouldn't be acceptable I don't know sacrifice - instead of juggling in this case two pieces of log free atomic data to pack them into one and then sacrificing size of that in this case this circular buffer so pointer can only occupy half of atomic well integer in this case just collapse all those obscure corner cases we are discussing from last few minutes to none well you would have one blow that one store remember that typically you only have eight bytes to work with if you have an atomic variable so would you say that you need eight bytes size of addressing of circular buffer no but you have some okay if you are storing integers in the queue and then you don't need to exhaust the whole range of the integers so you say instead of storing integers is going to store like short yes no no not this is not anything and think that positions are instead of integers are shorts yeah what do you think lorries are sure sure sure the positions can be short yes but that's not going to change and what you want to do is you want to you can load them both at once oh it's toward them also both oh oh oh that's that's interesting so you're suggesting to pack the reader and writer positions into a single atomic value here it looks to like a lot of the those bugs you just discussed just wouldn't be very firstly that's a good idea I'm actually a she thinks people do that okay I think they're implementations which do stuff like that I remember Tony fun air does these talks on lock see structures I think he has a few talks where he's showing tricks like that yeah people do this kind of stuff actually actually another comment if you do this kind of stuff you can't like the compare exchange becomes much more difficult because the way I'm using it here is you just want to know whether the reader position has changed and you don't want you only want to know whether the writer position has changed and that's really easy to do with the compare exchange if you have them packed into like what a single atomic variable you need to do something like atomic like bit masking stuff so it's going to be actually much more complicated yeah but I've seen people doing things like that but for me not quite not quite where you suggest it but like packing things and to like several things into one atomic variable that people do this kind of stuff but the power of what sorry can she use the mic please I can't really hear you very well so a battery point about not having to get into bit hacking and messing around like that if we just you just stood there and then his point about you could detect when you know doesn't it change so you want to pack what into the pair the two positions yeah we might position James well that's that's exactly what what you suggested as well yeah but simple I agree that's the little initiative yeah yeah you could you could pack them into a pair it's like bitwise it's the same thing anyway right yeah it's just you give it a different name but what's your opinion with transactional memory in the game is going to issue this kind of stuff or I think that's a topic for a whole other talk okay [Laughter] yeah I think I think the time is over let's I'll be I'll be around for the whole conference so I'm happy to chat about all these things yeah looking forward to [Applause] you