Thinking Outside the Synchronization Quadrant | Kevlin Henney

[00:00:09]are we live yes excellent good good afternoon um so what we can talk about for the next hour uh is thinking outside the synchronization quadrant which means I have to say some meaningful things about what I mean by that terminology um and uh this talk is placed in the C++ track I would say that probably uh half the talk relates to C++ um specifically um the code the code that I'm going to show is C++ some um but the principles that I'm looking at are actually far more General um so uh so it it depends on what you're coming in for um there should be something here for you um yeah uh code um architecture architecture good let's talk about architecture um so there are a number of different definitions floating around the one that I generally um find the most effective uh the most useful the most constructive uh is this one from greedy B architecture represents the significant design decisions that shape a system where significant is measured by cost of change now this is very helpful because it gets away from the false ideas of scale um what is the natural scale SC of software unlike Building architecture it's not as obvious um but there is a scale here effort how much how much effort is that to change very simple way of indicating and discovering whether or not something is architectural is whether if you make a suggestion of a change and somebody's face goes pale and we can't do that or no no no we never do that if people say you can't do it then it's architectural okay um and therefore that means um that it can relate to the smallest language feature as well as the more obvious major technology choices now one such thing that shapes a system and is non-trivial to change it's clearly something like um concurrency uh the presence of concurrency in any form now one of the things I find interesting um about concurrency uh and parallelism and our various definitions of all of these uh is the is the way that we have ended up accidentally being programmed to think in a particular way you can almost play a word association game in fact this is what I did a few years ago I did this with uh in two workshops I did play this word association game and I got the same results each time which I found absolutely fascinating first idea that comes into your head when I say concurrency and as a room everybody said threads so in other words it what I found interesting is that was with the um the the junior programmers but in another company with a whole load of advanced developers who were clear who actually wanted to discuss higher or higher level mechanisms it was fascinating if you catch people off guard threads oh damn I didn't mean to say threads I meant to say something like you know higher level and meaningful it's still in there it's still deep down there threads are the most powerful construct um for introducing uh concurrency in um in any code base and they are powerful like a go-to is powerful there was a an interesting proof um in the early 1970s that goto was the most powerful sequential construct and what was meant by power is you could build any other sequential construct out of it and then you have to throw the Spider-Man quote at this point with great power comes great responsibility and it turns out we're not quite as responsible as we thought we were the same goes for Threads you can build pretty much anything else out of threading constructs that that expresses concurrency the problem is they are too primitive they are too raw they are effectively the jump statement um at this level so we acknowledge that there are going to be threads but that may not be where we want to write our codee we want to leave those further down now the word association does not end there because I threw another one at people I said threads and they all said locks or synchronization in other words oh that's kind of interesting so hang on why are you guys doing threading oh we're doing threading because we want things to go faster why are you doing locking because we want them to go slower well they didn't say that but that's what they mean locks are the anti-th threat the purpose of a lock is to eliminate concurrency so if your goal is to get some of this then it's fairly clear whilst that may give you it this taketh away and uh this is a a struggle that we we often have um there's a a lovely quote and I realized I've just I just realized I've forgotten to put it in this talk um originally from David butenhoff uh who wrote the book on posix threads and he said you know what we made a mistake calling them mutexes we made a mistake adopting Esa dystra terminology we should have called them bottlenecks because then when developers talk to each other and have a conversation they're more likely to think twice uh oh you need to put a bottleneck in here hm doesn't sound quite so good whereas mutex has this kind of like lovely whiff of computer science about it yeah bottleneck not so good okay so what we realize is I'm going to pick on this quote from somebody actually talking about real Building architecture architecture is the art of how to waste space but I'm going to adapt it because when it comes to code what we realize it's about the the the ability and skill of wasting time so let's talk about this thing the synchronization quadrum um I Dre I found that I was trying to sort of classify things simply for a team a few years ago we ran a workshop on their on their development practices and some of the issues they were having and I found that one of the simplest ways to clarify um for them uh this I I put it up on a flip chart and then realized it actually was a really useful um classification mechanism um this let's let's just break the quadrant diagrams first of all it's the afternoon so your metabolism your brain and everything just gone into a very they've gone into a sleep State um so a quadrant diagram is is your friend at this point it divides the universe into four and there are two axes and there are two things on each axis it really doesn't get much simpler than that and um as with most quadrant diagrams there normally one quadrant that's either very very good or a quadrant that is very very bad now I'm G to I'm going to break this one down to um uh mutability there is an AIS of mutability the data that you are dealing with is either mutable or it is immutable and then there is the degree of sharing between threads your data is either unshared or shared now you can you can subdivide this far far further you can say oh I've got a single I've got a single writer and multiple readers that's great that's fine but that's over in in the shared quadrant I'm I'm going to keep this quadrant like and so here we have four places your code can be I'm just going to make this really really clear red Nature's color for bad or um in the in uh in Far Eastern cultures and contractors the color of Celebration okay um this this is the synchronization quadrant okay you have mutable data and you have state that is shared between your threads you will need some form of explicit synchronization in your code okay I'm not saying you don't need synchronization anywhere else is just that the synchronization either belongs lower down at the lowest level actually uh in the processor or it belongs in a library construct so there may be synchronization it's just that we don't want it all over youre code so but there is this thing but there's something about this quadrant this is where most code ends up living there are four possibilities but like moths drawn to a flame we are drawn our code bases are drawn into this vortex in the top right hand corner um and I have wondered about this for a while and I I realized having um uh I I I got a very very very long time ago um I uh got a master's degree in parallel computer systems and um so you know you kind of think everybody knows this stuff and actually turns out that they don't and You' just happened to be been exposed to all this good knowledge and it turns out as the uh as we tracked into the 90s and on um we ended up going into this quadrant over here and I I often wondered about this and there's a simple cultural and historical reason um before threads became commonplace all our code was on the left hand side because is quite by definition you cannot share between threads if you only have one thread um so all the code was over here and for historical reasons and our imperative background um and resource constraints and so on everything was in the top left hand corner a few things wand down is the bottom left but pretty much most code we're talking about is in the top left hand corner so when we added threading as a as a a language construct as a library construct as a feature in the operating system um we ended up naturally moving straight over to the right with our code and that led to the problem if you look at books that are written in the '90s up until the early 2000s whenever they introduce concurrency they follow this idea they they're Mo mostly about the locks how do we lock stuff uh indeed a lot of the literature published in the 70s and 80s was along these lines it's about how do we lock and all the constructs and proposed language mechanisms are all in that uh kind of view in the last decade or so we've kind of really shifted it's not the game that we didn't know that perhaps avoiding all of these this locking conversation was a good thing it's just that it's become more normal and more excepted so yeah we've ended up unfortunately with an awful lot of code over there so let's talk about the qualities of such code um when you're dealing with a code when you're dealing with code there are it's kind of simple right- hand rule that I quite like to use um the axes are not perfectly orthogonal but then again neither of my fingers so it's a good enough approximation but it allows you to reason about code um reasonably simply um functional behaviors operational behaviors and developmental qualities okay so in other words the functional and operational qualities functional as in uh the semantics the operational as in resources as in what many people refer to uh as the ilities that are not related to the development time the development Time stuff is your experience as a developer those other two refer to runtime qualities and if we look at those we can see that obviously when you are improving performance you're moving along the operational axis when you are refactoring you are maintaining a constant functional axis but you are trying to improve some developmental quality and so on it's is kind of an easy way of kind of reasoning about uh your code um if you add functionality you move along the functional axis okay um if you fix a bug you move along the functional axis as well yeah you had a deficit of functionality now you make up for it so it's a nice simple um model but I want to start first of all with the operational access this idea that the qualities of execution are one of the reasons that people um are motivated to uh introduce some form of concurrency uh into their code um it turns out Shakespeare was on this one as well I mentioned Hamlet this morning um for memory management um but he's here talking about resources uh the monstrosity and love lady that the will is infinite and the execution can find the desire is boundless and the ACT a slave to limit we're going to come back to limits again uh in a bit um the problem is you do not have the ability to run things at infinite speed everything has some kind of cost no matter how brilliant you think your architecture is it turns out this is the point at which our beautiful abstractions meet the laws of physics um and there are costs to the laws of physics there's a rather good um uh blog came across uh recently um link is at the bottom uh what are the costs of various operations um from the kind of CPU perspective uh and this is going to vary from processor to processor and so these are defined as ranges uh importantly it's logarithmic um I rather like the uh display um the idea of Light how far does light go uh travel during the time uh that this operation takes um clearly he has a smaller laptop than me because it's not the diagonal on this one this is one light nanc I I often use that as a measure when I'm telling people so I delighted so he's done the same thing that's one light nanc which sounds you know terribly fast Until you realize that gives you a cycle time effectively if that's the distance over that that's a cycle time of 1 GHz which is not so smart it's really you exhaust the possibilities of 1 GHz in a very short physical space um and then he goes through these are orders of magnitude um the thing I want to draw your attention to thread context switch um that's generally more expensive um in terms of cost the raw direct costs lie between um a kernel call and a C++ um exception throw and catch okay stack on winding the whole bit um but as he says in the article there this is quite difficult to measure because there are loads of indirect costs that go on you can and and it turns out that um uh those can be ridiculously expensive this is one of those things that and one of the great disappointments people have when they fire up threads hoping for um a linear uh improvements what they suddenly discover is they they're not getting them there's aost cost involved there are lots of costs effectively there are coordination costs so if we take um the idea to understand whether or not you want to um introduce uh introduce threading if we take this idea completion time for a single thread and we're working on some task um the classic view of division of labor we going to throw end threads at this okay that's brilliant if everything's independent and everything is for free and if you remember at school um you probably did some uh probably did some electronics at some point point and um there was this rather brilliant um assumption that was made when you're first introduced to electronics what is the resistance of a wire that connects all your components together zero I know isn't that brilliant you're at school and you get superconducting wires how cool is that yeah but it's a beautiful idealization so this is the way that people often think about threads it's just like we end up with zero cost this is this is fantastic um even without worrying about that though we haven't even looked at the nature of the task we are assuming that everything is perfectly independent it's not going to be there is some portion that you can do in parallel and um tasks have interdependencies if they need to talk to one another share data do whatever then there will be some portion they cannot do in parallel um so uh a lot of it depends on on P um this is amal's law uh we haven't even we now we're going to get rid of the ideal wires now it's quite difficult to do this in a simple equation so I'm going to uh uh I'm going to give you worst case and oversimplified view but get a shape out of it um inter thread connections let's assume the worst case that everybody needs to talk to everybody else that is the absolute worst case okay if you have that and you're a contractor this is magnificent you have a job for life okay um but really you don't want to be in this kind of uh uh this kind of mess um let's let's assume that we've got some kind of concept of an average communication overhead average is a very difficult concept uh to apply in this case but let's just say we've got some kind of typical communication overhead and that it's going to give you a curve like this what that basically means is the minute you introduce threading into minute you divide many tasks across threads you get slow down not not it's not Universal but people are often surprised at how much benefit they do not get um this is the F this is the first thing you need to remember it turns out that if you don't have the cost of a contact switch then just being able to do things really fast sequentially turns out to be an absolute winner um we see this um classically in the sense that um historically x windows servers um sequential they use basic reactor pattern and they just handle something get on with it handle it get on with it and they just do lots of tasks very very quickly um and there is no uh need for concurrency the minute you start hitting the concurrency barrier you have to ramp it up quite a bit and then you get something out of it um we're not even worrying about whatever else is going on in the processor there's a whole load of other stuff going on I'm just I'm just skimming and lurking at the surface here if you want that Sean's doing a talk later and he will talk more about stuff like that unless you've radically changed the slide since I last saw it um so so I'm just scraping the surface here in the terms of the bits that you can easily do and touch okay just with these constructs um so we have this and there's there is this question of locality and cost uh the landscape has changed as well uh every few years we end up with a shift in our um architectural defaults the thing that developers think oh that's so obvious you always do that and it turns out it's not um so we're at this point lovely this um uh this is a Blog from two years back Adam Drake um did very simple uh task command line tools can be over 200 times faster than your hadu cluster and he basically did this he basically uh uh did this particular number crunching task um not particularly big data but um for some people it would be big data obviously what we consider to be big data is a function of time um you know once upon a time one megabyte was quite Big Data um so there is the point here that people have got into the habit of saying right distribute that you distribute that across multiple processes to the cloud with it to the cloud with it uh so we wrote this in John and then he wrote it again using Bourn shell and ran it on a single machine because it turns out the thing we now have it used to be cheap processes uh across a network turns out that memory is way way better if you can keep it local do so you cannot beat the speed of light it really is it really is that simple um so um this this is a key Point we've got an interpreted language here but because it's able to use local memory um brilliant uh brilliant benefits now um speaking of that uh time is and code um I'll do a very simple um I want to look at a couple of constructs and what what is involved here and I also want to place this on the synchronization quadrant uh I'll do a very sort of simple naive kind of map reduce approach we're going to map um some operation called mapping across um a number of um tasks and I've just realized I've got I overdid that let's uh a great thing about live stuff you spot the bugs and you can fix the Box you saw nothing okay okay and that's good there you go right um so we've got um that and so then we end up with uh a whole of choreography um oops all the sequencing has gone out of that one um right there we go that's what I'm after um there's a whole load of um uh noise that we get from um uh C++ uh in its kind of classic form um I've got my data from beginning to end I've got a mapping operation mapping I've got a reduction operation that's going to combine everything with respect to an initial value and then I'm going to code this up raw by hand I'm going to create a vector of threads and I'm going to um set up a loop where I go and launch a thread we don't even know that this is going to be appropriate we haven't even looked at what cores are available and you know I'm I'm going to hit the threading really really hard here um and uh fire off um each task and then I'm going to wait and join on them and once I've got everything joined at that point I can combine everything I can use accumulate accumulate is the standard Library default term for um what everybody else calls reduce or fold so we've got that okay um now there's a few things we can do to tidy up here um one of which is um C++ 14 allows me to just deduce the result type and we're good with that um the C++ Concepts um technical specification allows me to get rid of all of that which is marvelous um so that that tiies it up a bit um then if I take on board um the um parallel technical specification um I can now get a parallel version of for each that can vectorize uh I can give it a policy I can say right vectorize that I've also got one for accumulate that I can now do a reduce so reduce did get spelled correctly at some point and we've got that so if we look here and relate that the bit that can re although I'm doing the reduce although I'm doing the reduction um I I've said well let's assume that we that our operation will actually work um I'm missing an argument in there I've just realized will actually um work fine uh from one particular point of view um there is uh all the concurrency that we can really squeeze out of this is going to be in the four each bit and the last bit is most likely better off done sequentially so in that sense that code is from the point of view of the um synchronization quadrant the first part assumes that nothing is shared each piece of data is independent therefore able to fire everything off in parallel um so there's no no locking there there is a synchronization point at the end but that is hidden from us and then again for the last Point um but portion that can really be done in parallel p is the first part okay so there's another aspect here functionality people often throw threads at their code um because they want they want to express functionality why does that make sense normally it's performance actually we used threads for a very long time before we got multicore in fact one of the um first times that I was using threading was definitely well well before uh the multi-core era and our motivation was quite different it was the expression of functionality where where things are independent I don't want to have to write my own scheduler to make them independent I would like to be able to say there's this going on and there's this other thing and feel free to even to leave them as as and when so not getting true parallelism but um but some form of concurrency the idea that I want decoupling between tasks so from that point of view we're saying threading not as a performance gain but as a form of decoupling these things are independent why should I have to make them dependent on one another um by dividing up the task manually and creating effectively my own shedul so there are Mo there are reasons for doing this however the expressiveness is the bit that gets us and this is where um lurking in the top right hand quadrant uh causes US problems a large fraction of the flaws in software development are due to programmers not fully understanding all the possible States their code May execute in John karmac um of ID games in multi-threaded in a multi-threaded environment the lack of understanding and resulting problems are greatly Amplified almost to the point of panic if you are paying attention in other words we struggle to reason about state in a code base we struggle more when there's state to change and then if we say by the way things can happen out of sequence and whilst your back is turned then this is where the Panic sets in and if you do not have a healthy sense of panic there is something wrong with you you've not reach some Zen State there is something wrong with you if you are dealing at this level it's just like there's a lot changing and there are threats um you need to take a very rigorous approach to get away from that sense of panic so um you know most common uh example best expressed um here um take me down to concurrency City where green pretty is grass the girls the and are um it's things happen out of sequence we have the problem of race conditions this is why people often say you know this is why I need locks the problem is that we have this programmed into us to such a degree that we people do not question why they have locks and I had this conversation with uh a group the conversation was interesting because I said why do you have locks and they said because we have threads and I said yeah but that's not a reason why do you have locks they're kind of looking at each other and they said well you know because because we got threads and well yeah because otherwise it wouldn't be safe well why would it not be safe why are you writing unsafe code that's always a challenge why are you making your code unsafe and said well yeah because we're sharing data and I said yep you still have have not given me a reason why you're locking and they're kind of looking at them each other as if as if they were my teenage son you know in other words you're an idiot yeah um and then I said okay so why but why does sharing stuff between threads cause problems and they said well because one thread might change something and I said well hang on wait a minute that's really important that's the most important thing you've said and you left it till last that should have been your opening sentence we've got changeable State and it's been shared between threads not we assume that all state is changeable you should consider State change to be a privilege not a right but the problem is that the way we've been taught to program is the opposite way around and so therefore we fall into this default way of thinking so um there are other surprises uh to be had when we start throwing locks at things um locks mean ultimately you're going to end up with deadlocks um and there's a rather good summary of some of tanon bal's um points uh on the site that I found several ways to address the problem of Deadlock just ignore it and hope it doesn't happen U this actually has a name it's called the ostrich algorithm yeah it's surprisingly popular and actually not as ineffective as you would think until you ramp up the number of states your system can be in and the speed at which it runs then it gets more exciting and there are in there are also a lot of systems um that uh a lot of uh Credit Systems where these problems were in started to happen with code that had threads and been perfectly fine for years but they've been single core um they hadn't actually they'd managed to sidestep the actual issues and there are some really subtle cases um that uh that can cause you these um odd issues where well let's just restart the server again you know we have to do it once a month we're not entirely sure why um but there are the wor there are the ones that happen uh in a far worse sense we have to restart the server every minute is not viable so this can work but I'm I'm not going to I wouldn't put I wouldn't put money on it um detection recovery if it happens take action so people spend a lot of time coming up with very clever techniques um uh for doing this um Dynamic avoidance by careful resource allocation check to see if resources granted and so on so in other words this is kind of an amplification of the previous point but I prefer the fourth option prevention change the rules yeah don't don't play that game um sometimes people do this by introduc imposing some kind of uh lock ordering or some form of lock discipline and basically saying this code so it's an it becomes an architectural guideline none of this code has any locks this is the only code that can have locks if you're going to plug this code into this code here are the rules if you follow these it all will be good and it's a detectable thing in other words there should be no uh synchronization Primitives and you're only allowed to call this this object um so these become a set of conventions and Architectural guidelines um rather than sort of happen stance and accidents um so yes we can do that and we'll change the rules a little bit as we go now I want to close this kind of consideration with this last aspect of Developmental qualities what are the developmental qualities when we start throwing um things like threads at our code when we start actually introducing uh uh these lowlevel constructs or even higher level constructs what are we getting well what would do we want from our code one of the things we want from our code is habitability habitability is not a common phrase um that people throw around code but I've been uh very keen on using it for the last few years I first came across it in this book uh by dick Gabriel patterns of software uh in the late 90s uh and he makes this observation very simple observation we can apply to any code based in any language um habitability is the characteristic of source code that enables programs and so on people coming to the code later in its life to understand its construction and intentions and to change it comfortably and confidently it's a very simple idea it's what we would Define as habitability in a in a in a home environment or in a building you want to arrive in a code base and basically say yeah I I want this to be livable this should be comfortable place for me um to work in um I shouldn't have to sit there and go oh please don't send me into that threaded nightmare um it should just be a case of like right okay I understand what's going on um this is what we want in software developers can feel at home they can place their hands on any item without having to think deeply about where it is that's that's what we would like but what we find in practice is a lot of threaded code is in exactly the opposite place is uninhabitable you know it makes um uh uh it makes the rare vacuum of space um uh seem like a nice place by comparison so how are we going to get this well there are a number of different qualities we want from such code testability is quite a nice one qu quite fond of that one um you'd like to know something about how it works but there are a number of misunderstandings when we start talking about things like um you know test sometimes people have different takes on this uh and there are different views now one of one of the ones that uh I I notice in a number of cases is where people say well you know we can't really afford the time to do unit tests we don't find them particularly effective now sometimes that's actually an indication of something deeper in your architecture um but I I came across this paper um couple of years ago uh beginning of last year came across it and uh then twice more later in the year and uh it's rather interesting analysis of certain distributed uh open source systems simple testing can prevent most critical failures um looking at actual production failures but the statistic that leapt out at me um is the um they actually revealed that something like 77% uh of the tests oh sorry 77% of the problems could actually be revealed um with unit tests so over three quarters of the problems that they found could have been discovered with the unit test you didn't actually have to fire up the whole system in order to discover these uh but that does lead to the profound philosophical question um you know when people say we want our code to be unit testable what do they mean and there's kind of an implied idea which is um uh which is quite difficult um people tend to think of their code like this they tend to think of their unit test they think ah when a unit test passes it shows the code is correct actually that's not what you get and assuming the test is correct okay I'm going to give you that one okay let's assume the test is correct that doesn't show you the code is correct uh when a unit test fails it shows the code is incorrect it's the other way um and this is rather important because sometimes people will it gives you confidence but that's not the same that's not the same measure and particularly where you start doing things concurrently you cannot assume that green means it's good um it just means it's good so far you can be sure that red is bad but green is a rigidly defined area of doubt and uncertainty um in this case you have to be very cautious with it it's a level of confidence but it's not absolute confidence and the and the law of the excluded middle does not apply here it's it's quite important to keep uh keep in mind um how do we achieve this what what helps us with testability um what helps us get away from that idea of like well I can't really test it because the the architecture is uh so sophisticated well actually it's not it's probably a lack of isolation isolation allows the code to be testable but there's something else there's something far more important than that um isolation allows you to reason about it um we are surprisingly good at reasoning about certain things um as long as they isolated from others but humans can be easily flooded with too much connection when you have to take in take on board too much you will not cope with everything you will Overlook something so there's this idea the more we are able to isolate things the more we are able to reason about them in confidence this is why people bang on about modularity for and have been doing so for decades it's not for mathematical Elegance it's actually the fact it respects uh Being Human um other qualities that may help us immutability is one of those things that helps us things being in sequence it turns out we're really good with this happens then that happens then the other happens but that is at one level it feels like it's at odds with our desire for concurrency but we are good at reasoning sequentially um and one of the ways that we can reason about this and int and kind of have the best of both worlds is by the introduction of asynchrony um but obviously not everything that is asynchronous is easy to comprehend that's my my favorite one recently 10 things you'll find talking about asynchronous operations uh beautiful um just one of one of the best I've come across uh in terms of it captures it captures it rather elegantly um so there is this question if I take operations that are synchronous and I would like to make them asynchronous what do I have to be aware of well obviously there's a question of ordering um uh how do I pick up results and we talk about uh futures um imposer for um immediately return a virtual data object a virtual proxy effectively called the future also known as an IOU um to the client when it invokes a service this future only provides a value to clients when the computation is complete now you can take future-based computation a very very long way I propose not to because I also know that sha will be talking about that way way more deeply than I'm going to but I'm going to introduce the basic concept here if we do this sequentially we get a result from a function now if we want to do something after it that is independent then we've just forced forced this into an unnatural sequence um there's a thing I want to do call a function there's another thing that I want to do and then I probably want to combine these things later um I could switch them around but same issue so what we do is we separate this stuff out um and we say okay uh let's launch the function asynchronously I'll pick it up as an IOU I'll go and do other stuff and when I actually need the result then I'll go and get it this is the kind of basis of where we can start taking certain data flow ideas uh I will interject at this point though I think the um C++ 11 Syntax for this sucks completely I had a model that I published a number of years ago actually made it into proposal form where I decided that well I said basically everything should be a function and we should follow a function model and the idea is that um a future um is effectively a thread or is effectively a function object thread is a verb you take a function and you thread it it is not a thing it is a verb that you do to something something what you get back is um something that allows you to join it and pick up the result and everything is done as a function you thread things using functions the result of calling one of those is itself a function if you want the value then that is itself a function so you can use that wherever function objects are expected and you can extend this model quite a lot it's it's quite a regular one and fits with the C++ style um this whole get thing doesn't really appeal to me however that's that's a by the buy um but there is a there's a kind of an idea there that these ideas uh there's a that these uh practices have been around for a very long time and people have got different ways of expressing them and different languages have different ways of expressing them but if we go beyond um go beyond the future which sounds very dramatic if we go beyond the future I want to pick up on this General observation from Russell Winder uh instead of using threads and shared memory as our programming model we can use process as a message passing process here just means a protected independent state with executing code not necessarily an OS process now we have a lot of terminology C we sometimes refer to such systems as message passing but it turns out We've Ended up with lots of terminology um for the same constructs and subtle Shades and variations between them uh which I'd like to explore um but Russell points to two things um languages such as erlang and okam before it erlang uses the actor model and Aram uses something called CSP um have shown that processes a very successful mechanism for programming concurrent and parallel systems and such systems do not have all the synchronization stresses that shared memory multi-threaded systems have and more importantly they do not have the reasoning challenges um that such systems have in other words the the code is very localized it feels very sequential it has this idea and this is an idea I I guess I've been pushing for a while by various names um it allows you to think in a sequential bubble I said that sequential reasoning is something we're quite good at what you want from your code is that each part of the code is sequential and has no idea about um the world of concurrency um the construct of threads or anything like that um in essence it becomes the idea that any piece of code you write is therefore more easily testable because it itself is um uh sequential and simply reasoned the idea is that you then through a compositional approach whether it be wiring whether it be coordination language or something else you then say and here is where we introduce the concurrency we take our um rather simple modules and wire them together but there is this idea that wherever you are the world should look sequential and if you're getting data then that data arrives as if it were events or it arrives because you pull it from a Channel of some kind but you don't have the idea of I am interacting with another thread you try and avoid that kind of um uh structure in one sense uh this is uh uh what can be called a virtual uniprocessor um for a number of uh a number of decades uh computer science spent a lot of time talking about virtual multiprocessing how to give the illusion um of parallelism on a single core whereas virtual uniprocessor is you've got massively parallel hardware and you like to give the illusion of sequential uh reasoning and that term was first applied to the best of my knowledge to describe the human uh brain uh we have this beautiful illusion of a stream of Consciousness on this ridiculously parallel hardware and it turns out that's not a bad way of thinking about stuff so you want your code to have that kind of feel to it and these models generally give that uh um generally give that kind of feel so the most fundamental construct let's talk about Q's for a moment um Q uh you got producers you got a producer there you got a consumer there you got a cure in the middle um so the producer and the consumer represent activities that are uh decoupled from one another with respect to time um most um and the most obvious concept of time in this case I'm talking about is um uh threading um but decoupling Through Time is what we're talking about I can actually have a perfectly sequential system system where I have um a producer producing into a queue followed by a piece of code in the same thread um that unpacks that queue as a consumer so the idea is when we say decoupling through time that can mean true parallelism but can actually mean we've ordered things um uh uh sequentially or we're doing things by a uh uh time Trigger or whatever the idea is that we're trying to create a model that almost doesn't care at some level so this is a simple onetoone relationship um this guy's doing something maybe he's doing IO this guy's doing something else you know fine now that's the simplest Arrangement that you can find and we're going to come back to it later what you may find um is that you're taking things from lots of different sources there are lots of different uh places you can be getting your uh input from or alternatively um these um these guys are uh uh these guys are running at different speeds and therefore you would like to uh past them so you got an end to one Arrangement here or it may be the other way around um and there may be a logical thing maybe you've actually you got ports out here so on that you want to uh send things through so there's reasons either physical um uh or no physical or physical physical in the sense of um uh Communications or physical in the sense of time so you can decouple them like that now that's an n to1 and a 1 to n Arrangement uh you may also find but I would generally recommend that the N not be the same on both sides um m2n you may find that um it's uh makes sense to serialize things there may be a lot of stuff coming in on the left hand side again IO rather than computational tasks probably makes more sense for this Arrangement and on the right hand side um you want some kind of fan out to different tasks and other configurations use more more than one Q okay um and likewise on the other side and then obviously I guess the degenerate cases where you realize actually you've just got a onetoone Arrangement just lots of it okay so you can keep combining these and crossing over you can have one thing poting to lots of cues and lots of things picking up on the other side there's lots of Arrangements I could just keep copying and pasting this slide to generate all of them but the idea here is the Q is the most General construct at this point for decoupling in time and it is the performance and characteristics of your system um that will dictate which configuration you're interested it now from a Cod perspective let's try and want some of this together and and get a feel for what this might look like if we create a cue of anything so make it generic so we've got a template there um I'm going to start with the simplest idea is that I can send something and I've got a choice of uh receiving it I'm going to do this as a a non-blocking receive a try receive I can pick up a value um if there's nothing there to receive um then I will return false um and uh if somebody's trying to if I assume that I've got a very simple um locking mechanism well let's do it sequentially first um if there's nothing there then I'll get back false I'm just going to use the standard Library deck uh type so um that's going to be nice and easy from that point of view if you send you're just pushing back and and if you try well if you try and receive um if there's something there we do something with it otherwise uh we don't it's as simple as that we return false so that all works rather nicely and is profoundly not sequential or rather profoundly not concurrent uh uh in any way shape or form not safe so we reach for our bottleneck um throw in a mutex and we say okay now we can start sharing this between arbitary number of um senders and receivers and that allows us that uh and this works quite nicely for the um non-blocking approach uh and this may be sufficient this may be what you want um and so we use a scope lock um to ensure that we have a uh a critical section that's automatically locked and also um exception safe and we kind of do the same on the other side um but now we've got two reasons why we may fail to return a value previously it was if I try and receive and there's nothing there I return false here there's now another reason I tried to receive and either there was nothing there or um something was being uh something was being put in at the other end now if you know more about the characteristics of your system then you can start separating uh locks for your ends but I'm writing the most generic form of Q here I cannot assume that the ends are always going to be far apart I cannot make certain assumptions uh in this case but I'm giving you something that uh reasonably uh Works reasonably well so um that's the basic construct now the next thing we might want to put in is a receive um uh that uh is a blocking receive sometimes we don't actually want to do anything else there is nothing more for this thread to do um I don't want to just sort of say I tried to receive and I failed what do I do now I'm going to spin lock no that's probably not a good idea perhaps this task exists only to work with values so um there are further layers we can put on this but I'm going to leave this at a fairly raw Q level but we're still hiding the lock and I want to be able to block on that receive until I get something now we could go further so I'm going to have a throw in a condition variable there we could go further and also have a try received now I'm going to make a point here I'm not going to explore it much further than this um because I did mention the Shakespeare quote everything is a is a is a slave to the Limit um you don't really want a queue like this in production code for the simple reason that there's no bound on the que if something goes wrong if you've if if something goes wrong you've not anticipated it you can use up all of memory which is really not what you want this queue can fill up to infinity or the amount of memory you have available whichever comes sooner and I think I have a pretty good idea which one's going to come sooner um the idea is you can end up with if you end up with a locked rece if you end up with a locked receiver and you're still sending that Q is just going to pile up that's why people care about Q lengths and production code so really you actually need to have the idea of a bounded queue um these are great for prototyping things and they will work fine in certain classes of system but either you have to have a hidden um a hidden constant or you need to be able to parameterize it yourself and say no there is a maximum size for this we are not going to let this grow until uh all of our resources have been exhausted and you can choose to embed that within the Q construct or put it somewhere else in the code but it has to exist somewhere do not assume that they should be unbounded in production code however to keep things simple I'm just going to say right let's not worry about that I've talked about the bit that sort of there's a heads up there but um the next thing is um yeah there's some code here I'm not really going to worry about that it just uh does the right thing um we've got a condition variable we will continue blocking um uh or suspending while there is no um content to receive and when there finally is we'll actually do something and actually pop uh the result now there's a few other bits and pieces that we can start adding in um to refine the code I'm not going to worry about those I want to go back to the idea that we've got a basic function in Q I want to go back to an idea that earlier on I mentioned we'd be coming back to the onetoone case um there is a particular name the idea of Q is that we can have a Q allows many to many one to one one to many many to one a channel is a special case a channel is UM and we borrow the terminology um from CSP uh communicating sequential processes it's a single pointto point of contact go also uses the term Channel um but is is perhaps not as strict it really just means Q at one level um uh but it borrows some of these ideas um but strictly speaking if we have a channel it is it is there is one sender one receiver it is a dedicated line of communication it is a dedicated Q um which allows certain simple optimizations I can have a channel I can just basically say that queue that I just showed you I'm going to go with that or alternatively I can create something else that's a channel and have some rather clever low lock implementation that takes advantage of our known limits and the fact that there's only one re there's only one sender and one receiver we can start taking advantage of this knowledge whichever one we do I'm just saying that the configuration I'm interested in here is this one that there is this dedicated um receiver um so we're going to take a you know one of those great problems of uh uh uh software developer development that taxes everybody's minds and imaginations U fsbs um and uh is not exactly the hardest problem in the world and there's I'm not going to look at clever ways of parallelizing it uh I just needed something for the code to do um so here is the thing for it to do um if a number divis is divisible by um three and five uh you get Fizz buzz by three Fizz by uh five Buzz otherwise you just get a stringified form uh of the number that's it that's there's nothing interesting parallel or whatever about this that's not what I want I just wanted something to chew on um the parallel bit um comes in here um what we're going to do is we're going to have a we're going to set up a fizzbuzz server because that's what everybody needs it's called Fizz buzzer okay what it's going to do is it's going to take an input channel it's going to have an output channel uh on the input Channel we're going to see vages on the output Channel we're going to send strings nice and simple so now from this point of view if we look at this piece of code there's absolutely nothing sequential or there's nothing parallel or nothing concurrent rather about this piece of code um it is a you know I'm just basically taking in uh a channel and uh another Channel I'm going to use both of those I'm going to just run around and do stuff that's fine this is actually quite easy to test um I'm going to set up main we going to have a channel out a channel back um we're going to launch that as a separate thread um I don't have to um there's absolutely nothing here that's of Interest here but um uh I'm going to go and send something and then I'm going to get back a result and I'm going to print it out really nothing nothing exciting going on here I can resequence I can mess about with the syntax a little bit and make it feel a little more C+ plusy but what's more interesting here is I'm able to decouple and have a thread that's out there waiting for Stuff send it a whole load of requests and now the channel the return channel the back channel is now full and then I pick up the results separately so now we actually introduced something some slightly more meaningful concurrency uh not particularly meaningful but the idea here is I'm able to rearrange the code um from that point of view the channel concept a specific out and back approach is a really s simple way of decoupling pieces of code it allows me to actually fill up stuff um Prime something for testing so you know some people might say I'm mocking it well I'm I'm not mocking it at all I'm just simply giving it a pre-loaded queue I can get rid of um uh and rearrange this relatively easily it's a matter of wiring uh it doesn't mean you can't get deadlock yes you can um but it means that it's now down to the wiring rather than uh the core logic that's going to give you that um and is there anything else to say about that no that's that's all the fizzbuzz is going to do in renewed syntax so let's look at a particular application and again the terminology um pipes and filters is really built on channels but we talk about it slightly different again a pipe is the idea of a dedicated point-to-point um piece of communication um very powerful from a general point of view um in terms of thinking about composition um we divide an application's task into several self-contained data processing steps connect these steps to a data processing pipeline VI intermediate data buffers we see the pipes and filters model um allows us uh uh the introduction concurrency but it also allows us expressiveness um we find that many people you can see in the Java um streams model um without introducing concurrency it's a very profound and useful way of reasoning about a task because it is based on a functional programming model and a lot of people don't realize this but this rather good point was made by John pie um uh a couple of years back um concatenative programming is the style um it relies on function composition rather than function application um and this is the basic reason Unix pipes are so powerful they form a rudimentary string based uh concatenated programming language it's a very simple idea each step it's a compositional step you're going to take data you're going to process it you're not going to worry about you're introduce side effects on the data because you pass on new data to something else um and it is a particularly different style of functional programming it should that is is not the same as the classic applicative approach and there's a lot of benefits to that without concurrency but we're going to throw some concurrency at it um so I'm going to pick on um sort of a very simple idea what we've got here is we have some kind of source um and the arrangement is that we have a filter then we maybe have another filter um and then we have a sync and they're connected together um using these pipes I'm going to pick a a not particularly meaningful problem uh although this is one of those ones that came out of um in um a rather interesting conversation about Friday the 13th we had a Friday the 13th last week so this seems timely um if you are superstitious um um then we should have a proper conversation but that's nothing to do with C++ um if you are superstitious and you fear Friday the 13th uh then you might sit down and write some code to decide when the next Friday the 13th is uh you might do this in a kind of raw SE approach um we're going to move this to C++ and uh not a lot of change actually um the C++ Chrono Library actually um if I were to Port this to that I would end up using more keystrokes so I'm not going to do that I'm going to just leave us with the raw stuff this will find you the next um the next Friday the 13th after the one that you Prov uh the date that you provide so so this this is all good now not um so what we're going to do is we're going to break this one down um instead of expressing the logic um uh uh instead of expressing the logic this way I want to find I want to get a steady stream of Friday the 13th and what I'm going to do is I'm going to turn this into a pipes and filters Arrangement I'm going to start off like this I'm going to say right first of all we need to generate all the days of interest you give me a date and then we will just generate we will Loop forever then what I'm going to do is I'm going to filter in I'm going to select in the 13th of every month okay so this is how we do this is a simple way of doing and with uh pipes and filters okay uh what I'm going to do is I'm going to include in select in every 13th of the month and then I'm select in all the Fridays and what I get out is a steady stream of Friday the 13th which I will then display so I've broken it down into a pipeline um and so we're going to wire this up we're going to have a a channel for all the days and we're going to arrange this so that the days are from the start yeah unfortunately the uh uh the outlining here has got bleached out by the um uh uh projector um we'll have days from the start we'll wire it into to days and that's just going to go on forever actually they don't go on forever they tend to they will hit a limit it turns out disappointingly um uh we're not allowed to compute to Infinity uh on this but you know what we're going to do is just keep on looping generating days we move forward a day at a time then we'll wire up the next bit by saying okay you give me all of those days that's the input and then I'm going to give you the output which is only the 13th so I'm going to just select in read a day if it's the 13th then I write it out otherwise I'm not going to then the next one I only want the Fridays and we wire that one together and then finally we actually display it and we pick that stuff up so it's a nice little pipeline uh progression there um that will give us all the Friday the 13th U of interest and there is a a simple idea here we can actually we can rearrange there's a few things that we can rearrange we can actually I've done this in a more classically CSP Style in the sense that what I've done is I've created functions that take channels it is possible to invert this relationship um and say Here's a channel and I'm going to associate behaviors with its ends um which is a sort of an inversion of the model that I've got here but I'm going to leave that one uh to one side there's quite a lot that you can do with this once you start down this road so there's sort of an elegant um sign to that if your architecture fits that that's great um you know very easy to reuse um far easier to compose and work with than other pieces of code but there are most interactions that we want to uh probably introduced threading into don't really fit um a a pipeline model a one-way data flow we might need some interaction uh and at this point uh this thing that I did many years ago for uh my Master's uh thesis was um actor based systems and I one of the things I worked with was a language called abcl um uh actor concurrent language or an object based concurrent language depending on which version you read um and when we talk about raw multithreading uh Andre alexandre's quote is one of my favorite ones multi-threading is just one damn thing after before or simultaneous with another um but what is actor-based computation um active based concurrency is just one damn message after another you are in this sequential bubble everything is sequential you just receive something you handle it you pass it on but that's obviously doesn't have a unique claim to that so let's have a look at one of the classic approaches which is Monitor objects a monitor object is the way that um Java decided to uh bake into the language every um every object is effectively a monitor object which means that it can be uh it has a lock over the whole object and it can be synchronized every method can be synchronized or part of the method can be synchronized in execution and there is a locking scope it's the idea of passive data objects that have such synchronization built in um so that's great because that shouldn't be our code it should be somebody else's code but uh it is very lock based and it doesn't work well in a compositional sense but it can be okay to write and if we imagine something like a phone book on which we're going to provide basic operations an update operation uh for somebody's name and number a drop operation to drop um an entry and a find operation that optionally returns a string if nothing's there so optional it is now 2017 optional is now finally in the c or will be in in C++ 17 um so that saves all those null things or using empty string as a marker so basically uh if we find the name and it's there we get a result if we don't um then uh uh we're told that we don't have a result and um this is in um uh optional appears in other languages sometimes called different things fallible maybe and so on so got that structure we're going to have a simple mutex model like we had earlier on um and we can go ahead and we can build this stuff up we can up date it's an upsert operation we can drop um and then we've got the find operation so in action what we're going to end up with is something like this we create a directory phone we have our phone book um and in another thread we go and look for Thomas Anderson Thomas Anderson is not yet in the phone book um so we've got an updating thread so we got um two threads of Interest here the F the directory thread is actually passive um uh we're going to go and update that next time we um try and find Thomas Anderson in the in another thread um both of these operations will be um ordered in some way and mutually exclusive so therefore we're guaranteed of some kind of coherence and we will get um uh some value we go and look for Neo Neo's not in there um we're going to update with Trinity we're going to update with morphus we're going to update with uh we're going to drop Thomas Anderson we're going to add Neo um now when we go and find Thomas Anderson will not be found um but Neo will be and uh because he is the one so we've got a simple model there so monitor objects are very attractive and very simple at that level there is another approach which for reasons of time uh active objects we could go into um but I'm going to leave that out for your comfort um but I wanted to put them in there why am i showing you something and then saying I'm not going to show you it I'm putting that in there because a lot of people confuse active objects and actors they are not the same programming model they are potentially related but they are not the same programming model um the actor model has a different Outlook the actor model I'm not going to show you a full actor model I'm just going to build it out of the um uh build a very very very basic version out of the Q construct and the standard Library thread we had earlier uh also in C++ 17 will be um standard any um a variant type uh there are actually two variant types U this is a universal variant type uh and what I'm going to do here is that phone book you'll notice I've changed it into a function it is uh what we're going to do here is we're going to bind it together we're going to say look here is your Q you have an Associated Q um and anybody can talk to you using this que um we can be more specific about the message set but I'm going to leave it as open and generic message set here I'm going to say well you can have um an entry um either you're giving an entry or you're receiving an entry in other words um it's a name and a number you can have a no entry either you're telling uh the phone book please I don't want this anymore or you're returning this entry does not exist and you can have a find request uh here is a name and here is the return address please send it back on this CU okay so there's the idea that somebody can talk to a running function that is that is the basis of the actum model it's not that we are creating a classic object and putting locks in it it is that we're creating a function and we are now communicating with a running function this function um uh it doesn't reveal its own State its private State really is private it's local variables in fact let's actually have a look at that here is the phone book um here's the scope it's going to get a bit Messier you can tidy this up but I I realize that for reasons of time well that's really what this whole talk is about isn't it time uh and temporal decoupling um but for reasons of time I'm not going to go into the details of it so I'm going to do the kind of the raw uh ugly almost assembler likee version but show you the the basic construct here is the private State this was previously private um actually private within an object but this is now just a local variable um the function is just going to keep on requesting I'm not going to put any termination it's just going to Loop forever um or control c um and the only operations that it can do is to affect entries there's no there's no kind of clever thing that somebody can do to get their hands on your private State and that is the private State entries so now we're just going to repeatedly handle requests um we pick up a request uh now comes the ugly bit is I now have to go and do a bit of type dispatch this is the bit that you can tidy up with a little bit of uh jiggery pokery but um what we're going to do here is we're going to pick up is it an update have I received um an entry if it's an update then I update I update the entries with update name and update number um on the other hand is it a drop request am I being told no entry if it's a drop request then I will erase that entry um uh if that's the case but the the bit that's interesting is um notice neither of these requires interaction when another thread another actor is basically communicating with you and say I'd like to add this entry or please drop this entry they're not expecting a response it's uh it's asynchron without any kind of blocking return there's no Futures involved they're doing this but now we need to talk to somebody and that's where uh the find is quite a good example um somebody's going to send us a fine request please find us NE or Thomas Anderson or whatever if the entry is not there we need to tell somebody it was not there if the entry is there we need to tell somebody we need to talk back in this case the return address is useful uh an important thing that is often overlooked in actors is you don't have to actually return the call to the caller you don't have to return the result to the caller what they can do is they can set this up and this is perfect decoupling I'm going to make a request of you you talk to that guy over there okay it's not an actual return address it's a really a forwarding address um and it may come back to the requester but it may go on to somebody else so what we're going to do here is we've got this if it's uh if it's not there we're going to um uh use the cue that was given to us and say look there was no entry on the other hand if it is there there was an entry so what we've got here is a proper message handling Loop um but uh all baked into constructs that are now available uh in the C++ Library plus um the Q construct that I added in uh earlier um in execution that's going to the call we're going to move away from the idea that we're dealing with functions we're going to do something that's a little more uh message like um so I'm going to set up a directory then I'm going to launch um a thread that holds the phone book um with the directory uh and then I'm going to say right okay I've got a queue and I would like to find Tomas Anderson please return it here um we're not going to find anything so I'm actually going to pick that result up um what I should get back is no entry Thomas Anderson in another thread we're going to have an updating thread um so we've actually got three threads running here um we're going to have um something updates with Thomas Anderson one um back in the uh requesting thread um we're able to Now find it we pick up a result and that should be the result that we get and we can go through at Trinity Morpheus U drop Thomas Anderson and add Neo because he's the one and we can now find Neo and we get that back and what we've done there is that that is the the raw ingredients if you like uh this is the actor model broken down to its most fundamental level and um clearly with a little bit of imagination and if you've got experience of um actor models in other languages you can immediately see the opportunities for wrapping that up but just based on a que and a thread we can actually affect this model um and and note where it goes and what style uh it gives us um that our messages become first class objects rather than methods and we get this inversion um that the function itself becomes a running object that we communicate with okay so sort of bring that to a close there's an awful lot in there and it's definitely time for a coffee um but I'm going to go back to John karmac he said you know it's a point there is that what we've ended up with is a number of things that are actually relatively functional in their nature um functional style makes the state presented to your code explicit which makes it easier to reason about and in a completely pure system makes thread race conditions impossible the idea is that we are explicitly not thinking about I have data that I wish to share we are thinking about there are things to be done who do I talk to um and uh that kind of approach isolates it's a it's a it's a slightly different philosophy but using the same basic language you end up with a very very different architecture and one that is more composable um so hopefully uh the one thing we've learned about thinking outside the synchronization quadrant is that our default desire to put locks around everything um when we care about speed um is going to be thwarted um because you know the thing you always have to keep in mind is is all computers wait at the same speed and this is the problem that we've been encountering as people have been trying to scale things up uh what they've leared is a number of lessons sometimes the hard way and particularly now that we are moving from uh the moment I would sense that we're moving a little bit back from operating system processes to threads uh because we've discovered we have a remarkable amount of memory available um this is worth keeping in mind and not to say oh now I'm in the same process I can just go back to my old SE like ways of sharing everything and just adding locks no the lessons that were learned uh pushing things out where you genuinely couldn't share them those are valuable and uh worth keeping in mind I hope that's been useful I'm around uh for any questions as I'm unpacking um uh please feel free to ask thank you