Live data from Hacker News

Show HN: uThreads – Concurrent User Threads in C and C++

samanbarghi.com

51–60 of 64 posts

Re: Show HN: uThreads – Concurrent User Threads in C and C++

#51
post #49

How would something like this differ from something like Sandia National Lab's Qthreads ( http://www.cs.sandia.gov/qthreads/ )? Seems it's a tried and true solution in C that also works with C++11 (committed a test case for C++11 myself)...It is also an optional underpinning for some relatively big-name frameworks like Kokkos, Chapel, RaftLib, etc.

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.

Re: Show HN: uThreads – Concurrent User Threads in C and C++

#52
post #4

Interesting, I've recently been looking for a user level threading package in C/C++. I ended up settling on lthreads: http://lthread.readthedocs.io/en/latest/intro.html Does anyone know how it compares?

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…

> uThreads is using run Queues

This sounds like the Linux kernel. I'm curious to understand why copying this logic into user space is worth while?

Re: Show HN: uThreads – Concurrent User Threads in C and C++

#53

Earlier quoted context omitted.

It's not nonsense if, to render each pixel, you issue an HTTP request containing the scene/eye data and requested pixel coordinate, and wait for a response to come back from your magic render farm that lives in "the cloud". Now your "ray tracer" is totally I/O bound! :-)

Not sure if /s, but, to rasterize a 1920x1080 image you would make 2073600 HTTP requests? Sound reasonable.

Double that if you want to PUT the pixels on a screen.

Re: Show HN: uThreads – Concurrent User Threads in C and C++

#54
post #44

Earlier quoted context omitted.

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 thre…

> 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. Wouldn't an M:N model simply amount to work stealing among N kernel-thread-local queues? This seems like it should be a pretty straightforward extension to one of the user-level C thread packages. Or are you doing something more elaborate for your resea…

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 :)

Re: Show HN: uThreads – Concurrent User Threads in C and C++

#55
post #4

Earlier quoted context omitted.

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…

> uThreads is using run Queues This sounds like the Linux kernel. I'm curious to understand why copying this logic into user space is worth while?

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).

Re: Show HN: uThreads – Concurrent User Threads in C and C++

#56
post #13

Is there any reason you chose GPL3 or would you consider a less restrictive license like Apache or BSD?

Is there a reason you'd choose Apache or BSD instead of a freedom preserving license like GPL3?

Because I work on a few GPLv2 codebases, so we can't use GPLv3 code.

Re: Show HN: uThreads – Concurrent User Threads in C and C++

#59
post #54

Earlier quoted context omitted.

> 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. Wouldn't an M:N model simply amount to work stealing among N kernel-thread-local queues? This seems like it should be a pretty straightforward extension to one of the user-level C thread packages. Or are you doing something more elaborate for your resea…

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.…

I agree there are additional complexities with M:N. I was assuming a lock-free queue, since you'll need this for scalable work-stealing.

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.

I'm not sure whether this would scale as well as what you're doing since you mentioned an epoll-per-kernel thread, but I wouldn't be surprised if it got close since it's so I/O-bound.

Re: Show HN: uThreads – Concurrent User Threads in C and C++

#60
post #51
post #49

How would something like this differ from something like Sandia National Lab's Qthreads ( http://www.cs.sandia.gov/qthreads/ )? Seems it's a tried and true solution in C that also works with C++11 (committed a test case for C++11 myself)...It is also an optional underpinning for some relatively big-name frameworks like Kokkos, Chapel, RaftLib, etc.

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…

ooh, ok. you might also check out openshmem (http://openshmem.org/site/) and openucx (http://www.openucx.org). I'd been planning on integrating both in RaftLib just not enough cycles to get it done yet. These combined would make it much easier to maintain a relatively portable yet performant back end. My thesis research was all about locality, memory placement, and throughput for big data systems. Current work is similar but I'm not neck deep in the hardware dev world. There are current research efforts on my part outside of work, most center around the raftlib.io platform. Before I forget, you might also want to check out the graph partitioning frameworks like metis and scotch...both are used in some MPI frameworks for more optimal partitioning. To get topology data you might want to look at the hwloc framework, it's cross platform and provides input for things like NUMA/cache/PCIe topology for optimization. I haven't had a chance to integrate this hook into RaftLib, however it's just a few lines away once I find the time. If you're wondering...I started out writing my own fiber library for RaftLib. Had ports for both IBM Power and Intel, but it gets a bit tiring maintaining/optimizing for every new architecture. Qthreads and the like have been used in HPC circles for quite awhile, so it made sense. There was no way I was beating them for dev time, so might as well join them.

Based on your auto-tuning discussion...RaftLib aims to do something similar, but for big-data stream processing workloads. Here's my 2016 IJHPCA paper: http://hpc.sagepub.com/content/early/2016/10/18/109434201667...

It looks like it's behind a paywall so if you don't have access I'll update my website with the "author archive" copy sometime today...will be at ( http://jonathanbeard.io/media ) once I update it. Bottom line if there's intersected interest, definitely open to collaboration :).

Post reply on HN