saman_b

I believe one should not confine event-driven only to applications that don't do synchronisation, that's part of the misconception that leads to thinking event-driven has higher performance. This is due to the fact that part of the problem with threads (as you mentioned) is synchronisation, but this is the same problem with event-driven applications. We have a web server experiment that shows comparable performance to an event-driven web server (ulib) with its various hacks to make it faster and is always on the top list on tech-empower.

Regarding memcached, the first reference you posted is from 2015, yes in 2015 memcached was in a very bad shape in terms of synchronisation and things have significantly changed from that version with locks per hash bucket rather than a global lock, avoiding try_lock and .... So those results are too old to rely on. Seastar moves network stack to user-level and if I remember correctly the scheduler consisted of multiple ever looping threads even if there was no work to do. Considering in our experiments 40-60% of the memcached overhead were coming from network I/O, there is no surprise about their results. I would call this a hack for sure.

I have not read the Anna paper to be able to comment, but it seems that they are creating a key-value store using the actor model. I briefly schemed through the paper, and I did not find anything that points to "killing any possibility for shared memory multi-threading as a concurrency model"; this is a very bold claim and if they do claim that, they should have really strong results.

But my guess is anna's whole actor model was implemented on top of threads and shared memory multi-threading? Which will be in contrast of that bold claim. I worked with actor models and implemented one as well, it is a perfect fit for many use cases but threads at least for now are the bread and butter of multicore programming.

Having said that, all these models have their respective place in the software world. What we are trying to show in our paper , through thorough experiments, is that the misconception that event-driven has higher performance than thread programming is not fundamentally true. Therefore, falling into asynchronous programming and create hard to maintain applications [1] only due to better performance has no merit.

[1] https://cacm.acm.org/magazines/2017/4/215032-attack-of-the-k...

The results of our to be published paper clearly confirm the claims of this paper and shows that if implemented well, threads can perform and scale as good as events with not much memory overhead.

I worked on this subject during my Phd, and the result is a paper that will be published in sigmetrics2020.

We developed an M:N user-level threading library and exhaustively tested it against event-based alternatives and pthread based solutions.

We used both memcached and webservers to test it on 32 core and 64 core servers.

Even connection/pthread looks promising in terms of performance.

You can find the paper and source files here: https://cs.uwaterloo.ca/~mkarsten/papers/sigmetrics2020.html

I think it was the "flash boys" by Michael Lewis, that mentioned a Russian programmer that was very good at programming with pen and paper, and the reason was in old days there were not many computers around or you had to use punch cards to program. So the only option was to have the ability to write the code on paper and make sure everything is well thought of before you run the code on an actual computer.

It only makes sense if the interview process followed the same pattern in those days. The difference is there were not much information to remember, most probably if you knew few data structures and algorithms that was enough.

I feel the tech interview process, like so many other things, is still stuck in the past. Seems that the monks are still tying the cat to the tree without knowing why. Everyone seems unhappy about this but nothing changes.

Since IO Multiplexing in go is based on Edge-triggered epoll, you always need to do a write/read syscall (it happens underneath) before blocking the goroutine to arm the epoll to poll that specific FD. Also this approach relies on parking/unparking the goroutine and there is no way around it, since it is part of the runtime.

One way go can make it nonblocking is to do the read/write and return the result immediately, but this kind of call requires a call back function to be provided, so instead of parking/unparking the goroutine, the call back function is called (either directly or by "go cb_function"), It can be tricky to make it work, since the initial goroutine might not be allowed to call read on FD anymore (maybe exit from the goroutine if the read was unsuccessful). In addition, you still need to provide a buffer to read from, the 1 byte trick works though, but the buffer management can be done either if the read was successful or in the call back function. Also this approach makes the programming asynchronous and similar to event programming.

> I was also assuming a single kernel thread performs I/O via epoll/kqueue/etc. and either has its own queue from which other threads steal, or simply pushes results onto a random queue when requested I/O are complete. This accomplishes the migration I believe you were describing.

> When I/O needs to be done, you enqueue the uthread on the I/O queue and invoke a reserved file descriptor to notify the I/O thread, which then reshuffles its file descriptors and again calls epoll/kqueue.

If I remember correctly, what you described is similar to how golang perform I/O polling since they are using work stealing, except there is no dedicated poller thread, and threads take turn to do the polling whenever they become idle.

Also, with epoll/kqueue there is no need to enqueue uThreads and you can simply store a pointer(a struct that has reader/writer pointers to uThreads) with the epoll event that you create and recover it later from the notification, this way you can set the pointer when need to do I/O.

I agree a single poller thread does not scale as well as per kthread epoll instance, and that requires some meditation to provide a low overhead solution that does not sacrifice performance over scalability.

Thanks, so much information to absorb, let me go through all this and get back to you. I shoot you an email when I processed all this :)

I am not sure if you are referring to the runQueue being used in Linux or the whole approach. I try to answer both:

Run queues can be part of any scheduler, they are queues with runnable tasks.

But as why the approach is worth while in user space, it has to do with low cost of operations (context switches) in user space, and also using cooperative scheduling instead of preemptive. Cooperative scheduling provides more control to the user over the tasks, and also has lower overhead since there is no need to manage a quantum for each taks (thread).

Well on the surface, yes! when I started I expected the same. For now there is no work stealing among kThreads. But let me dig into the problem a bit deeper so you get an idea why it might not be very straight forward (also it very much depends on the use case).

Usually these libraries either provide their own queue or rely on underlying event system e.g. epoll/kqueue to manage the state of the light weight threads. Also, the other main part is IO multiplexing, which can be done using select/poll/epoll/kqueue ...

Lets say if they are using some sort of queue, since there is no other thread in the system, thus no synchronization required and its as simple as pushing to the tail of queue and pulling from the head. Now, if I add more threads, now I have to think how I want to synchronize among threads. The straight forward way of doing this is using the same queue and multiplex among kernel threads and use Mutex and CV. However, Mutex has high overhead and is not very scalable (pthread_mutex does not scale well under contention in Linux). What about N-kernel-thread-local queues along with Mutex? Well, if you see the documentation this approach does better but has high overhead as well. What is next? remove the queue and add some sort of lock-free queue, either MPMC, MPSC, or SPSC. This requires some work to determine which one has lower overhead, in my case I have not tested SPSC, and for now settled with MPSC. So the queue part is totally gone, since they probably did not care about all this and used a simple queue.

Next, comes the IO multiplexing. Relying on an epoll instance per kernel-thread is absolutely fine specially for cases where uThreads stick to the same kernel thread, but as soon as I introduce the notion of migration then moving from on kernel-thread to another kenrel-thread means issuing at least two system calls (in case of epoll, deregister from current epoll instance and register to the new one). This has high overhead, so I need to provide some sort of common poller that do multiplexing over multiple kernel threads, but due to having more than one kernel thread, it means connections should be properly synchronized as more than one thread might try to access a connection. Also, it has to be done in a way with low overhead as migrations for my research require to have very low overhead. Thus, the IO multiplexing part should be replaced.

So the main parts are required to be changed, and I believe the effort required to make fundamental changes to an existing system might be more than the efforts required for writing it from scratch. Also for each part implemented, I did performance optimisations and build on top of that which helped to keep the performance at an acceptable level, it would be hard to do the same with an existing system as it requires to isolate various parts and optimise each part, which requires additional effort.

I hope it makes it more clear :)

Thanks for mentioning this, it is indeed very related and very interesting. I am not sure why not me or people around me were aware of Qthread, it has very good support for various architectures and provides many interesting features. It has many similarities with I have in mind for a concurrent library, and even some research goals seems to be very close to mine. Specially the notion of affinity and locality is what I am focusing on in uThreads. I am going through the papers and the source code at the moment to see what are the similarities and differences.

uThreads is still a work in progress and I have specific plans for it in the future that might differ of what Qthreads is trying to accomplish. For now my focus is more on providing auto tuning of Clusters based on the workload. I also will try to explore the pros and cons of uThread migration based on Cluster placement (NUMA and cache locality), and from the 2008 paper it seems that it is what you are trying to study as well. I am open to collaboration if there is an ongoing study around this topic.

Seems like a very mature library, I can't answer your question before I go through their documentation and code. Also, I find your question a bit abstract, since I am not aware of the details of the problem you are trying to solve, I cannot reason why any library or tool can be better over other libraries. In your case, TBB might fit your requirements and it might be hard to give a reason to switch to another library.

I have seen this before. Those are very good points, and I am trying to move this library towards supporting a SEDA type architecture with dynamic control and auto tuning runtime parameters.

Do you have anything specific in mind? The only code I found similar to this is uC++ [1], which has way more features and more sophisticated scheduler. I am using this as part of my research and wanted to have sth very simple.

For all N:1 mappings, since there is only a single process, there is no need for synchronization, also there is no need for any scheduler as a simple queue suffice. But as soon as multiple threads are introduced, there is a need for orchestration among threads and it also changes all other aspects of the code. Of course, I could develop on top of an existing codebase, but I suspect I had to change so much that it is better to start from scratch anyway.

------------------------------------

[1]https://plg.uwaterloo.ca/usystem/uC++.html

Good idea, I probably write a blog post on this later. If you take a look at [1], I explain the difference between N:1 and M:N mappings. StateThreads uses a N:1 mapping which means you can multiplex many fibers over a single thread and to take advantage of multi-processors you can have M processes that do N:1 mapping, which is a common practice (libmill, libdill, ...). But with uThreads you can multiplex many fibers over many kernel threads.

---------------------------------

[1]https://github.com/samanbarghi/uThreads#what-are-uthreads

In libdill approach, you are probably limited to only multiplex connections over multiple kernel threads. And when a connection is accepted over a kernel thread it has to perform all further instructions over that kernel thread. So it gives you a bit of control over which cores to be utilized but after that you do not have control over what part of the code should be executed on each core.

Using uThreads you can decide what part of the code should be executed over each kernel thread and, if taskset is used, which core to execute your code. You can do this by creating Clusters and using migration or uThread creating in runtime. Thus you can decide which thread is used to multiplex connections and which one is used to run CPU bound code in addition to having a thread pool for example to do the disk IO asynchronously. Ultimately, one can create a SEDA[1] like architecture using uTrheads. Also you can always use uThread as a single threaded application.

------------------------------------------

[1] https://en.wikipedia.org/wiki/Staged_event-driven_architectu...

You are right, I have access to machines with higher number of cores, but they have multiple sockets and at some point I need to address the cross NUMA cost which adds a whole new level of complexity and design decisions.

For sure at some point the poller thread will be saturated and the program will not scale past a certain number of threads. I used to have a poller thread per cluster for better scalability, but that would add overhead for migrations between clusters, thus I had to remove it for now until I can somehow find a low overhead solution. uThreads is a work in progress and all these need to be carefully considered in the future :) Thanks for your feedback

Yes, there is a specific reason behind it, but in the future I might consider a less restrictive license.

Thanks, oh all those fancy functions. I need to improve the interface a bit, as for now everything is only based on using uThreads as the unit of concurrency. e.g., this is a recursive Fibonacci: https://github.com/samanbarghi/uThreads/blob/master/test/Fib... and a fork-and-join Fibonacci: https://github.com/samanbarghi/uThreads/blob/master/test/Fib...

There is no fork-and-join in uThreads yet, and I created it using create and join. The interface will improve in the future :)

Right, however segmented stacks are have high overhead and stack copying is not very easy in C/C++. Thus, for now uThreads only support fixed size stacks, I know it makes it harder to be used in production, and in the future I might provide optional segmented stacks. As for why not using `boost::context`, I am implementing uThreads as part of my research in uwaterloo, I wanted to have full control over the code and be able to optimize for performance as much as I can. Thus, tried to avoid relying on any third party code when I started :)

Thanks! good point; now that I look at the page, there is not a single sample code in there. I'll update it soon.

Hi, I developed uThreads. I looked at lthreads quickly, and it seems lthreads only maps multiple coroutines onto a single pthread (N:1). Although, it adds the possibility of running multiple pthreads, but each pthread can only run their local lthreads (using M threads that do N:1 mapping). However, in uThreads, uThreads can be multiplexed over multiple pthreads (thus M:N mapping). Also lthreads scheduler is based on epoll/kqueue per pthread, and uThreads is using run Queues to manage uThreads which has less overhead. Per pthread epoll/kqueue can mean better scalability for large number of threads in comparison with uThreads that is relying on a single poller thread. But since the poller thread and synchronization is very low overhead in uThreads, the scalability is not an issue (Experiments to up to 16 threads show that uThreads scale very well). Although lthreads provide compute boundaries and async IO to move lthreads over other pthreads, but this process seems to be very expensive. uThreads does not provide these features, but it provides more flexibility and control to the developer by providing migrations. Developers can use migration at any point to move the uThread to another set of kThreads to execute tasks asynchronously (By defining Clusters of kThreads, e.g., IO cluster or Compute Cluster).

Thanks :)

That would be great, my email is: saman<dot>b<at>gmail<dot>com. I am not aware of such collection, and sure I would be happy to collaborate with you and expand on this.

That sounds like a promising collection.

Thanks for the pointers. But wow, the Thai magical ward shapes matches my mental image! In an older version of this project with PHP, I even had the same idea as spire shaped verses! I need to find more resources on this. This is really interesting, thanks a lot. The calendrical system looks nice too. You got a great photo collection :) Although the last pointer points to another album I guess? I can't find any Berber patterns and it is pointing to Tattouine photos instead of Doiret.

Nice, it would be nice to see those pieces. I guess you are looking to study arabesque (http://en.wikipedia.org/wiki/Arabesque_(Islamic_art), which includes calligraphy and patterns.

"In the first mode, each repeating geometric form has a built-in symbolism ascribed to it. For example, the square, with its four equilateral sides, is symbolic of the equally important elements of nature: earth, air, fire and water. Without any one of the four, the physical world, represented by a circle that inscribes the square, would collapse upon itself and cease to exist..."

I have limited knowledge on the topic to be honest, you might find this one related though: http://www.amazon.com/Islamic-Architecture-650-1250-Richard-...

I used the digital canvas as a medium to project what I had in mind with added randomness to make it dynamic. Although the persian/islamic art, I was exposed to in childhood and teenage-hood, helped me with the idea but I was not trying to connect it to any particular known art. It would be great if you can provide some pointers to both Pali and Thai scripts/art, so I can study them and probably expand the project on them. I had some other ideas for the project, but unfortunately since arabic/persian fonts cannot handle spaces and words becomes a series of disconnected letters I could not fully implement them. e.g. I cannot make verses follow a specific path due to that problem.

Wow those pictures are really interesting, specially the first one. I have seen how they do this with Chinese calligraphy but seeing the Arabic calligraphy is surprising. Thanks for sharing :) I am sure you had fun taking those shots.

Thanks man, same for you :)

Thanks for letting me know, I tested it on chrome and firefox under Linux mint and Nazanin shows up correctly, I have to lay my hands on a Mac then.

Mine looks like a human: https://identicons.github.com/samanbarghi.png

You can read about it here : http://diet4fitness.blogspot.ca/2008/06/secret-to-buring-cal...

Qouting from this page: "I like relaxing runs, but if you do the same slog every day, you can suffer from what's sometimes called "postman's syndrome"—named for those who do the same walk every day and yet their bodies never change. Your muscles become so efficient at a movement over time that if you do it day after day and eat the same way, you never overtax your system and burn more calories to lose weight."

Basically it says postmen lose weight during the first months of their work, cause they started a new activity. But after a couple of months they start gaining weight as their body get used to walking everyday :)

What about the postman syndrome?

Relying on the results of the first week and presenting them as some misleading charts, are not the best way to encourage people to buy these desks. It is obvious this is an advertising article. In next few months your body will consider this as a habit, adapt to the situation, hit a plateau, stop burning extra calories and you start gaining weight despite the fact you are walking everyday (The postman syndrome !!). unless you change the intensity of your exercise, which is not possible at all while you are working. I am sure there are plenty of researches on postman syndrome that you could include.

So why don't you just talk about the actual benefits for body, and skip the weight loss part?

That's what I was discussing with my friend a few days ago. He had an interview with Google last month and it took him a month or two to prepare for that. he did not pass the interview, but he got an interview with Amazon this month. He was busy with other things and he could not study for the interview. He mentioned that he cannot remember most of the things he prepared and read for the last interview. I am forgetful too, and I guess 90% of people forget details about algorithms and how to answer a puzzle very fast if they don't use it everyday.

So the question is what is the value of a skill or knowledge that fades away after a month or two? I know people who got hired by Google or other big companies that forgot all the information they acquired before the interview. Cause most of it is useless for the actual job. Many logic questions or puzzles are well known and people tend to know the answer before the interview.

If I had to interview someone; I would assign him a project from the company that is part the of the job he is going to do, leave him alone in a room with a computer for a time period I expect someone to finish that specific project. Finally, I come back to see the out come.

It is good for the applicant, as there is no pressure on him (except some time constraints maybe which is not a big deal), I do not put him on the spot and he does not have to deal with his boss while answering to a question. He does not have to dig unrelated information before the interview, and he can show off his programming skills if he has any.

It is good for the company, as I do not have to spend a day interviewing and prepare for that, I will know right away from the code if the guy is a good fit or not, I can see his programming skills, I know ahead of time how long in average it takes for an internal person to do the job, so I can measure his performance relatively. I do not even have to evaluate the code in front of him, I can invite multiple candidates at the same time, put them in separate rooms. Get the results, evaluate them and invite them for the second round if I liked their code.