Thinking Outside the Synchronisation Quadrant - Kevlin Henney

we like yes excellent good good afternoon and so what we can talk about for next hour is thinking outside the synchronization quadrant which means I have to say some meaningful things about what I mean by that terminology and this talk is placed in the ceaseless fast track I would say that probably Hospital relates to C++ specifically and the code the code that I'm going to show you C++ some but the principles that I'm looking at are actually far more general so so it depends on what you're coming in for there should be something here for you and yeah code architecture architecture good let's talk about architecture so there are a number of different definitions floating around the one that I generally find the most effective the most useful the most constructive this is one from Grady Booch 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 what is the natural scale of software unlike building architecture it's not as obvious 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 we never do that if people say you can't do it then its architectural okay and therefore that means that it can relate to the smallest language feature as well as more obvious major technology choices now one such thing that shapes the system and is non-trivial to change it's clearly something like concurrency the presence of concurrency in any form now one of the things I find interesting about concurrency and parallelism and our various definitions of all of these is 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 into 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 threats so in other words what I found interesting is that was with the the junior programmers but in another company with a whole load of advanced developers who were Clint who actually wanted to discuss higher order higher level mechanisms it was fascinating if you catch people off-guard threads are how I didn't mean to say threads I'm it 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 for introducing concurrency in any code base and they are powerful like a go-to is powerful it was a an interesting proof in the early 1970s that go-to is 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 it expresses concurrency the problem is they are too primitive they are too raw they are effectively the jump statement at this level so we acknowledge that there are going to be threads but that may not be where we want to write our code 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 that's kind of interesting so hang on why are you guys doing threading are we 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 threat the purpose of a lock is to eliminate concurrency so if your goal is to get some of these then it's fairly clear whilst that may give you it this take us away and this is a a struggle that we often have there's a lovely quote and I realized I've just I just realized I've forgotten to put it in this talk really from David Boonton Hoff who wrote the book on POSIX threads and he said you know what we made a mistake calling them you Texas we made a mistake adopting Eska Dijkstra's 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 oh you need to put a bottleneck in here mm-hmm doesn't sound quite so good whereas mutex has it's kind of like lovely width of computer science about us 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 know adapt it because when it comes to code what we do realize it's about the ability and skill of wasting time so let's talk about this thing with synchronization quadrant and actually I found that some classified things simply for a team a few years ago we went 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 for them if I split up on a flip chart and then realize actually was a really useful and classification mechanism this let's just break them in a quadrant diagram first of all it's the afternoon so your metabolism your brain and everything just gone into very has gone into a sleep state 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 as with most quadrant diagrams is only one quadrant that's on a very very good or a quadrant that is very very bad now I'm going to I'm gonna break this one down to mutability there is an axis immutability 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 unsure or chair now you can you can subdivide this far far server you can say 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 the shared quadrant 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 read nature's color for bad or in Far Eastern cultures and contractors colored celebration okay this is the synchronization quadrant okay you have mutable data and you have state 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 it's just that the synchronization either belongs lower down at the lowest level actually we're 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 your 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 I'm and I have wondered about this for a while and I realized having I I I got a very very very long time ago I got a master's degree in parallel computer systems and so you know you kind of think everybody knows this stuff and actually turns out that they don't and that you just happen to be being exposed to all this good knowledge and it turns out as the as we tracked into the nineties and on we ended up going into this quadrant over here and I often wondered about this and there's a simple cultural and historical reason before threads became commonplace all our code is on the left-hand side because quite by definition you cannot share between threads of you and you have one thread so all was over here and for historical reasons are in our imperative background and resource constraints and so on everything was in the top left hand corner a few things wandered down to 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 language construct as a library construct as a feature in the operating system we ended up naturally moving straight over to the right with our code and that led problem if you look at books that are written in the 90s up until the early 2000s whenever they introduced concurrency they follow this idea they're mostly about the locks how do we lock stuff indeed a lot of the literature published in the 70s and 80s was along these lines about how do we lock and all the constructs and proposed language mechanisms are all in that 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 accepted so yeah we've ended up unfortunately with a little flock of code over there so let's talk about the qualities of such code and when you're dealing with a code when you're dealing with code they're a kind of simple right-hand rule that I quite like to use 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 reasonably simply and functional behaviors operational behaviors and developmental qualities okay so in other words the functional and operational qualities functional as in the semantics the operational as in resources as in what many people refer to as the illa T's that are not related to the development time the development time stuff is your experience as a developer most other to 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 kind of an easy way of kind of reasoning about your code if you add functionality you move along the functional axis okay if you fix a bug you move along the functional axis as well you know you had a deficit of functionality now you make up for it so it's a nice simple model but I want to start first of all with the operational axis this idea that the qualities of execution are one of the reasons that people are motivated to introduce some form of concurrency into their code um it turns out Shakespeare was on this one as well I mentioned Hamlet this morning for memory management but he's here talking about resources monstrosity and Lovelady 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 in a bit 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 and there are costs to the laws of physics it's a rather good blog came across recently link is at the bottom what are the costs of various operations from the kind of CPU perspective and obviously this is going to vary from processor to process and so these are defined as ranges importantly it's logarithmic I rather like the display the idea of light how far does light go travels during the time that this operation takes clearly he has a smaller laptop and me because it's not the diagonal this one this is one light nanosecond I often use that as a measure when I'm telling people so I was delighted see he's done the same thing that's one light nanosecond which sounds you know terribly fast until you realize that gives you a cycle time effectively that's the distance over there that's a cycle time of one gigahertz which is not so smart it's really you exhaust the possibilities of one gigahertz in a very short physical space and then he goes through these are all of the magnitude and the thing I want to draw your attention to that context switch that's generally more expensive in terms of cost the raw direct costs lie between a kernel call and a C++ exception throw and catch okay stack I'm winding the whole bit but his he says in the article there's this is quite difficult to measure because there are loads of indirect costs that go on you can and it turns out that 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 linear improvements what they suddenly discover is they are not getting them there's a cost involved there are lots of cost effectively our coordination costs so if we take the idea it's to understand whether or not you want to introduce introduced threading we take this idea completion time for single thread and we're working on some tasks and the classic view of division of labor I'm going to throw in threads at this okay that's brilliant if everything is independent and everything is for free and if you remember at school you probably did some projects of electronics at some point and those is rather brilliant 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 it's not brilliant you're at school and you get superconducting wire 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 even without worry about that though we haven't even looked at the nature of the task we are assuming that everything is perfectly independent and it's not going to be there is some portion that you can do in parallel and tasks have independence ease if they need to talk to well on the share data do whatever then there will be some portion they cannot do in parallel so a lot of it depends on on peak misses and as well we haven't even 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 I'm going to give you worse case and over simplified view but we get a shape out of it into 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 but really you don't want to be in this kind of this kind of mess let's let's assume that we've got some kind of concept of an average communication overhead average is a very difficult concept to apply in this case but let's just say we've got some kind of typical communication overhead I think it's going to give you a curve like this one that basically means is the minute you introduce threading into number of minute you to find many tasks across threads you get slowed down not knots not Universal but people are often surprised at how much benefit they do not get this is the third this is the first thing you need to remember it turns out that if you don't have the cost of a context switch then just being able to do things really fast sequentially turns out to be an absolute winner we see this classically in the sense that historically X Windows servers 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 and there is no 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 and 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 if you want that Shores doing at all later and he will talk more about stuff like that unless you've radically changed the slide since I last saw it so I'm just scraping the surface here in terms of the bits that you can easily do and touch ok just with these constructs so we have this and there's there is this question of locality and cost the landscape has changed as well every few years we end up with a shift in our architectural defaults the thing that developers think oh that's so obvious you always do that and it turns out it's not so we're at this point Lovelace um this is a blog from two years back and Drake this very simple task command-line tools can be over 200 times faster than your Hadoop cluster and he basically did this basically did this particular number crunching task not particularly big data but for some people it would be Big Data obviously what we consider to be big data as a function of time you know once upon a time one megabyte was quite big data so there is a point here that people have got into the habit of saying write distribute that you distribute that across multiple processors to the cloud with it to the cloud with it so we wrote this in Java and then he wrote it again using Bourne shell and ran it on a single machine because it turns out the thing we now have it used to be cheap processes across the 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 so this this is a key point we've got an interpreted language here but because it's able to use local memory brilliant really benefits now speaking of that a time to encode and do a very simple 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 I'll give a very simple kind of MapReduce approach we're going to map some operation called mapping across a number of tasks and I've just realized I've got over did that creating that live stuff you spot the bugs and you can fixa bucks you saw nothing okay Kenny and that's good there you go right so we've got an that and so then we end up with a whole and choreography it's all the sequencing is gone whereas that one right there we go Castle I'm after there's a whole load of noise that we get from C++ in it's the kind of classic form 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 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 sure I'm going to hit the threading really really hard here and fire off 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 what everybody else calls reduce or false so we've got that okay um now there's a few things we can do to tidy up here one of which is c++ 14 I was going to just deduce the result type and we're good with that the c++ concepts technical specification allows me to get rid of all of that which is marvelous so that Tiny's it up a bit then if i take on board the parallel technical specification i can now get a parallel version of full reach that can vectorize I can give it a policy I can say write vectorize that I've also got one for accumulate that I can now do a reduce so reduced it get spelt correctly at some point and we've got that so if we look here and relate that the bit that can really I'm doing the reduce around doing the reduction I said well let's assume that we're that our operation will actually work I'm missing an argument in that I've just realized will actually work fine one particular point of view there is all the concurrency that we can really squeeze out of this is going to be the for each bit the last bit most likely better off done sequentially so in that sense that code is from the point of view of the synchronization quadrant the first part assumes that nothing is shared each piece of data is independent therefore we're able to fire everything off in parallel so there's no locking there there is a synchronization point at the end but that is hidden from us and then again for the last point but portion that can really be done in parallel P is the first part okay so there's another aspect to functionality people often throw threads at their code and because they want they want to express functionality why does that make sense only as performance actually we use threads for a very long time before we got multi-core in fact one of the first times that I was using threading was definitely well well before 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 something dependent I would like to be able to say there's this going on and there's this other thing feel free to leave them as as a web so not getting true parallelism but 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 by dividing up the tasks manually and creating effective in my own scheduler so there are motor there are reasons for doing this however the expressiveness is the bit that gets us and this is where lurking in the top right-hand quadrant causes us problems a large fraction the flaws in software development are due to programmers are not fully understanding all the possible states their code may execute it John Carmack of id games in multi-threaded in a multi-threaded environment the lack of understanding and resulting problems are greatly amplified almost at the point of panic if you are paying attention in other words we struggle to reason about states in a code base we struggle more when their 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 would not reach some Zen state yeah there is something wrong with you if you aren't dealing at this level it's like there's a lot changing and there are threats you need to take a very rigorous approach to get away from that sense of panic so it's most common example best expressed here and say Myriad's of concurrency city where Green pretty is grasped the girls and are it's things on our sequence we have the problem of race conditions this is why people often say yeah this is why I need locks the problem is that we have this programmed into us to such a degree that people we people do not question why they have locks and I have this conversation with a group of 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 I can't looking at each other and they said well yeah because because we got threads and as 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 well yeah because we're sharing data I said yep you still have not given me a reason why you're locking and they're kind of looking at each other as if as if they were my teenage son you know in other words you're an idiot yeah and then I said okay so what but why does sharing stuff between threads cause problems I 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 let it to last that should have been your opening sentence we've got changeable state and it's being 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 talked to program is the opposite way and so therefore we fall into this default way of thinking so there are other surprises to be had when we start showing lots of things locks mean ultimately you go end up with deadlocks and there's a really good summary of some Tenenbaums points and the site that found several ways to address the problem of deadlock just ignore it and hope it doesn't happen 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 could be in and the speed at which it runs then it gets more exciting and there are in turn there are also a lot of systems that a lot of threaded systems where these problems were India started to happen with code that had threads and been perfectly fine for years but they've been single core they hadn't actually they'd managed to sidestep the actual issues and there are some really subtle cases that that can cause you these 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 but there are the words there are the ones that happen in a far worse sense we have to restart the server every minute is not viable so this can work but I'm not going to I wouldn't put money on it detection recovery if it happens take action so people spend a lot of time coming with very clever techniques for doing this dynamic avoidance by careful resource allocation checks use of resources granted enter data there 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 and sometimes people do this by introduce imposing some kind of law ordering or some form of LOC discipline and basically saying this code so as an art 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 synchronization primitives and you're only allowed to call with this object so these become a of conventions and architectural guidelines rather than some happenstance and accidents 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 one of the developmental qualities when we start saying things like threads at our code when we start actually introducing these low-level constructs creating high level constructs what are we getting well what would we want from one code one of the things we want from our code is habitability habitability is not a common phrase that people throw around code I've been very keen on using it for the last years I first came across it in this book by dick Gabriel patterns of software in the late 90s and he makes this observation very simple observation we comply to any code based on any language habitability is the characteristic of source code that enables programmers and so on people come into the code later in life to understand its construction and intentions and change it comfortably and confidently it's very simple idea it's what we would define as habitability in a home environment from a building you want to arrive in a code base and basically say yeah I want this to be livable this should be constable place for me to work in I shouldn't have to sit there and go oh please don't send me into that threaded nightmare it should just be a case flight right okay I understand what's going on this is what we want in software developers could 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 it is uninhabitable you know it makes it makes the rare vacuum of space 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 codes testability is quite a nice one quite fond of that one you'd like to know something about how it works but there are a number of misunderstandings when we start talking about things like unit tests sometimes people have different takes on this and there are different views now one of the ones that 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 sometimes that's to be an indication of something deeper in your architecture but I came across this paper 40 years ago beginning of last year came across it and then twice more later in the year and it's rather interesting analysis of certain distributed open-source systems simple testing to provide my most critical failures looking at actual production failures but the statistic that left out at me is the they actually revealed that something like 77% of the tests of sorry 77% of the problems could actually be revealed with unit tests so over three-quarters of the problems they found could have been discovered the unit tests you didn't actually have to fire up the whole system in order to discover these but that does lead to the profound philosophical question you know when people say we want our code to be unit testable what do they mean and this kind of an implied idea which is which is quite difficult people tend to think of their code like this if anything is a unit test I think our only it's as fast as it shows the code is correct that's not what you get and assuming the test is correct okay I'm going to give you that one again let's assume the test is correct that doesn't show you the code is correct when you used to sales it shows the code is incorrect it's the other way and this is rather important because sometimes people will it gives you confidence but that's not the same it's not the same measure and particularly where you start doing things concurrently you cannot assume that green means it's good 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 in this case you have to be very cautious with it it's a level of confidence but it's not absolute confidence and there and the law of the excluded middle does not apply here it's quite important to keep keep in mind how do we achieve this watch what helps us with testability what helps us get away from that idea of like well I can't really test it because the architecture is so sophisticated well actually is 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 that isolation allows you to reason about it we are surprisingly good at reasoning about certain things as long as they are 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 all about modularity fur and have been doing so for decades it's not for mathematical elegance it's actually the fact it respects you being human 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 and one of the ways that we can reason about this and kind of have the best of both worlds is by the introduction of a synchrony but obviously not everything that is asynchronous is easy to comprehend hasn't my favorite one recently ten things you'll find shocking about asynchronous operations beautiful just one of one of the best I've come across in terms of it captures it captures it rather elegantly so there is this question if I take operations that are synchronous and I would like to make some asynchronous what do I have to be aware of well I'm sure there's a question of ordering how I pick up results and we talk about futures imposer for immediately returned a virtual data object a virtual proxy effectively called the future also known as an IOU to the client when it invokes a service this future only provides a value to clients from the computation is complete now you can take future based computation a very very long way I propose not to close I know that sure we'll be talking about that way way more deeply and I'm going to but I'm going to introduce the basic concept here 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 forces into an unnatural sequence there's a thing I want to do call the function another thing that I want to do and then I probably want to combine these things later I could switch them round but same issue so what we do is we separate the stuff out and we say okay let's launch the function asynchronously I'll pick it up as an IOU I'll go and do other stuff when I actually need the result then I'll go get it this is the kind basis of where we can start taking certain days flow ideas I will interject at this point though I think the C++ 11 syntax for this sucks completely I had a model that I published a number of years ago actually made into proposal form where I decided that what I said basically everything should be a function and we should follow uncle and the idea is that a future 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 singie it is a verb that you do to something what you get back is 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 you can extend this model quite quite a lot so it's quite a regular one of fits with the C++ style this whole get thing doesn't really appeal to me well that's that's a binder by but there is a there's a kind of an idea there that these ideas there's a these practices have been around for a very long time and people have got different ways of expressing them in different languages have different ways of expressing them but if we go beyond go beyond the future it sounds very dramatic if you go beyond the future on a pickup on this general observation from Russell winder instead of using threads and shared memories our programming model we can use processes and message passing process here just means protected independent state with execution code not necessarily in our ass process now we have a lot of terminology collision we sometimes refer such systems is message passing but it turns out we've ended up with lots of terminology for the same constructs and supple shades and variations between them which I'd like to explore but Russell points to two things languages such as Erlang and Aachen before it Erlang uses the answer model and akhom uses something called CSP 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-layered systems have more importantly they do not have the reasoning challenges that such systems have in other words the code is very localized it feels very sequential it has this idea and this is an idea I guess I've been pushing for a while by various names 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 the world of concurrency the construct of threads or anything like that in essence it becomes the idea that any piece of code you write is therefore more easily testable because it itself is 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 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 threat you try and avoid that kind of structure in one sense this is what can be called a virtual uniprocessor for a number of number of decades computer science spent a lot of time talking about virtual multiprocessor I think how to give the illusion 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 reasoning math term was first applied to the best of my knowledge to describe the human brain 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 generally give that kind of feel so the most fundamental constructs about queues for a moment cube are you got producers you've got producer there you've got a consumer there you've got a queue in the middle so the producer and the consumer represents activities that are decoupled from one other with respect to time most and the most obvious concept of time in this case I'm talking about is threading but decoupling through time is what we're talking about I can actually have a perfectly sequential system where I have a producer producing into a queue followed by a piece of code in the same thread that unpacks that queue as a consumer so the idea is when we say decoupling through time that can mean true parallelism it can actually mean we've ordered things sequentially or we're doing things by a time trigger or whatever the idea is that we're trying to create a model that almost doesn't care some level so this is a simple one-to-one relationship this guy's giving something maybe is doing i/o this guy's doing something else yeah fine now that's the simplest arrangement you could find we're going to come back to it later what you may find is that you're taking things from lots of different sources there are lots of different places you can be getting your input from or alternatively these these guys are these guys are running at different speeds and therefore you would like to pace them so you've got an end to one arrangement here or it may be the other way round and there may be a logical thing maybe you've actually got ports out here so on that you want to send things through so there's reasons either physical oh and that physical or physical physical in the sense of communications or physical in the sense of time so you can decouple them like that now that's an N 2 1 and a 1 to n arrangement you may also find what I would generally recommend that the end not be the same on both sides m to n you may find that it 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 body makes more sense for this arrangement and on the right-hand side and you want some kind of fan-out to different tasks and other configurations use more than one cue okay and likewise on the other side and then obviously I guess generate cases where you realize actually you've just got a one-to-one arrangement just lots of it okay so you can keep combining these and crossing over you can have one thing posting to lots of queues 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 queue is most general construct at this point for decoupling in time and there's performance and characteristics of your system that will dictate which configuration you are interested now from a code perspective which Y and Y and summers together and then get a feel for what this might look like if we create a queue of anything so make it generic so we've got a template there I'm going to start with the simplest ideas that I can send something and I've got a choice of it receiving it I'm going to do this as a non-blocking receive try receive I can pick up a value if there's nothing there to receive then I will return false and if somebody's trying to invite a fume then I've got a very simple locking mechanism well let's do it sequentially first if there's nothing there then I'll get back false I'm just going to use the standard library deck type so that's going to nice and easy from that point of view if you send you just pushing back and if you try well if you try and receive if there's something there we do something with it otherwise we don't it's as simple as that we return false so that'll works rather nicely and it's profoundly not sequential or rather family not concurrent in any way shape or form not safe so we reach for our bottleneck throwing a mutex and we say okay now we can start sharing this between arbitrary number of senders and receivers and that allows us that and this works quite nicely for the non blocking approach and this may be sufficient this may be what you want and so we use a scope lock to ensure that we have a critical section of automatically lock and also exception safe and we can't do the same on the other side but now we've got two reasons why we may fail to return a value previously was if I try and receive and there's nothing there I return false here there's now another reason I tried to receive an either there was nothing there or something was being something was being put in at the L and now if you know more about the characteristics of your system then you can start separating 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 in this case but I'm giving you something that reasonably works reasonably well so that's the basic construct now the next thing we might want to put in is a receive that is a blocking receive sometimes we don't actually want to do anything else there is nothing more for this thread to do I don't want to just sort of thing I tried to receive and I failed what do I do now I'm going to spin lock now that's probably not a good idea perhaps this task exists only to work with values so 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 I want to be able to block on that receive until I get something now we could go further so I'm gonna 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 because I did mention the Shakespeare quote everything is a slave to the limit you don't really want a cue like this in production code for the simple reason that there's no bound on the Q if something goes wrong if you if something goes wrong you've not anticipated it you can use up all of memory which is really not what you want this Q 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 soon the idea is you can end up with if you end up with a locked receive if you end up with a locked receiver and you're still sending thank-you is just going to pile up so I people care about Q links and production code so really you actually need to have the idea of a bounded queue these are great for prototyping things and they will work fine at certain classes of system but either you have to have a hidden hidden constant or you need to be able to parameterize it yourself so now there is a maximum size for this we are not going to let this grow until all of our resources have been exhausted and you can choose to embed that within the Q constructor or put it somewhere else but it has to exist somewhere do not assume that they should be unbounded in production code however its keep things simple I'm just going to save like this don't worry about that I've talked about the bit that sort of there's a heads up there but the next thing is yes and Cody I'm already going to worry about that it just does the right thing we've got a condition variable we'll continue blocking or suspending while there is no content to receive and when they're finally is we'll actually do something and I should pop the result now there's a few other bits and pieces that we can start adding in 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 functioning queue I want to go back to an idea that earlier on I mentioned we'd be coming back to the one-to-one case there is a particular name the idea of queue is that we can have a queue allow many too many one-to-one one-to-many many-to-one a channel is a special case a channel is we borrow the terminology from CSP communicating sequential processes it's a single point to point of contact go also uses the term channel like these perhaps not as strict it really just means queue at one level but it borrows some of these ideas but strictly speaking if we have a channel it is it is there is one sender one receiver has a dedicated line of communication it is a dedicated queue 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 as a channel and have some rather clever low LOC implementation that takes advantage of our known limits in the fact that there's only one there's only one sender and one said 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 so there is this dedicated receiver so we're going to take a you know one of those great problems of a software developer development of tanks is everybody's minds and imaginations fizzbuzz and is it not exactly the hardest problem in the world ms I'm not going to look at clever ways of paralyzing it I just needed something for the code to do so here is the thing for it to do the number de visite is divisible by 3 & 5 you get fizzbuzz by 3 fees by 5 buzz otherwise just get a string aside form 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 so parallel e bit comes in here what we're going to do is going to have a going to set up a physical server because that's what everybody needs it's called sous buzzer okay what is going to do is going take an input channel it's going to main output Channel on the input Channel we're going to see vintages on the output Channel I'm 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 can Carolla about this piece of code it is a you know I'm just basically taking in a channel and another channel I'm going to use both of those I'm going to just run around and do stuff that's fine so this is actually quite easy to test I'm going to set up main we're gonna have a channel out the channel back we're going to launch that as a separate thread I don't have to and there's actually nothing here interested but I'm gonna 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 resequenced in tax a little bit and make it feel a little more c++ e 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 the other channel with the return channel a back channel is now full and then i pick up the results separately so now we actually introduce something some slightly more meaningful concurrency not particularly meaningful but the idea here is i'm able to rearrange the code from that point of view the channel concept a specific out and back approach is a really simple way of decoupling pieces of code it allows me to actually fill up stuff prime something for testing so something like they are mocking it well I'm not mocking - I'm just simply giving it a pre-loaded cue I can get rid of and rearrange this relatively easily as a matter of wiring it doesn't mean you can't get deadlocked yes you can but it means that it's now down to the wiring rather than the core logic that's going to give you that and it's anything else oh man that's that's vessel if his mother is going to do so in renewed syntax so let's look at a particular application and again the terminology pipes and filters is really built on channels but we talked about it slightly different again a pipe is the idea of a dedicated point-to-point piece of communication very powerful from a general point of view in terms of thinking about composition we divide applications tasks in several self-contained data processing steps connect these steps to a data processing pipeline firing immediate data buffers we see the pipes and filters model allows us the introduction concurrency but it also allows us expressiveness we find that many people you can see in the Java streams model 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 a lot of people don't realize this but this rather good point was made by John Purdy a couple of years back concatenated programming is the style its relies on function composition rather than function application and this is the basic reason UNIX pipes are so powerful they form a rudimentary string raced I can cancel into programming languages a very simple idea each step is a compositional step you're going to take data you go process it you're not going to worry about you don't introduce side effect on the data because you parse on new data something else and it's a particularly different style of functional programming it should that is not the same as a classic applicative approach and there's a lot of benefits to that without concurrency but in a thread some concurrency on it so I'm going to pick on a very simple idea we've got here is we have some kind of source and the arrangement is that we have a filter then we can maybe have another filter and then we have a I think and they're connected together using these pipes I pick a not particularly meaningful problem although this is one of those ones that came out of in a rather interesting conversation about Friday the 13th we had a Friday the 13th last week so now this seems they're timely if you are superstitious then we should have a proper conversation but that's nothing to do with C++ if you are superstitious then you fear Friday the 13th then you might sit down and write some code to decide when the next Friday the 13th is you might do this in a kind of Rossi approach we're going to move this to C++ and not a lot of change actually they c+ stuff chrono library actually 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 this with the raw stuff this will find you the next the next Friday the 13th after the one that you prefer the date that you provide so so this is this is all good now not so what we're gonna do is going to break this one down instead of expressing the logic stead of expressing the logic this way I want to find I want to get a steady stream of finding the 13th and what I'm going to do is I'm going to turn this into a pipes and filters arrangement I can start off like this so 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 here I'm going to select in the 13th of every month ok so this is how we did this is a simple way of doing and with pipes and filters ok what I'm gonna do is I'm going to include in select in every 13th month and now I'm selecting all the Friday's when I get out is a steady stream with Friday the 13th switch I will then display so I broken it down into a pipeline and so we're going to wire this up we're going to have a channel for all the days and we're going to arrange this so that the days are from the start yeah unfortunately the outline here it's got bleached out by the projector will have days from the start will wire it into the today's and that's just going to go on forever actually they don't go on forever - they will hit a limit it turns out disappointingly we're not allowed to compute to infinity on this but you know what we're going to do is just keep on looping generating days and 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 a 13th then I write it out otherwise I'm not going to then the next one I only want the Friday's and we wire that one together and then finally we actually display it and we pick that stuff up so there's a nice little pipeline progression there that will give us all the Friday the 13th of interest and there is 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 and say here's a channel and I'm going to associate behaviors with its ends which is a sort of an inversion of the model that I've got here but I'm going to leave that one 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 sign to that if your architecture fits that that's great you know very easy to reuse far easier to compose and work with some other pieces of code but there are most interactions that we want to probably introduce threading into don't really fit a pipeline model one-way data flow we might need some interaction and at this point this thing that I did many years ago for my master's thesis was extra base systems though one of the things I worked with was a language called ABC L actor based concurrent language or an object based concurrent language depending on which version you read and when we talk about raw multi-threading other Alexandros whose quote is one of my favorite ones multi-threading is just one bad thing after before simultaneous with another but what is acted based computation acts based concurrency is just one bound message after another you are in the 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 the monitor object is the way that Java decided to bake into the language every every object is essentially a monitor object which means that it can be 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 so that's great because that shouldn't be our code should be somebody else's code but and 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 and update operation for somebody's name and number a drop operation to drop an entry and a find operation that optionally returns a string and nothing's there so optional it is now 2017 optional is now finally in the seaport will be in C++ 17 so that saves all those null things or using empty string as a marker so basically if we find the name and it's there we get a result if we don't then we're told that we don't have a result and this is in optional appears in other languages sometimes called different things fallible may be and so on so got that structure we're going to have a simple mutex model like we had earlier on and we can go ahead and we can build this stuff up we can update it's an upset operation we can drop 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 so we have our phone book in another thread we go and look for thomas anderson tom stands and is not yet in the phone book so we've got an updating thread so we've got two threads of interest here the FIR the directory thread is actually passive we're going to go and update that next time we try find Thomas Anderson in the in another thread both of these operations will be ordered in some way and mutually exclusive so therefore we are guaranteed of some kind of coherence and we will get some value we go and look for neo neo is not in there we're not date with Trinity we're going to date Morpheus we can update with we haven't dropped on us and so we're going to add neo now we're going to find Thomas Anderson but what we found but neo will be and 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 active objects we could go into but I'm going to leave that out for your comfort but I wanted to put them in there why am i showing you something in 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're not the same programming model the actor model has a different outlook the actor model I'm going to show you a full Actimel I'm just going to build an apathy a build a very very very basic version out of the Q construct and the standard library thread we had earlier also in C++ 17 will be standard any a variant type there are actually two variant types this is a universal variant type and what I'm going to do here is the phone book you'll notice I've changed it into a function it is 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 and anybody can talk to you using this Q 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 an entry I mean you're giving an entry or you're receiving an entry in other words it's a name and a number you can have a no entry in either you or telling the phonebook please I don't want this anymore all you're returning this entry does not exist and you can have a find request here is a name and here is the return address please send it back on this Q okay so there's the idea that somebody can talk to a running function that is that is the basis of the anthem model it's not that we are creating a classic object and putting locks in it it is that we are creating a function and we are now communicating with a running function this function it doesn't reveal its own state its private state really is private its local variables if I might actually have a look at that here is phonebook here is the scope it's going to get a bit Messier you can tidy this up but I realized that for reasons of time well that's really what this whole talk is about isn't it time temporal decoupling but for reasons of time I'm not going to go into the details of it so I'm going to do the kinds of raw ugly almost assemble like version but show you the the basic construct here is the private state this was previously private actually private within an object but this is now just a local variable the function is just going to keep on requesting I'm not going to put any termination it's just going to loop forever or ctrl C 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 that is the private state entries so now we're just going to repeatedly handle requests we would pick up a request now comes the ugly bit is I now have to go and do it in a type dispatch this is the bit that you can tidy up with a little bit of a a poker but what we're going to do here is we're going to pick up is it an update how I received an entry if it's an update then my update I update the entries with update name and update number on the other hand is it a drop request am I being told no entry if it's a drop request and I will erase that entry if that's the case but the bit that is interesting is a notice neither of these requires interaction when another thread another actor is basically communicating with you say I'd like to add this entry or please drop this entry they're not expecting a response it's it's a synchrony without any kind of blocking return there's no futures involved they're doing this now we need to talk to somebody and that's where the find is quite a good example something's going to send us a fine request please find us Nia or Thomas Anderson or whatever if the entry is not there we need to well 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 an important thing that is often overlooked in actors is you don't have to actually return the call to the caller you do have to return the result of 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 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 if it's not there we're going to 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 but all baked into constructs that are now available in the C++ library plus the Q construct that I added in earlier 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 message like so I'm going to set up a directory then I'm going to launch a thread that holds the phone book with the directory and then I'm going to say right okay I've got a Q and I would like to find Thomas Anderson please return it here we're not going to find anything so I'm going to pick that results up and what I should get back is no entry Thomas Anderson in another thread we're going to have an updating thread as we've actually got three threads running here we're going to have something updates with Thomas Anderson one back in the requesting thread 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 dropped on the Sanderson 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 man is the the raw ingredients if you like this is the actor model broken down to its most fundamental level and clearly with a little bit of imagination and if you could experience of mental models in other languages you can immediately see the opportunities wrapping that up but just based on a q-and-a thread we can actually affect this model and a note where it goes and what style it gives us that our messages become first-class objects rather than methods can we get this in version 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 coming for a coffee bar go go back John Carmack instead yeah 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 function style makes the state presented to your code explicit which makes it easier to reason about and in a completely for your 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 and that kind of approach isolates a service it's a slightly different philosophy but using the same basic language you went with a very very different architecture and one that is more composable so hopefully the one thing we've learned about thinking outside the synchronization quadrant is that our default desire to put locks around everything when we care about speed is going to be sorted 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 been trying to scale things up what they've learnt is a number of lessons sometimes the hard way and particularly now that we are moving from at the moment I would sense that we're moving a little bit back from operating system processes to threads because we've discovered we have a remark when out of memory available 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 see like ways of sharing everything and just having locks no the lessons that were learnt pushing things out where you genuinely couldn't share them those are valuable and worth keeping in mind I hope that's been useful I'm around for any questions as I'm unpacking please feel free to ask thank you

Channel: NDC Conferences

Views: 25,413

Rating: 4.7307692 out of 5

Keywords: c++, kevlin henney, ndc, ndc london

Id: 2yXtZ8x7TXw

Length: 67min 43sec (4063 seconds)

Published: Mon Feb 27 2017