saman_b

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.