Generic Locking in C++
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 96 | |
| Author | ||
| License | CC Attribution - NonCommercial - ShareAlike 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/51717 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
NDC Oslo 20167 / 96
2
7
8
9
12
14
19
20
26
28
31
33
38
40
43
45
48
50
51
61
63
65
76
79
80
83
87
88
90
93
94
96
00:00
Object (grammar)Standard deviationLibrary (computing)Type theoryThread (computing)Social classConditional probabilityInheritance (object-oriented programming)Operator (mathematics)SynchronizationWilliam BurnsideDuality (mathematics)Observational studyParameter (computer programming)Boilerplate (text)SynchronizationConstructor (object-oriented programming)QuicksortVector spaceNumberBitPointer (computer programming)Element (mathematics)ParsingObject (grammar)Wechselseitiger AusschlussDefault (computer science)ExistenceMacro (computer science)ImplementationCodeSpacetime2 (number)Right angleFunctional (mathematics)WordMereologyCompilerException handlingArrow of timeExpressionArithmetic meanBoolean algebraCASE <Informatik>Electronic mailing listAttribute grammarPoint (geometry)Rule of inferenceProgramming paradigmState diagramLibrary (computing)WritingMultiplication signPrimitive (album)System callMechanism designRecursionComputer programmingMultiplicationOperator (mathematics)Thread (computing)DeadlockSimilarity (geometry)Video gameState of matterIterationOrder (biology)Cheat <Computerspiel>Goodness of fitMathematicsVariable (mathematics)Expected valueSoftware testingStandard deviationPhysical systemReading (process)Inequality (mathematics)Level (video gaming)Template (C++)Pairwise comparisonAddress spaceCartesian coordinate systemSheaf (mathematics)Moment (mathematics)Inheritance (object-oriented programming)PlastikkarteTheoryHookingInfinityEncapsulation (object-oriented programming)Formal languageSemiconductor memoryClosed setComputer architectureOpen setBoom (sailing)CurvatureSocial classFacebookSpherical capPlanningStatement (computer science)PlotterWeb pageSession Initiation ProtocolProof theoryFeedbackDifferenz <Mathematik>Correspondence (mathematics)Dot productFluid staticsVapor barrierPosition operatorType theorySound effectInterior (topology)Finite differenceCycle (graph theory)BijectionLoop (music)InjektivitätSlide ruleAsynchronous Transfer ModeFiber bundleRepository (publishing)Mathematical optimizationMessage passingExtension (kinesiology)Limit (category theory)ProgrammschleifeProduct (business)NeuroinformatikProcess (computing)Probability density functionPhysical lawWebsiteGrand Unified TheoryParallel portData storage deviceConcurrency (computer science)Generic programmingFlow separationBasis <Mathematik>Different (Kate Ryan album)Connected spaceSequenceProgrammer (hardware)Text editorSemantics (computer science)MappingPrice indexCodecTerm (mathematics)Suite (music)Source codeCasting (performing arts)Arithmetic progressionBefehlsprozessorKernel (computing)FrequencyError messageEqualiser (mathematics)Punched cardLine (geometry)Electronic signatureoutputLogical constantWater vaporVideo game consoleHidden Markov modelServer (computing)ThetafunktionFreewareExecution unitPattern languageFreezingFood energyGodAbstractionVarianceMetropolitan area networkLambda calculusMusical ensembleSquare numberComputer animation
Transcript: English(auto-generated)
00:04
Morning, all right. Well, who here has been at my talk of yesterday? All right, did you like it? All right, I got some good feedback. One of them was, Andre, can you ever give a talk that is not revolutionary?
00:25
The answer is yes, and the proof is this talk that's coming right now. So if you want something new, go for that. If you want something nice, come here. Otherwise you can go right now. Another piece of feedback I got was very nice.
00:45
Somebody told me, Andre, you are the master of uncomfortable silences, because you ask a question and you have the guts to wait until somebody answers, until everybody in the audience feels hot in their seat. He's asking me, probably, so he's looking at me right now.
01:02
This is going to happen today, so be prepared. How about we build the slides? How about we build the slides? So make slides.ps and scps slides.ps to my site, and SSH into my site and call ps2pdf, because I don't have it on Mac. For some reason, the Mac doesn't have ps2pdf,
01:22
and then I'm going to scp the pdf back to my computer here, and let's see if it works. 100%. Oh, nice processing. So we've got to wait for it to be copied back, and there we go.
01:41
Alright, that was a huddle. So now we have them nicely built and fresh. And I'm going to talk about the topic for which I'm not the most qualified in the room, for the simple reason that you guys are awesome. And that awesomeness includes two particular folks.
02:01
Anthony, who has been giving a great talk yesterday, and the tutorial two days before that. And Mr. Hubert Thundering Voice Matthew, at least. Not to mention Mark and other folks in the audience who I know for a fact are very good at this kind of stuff.
02:23
That being said, I'm going to discuss code that is actually used in production at Facebook on a regular basis. Essentially, it is literally used every time you use the site. So that's pretty nice, right? I call the topic generic locking.
02:42
To give you a bit of a background of how this came about, there's a story to this. In the early 2000s there was a huge battle of concurrent paradigms, a huge competition going on. There were a number of contenders, like patterns, let's say.
03:02
Message passing, lock-free, work stealing, automated parallelization. Detlev gave a great talk about this yesterday, defining properly and comparing all of these ways of doing things. And in a way, nobody won. Although, clearly before that,
03:20
you had some sort of lock-based program that was the dominant paradigm and everything else was new. Right now, it's not a lock-based program that kind of disappeared and then it's not there anymore. It still remains a very important paradigm. It's actually better than lock-free approaches in certain situations, such as when you want to set priorities for things
03:42
and they need to be different. Lock-free is entirely all too democratic, if you wish. Lock-based programming, it turns out, it remains hugely important for C++ programs. Do we have agreement on this? Do you agree? Against? No.
04:01
So that was a bit of a latency there. Abstain? Like, eh, I don't care. I would take off right now. Go to that AngularJS talk. Alright. So, now, actually, in 2001, I wrote a very controversial article,
04:20
so I'm kind of building a, waving together a story here. So, in 2001, I wrote probably my most controversial article in the C++ world. Volatile... You know, this is actually a typo. But it's very interesting because it was auto-corrected. It was multi-threaded.
04:42
I'm not kidding. The editor fixed that for me. And it's the first time I'm noticing it. Because, you know, it's like, I'm reading the slides, I'm kind of rehearsing, and I'm like, ah, I know this title, so just my eyes are going to skip over it. And at this moment, I was like, ah! Maltreated. Which is actually kind of whimsical.
05:04
It's interesting that auto-correct happened. It's visionary, right? The Maltreated Programmer's Best Friend. Yep. Multi-threading is maltreating. Alright, so, that article uses a trick.
05:20
It uses the volatile connection to the C++-type system, which is it's a qualifier like const or any other. I mean, that's it. Like const, or any other, or const or itself. It's a qualifier, and you can use it for overloading and for sort of defining methods that apply to threaded or non-threaded objects.
05:41
And it introduced a nice idiom, which was, you know, whenever you have volatile, you can't use the object, and in order to get rid of volatile, you would need to lock the object. So it would use the volatile qualifier as an indicator that the object is locked or not.
06:02
So, it did not rely on volatile semantics. Anyhow, moving forward, in 2011, C++ introduced multi-threading rules for containers, and the way they work is the following. In C++, as of year 2008,
06:22
this particular proposal was introduced. Let me kind of summarize it for you. If you have a container, an STL container, you can call const methods from different threads, literally simultaneously. If you want to modify it, you can't do that.
06:42
But as long as there are multiple calls into const methods, you can do it simultaneously. To continue the story, I'm going to go back a couple of slides. To continue the story, lab-based programming has also made progress, even though as competition had intensified,
07:03
even though there are new paradigms coming, lab-based kind of followed suit and just got better. To wait, only yesterday I was talking to Hubert, and he said, actually, there are new implementations of readers, multiple readers, one-writer locks,
07:22
which are very good. They are just very good quality and very refined and very subtle. There's been a lot of improvements in CPUs, operating systems, APIs, better kernel-level mutexes, better user space mutexes, better spin locks, better readers, writer mutexes.
07:41
Again, just to define terms a bit, could someone tell us what many readers want writer mutexes? What is that? Yes, please. So, right, so you can have many readers accessing the,
08:02
entering the critical section at any time, but if a writer comes, it would have to wait for readers to go away, right? And once it acquires the lock, nobody can either read or write, okay? Question.
08:21
If a writer is waiting and a reader is waiting, who should get priority? Somebody else. So if a reader, if I have like, so any number of, a million readers can read, be simultaneously, you know, acquiring the lock, the mutex, right?
08:43
So then if a writer wants to wait and there's other readers waiting, who should get priority? The writer. Why? The writer, why? Otherwise it's very easy to start the writer for the simple reason that new readers can come at any time in the door at no cost to them and essentially they would start the writer away.
09:04
Of course there's more refined ways to do this prioritization, but in essence you gotta be careful with this kind of starvation. So, okay, great. So allow, we can do one write access that precludes all other reads or writes, but we can do any number of read accesses.
09:22
Excellent. So C++ 1x is serious about lock-based programming. We already have a bunch of stuff in there such as mutex, time mutex. Anthony knows all about it. Is the list even complete? Probably not. Recursive mutex returns recursive time mutex.
09:41
And then we have shared mutex, shared time mutex, so these would be, these would be reader's writers. And you have only C++ starting with 17, you have the multiple readers, one writer lock, but it's available today in Boost, et cetera. Now here's the interesting part. Here's what I'm kind of getting. So there is a punchline to this,
10:01
kind of building a story here. There's a punchline, which is the std containers were designed for readers and writers. And let me explain why. So you have this, right? You have multiple readers, one writer. And then you have STL containers. And STL container says, eh, for const methods you can have many readers.
10:22
For non-const method, that means you're assuming you're writing to the object and, you know, there could be no readers or other writers. Now, let me ask you this. Practically, to implement such a container, what rules would you need to observe?
10:43
So to implement the container, I can have in const methods any number of readers. Any number of threads can enter the const methods of the container. What, like if you implement such a container, what would you need to be careful with?
11:03
No mutable members, thank you. Anything else? There's another thing. So no mutable members because mutable allows you to cheat const, essentially, and change the object surreptitiously, right? And there's one more. Yes?
11:21
Iterators will be problematic because they kind of look into the container but they have their own life. But there's one more simple thing that you need to avoid. Yes? No global function? No global data. No global mutable data. So you can't have global state kind of manipulated in...
11:41
Because, again, global, in a way, allows you to cheat const, right? So if you observe these two simple rules, you can say, well, my container basically is obeying this particular rule. You know, no IO, which is also sort of a global thing.
12:00
So you don't have to have hidden mutation inside your const functions, right? So now, let me ask you this. So we have two things. We have this rule, which says if you have a container, as long as it's const, many people can call it. But if it's non-const, nobody else can use that container.
12:23
And then you have the reader's writer lock, which goes, you have many readers for the subject but one writer. Aren't these two... Isn't there an eerie similarity between these two things? So it's, you know,
12:41
the wait a minute moment here, right? We have a wait a minute moment. Which is, well, how about then I kind of make the two dovetails? So you have multiple simultaneous calls to const methods, no calls to const methods, concurrent with calls to non-const methods. And you have user serialized calls to non-const methods.
13:00
And this is the same exact thing for the write reader's writer. It's almost the same, you know, almost the same bullets here. Which is amazing, right? So this is kind of the nice thing that is noticeable. So you're looking at this. One-to-one correspondence.
13:23
Am I making sense here? Am I gaining your trust here so I can trick you into using a template or something? And, you know, I'm going to even pull a macro on you if I feel like it. Right? So, OK. One-to-one correspondence.
13:41
Reader's writer and const non-const. Amazing. So whenever I call a const method I need to enter a read acquire. And whenever I enter a non-const method I need to enter a write acquire for the same lock, for the same mutex. The same synchronization object. And it just works. By that rule. So it works like today
14:01
with the STL. Just do it. So that's the idea. Now, we want to encapsulate all of this good stuff. And because of this rule and because of this rule in the language it becomes very easy to encapsulate and put together a little library and you have it.
14:22
So this is the idea. Let's keep a reader's writer lock outside the guarded object and issue a read lock around each const method and issue a write lock around each non-const method. So now, OK. In order to do this kind of stuff which of C++'s encapsulation mechanisms
14:43
can you think of? I want to hook every const and every non-const method of any object. There is a type that does the same exact thing which is a smart pointer. Shared PTR.
15:01
A smart pointer essentially hooks every method by defining operator arrow and then it allows you to do things. So let's do that. How about the following? Alright, let's get ready here. OK? Have a sip of coffee there.
15:20
Alright, let's see. So we have a template of any type and any mutex type not any mutex, but a special kind of reader's writer mutex. So by default it's going to be a shared mutex or whatnot. And we have defined a struct Synchronized which is going to hold a datum right?
15:40
And the datum is not mutable you don't cheat on the datum. And it has a mutable mutex because you're going to manipulate it even in const methods. And I'm going to define a little class locked pointer which defines operator arrow and I'm going to define for this very class Synchronized, I'm going to define its own operator arrow which returns
16:02
locked pointer. Similarly for const Synchronized object I define a different operator arrow which returns a const locked pointer which has its own definition. Has its own definition which is very similar to this guy. Now explain to me please if I have a Synchronized object like this
16:22
and I say object arrow method what functions are going to be invoked and in what order? Yes please. So the arrow operator is going to be called recursively. Notice the completely
16:42
incorrect use of the recursive. I'm kidding. Indeed it's going to be called transitively for as long as it returns a non pointer. Right? Excellent. Thank you very much. I'm going to call first the operator arrow on this guy, on the Synchronized object and that's going to return a locked pointer.
17:02
And the C++ compiler is going to be like wait a minute, I didn't get a pointer yet for this operator arrow. So let me continue. It's going to invoke the operator arrow for this guy. The locked pointer. And then I'm going to get a T star and finally the T star is going to be happy. It's going to stop the
17:21
recursion. It's going to stop transitively invoking the operator arrow and it's going to call the method against that pointer. But there is one more thing that's happening because this object is returned by value. It's an R value. So if I call operator arrow against the Synchronized object
17:40
several other things are going to happen. So why don't you continue telling us what's happening. So first thing that happens is I call this guy. It would call the constructor of locked PTR or whatever the hell that does. You don't know. I'm saving that.
18:05
You don't know yet. Don't get ahead of me. What I'm saying is that this object is going to be first constructed returned from the operator arrow. The compiler is going to invoke operator arrow on this guy and is going to finally get the pointer after which the invocation occurs
18:22
whatever you've invoked it for. And then, somebody else? What's going to happen after the call returns? The destructor of locked PTR is going to be invoked and I'm done with the call. So by just writing object arrow method I create an object, invoke a function,
18:41
destroy an object in this order. Right? So you see I'm very deliberately here setting you up for a locked method call on locked sequence. Better yet, in case I have a constant synchronized object
19:01
I'm going to return a different type here so I'm going to go through the same motions except I'm going to create and destroy a different type of object which you can see where I'm going with this. This is invoking the reader's lock and this is invoking the writer lock. And all of a sudden
19:21
with essentially like this code only I got one to one mapping between everything non-const and the writer lock and everything const and the reader lock. Alright. So let's see a bit of the implementation here. There's of course a lot of details
19:41
to fill. So we have a constructor here that's private. We don't need it. We have the default. We have a synchronizer that takes a copy by const reference and by our value reference. These are sort of the usual suspects.
20:04
One nice trick here is we have the conditional noexcept going on which goes like this. Whenever you copy a synchronized object it's going to be noexcept if and only if the value itself is no-throw copy constructible. So that's a nice example
20:21
of using a bit of introspection there to make sure that we propagate properly the capabilities of T which is our generic argument into the capabilities of synchronized. Did you know about this? Noexcept.
20:41
So I have a few folks who don't. So it's very nice. Noexcept is an attribute of the function. It's it takes a boolean. It takes a boolean as an argument. You can write noexcept and put noprene and no boolean and that means
21:01
it's never going to throw. That's not entirely true but anyhow. So it's the user makes a vow, a pledge to not throw. That's probably more like it, right? Like in C++ never is it means almost never and always
21:21
means almost always. Except for this long list of exceptions. And this is noexception. Gee, wow. Three meanings of the word in one sentence. You have to disagree. Yeah, never say almost never. Except. Ok, so. So just say noexcept
21:41
it means I'm making a vow here to never throw. But if you put noexcept and you open a parameter and you put a boolean constant in there it's going to be noexcept or not depending on the boolean if it's true, you know. And in this case it turns out there is no throw move constructible standard
22:01
introspection facility which cannot be implemented in standard C++. It's magic. So you can't sit down and implement it. The compiler has to define it for you. And the compiler inside is going to do some underscore underscore things to implement it.
22:21
But it's not implementable in user code. It's an introspection primitive. And the same goes about nothrow copy constructible which is also magic provided by the compiler. So by this I'm saying well if the original type was copy constructible without exception then I'm going to
22:40
nothrow from the synchronized constructor as well. Which is as expected. When it builds from a piece of data you actually don't need to lock anything. Because it's just building the object anew so there's no need for locking. There's no multiple threads accessing this constructor.
23:02
So again there's this whole noexcept trick again. So with assignment we have an interesting we have an interesting thing here to worry about. Who's been in Anthony's talk yesterday?
23:22
Anthony made a very good point yesterday which was if you want to if you have any piece of code that needs to needs to acquire more than one lock they need to be acquiring the same order in all threads. Because if not what's going to happen? Somebody who hasn't been in
23:40
Anthony's talk let's think real time here. So if you acquire if one function acquires lock1 lock2 and the other function acquires lock2 lock1 what's going to happen? Yes? Deadlock. How is it occurring? Someone in the front because it's easier for me to hear. How is it happening? How is the deadlock occurring? Yes.
24:04
So it just happens. It doesn't always happen. It only happens when one thread got so far as acquiring one of the two locks and the other also has gotten to acquire the other of the two locks and then they both wait for each other and then they never release. So what is the obvious solution to that?
24:22
Yes? Cycle detection. There's an easier solution actually to that. Which is here. Lock in increasing order of the address. Because the address is unique and ordered for the whole application. You don't care what the order is. It just has to be the same.
24:41
So that's the clever thing here, right? So to be more Catholic than the Pope himself I just say STD less of void star. Which is a guarantee that I can compare pointers for inequality regardless of where they come from. This is the standard way of saying I want to compare two pointers they're not in the same array. They're not in the same object.
25:04
Did you know this? Everybody should know this. And everybody knows it starting as of a second ago. Awesome. Great. So I just used this last thing and on these flat memory systems of today
25:20
it just works automatically. But remember when you were kids there's a thing called segmented memory architecture. Does anybody work with this? Ok, some of us do have the grey hair to prove it. Or no hair. Or no hair at all.
25:42
The bold thing is in vogue right now. I should try it. Essentially in those days you would need to do some pointer adjustment so the comparison would be more complicated and more costly. So therefore you would need to use this last thing. So all I'm saying is that if
26:01
this is at the lower address than RHS you lock in the order of this and the other guy. Otherwise you lock in the other order. And that way the assignment of two synchronized objects proceeds nicely. Right? And we have a number of
26:21
other usual suspects such as move assignments, swap and such. Right? Awesome. Questions so far? Ok, let's recap the basic plot here. Ok, excellent. So before getting into the implementation of the operator Arrow, let me share again
26:40
the basic plot I'm following here just to make sure we are on the same page. So we built this synchronized type around the following realization. Which is the new
27:02
C++11 rule guarantees that I can enter from any number of threads the const methods of a container. At the same time if the method is non-const I could allow no other
27:20
const or non-const method to be executed concurrently. So I need to do locking. No, go ahead. Yes.
27:50
No, because you create objects here. So you create actually named objects which are going to be through the end of the scope.
28:01
So these G1 and G2 are these locked PTR types and they are going to exist until the end of the scope. Ok, actually I did have a moment when I thought, oh my god, this may be all wrong. But then I thought, you know, this type is used a lot inside
28:20
Facebook. So if there is a big mistake like this, I'm sure it would have been discovered by now. Or not. So you know that when Facebook fails people call 911 and there is this issue. Moving on with the recap. So my plan here is to say
28:41
we have const methods, many readers so the const methods would be the many readers and the non-const mutating methods would be the writers. And then I have this nice correspondence I can use const as my trigger, my indicator for whether I want to lock the object for reading or writing.
29:01
So that's my plot. That's my basic... This is sort of the discovery we've made that allows us to implement the subtraction. Without that particular rule in C++ you can't. And actually let me tell you this. This was the case before C++11.
29:21
All C++ implementations I know of had containers that obeyed this rule. So this was just simply enacting into law what was de facto true. Which was STL containers never use mutable data and never use globals
29:40
because people notice a number of issues with those related to threads or not. So there's actually in the 94 there's kind of a transient issue with that. And people are like, you know what? No globals, no mutable data in STL. So this was kind of the case before this and I'm very happy it became law because then it allows us to do this.
30:02
So we have this operator arrow which is going to be overloaded for const and uncast objects and this little thing here allows me to choose whether I use read locking or write locking by means of the return type and then the return type has its own error.
30:22
Great. Alright, so moving on with the implementation of operator arrow the locking pointer which is kind of inside the synchronized holds a pointer to its parent and it does not have a default constructor. You wouldn't it doesn't make sense to create
30:41
a default locking pointer object. It's only it's only is to just be created as a temporary from operator arrow from the synchronized guy. So, you know, simply locking pointer synchronized to our parent stores the parent and
31:00
mutex lock. Boom. So that's my locking pointer. What do you think the const locking pointer constructor looks like? Yes? So it's going to be a shared lock here, a different call. This is acquiring the lock in write mode and this other guy is going to acquire the lock
31:22
in yeah come on ah okay oh man I didn't write that. Okay, well I'm missing a slide here which was very nicely
31:40
the next slide should have been the identical code except the name locking pointer becomes locking pointer and this would be a call to shared lock. Shared lock, right? Okay, so as a small details you should know that reader's write or mutex are recursive so you can lock the same thing multiple times.
32:02
Which is nice and you know it's convenient. When you assign a lock pointer to another you just have to make sure it's there's no self-assignment etcetera so this is just for optimization.
32:20
You could actually acquire it twice. Alright. So for efficiency you also want to implement the move constructor which takes our value reference to the other lock pointer and again you make sure you don't self move assign which would be very
32:42
very bad. But it's still legal, is that right? Can you self move assign? Are you allowed to? I'm seeing some raised eyebrows up to the ceiling there. I'm seeing a sad nod from death left in the back and just like telling you people what's happening in the room right now.
33:01
So it's very bad but it does happen. People kind of do it, they shouldn't. This is like code for bad people it's going to support them. It's going to make them happy. Alright, so awesome.
33:21
And what else? Oh yeah, you can't move construct an object into itself that you're not allowed to. Although you syntactically can. You can't move from a non-existing object into itself. Well this is C++ for you, right? As always you can't construct
33:41
these sentences that kind of parse and then like, well, that can't be, right? So in the destructor obviously you're going to unlock the mutex if the parent was not null and that sort of completes the locked pointer. So it's all boilerplate and it's all simple code. The nice thing is
34:00
it's highly reusable. So the whole point of the locked pointer was to implement this operator arrow which simply just returns the data. No problem. Of course if you create a locked pointer and you move from it or something and it gets to the null pointer, if you try to
34:20
invoke the operator arrow you're going to get a segmentation fault. Which is, you know, pretty much what you deserve. Right? Excellent. We pop out of locked pointer and at synchronized level, as I promised, we have an operator arrow non-const which returns
34:40
our value of type locked pointer. And this completes the locked pointer part. So whenever I use some sptr arrow xyz you have three vocations of operator arrow. One for the synchronized object the next for the locked pointer and then you get the object and then the locked pointer gets destroyed and the whole locking and unlocking
35:00
mechanism is automatic. Cos locked pointer looks a lot like, and it's essentially the same code as I said it's pretty much just the same except you're going to call parent mutex lock on lock shared. Right? So you're going to call different methods. Right? Alright.
35:25
Who can tell us what C begin and C end do in C++11? C begin C end. Yes. They return a constant iterator for a mutable object. Right?
35:40
For a non-const regular container they return constant iterators. Could you do you need them? Are they necessary? Are they necessary? Or are they convenience?
36:02
Well they're convenience and I'll tell you why. You could take the container cast it into a reference to a const container and then take begin from that. And that's my C begin. But it would be through two lines. Only variable. It would be ridiculous. Instead of a const cast
36:21
like an idiot there and I put const container and then I make a missed typo and I cast something that I shouldn't be casting to. You know, you don't want all that. So C begin is a convenience function that says even though I could mutate this container if I so wanted I'll be good today. I'm not going to mutate it.
36:40
So let me call C begin and C end. Is that right? So for the same reason sometimes I want to be nice to an object I could mutate and say actually I want ask const. I want to look at the subject as if it were a const object. So then you can say sptr. ask const arrow method
37:00
and that's going to require which kind of lock. Which lock? The reader's lock or the writer lock? The reader's lock. The multiple reader because it's a const object is going to invoke the method. So that's a nice convenience function. So now it gets to the fun part. So whenever I give talk about anything
37:21
really at some point if I have a macro in variables there's going to be like three dudes at the end of the talk saying you know that macro let me ask you a few questions about it. I'm not kidding. It fascinates people. It's like I don't know it's like people are weird. Like that. This is like that is the I don't know adults only section of my
37:41
talk. It's like you know what I have to ask you in private a few questions about that macro because I found it very interesting and dignified with you know I think it's good to talk about it. And I'm going to use this for the rest of my life. Right? So this is going to be fun.
38:03
So you know here's the thing. I'm going to do something stupid. Here's something stupid I'm going to do. Who can spot the huge mistake I'm making here? Yes please.
38:23
Yeah this is kind of a rookie mistake. So SV is like a synchronized vector right? Very nice. Well let me test if it's empty. SV acquire a reader lock call empty. Get back from the reader lock. Unlock. And let's say it returns it's not empty.
38:41
Boom. Okay. So then I open a scope here and I'm going to say oh if it's not empty I can access the front right now. Because I'm so smart. So good. Right? And this is going to acquire another lock and of course in the meantime between the closing of this particular and the opening of this guy like
39:01
there's an eon here. There's an infinite amount of time in theory. You could think an unbounded amount of time could occur in there. And you know the other threads may have a party right then. They're like you know this is awesome. I'm going to lock and unlock the object and manipulate it any way we want including making it empty.
39:22
How about that? So then I'm going to take front of an empty vector. So you can't use the object that way. And actually I've been criticized by people at Facebook who said you made it too easy to do this. Because people just write an arrow and then whenever they write an arrow
39:40
there's a lock and unlock happening and I'm like well read the fine manual. RTFM right? Read the fine manual. So alright. What's the cure for this? What is the cure for this? Yes please. Right.
40:03
So I need some sort of a I need a mechanism to be able to lock the whole SV thing and then use it inside the critical section and then be done with it. So you know I've been thinking about this for a while and I found something that's very nice except it uses a macro.
40:21
Here's what the trick is. I define a pseudo statement which is called obviously synchronized in all caps because we like to shout when we write macros. Synchronized SV. And this is the use. It's almost like magic because inside synchronized it's a critical
40:41
section and I can use SV as a vector so I can write SV dot empty instead of SV arrow empty. So inside the pseudo statement I have an already locked vector and if it was mutable it's going to be acquired for write and if it was not, if it was const it's going to be synchronized for
41:01
reads only. So now inside the synchronized section I can call any method on the vector because SV was mutable. So inside SV is an L value of type vector int and lock is in effect I can use this vector. Notice something interesting. This
41:21
macro not only does the lock and all that stuff but also it changes the type of the name SV. From synchronized vector to vector. Do you want to see the definition? Are you up for it?
41:40
Do you have that blood running through your veins right now? Alright, this is it. I'm not kidding. This is it. Oh man, it looks ugly. Oh man, this looks really bad here. This next section is like Andrei
42:01
tricks for writing macros and the trick number one is you want to inject things into a new scope then you have these if statements and these for statements that all they do is kind of inject names into the upcoming scope. So first I define an if bool underscore one equals zero like an idiot and I do
42:21
nothing and I say else and that made available for me a boolean variable because I want to play with it. And then I have a four that does pretty much nothing because it's going to last until like not underscore one. It's going to run exactly once. So I have a four and it says auto underscore
42:40
two equals x which is my argument. Operator arrow uh huh. So at this point I'm acquiring the lock. And then I'm going to do this stupid thing that essentially makes the loop run exactly once. And then I'm going to take so here I'm taking the locking pointer and at this point
43:00
I'm taking the vector which is an l value and I'm calling star underscore two which is my locking pointer operator arrow. So I need to call by hand those I made by hand those two calls to operator arrow that we are talking about they are done automatically by the compiler otherwise. In the macro I'll do that by hand. So at this point
43:20
notice that I introduce x which is a template sorry a macro parameter and effectively x is going to shadow the name x in the scope that's above it. And I redefine x to be this time a reference to in our case a vector.
43:43
Yes. Does the compiler not do that trick for you? No because what I want to get is not the pointer I want to get the reference.
44:00
So if I want to get the reference I need to do them by hand. Alright. So all this guy does one is limit loops to one pass as you see there's not one and one gets like there should be true here just to be nice but I didn't have room on the slide. There should be true. I'm not kidding actually there's no room on the slide so
44:21
I could use one. It compiles and runs. So it gets actually I've checked it does get optimized the way. All that bullion nonsense the compiler is like huh this guy must be an idiot. So okay let me compile this better for him because I'm not sure what's wrong with
44:42
that code but I don't care. So okay fine. First it creates a locking pointer the second is going to take from the locking pointer the l value and is going to shadow the object with an object by the same name. And this macro actually does everything all of that that allows me to do this.
45:03
Cleanly. Very nice. Alright. There's an issue though. What if I have and careful here is not a synchronized vector it's a vector of synchronized. So the synchronized is inside the each vector element is synchronized
45:21
has a lock. Right so not the whole vector is synchronized but only what's inside. And now I want to say I want to synchronize on this vector front. What's going to happen there when you expand the macro? Who can tell us? Yes.
45:42
Aha. So remember I said this x here is a macro parameter is going to shadow whatever but in this case I call synchronize with an expression it's not a name. It's an expression. So the compiler is going to be like you are an idiot because you're trying not to define a name but you're trying to define an expression
46:02
as equals something which is ridiculous. You can't do that. So this is not going to work. As soon as you have an expression here that's not just exactly one name you can't use this. So you know I lost a few nights of sleep over that because I was ah so I need to kind of create like a temporary here and it's
46:22
not pleasant. Here's what I came up with. Well when one argument is not enough I'm going to define two. So synchronize with two arguments and this is my name first and I'm assigning it from vsw.front and inside I'm going to use the name first.
46:45
Now anybody who's ever written one macro is going to know that we're entering dangerous territory here because we have the same macro name used with one argument or two arguments and you kind of got to distinguish
47:00
the situations. Do you think it's doable? Honest because I thought it's not doable for a long time and then I don't know one day I had the divine inspiration so I did it. So here's how it works.
47:21
I'll start innocently. Define arg1 of a and any other number of parameters a. That gives you the first argument of any number of arguments. Nothing on my sleeves. Define arg2 or 1 so if I call arg2 or 1 with two arguments it's going to give me the second argument but if I call it with one argument it's going to
47:41
give me the first argument. And here's how it works. arg2 or 1 inpl va-args comma va-args and arg2 or 1 inpl of a, b and any other argument is going to return b. So now let's see. If you call arg2 or 1 with
48:02
one argument x it's going to expand into arg2 or 1 inpl x comma x and then arg2 or 1 inpl of x comma x is going to expand to
48:21
x comma x it's going to return x so that's what I wanted and I'm done. How about we call this guy arg2 or 1 with x comma y. Two arguments, right? In that case I'm going to expand it to x comma y comma x comma y x y x y because I'm doubling the
48:42
arguments here. And in this case it's going to go into arg2 or 1 inpl of x comma y comma x x comma y. So it's going to give me y. So if I call it with one argument it's going to give me that argument. If I call it with two arguments it's going to give me the
49:01
second argument. So I have two macros. Give me the first argument give me the second or first argument. Are you ready? Are you ready for the next level here? Alright. So we're there because we get arg2 or 1
49:23
of the args and I'm getting arg1 here and it turns out it just works that way. So if you invoke this guy with one argument you're going to get just like before but if you invoke it with two arguments this operator arrow is going to be the second argument called against the second argument.
49:42
And in this case I'm always picking the first argument to define the variable. So this very macro is going to be usable with this idiom and that idiom. Which is awesome. I'm very happy. I've got to tell you this is one of those dirty pleasures of life.
50:03
Right? I felt very satisfied in a kind of shameful way I should add by having written this. Ok. Great. So now so recall cb and cn
50:21
we sometimes want to specify even though this particular expression is mutable I just want a const a const lock a reader lock. So in that case it's good to define a new macro which fortunately can reuse the existing macros. So we're good. We just use this as const method here
50:41
and whenever I say synchronize const you know that inside you're going to have a reader lock and you'll be able only to call the const methods of that guy. Terrific. Alright, so
51:03
this code this macro is used at Facebook and actually there's 7,000 something uses of it. Is that right? It's in the thousands of uses. Of course the code is much larger but it's used intensively.
51:23
Yes. You don't get shadowing warnings all the time. No, actually I'm not sure if that warning is explicitly suppressed or if it's just do you know ok, well I got to get back to you on that. So I remember there's a discussion about that and people
51:41
are like you know what I like shadowing things all the time so I'm not going to oh and actually I remember the problem there are some globals that people defined and you know these shadowing warnings were too many false positives and people didn't like it so they didn't enable that warning. I remember Jim Myring a former coworker he really wanted to introduce this warning
52:01
and everybody protested so it didn't take. Yes. Can you implement this as a function taking lambda? I think you can implement this as a function taking lambda instead of a macro, right? Yes. It would be a bit more quirky syntactically but
52:21
you can do it. You can say log this object call this lambda, unlock the object. Yes, Anthony. So there is it's not there yet
52:41
it's going to be in like year 3000 okay, awesome. Thank you. That's great. Yes. Did I have any argument of using volatile? No, actually this works better because I noticed that
53:01
people have a very strong emotional reaction when they see volatile. They're like oh, this can't possibly work. And they stop there it's like a psychological barrier that I found it's unpassable. So I'm very happy that this whole constant mutable thing works properly with
53:20
STL containers and actually works with a lot of user defined data to be honest. You know, you don't use mutable data everyday and you don't use static state everyday, right? So I'm happy with the state of affairs and I kind of reneged that whole article. Yes.
53:42
As long as you don't have operator dot, is the macro confusing by the use of the arrow if you want to lock the object on the fly versus dot if you don't lock the object
54:01
on the fly. This comment came a couple of times. So let me kind of make sure I understood what you mean. So I mean this like arrow here, right? And here.
54:21
So here you use the dot and if you don't use a synchronized pseudo statement you just use the arrow. People mention that, actually let me add this. It's easy to implement the macro to force you to use the arrow in both cases. I chose to allow people to use the dot because that pointer can never be null.
54:41
So I'm not I don't think it's a huge problem. I think people just get used to it. Yes. Can you use an
55:04
acquire method in the object that returns a lock? I got to take this offline because I'm not sure I understand how this would work. So it would be instead of the arrow there would be an explicit call? I guess you could
55:31
just to make sure I understand so essentially instead of the synchronized macro you would have a method and it would return an object and then you would use that object
55:41
and then get rid of that object. You get a reference ah, yeah I got to look at it to make sure how but anyhow you open with instead of a magic macro that's when my brain stops
56:01
no, instead of a magic macro it's nothing else. I would use a magic macro, period, thank you very much. So a magic macro is kind of cool and I have the suspicion that the C++ standardization committee defined apply just because they didn't know how to do this args 1 and 2 this thing. How about that?
56:22
Alright, so further reading. Where are we getting there? Alright, further reading. just Google for polysynchronized. You're going to find it on GitHub and Facebook repository I'm very happy to report that it's
56:40
been used quite a bit there's like there's a number of other methods that I didn't discuss because they're trivial there's time locking, there's an interesting other magic macro unsynchronized, which inside a synchronized statement it just so happens sometimes you want to get rid of it. So you have synchronized, you open a scope and you're like
57:02
at this point I'm kind of tired of being synchronized so let me unsynchronize the following operations so you open a new scope with unsynchronized and then you write some unsynchronized code, then you close that guy, you're back to synchronization, it turns out it's good to have. And synchronized dual is a macro that allows you
57:21
to synchronize on two objects at the same time by doing that trick of locking them in increasing order of the address. Right? So I can take a few more questions. Do you
57:50
allow concurrency errors? By using this things like this?
58:05
So you're asking if I'm making it too easy to... That argument can be made and has been made. So on the other hand, this is C++, I mean you're trusting that people know what they're doing to some extent and it turns out very often for
58:21
highly granular objects you do want to lock the object column method and lock the object quite often. So you know I'll let you decide. The argument can be made, I do agree. I could make it more difficult, like just say SV dot you know make sure you know what you're doing
58:41
open and close for that kind of function. Yes, there's another other questions? Yes. How's debugging? You know I'm having difficulty answering this question because like how's debugging going with
59:01
step by step debugging and stuff. I'm having difficulty with this question because I never need to debug my programs. It's like it's an unknown territory to me. All my programs work from the first go so I have no idea.
59:21
I suspect debugging goes just macros have the usual issues debugging. Step by step is going to keep the object locked inside the synchronized method so it's probably the usual suspects. I don't think there's anything sort of new or interesting in the debugging space brought about by the use
59:42
of these functions and macros. Yes.
01:00:02
So getting back to the lock pointer that use volatile and non-volatile and you'd yes, so what is the what's the question? Yeah, you could say if you could take sort of a temporary object and use it in knowledge that that's a locked object
01:00:25
Yes, definitely there. I think there are a number of other idioms that you could use Around this the C++ standard rule About the STL containers, so I happen to like this one It's it's very it's very convenient and very terse, but definitely you can make it more explicit if you so wanted all right
01:00:47
last question All right, you've been awesome. Thank you so much. Thank you