8 ms·
Fibers, Oh My
- ncmncm 6y agoParallelism giveth, and concurrency taketh away. Technically, "concurrency", nowadays, refers to the apparatus and overhead involved in coordinating parallel activity. The more concurrency you are involved in, the less parallelism you get. It is an odd choice, but it appears to have stabilized.
- mrkeen 6y agoWhen I aim for parallelism, I seem to fare a lot worse than when I aim for concurrency. (In the parallel case, I hit Amdahl's law hard and my throughput for 1, 2, 4 cores goes something like 1, 1.8, 2.4.)
- quietbritishjim 6y ago> "concurrency", nowadays, refers to the apparatus and overhead involved in coordinating parallel activity Are you saying "highly concurrent" would mean "lots of unnecessary overhead"? I strongly dispute that is the widely accepting meaning. My understanding of concurrency vs parallelism (this is also the definition implicit in the article): * Parallel: n processes running on n physical processors * Concurrent: n processes running on m≤n (possibly m=1) physical processors due to preemptive or cooperative multitasking (the latter is common in async frameworks). (Edit: Changed m<n to m≤n. To be clear: parallelism is a type of concurrency.) A system with a lot of concurrency might not have any parallelism but still have less overhead than a parallel system e.g. in the case the processes are IO bound rather than CPU bound and need to communicate between each other a lot.
- deleted 6y ago[deleted]
- loopz 6y agoConcurrency - computer science: In computer science, concurrency is the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the final outcome. This allows for parallel execution of the concurrent units, which can significantly improve overall speed of the execution in multi-processor and multi-core systems. - Wikipedia If you start delving into how, you quickly lose the overall meaning of the concept over to specific implementations.
- kqr 6y agoThis is indeed it. Concurrency is a design/architecture concern. It's a property of the code: are parts of it independent of time with respect to each other so that they can execute out of order (including interleaved in time slices.) Parallelism is a run-time concern. Are parts of the code executing literally simultaneously?
- quietbritishjim 6y agoThat confirms my point that "concurrency" doesn't mean anything close to what the grandparent comment says, which claimed the concurrency is to do with overhead of parallelisation. What's more, it all mostly agrees with what I was saying. Look at this bit in particular: > This allows for parallel execution of the concurrent units Notice how it uses "parallel" to mean that the concurrent units (to use the quoted terminology) are actually executing at the same time, exactly as my previous comment says. OK, it avoided talking about "physical processors" or "cores", but that's what this boils down to on practical digital computers. Maybe the wording in my last comment wasn't 100% perfect, and there are some slight differences on details (e.g. the quoted Wikipedia text only seems concerned with processing-bound units of execution, not IO-bound waiting) but it's clearly talking about the same two definitions.
- ncmncm 6y agoTerminology is often not adopted universally and immediately. But different concepts need different terms. Yours also need different terms. We will find out eventually what the world decides things will be called.
- quietbritishjim 6y agoI absolutely get that (and get that not everyone does). Meanings evolve over time. Or are understood to mean different things to different people (an example I like is the almost opposing meanings of "implies" between mathematicians and mainstream English speakers). You can even use words to mean something different from the usually-accepted meaning, so long as you're clear about your own definitions up front. But you specifically claimed that your definition of "concurrency" is the main accepted one: > "concurrency", nowadays, refers to ... > ... it appears to have stabilized This is the part I disagree with. My understanding of the word "concurrency", the Wikipedia definition that someone quoted, and the meaning in the article all align, and are all different from the meaning you gave (if I haven't misunderstood it, which admittedly is very possible). So it seems very unlikely to me that we all hold the minority understanding while yours is the mainstream.
- ncmncm 6y agoI am just reporting what I observe in usage in, e.g. SG1 working group of the ISO C++ Standard committee. Parallelism is an abstract behavior to be sought for, but concurrency is about code or apparatus to manage, enable, or coordinate it.
- amelius 6y ago> cooperative multitasking (the latter is common in async frameworks) ... and is also how Windows 3.1 worked.
- guenthert 6y agoOr MacOS before OSX or Oberon or Amiga OS or how multitasking was typically implemented in FORTH or ...
- gpderetta 6y agoActually Amiga OS was fully preemptive. What it did lack was memory protection and any clear distinction between kernel and userspace.
- guenthert 6y agoYou're right. I do remember now having discussed that more than 30 years ago with someone who actually owned an Amiga then. I also remember my puzzlement when I learned that Oberon chose to support only cooperative scheduling which seemed like a step back then already.
- amelius 6y agoYes, since then we've moved away from cooperative multitasking, especially in cases where we needed low latency, such as in UIs. It is therefore a bit strange that the pattern has resurfaced lately, and has been heavily used in the implementation of UIs and webservers ... You could argue that in small systems (compared to OSes), you can keep latency under control, but systems tend to grow, and modularity of the systems works against this (modules don't need to know what other modules do or how long they take to finish their tasks).
- imtringued 6y agoCooperative multithreading has lower overhead and latency than preemptive multithreading. I don't know what you are talking about. The problem with cooperative multithreading is that you have to yield manually which is a disaster for scheduling random applications but not a problem when used inside a single application where it is isolated from everything else.
- pron 6y agoI use the word parallelism to talk about multiple processors simultaneously cooperating on solving a single task for the purpose of making the time to complete it shorter (i.e. its latency is reduced). I use concurrency to describe the problem of simultaneously managing multiple mostly-independent tasks that are competing for hardware resources and performed on one or more processors. The performance we care about is throughput, not latency, and increasing concurrency helps throughput due to Little's law (https://inside.java/2020/08/07/loom-performance/ https://inside.java/2020/08/07/loom-performance/).
- jerf 6y agoTerminology's job is to help us think, and I am distinctly underwhelmed by the track record of the "concurrency vs. parallelism" terminology. It sets up an absolution distinction for something that is almost always on a gradient, and it seems to abstract away some of the most important details to concentrate on less important details. In particular, the problem itself often tends to pick whether you're "concurrent" or "parallel", which means it's not a useful metric to analyze possible solutions with since it doesn't change based on your potential solution because it doesn't provide a gradient to descend. I find it much more productive to consider "what resources do I have" vs "what resources is my code consuming". I think this focuses on the real questions, which is not "is this more about parallelism or more about concurrency?" but, do I have enough CPU cores for what I need? Am I using GPU resources? Can I use one or the other more effectively for this problem? Is this algorithm disk or RAM limited? etc. etc. In addition to simply subsuming all the considerations about "parallel vs. concurrent", this mindset raises questions like that last one that isn't even related to that question, but more directly gets at the real issues with making code run well on the real machines you have. This does provide a gradient to descend; "oh, I'm trashing memory, I can fix it with this... I can move this CPU task to the GPU... I can trade this CPU expense to reduce memory load...", etc.
- ece 6y agoIt's interesting to see a game use case via linked pdf. They increased concurrency by overlapping the processing for two frames (alternating gameplay and rendering code) because there were too many idle cycles when doing one frame at a time (which took 25ms instead of ~16ms for 60fps). This is after they had made all the jobs run as concurrently (and parallel on SPUs) as they could and reducing locking as much as they could per frame.
- 02020202 6y agoAm I the only one who read that title in George Takei's voice?
- rkangel 6y agoThis article is a bit mixed, audience wise. If you need the first section telling you what userpace M:N scheduling is, you really shouldn't be using the second part to implement a runtime for it. You can run into any number of subtle issues that will manifest with weird behaviour and be very hard to debug. If you have to use C/C++ use a library that has done it for you. If you don't then you can use Rust, Go or Erlang/Elixir all of which have excellent implementations.
- junon 6y agoMeh I don't like the absolutism in this comment, personally. I'm well versed in coroutines and "fibers" and all of the theory surrounding it but haven't come across the formalized terminology (m:n, n:1, etc.). I'll give you another example: ropes are string classes with more complex data storage, useful for optimizing mutations and cutting down copies. The concept is easy to understand, and personally I've implemented them a number of times, but didn't know about the formalized term until the last year or so. The last sentence is a bit unfair and presumptuous, I think.
- rkangel 6y agoPerhaps it was a little absolutist. Maybe it would be better written like this: If you're not familiar with implementing schedulers and concurrent systems then beware that implementing fibers from scratch is likely to result in some subtle and hard to debug problems. If you have to use C/C++ you may well get better results using a library. If you aren't tied to the language then Erlang/Elixir, Go and Rust all have excellent implementations that have more language support.
- dosshell 6y agoI dont't agree. I'm not used to implement schedulers and concurrent systems and I wrote my own fiber-system in C a couple of months back (https://gitlab.com/dosshell/tinyfiber https://gitlab.com/dosshell/tinyfiber) after listening to the famous talk from Christian (mentioned in article). Its a bit messy, sure. But I don't think I have any subtle bugs and was not hard to debug. Performance is good too. What I want to say is: it is easy to do, even I can :P
- EE84M3i 6y agoI'm confused about subtracting the redzone size from the stack pointer. Isn't the redzone "below" the stack?
- deleted 6y ago[deleted]
- mijoharas 6y agostacks grow downwards, so the (conceptual) bottom of the stack is the top of the memory. So we take the top of the memory and subtract the red zone. This is mentioned in the linked article in this comment: // Remember, stacks grow downwards so we need a pointer to the end of the stack. char *sp = (char*)(data + sizeof data);
- EE84M3i 6y agoRight. I'm talking about this: // Make 128 byte scratch space for the Red Zone. This arithmetic will not unalign // our stack pointer because 128 is a multiple of 16. The Red Zone must also be // 16-byte aligned. sp -= 128; Isn't the red zone normally implicitly below the sp? I'm not sure why you would need to explicitly subtract the size here.
- mijoharas 6y agoEDIT - the following answer is based on an incorrect understanding of the red zone. See the reply to this for a correction. I shall leave it here as a monument to my shame. Yes, so since the stack grows downwards, we subtract the size of the red zone from the top of the stack (represented by the stack pointer), moving the new stack pointer down. This "grows" the stack (downwards remember) by the size of the red zone. Future allocations on the stack bump the pointer further downwards to grow the stack further. This leaves the 128 bytes of the red zone always below the stack. EDIT: to clarify the red zone is below the stack pointer conceptually (below the stack) but higher in memory actually (since the stack grows downwards).
- 6y ago
- DarkWiiPlayer 6y ago> and it’s not what you’re interested in doing if you actually want to take advantage of hardware threads. This is not always correct. Coroutines don't necessarily have to be the only mechanism for splitting work within an application. A master process can distribute work among several worker processes that then use coroutines internally. This still takes advantage of hardware multithreading capabilities with a low number of separate processes and then further splits the work up on several coroutines in each thread.
- emerged 6y agoPinning to hardware threads is most certainly not "always" better with fibers. I can say with certainty after very thorough performance testing across dozens of architectures and dozens of workloads. The difference can be dramatic and it's difficult to determine in advance which will.be faster (heuristics are necessary).
- deleted 6y ago[deleted]
- chrisseaton 6y ago> Pinning to hardware threads is most certainly not "always" better with fibers. The article is recommending pinning the worker (N) threads to cores, not pinning fibres (M) to cores. If it makes sense to schedule a fibre on a different core to the last one it ran on (perhaps because the data it needs is already on the other core) then you do that yourself when you pick which N to run it on, but if the N threads weren't pinned how would you keep track of which is the right one to run on to get your fibre onto a particular core? What would you do if you selected the right N for a core... but then it got moved when you went to actually run it? That's why we pin.
- emerged 6y agoI was talking about pinning workers, not fibers. Empirically, it is often better for performance to allow the OS to manage the hardware threads. Sometimes its worth pinning to a NUMA node, sometimes to a core, rarely to a cpu. Just reporting our results for many thousands of hours across a wide spectrum of test environments. I can understand it being counterintuitive, believe me it has been a shock. But it's true.
- matheusmoreira 6y ago> perhaps because the data it needs is already on the other core I'm curious. How does the scheduler know that?
- chrisseaton 6y ago
- gpderetta 6y agoI love coroutines and have written a few implementations myself. A few comments: Don't have separate get and set_context. They are hard to understand and use (see the volatile x) and are suboptimal, a swap_context is better. With this change, you do not need to store the callee save registers in the context, you can save them on the top of the stack directly, including ip. The pointer to context is just a pointer to the top of stack of the suspended context (there is no actual Context object). The perfect primitives are: // switch to 'to'. Returns another context on return, possibly, // but not necessarily 'from', also possibly null. // This is an optimization as the next funciton is enough ctx* swap_context(ctx * to); // same as swap_context, but execute fn in the 'to' context, before // returning from swap_context. 'fn' takes a pointer to the newly suspended // calling context and closure is passed through. // The function should return a context (possible 'from') or nullptr. ctx* swap_context_ex(ctx* to, ctx* (*fn)(ctx*, void*), void* closure); // create an empty context with an allocated stack. swapping to it will deallocate // the stack and terminate the context. use swap_context_ex to actually assign a // function to run on the the context ctx* make_empty_context(); edit: the bits in the article about improving the gdb and *san experience are great and it something I wasn't aware!
- Veserv 6y agoIf you do not have an independent context structure how do you avoid stack overflow in the event of a coroutine cycle with an unknown cycle length (e.g A -> B -> C -> ... -> A in an infinite loop)? For an example of where this comes up in schedulers, consider a simple periodic schedule that runs A then B then C then ... then starts back over.
- gpderetta 6y agoI do not understand, why would there be a stack overflow? The "context" is saved (pushed) at the top of the suspended coroutine stack and restored (popped) when the coroutine is resumed (each coroutine has of course its own stack), so with a simple a->b->c->...->a cycle there is no issue. In fact given swap_context_ex, yielding to the next ready task in the scheduler (and queuing the current task at the end of the queue) is trivial [1]. To simplify the code and the boundary conditions, I maintain the invariant that the ready queue always has at least one coroutine (the 'idle' coroutine). Also note how the queue node is stack allocated directly on the suspended coroutine stack. [1] https://github.com/gpderetta/libtask/blob/master/task.cpp#L149 https://github.com/gpderetta/libtask/blob/master/task.cpp#L1... ; note that here 'swap_context_ex' is called 'callcc' as is conceptually very similar to scheme call-with-current-continuation. edit: of course if you are not careful with swap_context_ex and keep pushing new functions to execute on a context without them ever returning to the (recursively) previous context, you can run out of space, but I haven't found a case where this would happen in practice (not that I looked hard enough though).
- leeter 6y agoA few things worth reading on the topic: Why the C++ committee didn't go with 'Stackful coroutines AKA Fibers' http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2018/p1364r0.pdf http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2018/p136... Raymond Chen's thoughts on where they are still useful (hint they really aren't): https://devblogs.microsoft.com/oldnewthing/20191011-00/?p=102989 https://devblogs.microsoft.com/oldnewthing/20191011-00/?p=10...
- jlokier 6y agoInteresting first link, thanks. Though I'm not impressed with the thread-local storage errors argument, as it's just an argument against low quality implementations. In a good implemention of fibers or green threads, TLS APIs should be replaced by fiber-local storage using the same APIs and fast access method, and FLS doesn't have those errors. Perhaps there's another argument against FLS, but the TLS errors argument should have considered FLS rather than leaving it implied that there's no solution.
- gpderetta 6y agoI think the actual issue with TLS is that compilers will happily hoist TLS address computations across function calls. It they didn't do that, TLS would be much safer (at least as safe as with stackless coroutines). TLS Address computation is pretty much free in non-PIE code on x86-64 linux so normally GCC doesn't do it, but on shared libraries or on other architectures, you can randomly get corruptions. I do not think that FLS (at least by default) is the right solution as it would consume a lot of memory, increase the switch overhead and add complexity for little benefit.
- HexDecOctBin 6y agoWait, are you saying that compilers can cache the pointer to TLS across function calls, even when inlining is disabled? Does this mean that the OP article is wrong when it says to use a separate getter/setter function for each TLS variable (even if we manually disable inlining for those accessor functions)? Also, regarding shared libraries, how can compiler cache the TLS address, since the compiler versions that compiled the shared library may be different that the version which is compiling the executable that links to it, and thus may have different caching behaviours?
- jeffbee 6y agoOf interest: Google has recently resumed trying to upstream its SwitchTo API into Linux. This API is 10-20x faster way to schedule threads (real threads) from userspace. https://lkml.org/lkml/2020/7/22/1202 https://lkml.org/lkml/2020/7/22/1202
- sosodev 6y agoWoah, that's really interesting. I was wondering if something like this had ever been explored.
- Qerub 6y agoOh, yes. I've been looking forward to this since I saw https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw (User-level threads....... with threads. - Paul Turner - Google) in 2013.
- new_realist 6y agoThe best solution is to standardize tooling around backtraces and switch in userspace. Kernel switchto() has its place, but only between processes. It’s much, much slower than a userspace function call.
- gpderetta 6y agoThe way it is implemented in on top of the futex machinery is very elegant. Unfortunately it still need to go through the kernel, so it is probably going to be orders of magnitude slower than pure userspace based task switching, especially after spectre.
- jeffbee 6y agoAnd yet it is an order of magnitude faster than using the kernel thread scheduler, and you get to keep working thread-locals, normal process ID behavior, etc. It's a compromise.
- matheusmoreira 6y agoGreat! I remember reading about this but I thought it'd never make it into the kernel. What blocked its inclusion last time?
- mey 6y agoThis written with the focus on the game development audience, but I'm really excited for green threads to be coming full circle on Java with Loom. (Green threads were in Java 1.1 then were quickly removed in favor of Native Threads) As a lot of the work described in the article are handled once in the JVM instead of each application dealing with it separately. Debugging tools that already work with it (except UI displays not used to displaying 1000's of threads at once). Still have to deal with the normal concurrency issues you always have, but how you approach them in the language isn't really any different then you have in the past. https://wiki.openjdk.java.net/display/loom https://wiki.openjdk.java.net/display/loom