Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Implementing simple cooperative threads in C

brennan.io

Post reply on HN
Print view View original

51–60 of 88 posts

Re: Implementing simple cooperative threads in C

#51

Post by loeg »

thornjm wrote: post #44

I wonder how hard it would be to try handle the segfault and allocate stack space on demand for these “threads”. Almost certainly stupid but a fun experiment to see if its possible... EDIT: found a nice example of this here: https://rethinkdb.com/blog/handling-stack-overflow-on-custom...

The kernel does this for you, generally. You could use a segfault handler, stack probing, and a guard page to figure out when you're out of stack, but it's not clear how you grow the C stack if you're out of contiguous virtual address space.

Re: Implementing simple cooperative threads in C

#52

Post by loeg »

nickelpro wrote: post #6
simias wrote: post #5

Earlier quoted context omitted.

Faster I can believe, but how can custom asm be more portable than setjmp/longjmp which are standard since C89? Although in this particular instance TFA also uses inline assembly to setup the stack, so it's moot.

I'm wrong, I seemed to remember many platforms not supporting them but a quick Google search reveals its just a foggy memory. I was probably thinking about ucontext actually.

ucontext is cursed with the behavior of setting and restoring signal masks with each context switch, involving a kernel syscall. If there was a ucontext-lite standard API that did not mess with signal masks you could cheaply switch green threads in userspace.

Re: Implementing simple cooperative threads in C

#53

Post by loeg »

adamnemecek wrote: post #14

Yes, this has been done ad nauseam. Do you know why no one uses it? Reasoning about cooperative threads in C is impossible. Reasoning about async C code is impossible.

> Yes, this has been done ad nauseam. Do you know why no one uses it?

Yes.

> Reasoning about cooperative threads in C is impossible.

Well, sorta. The problem with these approaches is mostly that C runtimes expect you to use the native operating system thread construct, not your own handrolled thing. If you were writing a libc for your own operating system you could use something vaguely like these libraries.

Another obvious problem is the lack of utilization of multiple CPU cores. And once you try and mix the two (M:N threading), the system becomes difficult to understand (and often has worse performance than just 1:1 threading).

I wouldn't say it's because reasoning about them is impossible, but that in practice, they are extremely difficult to use.

> Reasoning about async C code is impossible.

No, that part isn't true.

Re: Implementing simple cooperative threads in C

#54

Post by deepspace »

ausjke wrote: post #34

Other C coroutines https://github.com/hnes/libaco https://github.com/baruch/libwire https://swtch.com/libtask/ https://github.com/halayli/lthread https://github.com/Tencent/libco https://byuu.org/library/libco/

People just love re-inventing the wheel. I created my own implementation, back in the early 90s in Borland Turbo C and used it to implement a multi-terminal POS system for a busy bar. Did not know what the technique was called at the time though.

Then I joined a company in 96 and discovered that their software all ran on a custom in-house developed multitasking O/S (!). I immediately recognized the task switching mechanism and formally learned about coroutines.

Now here we are in 2020 and the youngins are still rediscovering the same thing.

Re: Implementing simple cooperative threads in C

#55

Post by jhomedall »

SlowRobotAhead wrote: post #20
asveikau wrote: post #4

Earlier quoted context omitted.

Does your blood pressure also rise from use of exceptions? Because the pattern that emerges with setjmp/longjmp is pretty similar, and that's the most common use: to simulate what other languages offer with exceptions. The most prominent libraries I can think of that force you to do this are image related, libpng and libjpeg both use longjmp to handle errors [though IIRC it's optional in the latter].

Are there exceptions in C? If I’m interviewing someone for a programming job and I see goto in there C code... they better have an amazing reason or they won’t be getting the job. Harsh, but it’s reality of how few people are suited for embedded programming.

Using goto is standard for handling errors in C. It's used pervasively in the Linux kernel.

Re: Implementing simple cooperative threads in C

#56

Post by Reelin »

chacham15 wrote: post #39

The main problems I've seen with cooperative threading (aka fibers) are threefold: 1. You need to decide how much stack space to allocate to a fiber beforehand. If you go over this limit, you will segfault. 2. Thread local storage doesnt exist anymore since you're potentially swapping between different kernel threads (and different fibers are using the same thread and will share storage). 3. Certain types of locks ca…

Regarding thread local storage - isn't that typically implemented using the segment registers (on x86 at least)? So you would need to vary those between fibers (instead of just between kernel threads) and your scheduler would have to explicitly save and restore them. I would guess that's not possible to do in portable C though.

Re: Implementing simple cooperative threads in C

#57

Post by moonchild »

ChuckMcM wrote: post #9

FWIW, the original implementation of Java (when it was known as Oak) used this trick to manage user level threading. There was also a some code to do the stack swap since you were in a virtual machine anyway, that stuff was all there to be adjusted. Random meta note brenns10, the idiom for giving up the processor is 'yield' (rather than 'relinquish') it is common in cooperative systems. That said, the code in Java th…

And now they've come full circle, offering coroutines in userland java code again.

Re: Implementing simple cooperative threads in C

#58

Post by greggman3 »

This style of coop multi-tasking was in Crash Team Racing on PS1 for a while. Unfortunately on a machine with only 2meg of ram it turned out to take too much memory and be too fragile. The stacks had to be small, add one printf for debugging and you'd overflow the stack. Eventually it was torn out.

Re: Implementing simple cooperative threads in C

#59

Post by pansa2 »

brenns10 wrote: post #12
ChuckMcM wrote: post #9

FWIW, the original implementation of Java (when it was known as Oak) used this trick to manage user level threading. There was also a some code to do the stack swap since you were in a virtual machine anyway, that stuff was all there to be adjusted. Random meta note brenns10, the idiom for giving up the processor is 'yield' (rather than 'relinquish') it is common in cooperative systems. That said, the code in Java th…

> FWIW, the original implementation of Java (when it was known as Oak) used this trick to manage user level threading. There was also a some code to do the stack swap since you were in a virtual machine anyway, that stuff was all there to be adjusted. I never knew Java did this. I figured most "interpreted" languages (via direct interpreters or bytecode) would be trivial to implement any kind of threads (even pre-emp…

> I figured most "interpreted" languages would be trivial to implement any kind of threads, because at any point the interpreter could decide to save the state of one language thread and switch to another, without bothering the interpreter's own stack.

Some language interpreters keep the "virtual" stack and the C stack separate like this, including current versions of Lua. As you suggest, this allows Lua to support coroutines which each have their own virtual stack.

However other interpreters, such as CPython, keep both stacks synchronized. In this case, a call in the interpreted language corresponds to a call in C - recursively back into the main interpreter loop. This is why Python's generators do not have independent stacks.

The awfully-named "Stackless Python" [0] breaks the synchronization between stacks, to allow Python to support stackful coroutines.

At least, the above was my understanding until recently. The upcoming Lua 5.4 changes to using a recursive call [1], like CPython, but still supports stackful coroutines. I don't know how this is implemented.

[0] https://github.com/stackless-dev/stackless

[1] https://github.com/lua/lua/commit/196c87c9cecfacf978f37de4ec...

Post reply on HN