Dope! I should have thought of that!

What's one of the biggest compliments someone can give me?
It's when I explain an idea or algorithm and someone says: Dope! I should have thought of that!

I think this a great compliment, and let me explain why.

First, when someone says something like that it means that they think the idea is almost obvious or at least simple (to them), which implies that I was able to explain the idea to make it sound simple.
This may seem a trivial task, after all, explaining simple ideas is easy, right?
Well, I'm not always the most articulate person and have a (bad) tendency to overly complicate things, which you might have already picked up on if you 're reading this blog. In my defense, I do make an effort to explain concepts in the simplest way I can think of, too bad that is sometimes a really overly complex way.
Andreia is much better than I at this game. She has this seemingly innate skill to dismantle complex ideas in its basic constituents, and she helps me with it  ;)
Nobody's perfect, but luckily, I don't have this issue when it comes to writing code... the problem with code is that is explains the how but it doesn't explain the why.
So, when someone says "I should have thought of that!" it gets translated in my brain into something like "You made it sound so simple that I wonder why I didn't think of it myself"  lol

Second, no matter how smart you are, if the idea is complex, you're not going to be able to explain it in a simple way. If someone thinks your idea is simple, then there is at least one person in the world to whom your idea is simple, and simplicity is elegance! Most people can make something useful and complicated, but only a few can make something useful and simple.
I'm not a big fan of Steve Jobs, but there is quote attributed to him that I think is perfect for this situation:
When you start looking at a problem and it seems really simple,  
you don’t really understand the complexity of the problem.  Then 
you get into the problem,  and you see that it’s really complicated,  
and you come up with all these convoluted solutions.  That’s sort of 
the middle,  and that’s where most people stop… But the really 
great person will keep on going and find the key, the underlying 
principle of the problem — and come up with an elegant,  really 
beautiful solution that works.
http://cdixon.org/2014/08/15/steve-jobs-on-problem-solving/

... or from C.A.R. Hoare, The 1980 ACM Turing Award Lecture:
There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies.

It's really hard to create something and then go the extra mile to make it as simple as possible.
It takes time, it takes energy, it takes money (aren't these three equivalent anyways?).
This has value not just due to aesthetics but because making something as simple as possible means it is much less likely to have bugs or flaws, and it's easier to propagate to other people, a kind of meme. It becomes viral and infects other people's brains!
Sometimes is goes to the point that other people think they have invented it themselves:
http://concurrencyfreaks.blogspot.com/2014/11/left-right-gt-variant.html

Left-Right is certainly one of these ideas. It can be implemented in less than 10 lines of code and explained in just a few sentences:
http://concurrencyfreaks.blogspot.com/2013/12/left-right-concurrency-control.html
http://www.youtube.com/watch?v=FtaD0maxwec&t=29m5s
The thing is, we spent nearly three years working on it. From its first inception until it was distilled into the simple idea it is today, there was a long journey, with lots of longs nights of discussions and coding.
The how it works may be deceivingly simple, but the why it works this way (and not some other way) is definitely not simple.


So, when someone tells me that Left-Right (or some other idea Andreia and I came up with) is so simple that they should have thought of it, I smile and say thanks, because that's a huge complement, whether they know it or not  ;)

Left-Right and the (broken) peer-review system

On early September last year, we finished an updated version of the Left-Right paper. We submitted it (again) to another of the major conferences in the field and (again) it came back with lots of weak-rejects. Here is the updated paper on github in case you're interested:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/left-right-2014.pdf

The reviewers were unanimously about the novelty of this technique, and most were encouraging in their statements and suggested us to continue to improve the paper until it is "ready for a conference", the problem is, it will never be "ready for a conference" because they ask for opposite things, or just too much work that we don't have the time or patience to do. This means that the Left-Right paper will most likely never be shown in a major computing conference, and that my friends, is a big shame, for multiple reasons.


The first reason is time: Most people in academia (i.e. peer reviewing papers for conferences) are either a PhD student, or a professor at a university that has one or several PhD students working under him.

If they're a PhD student, then they have a big slice of their time devoted to work on papers, unless their PhD supervisor is a jackass and suckered them into babysitting his kids or some other task completely unrelated to the topic of the student's PhD thesis. They still have to attend and sometimes give classes, which can suck up a good deal of time, but PhD students aren't expected to have any personal time anyways, so that's life.

If they're a Professor at a university, they will probably not have too much time (between classes and going to conferences and committees and whatnot) but they will have one or several PhD students to do the "grunt work" on the papers, and all the professor has to do is have a few somewhat original ideas and choose at least one PhD student that's not completely dumb and is capable of doing the work or explaining it to the other PhD students. He then reviews the draft and corrects all the crap the PhD students write, points them in the right direction, adds the right references to previous work, and the final result will be a decent enough paper, which doesn't even have to be very innovative, as long as it has "the right stuff". If they're really lucky, the professor will have a Post-doc that does this last part of the work of reviewing the paper and doing the multiple iterations, and all he has to do is look at the almost finished version and do some minor changes.

A much smaller group, consists of the people working in companies but still tied to academic life or to research (like on research labs), and I guess that for those, they have to show some results and they will have a lot more tasks than just write papers, but getting papers out is one way of "showing work done" and keeping their job, so they do it. I think these guys usually focus on stuff that is more on the practical side, i.e. more "engineering research" and less "pie in the sky research", but that's just my impression and I'm sure it varies a lot from company to company and research group to research group.

And then there are people like me and Andreia. We don't have a background in this particular field (Concurrency and Synchronization algorithms), Andreia has a masters in Applied Mathematics with a post-grad in Information Systems, and I have a PhD in Physics (but I spent most of my PhD doing non-parametric low-sample statistical analysis and developing new statistical techniques and algorithms), so we're only "amateurs" in this field, but we do have many years of experience in Java/C/C++ and we both like studying algorithms, so we ended up here.
We have a day job, and it's not really related to these topics, which means that whatever time we devote to Concurrent Algorithms must be taken from our spare/leisure time, and because we enjoy it so much, we do spend a big chunk of it doing research, but with a 4-month old baby, our spare/leisure time is getting shorter and shorter (as is to be expected).
This means that, no, dear reviewers, we won't do all that insane amount of work that you suggest us doing. The Left-Right paper explains the algorithm, has the source code, has microbenchmarks for a specific use-case, and even has a proof of correctness... there's just not much more we can do... even if we wanted to!


The second reason is that they don't get it: The first time we submitted the paper to a conference, there were a few reviewers that thought the Left-Right was some kind of new concurrent tree data structure. I must admit that we're definitely not the best people in the world at writing papers, but obviously those reviews skimmed just the paper and "didn't get" what it was about.
This time, none of them thought it was a new kind of tree, but almost all suggested that it should be compared against RCU, and saying that is about the same as you coming up a new algorithm for a Reader-Writer lock, and then someone telling you that you should compare your Reader-Writer Lock with Hazard Pointers... duhhh. This only shows that they either don't know what Left-Right is, or they don't know what RCU is, or both. I don't blame them for not knowing this, because both are non-trivial concepts, but it does upset me that they call themselves "experts" in the field, and then don't what these things are about.

The Left-Right pattern is a new kind of "synchronization primitive" or "concurrency technique" or whatever you want to call it, and the closest thing to it is indeed a Reader-Writer Lock, like we mention in the paper. Comparing it with a Reader-Writer Lock is a reasonable suggestion because we can use a Left-right pattern in almost all the same scenarios that we use a Reader-Writer Lock, and indeed we do this comparison on our microbenchmarks.

Comparing the Left-Right with RCU is not very reasonable, because Left-right is meant to be used in a very different way. And yes, it can be used in a similar way, and in fact, I believe it can even be used to implement a generic RCU API, but it's besides the point... it's like saying that a lock-free queue/list can be used to implement a Reader-Writer Lock (like on the MCS algorithm), and as such, we should compare the two with each other... how would you even do that, it doesn't make sense.

The goal of the Left-Right paper is to explain the Left-right pattern and the concurrency control algorithm behind it. It's impossible to "predict" all the applications that people will apply it to. The Left-right pattern can be applied to any data structure, just like you can apply a Reader-Writer lock to any data structure. If you discover a new algorithm for a Reader-Writer Lock, does that mean that to make a paper about it you will have to apply it to ALL the data structures that the reviewers know about it, and compare it against all the lock-free data structures that exist?
Well then, if that's true, then don't expect any other new Reader-Writer Lock to ever be discovered or at least published.
How's that for stifling innovation?


And that takes me to the third reason, the peer review system is stifling true innovation: Let me exemplify in another way by telling a personal story.
Last May, I challenged Andreia to come up with a technique for a Reader-Writer Lock that using a particular kind of algorithm, would be able to scale with readers just as well as the C-RW-WP but be starvation-free all around, i.e. starvation free for readers-to-writers, writers-to-readers, readers-to-readers, and writers-to-writers. For those of you unaware, this is kind of a "Holy Grail" of Reader-Writer Locks, because it provides good Reader scalability but has no preference for either Readers or Writers, which gives good latency guarantees (as good as a Reader-Writer Lock can provide). As it so happens, she "took the bait" and did come up such an algorithm, which we then expanded to multiple variants, implemented in multiple languages, ran on microbenchmarks, made plots, and even a nice powerpoint presentation with a few animations that we showed to a couple of people.
We haven't made a paper about it yet, mostly because we didn't have time because we're fixing up the other papers we are trying to submit in order to please reviewers in conferences.

One more example just to make my point, is that last year in January (more than a year ago) we had this idea for a Lock-Free linked list that is kind of like Harris's linked list, but easy to implement in any language and easy to explain. We implemented it in 4 different languages, benchmarked it, even used it as a building block to other more complex data structures... but we didn't write a paper.
Why? Because it would take a considerable amount of time, and most likely would not be accepted because of reviewers wanting it to be compared with x and y lock-free hashset or treeset, because hey, it's (also) a "set", so why not compare it against an "hashset" ?

I could go on with more examples, but I'll spare you.
There's no point in searching on github or the concurrencyfreaks site for the Reader-Writer Lock or Lock-Free linked list mentioned above, because we haven't made it public, and the reason for that is related with time it takes to write the papers, and reviewers that stifle innovation, but also with the next reason...


The fourth and final reason, is someone else stealing you work: Andreia and I work hard on these topics, expending most of our personal time, having long discussions over lunch, dinner, throughout the night, until we figure out the best way to do a certain algorithm, or to explain why a certain technique gives the results it gives.We write thousands of lines of code until the algorithm is fine tuned and free of bugs, we write benchmarks and stress tests, we add and remove debugging code, we write new ideas just to test some behavior or hypothesis.
We don't get paid to do this, we don't register patents of our discoveries (yes, they are "discoveries", not "inventions"), we make the source code available in multiple languages, we provide plots with benchmark results done on multiple architectures (as many machines as we have access to).
You're free to use the algorithms we make available to the public for whatever purpose you want, including getting rich from it (if you manage to do so, then you certainly deserve it, lol), and the only thing we ask in return, is to be given credit for them. That's not much to ask, is it?

Sometimes, different groups discover the same ideas at almost the same time, and that's normal, and whomever publishes first takes the credit for it, and that's the way it should be (one example that happened to us, was the C-RW-WP by the Oracle research labs that we discovered independently as Scalable Reader-Writer Locks). This is not a problem and it happens more often than we might think, probably because some ideas depend on previous work, and only once that work is made public, it "unlocks" the ideas that build on that.

What is problematic is when you come up with a new idea, and then make it publicly available, and then someone comes and claims it as their own (like WriterReaderPhaser).
There is a well known psychological effect that happens when you read/hear about an idea/concept and then you kind of forget about it, until later you "come up with it" again or some small variation of it and you think it is new. Our brain can trick us in that way, because we have a tendency to make good ideas our own, and personally, I'm probably guilty of this sin on more than one occasion, like for example this one which is just an implementation of the C-RW-NP, but once someone points out that this is an already known idea, we take the time to go over carefully to understand if that is really so. The truth is, it's really hard to know every thing that has been published, and even harder for stuff that is publicly known, but not mainstream published, even on a field like this one which isn't really all that extensive. Because of these factors, it becomes easy to copy someone else's idea (on purpose or inadvertently), or simply to re-invent the wheel.

Of course, we could do like Dmitry Vyukov. He publishes his ideas and algorithms on his website and doesn't spend useless time trying to please reviewers that don't understand what he's talking about. I'm afraid I don't have the "cojones" he has, because if we put all our stuff on our web site and not with papers, then it is easy for someone else to come and say it was their idea and there is not much we can do about it.
This effect is so strong, that some researches publish papers that are deliberately made complex so that it is hard to understand all the details or even copy the idea. And let's not even go into making source code available, because apart from a few great exceptions (with The Art of Multiprocessor Programming being best example of code source sharing), most papers don't have source code.

What good is to publish an algorithm if we don't provide the source code? I thought that one of the basic tenets of the Scientific Method is Reproducibility, and how can you reproduce a certain result in this field without (at least) the source code?


For the moment, the only way we found to protect our long and hard work is to write a paper about it and get it published, but the truth is, this is taking so much of our time that all of our great ideas are getting left behind, and it frustrates me a lot. I guess it is not just a critique to the whole peer review system, but also to our capability of writing scientific papers, but the end result is that innovation is being stiffed.
How many engineers finding new innovations don't even bother to put it anywhere, or even to spend time thinking about these things because they know that they won't get any benefit from it, most likely, they won't even get the credit for it?
It's all about the Incentives, and in our case, it's mostly about the Passion, because the incentives are nearly zero.

So that's it. If you don't see many updates to this blog for the upcoming times, it doesn't means we gave up, it just means we're spending our time exploring new ideas or writing some papers about them  ;)

WriterReaderPhaser: What's (not) new about it?

I would like to show in this post that the WriterReaderPhaser is a variant of the Left-Right and is therefore, not a new synchronization primitive.

First of all, what is a "synchronization primitive"?
After some quick googling, here are the best definitions that I could come up with:
-  "Languages and Compilers for Parallel Computing": IMO, this one seems a bit too strict.
- "Encyclopedia of algorithms": This one talks about primitives applied to wait-free consensus. Not sure it's generic enough to be used for a technique where some methods are wait-free and others are blocking.
- "Understanding the Linux Kernel": Although it is specific to the linux kernel, it seems the one that makes more sense.
- "Advanced Computer Architecture": This one seems to indicate that it's the algorithm the "synchronization primitive".
- "C# collections, a detailed presentation": This one has a longer list even though it is specific to C#

I'll let you make your own conclusions on what a "synchronization primitive" is.

In the meantime, let's try to get somewhere by doing a "Reductio ad absurdum", so please turn on your bulls41t detector!


The WriterReaderPhaser uses a new type of ReadIndicator with three counters and a special use of getAndSet()/atomic_exchange() operations. From a logical point of view this is an idea similar to the ingress/egress ReadIndicator, but there is some novelty in the way it is done, so lets say it is indeed a new ReadIndicator.
What if, applying a new ReadIndicator to an already existing concurrency mechanism is "a new synchronization primitive"?
If that is so, then Andreia and I have come up with many new synchronization primitives because we discovered (and re-discovered) several ReadIndicators, some of which are mentioned here.
We can then apply these ReadIndicators to existing mechanisms that use ReadIndicators, for example the three algorithms in the "NUMA-Aware reader-Writer Locks", which are C-RW-RP, C-RW-NP, and C-RW-WP. We've discovered at least three new ReadIndicators (CLQ+Array+finalizers, DCLC, LongAdderExt), so we can say that 3x3 gives us 9 new synchronization primitives.
If that's not enough, then consider that the Left-Right variants RV, NV and GT (with the ScalableGT ReadIndicator) also use different ReadIndicators, which means it's three more new synchronization primitives, giving us a total of 12 new synchronization primitives... uouuu that's great!


The WriterReaderPhaser uses a "role reversal" compared to Left-Right, where the threads doing modifications are calling arrive()/depart() on the ReadIndicators, and the thread doing read-and-write is calling togglerVersionAndScan().
What if, doing a role reversal of an existing concurrency mechanism is "a new synchronization primitive" ?
If that is so, then let me do role reversal on a Reader-Writer lock, where I do modifications inside the readLock()/readUnlock() block, and do read-only or read-and-write operations inside the writeLock()/writeUnlock() block.
If you need a concrete example, then think of multiple threads (acquiring the readlock) doing getAndAdd()/fetch_add() on an entry in an array of counters, and then one single thread (acquiring the writelock) wants a "snapshot view" of the array. Yes, it will be "blocking", but you can have multiple threads incrementing in the array simultaneously, which means it scales ok.
Moreover, we can apply the same kind of idea to an optimistic reader-writer lock (like StampedLock or seqlock), and even apply it to Double Instance Locking, thus providing lock-free properties to the threads incrementing entries in the array.
This gives a total of 3 new synchronization primitives that we've just discovered (plus all knows variants of all reader-writer locks?)!


One of the things about the WriterReaderPhaser is that it doesn't apply the same code to both instances.
What if, applying different user code within a synchronization primitive is a "new synchronization primitive"?
In the Left-Right paper we showed an example of how to apply it as generically as the user wants. Just look at Algorithms 12, 13, 14, 15 and 16.
For a concrete example of applying different code to the two instances, then just take a look at the LRLinkedListSingle (LROLLS) at this post we did a couple months before the WriterReaderPhaser was made public:
http://concurrencyfreaks.com/2014/10/linked-lists-with-wait-free-reads-in-c.html
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/lists/LROrderedLinkedListSingle.h
which shows a very different code is used before and after the toggleVersionAndScan(), for example in the add() function.
This means that if there is anything new about applying different code on the two instances, then we already came up with it long before the WriterReaderPhaser.


WriterReaderPhaser uses the same algorithm as Left-Right, but it changes the method names. Here is a translation table from one to the other:
writerCriticalSectionEnter()  ->  arrive()
writerCriticalSectionExit()   ->  depart()
readerLock()                  ->  writersMutex.lock()
readerUnlock()                ->  writersMutex.unlock()
flipPhase()                   ->  toggleVersionAndScan()
What if, changing the named of methods in a pre-existing synchronization primitives qualifies as a "new synchronization primitive"?
If that is so, then I can create a random letter generator to make random names for the five methods mentioned above. If I restrict myself to names with 10 characters with only letters (small and capitals), then this will give 52 "letters" raised to the power of (10 + 5) =  5.496 x 10^25
Holy cow, I've just invented 10^25 new synchronization primitives... amazing!


I hope the previous paragraphs were absurd enough to show the point.

Whether the Left-Right is a new synchronization primitive or not, may depend on the definition you chose from the multiple ones at the beginning of this post, but one thing is for certain, the WriterReaderPhaser is not a "new" synchronization primitive, because (at best) it's the same synchronization primitive as Left-Right, which was discovered several years ago.

The line between Research and Engineering

Here is a good post from Joe Duffy, that pretty much says the same I've been thinking about the difference between Research and Engineering:
http://joeduffyblog.com/2013/07/13/blurring-the-line-between-research-and-engineering/

The basic message he's trying to pass is that there is not much point in having ideas if they're not practical to implement, which means that to be a good researcher you have understand what is practical and what is not, which implies some degree of exposure to the real world, and more specifically for Computer Science, a good knowledge of the tools, systems, and languages required to implement the idea.

Personally, I go even further, and see the Engineering / Research divide as a Cooking analogy.
A good engineer is like a good chef: given a recipe book and good ingredients, she can make wonderful dishes, and sometimes even with crappy ingredients and crappy recipes she can make good dishes as well (that's the difference between an excellent engineer and a good engineer).
A good researcher is more akin to a Master Chef or one of those guys running restaurants with two Michelin Stars. They may not even be the top best executioners of a recipe (they do have to be pretty good though), but they make their own recipes, they're the ones that write the cookbooks. They experiment with new combinations and sometimes come up with totally unique flavors. Their skillset is a merge of Creativity with Technical Expertise, and you won't be a Master Chef without both.

Perhaps the name "Researcher" is not appropriate to what I'm describing because in academia pretty much every one is called a "researcher"... hummm a more suitable name would be "Innovator" (although Master Chef does sound pretty cool because it reminds me of Master Chief)

Every IT company (and job applicant) is interested in the differences between good engineers and excellent engineers, but these "Innovators" are the unspoken elements, mostly because people with such a high degree of technical expertise are rare on itself, but out of those then select the ones whose creativity allows them to make up new stuff instead of just being really good at "following recipes", and then you're left with a very small subset of individuals, so small a set, that each of them is close to unique in the way he/she innovates, and therefore, there is no point in trying to come up with generalizations to identify them (apart from the fact they are really good technically, and creatively, and they come up with ideas that are actually useful).
You see, the problem isn't coming up with ideas, we have entire Universities and research centers full of PhDs, Post-Docs, and even companies with very bright engineers, all of them with plenty of ideas to go around. In the Universisites, most of the ideas are focused on stuff that can "get a PhD thesis" or "get a grant for another year", and unfortunately that's not the kind of goal that is always innovative or useful to the field of study or the progress of Mankind as a whole. On Companies, many good and excellent engineers have ideas all the time, but these are usually very narrow focused to solve specific problems (at least those are actually useful for something).
Again the cooking analogy applies here: the excellent chefs can take a recipe and adapt it to the circumstances, applying their creative skills, they can take or add a few ingredients or processes and improve an already know recipe to almost perfection. The Master Chefs on the other hand go way beyond changing known recipes.

I guess that what I want to close with is that, we need it all: we need the "Research" and the "Engineering", we need a lot of "good researchers" and "good engineers", we need plenty "excellent researchers" and "excellent engineers", and every once in a while, we also need a few "Master Chief".