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

71–80 of 88 posts

Re: Implementing simple cooperative threads in C

#71

Post by winrid »

deepspace wrote: post #54
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 mec…

And it will keep happening, because there are many more people starting programming each year than old people that can teach them.

Re: Implementing simple cooperative threads in C

#73

Post by kccqzy »

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…

1. Easy on a 64-bit system. Just allocate dozens of megabytes of virtual address space with the memory being not readable nor writable. Mark a small proportion as readable and writable. In response to segfaults, grow the stack by marking even more memory as readable and writable. My toy implementation does this. It's very easy to do in about 20 lines of code.

2. You will need to reimplement thread local storage yourself. A production-quality implementation should handle this for you. Thread local storage just means having a special section of memory as a read-only template, and then duplicate them into fresh pages upon the creation of the fiber, mark them as writable, call constructors. And then remember to save the segment registers when switching. Tedious but doable.

3. You need your own locks. This is apparent even in high-level languages like Python. Notice how Python asyncio provides its own mutexes and semaphores? A production quality implementation will handle this for you, but you'll need to use them instead of the OS-provided ones.

Re: Implementing simple cooperative threads in C

#74

Post by kccqzy »

Blackthorn wrote: post #67
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…

I think there's a fourth problem that's even more dire: what do you do about blocking? A blocking call stalls the whole system. It doesn't in a non-cooperative threading environment. Various languages have "solved" this by not allowing you to use blocking calls and sometimes add syntactic sugar like async/await, but this sucks. The point of having threads is to use them like threads. At least Go gets this right.

> Various languages have "solved" this by not allowing you to use blocking calls

That is the right solution. Do you seriously think in Go when you make an apparently blocking system call, an actual blocking system call is made? No, you are calling the runtime provided version that doesn't actually block. Of course in C/C++ that needs more discipline to do.

Re: Implementing simple cooperative threads in C

#75

Post by kccqzy »

An alternative to implementing your own fibers is to use user-mode scheduled threads. It has advantages such as these are real threads, so supporting things like thread-local storage is much easier, and is much more forgiving when the code uses blocking system calls. Unfortunately the only mainstream operating system that implements it is Windows: https://docs.microsoft.com/en-us/windows/win32/procthread/us...

Re: Implementing simple cooperative threads in C

#76

Post by dfox »

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

I'm more or less sure, that original Oak/Java did cooperative threads only on the VM level by simply swaping the interpreter state without any C-level context-switching. But it was still cooperative and threads had to yield or block on something. Also the scheduling was simple round-robin with different static priorities and highest priority thread will always run unless it is blocked.

On the other hand in 90's many large portable software packages had their own userspace greenthread implementations with hand-written assembler context switches because many OSes did not have threads and these that had had wildly different and incompatible implementations. This was done by both Netscape/Mozilla (eg. NPR) and AFS (where IIRC the threading implementation is somewhat deeply integrated with used RPC mechanism), I would not be surprised if one could find remnants of something similar in LibreOffice codebase.

Re: Implementing simple cooperative threads in C

#77

Post by retSava »

winrid wrote: post #71
deepspace wrote: post #54

Earlier quoted context omitted.

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

And it will keep happening, because there are many more people starting programming each year than old people that can teach them.

And it's a Good Thing, since it fosters a inventive way of thinking around a problem rather than just reading/hearing that X exists, download that and be done. It's part of learning and honing a skill.

This doesn't mean that the implementation should then be used in practice, there are likely other solutions that are better suited, more mature, etc.

Re: Implementing simple cooperative threads in C

#78

Post by Blackthorn »

kccqzy wrote: post #74
Blackthorn wrote: post #67

Earlier quoted context omitted.

I think there's a fourth problem that's even more dire: what do you do about blocking? A blocking call stalls the whole system. It doesn't in a non-cooperative threading environment. Various languages have "solved" this by not allowing you to use blocking calls and sometimes add syntactic sugar like async/await, but this sucks. The point of having threads is to use them like threads. At least Go gets this right.

> Various languages have "solved" this by not allowing you to use blocking calls That is the right solution. Do you seriously think in Go when you make an apparently blocking system call, an actual blocking system call is made? No, you are calling the runtime provided version that doesn't actually block. Of course in C/C++ that needs more discipline to do.

> Do you seriously think in Go when you make an apparently blocking system call, an actual blocking system call is made?

Who cares? From the perspective of the programmer, it's a blocking call.

Re: Implementing simple cooperative threads in C

#79

Post by msaltz »

This is a really great explanation. I believe that libdill [1] [2] [3] works this way but this gave me a much more thorough understanding.

[1] http://libdill.org/ [2] Call to setjmp: https://github.com/sustrik/libdill/blob/de7a917bc39756f61237... [3] Call to longjmp: https://github.com/sustrik/libdill/blob/de7a917bc39756f61237...

Re: Implementing simple cooperative threads in C

#80

Post by aktau »

greggman3 wrote: post #58

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.

What was it replaced with?
Post reply on HN