V Concurrency Considerations

[ylluminate]

Transferred from a document posted here in these documents by @cristian-ilies-vasile:

V concurrency high level design

After a carefully consideration of proposed concurrency models and suggestions expressed on discord v-chat channel the high level design is based on GO language model (message passing via channels) which in turn is a variation of communicating sequential processes.

I did read papers on actor model but seems that coders do not use all the primitives provided by language and resort to threads and queues (see Why Do Scala Developers Mix the Actor Model paper).

Almost all high level requirements are taken from Proper support for distributed computing, parallelism and concurrency published on github.

Because there are many words used more or less interchangeably like coroutine, goroutine, fiber, green threads etc I will use the term green thread.

Key points

• the language will provide primitives able to deal with green threads – the green threads monitor/scheduler will be part of the language
• there will be no yield() points in code; the scheduler can suspend / resume / block / cancel any green thread in a preemtive mode
• based on memory model the green thread will be stackless or stackful
• one green thread could spawn n others green threads
• a green thread must be reentrant
• the scheduler could start a new instance of a green thread in order to accommodate load bursts (elastic computing)
• Green threads communicate using message passing (channels) instead of shared variables

Open points

• mux/demux green threads on real threads how to?
• structured concurrency
  • Martin Sústrik - http://250bpm.com/blog:71
  • Roman Elizarov - https://medium.com/@elizarov/structured-concurrency-722d765aa952
  • Alan Bateman - https://wiki.openjdk.java.net/display/loom/Structured+Concurrency
• depending on application scope could have cpu bound or io bound or both type of green threads; do we need 2 different approaches?
• Debugging
• how to catch programs bugs (Heisenbugs) before the code is shipped to prod systems?
• Formal methods / TLA+

[elimisteve]

I very very much want to see channels in V! They're one of the best ideas in Go; they're both simple and powerful, which is rare.

[elimisteve]

@ylluminate See related discussion: #1868

[cristian-ilies-vasile]

@elimisteve
It's there.
Almost all high level requirements are taken from Proper support for distributed computing, parallelism and concurrency published on github.

[dumblob]

@ylluminate @cristian-ilies-vasile @elimisteve thank you for summarizing the high level goals/requirements - they're pretty much what I envision 😉. I'll keep an eye on this to see how will everything evolve.

[dumblob]

An amendment:

the green threads monitor/scheduler will be part of the language

should read:

the green threads monitor/scheduler will be part of the language, but will be extensible by the programmer to allow changing the default scheduling behavior

[cristian-ilies-vasile]

@dumblob
I updated the document shared on google drive with your comment.

[cristian-ilies-vasile]

https://golang.org/doc/go1.14#runtime
Goroutines are now asynchronously preemptible. As a result, loops without function calls no longer potentially deadlock the scheduler or significantly delay garbage collection.

[dumblob]

@cristian-ilies-vasile that's definitely interesting (see specification), but it's still by far not fully preemptible (therefore it's called asynchronously preemptible, because it actually still just inserts safe points, but now starting from go 1.14 they'll be inserted in many more places but still carefully enough to not increase the overhead much - actually they tuned it so that the overhead is in majority of cases not measurable - though in some cases the overhead seems to be enormous as seen from this benchmark and it's equivalent in plain C which doesn't suffer from any such bottlenecks).

It's also good to note here, that the implementation of "asynchronously preemptible" in go is really tricky and is definitely not universally applicable (hehe) to other languages (e.g. because of the problem on Windows which they kind of "solved" for go semantics and internals).

Though I generally like the go design with "safe points" - I deliberately didn't go into details like this when describing the "interleaving between concurrency and parallelism" as outlined in #1868 (comment) because it's a lot of work with "little benefit" (as you see even go lang tackles preemptiveness - and to date still just partially - first now after many years of development by hundreds of engineers with many of them full time go devs).

[wanton7]

Not sure if this adds any value to this conversation but ScyllaDB is build on top this async framework https://github.com/scylladb/seastar
There is also this Redis clone that uses it https://github.com/fastio/1store

Maybe instead of fibers etc. this kind of library solution could be used and added to vlib?

[pquentin]

Regarding structured concurrency, I would suggest reading https://vorpus.org/blog/notes-on-structured-concurrency-or-go-statement-considered-harmful/ first, which explains reasons to use structured concurrency instead of go-style concurrency.

[dumblob]

@pquentin thanks for the pointer - didn't know about the Trio concurrency library (and the "nursery concept"). It's a very good approach to concurrency programming indeed. In the context of V I have these observations:

1. I'm curious how long running "background" tasks would be implemented in V as authors of the nursery concept recommend using yield to make a generator, but there are no generators/yield in V

2. Assuming my proposal gets implemented in V, nursery objects might be "simulated" using the pluggable scheduler from my proposa. The scheduler state can be tinkered with, i.e. read from and written to, any time pretty much as nursery objects has to be passed around though it'll be less convenient to traverse the one global graph in the scheduler state than to have explicit nursery object from each "split" where spawning happened. That said my proposal allows for cheap abstraction in form of an additional API modeled after nurseries, but doesn't enforce it.

   I think the only thing missing is to specify, that the pluggable scheduler has to handle "exceptions" (i.e. optionals "raised" by return error() and panics "raised" by panic() if panic() will stay in V). @cristian-ilies-vasile could you please add to your overview?

   Care would have to be taken also when implementing the automagical (de)spawning of reentrant go routines together with nurseries as that actually means dynamically at arbitrary times change the nursery objects (maybe making nursery objects just "live views" of the pluggable scheduler state?).

3. One thing to contemplate is enhancing go routines to immediately return something. E.g. a handle which could then provide methods like value<t>() t which would be a blocking method returing exactly what the routine would return if it wasn't executed with prepended go (including optionals, of course), running() bool which would check in non-blocking manner whether the routine already finished, wait( s float ) to wait for completion with a given timeout, etc. Such handle would need to support reentrancy though, so the methods above would need to distinguish which instance we're talking about 😉.

   This might ease an implementation of the nursery concept on top of the proposed primitives (with the chance of them getting included into V standard library and maybe even as built-in).

[elimisteve]

@pquentin Interesting concept, but preventing goroutines from being spawned without permitting execution of the main thread/goroutine is extremely limiting and would prevent a huge percentage of the value gained from having them in the first place.

The argument made against goroutines is honestly a severe straw man, as the normal and common way to achieve a nursery-like pattern in Go is to use a WaitGroup, or to pass a "done channel" (done := make(chan struct{})) to each function or method spawned in a goroutine, enabling each to signal when it's done doing its work.

The fact that general solutions exist in the ecosystem is eventually admitted in the middle of the 4th footnote:

[Edit: I've also been pointed to the highly relevant golang.org/x/sync/errgroup and github.com/oklog/run in Golang.]

That said, the point about stack traces only going back to the point where the goroutine was launched, rather than going all the way back to main, is an interesting one I hadn't realized 👍.

[smurfix]

I disagree. The argument against unstructured Go is not a straw man, just like the arguments against "goto" a generation years ago weren't straw men. Enforced structure allows new ways of reasoning about your code, thus enabling you to code the Happy Eyeballs algorithm in 40 lines of code instead of 400. This directly translates to fewer bugs.

Yes, cool, the ecosystem has solutions, but if it's way easier to not use them (e.g. because they require a heap of boilerplate in every function call, can't handle cancellation, and whatnot) they're ultimately not helpful. In Trio, "waiting for your child tasks" and "leaving the scope of a nursery" is exactly the same thing and requires zero lines of code (just the end of a block, in Python that's a de-indent), which again helps reduce the bug count and reduces the cognitive load on the programmer.

@dumblob The yield thing is just a convenient wrapper to package "run some code that returns a value, SOME_CODE, run some more code to clean up no matter how SOME_CODE exited" in a single function. The caller says with wrapper() as value: SOME_CODE, and Python guarantees that the cleanup code always runs when you leave the scope of that with block.

In current V (or Go) you'd use a defer block for cleanup, but that's potentially buggy – you must never forget the defer line, otherwise you have a resource leak, an unreleased lock, or whatever. Clean-up should be encapsulated in the object – the caller (i.e. the person writing the calling code) shouldn't have to think about whether, let alone how, to do it. Contrast Python's

    with open("/some/path") as file:
        write_to(file)

with

    file := os.open('/some/path')
    defer { file.close() }
    write_to(file)

IMHO that second line shouldn't exist. Not for files, not for locks, and not for nurseries.

In Go, starting a goroutine is as easy as it gets – but cleaning it up is not and needs to be done manually, esp when error handling is involved. Making coroutine creation slightly more difficult (by requiring a scoped nursery object to attach them to) is a no-brainer when the dividend you get from this is trivial cleanup.

@elimisteve

preventing goroutines from being spawned without permitting execution of the main thread/goroutine

I don't understand that sentence.

[dumblob]

In current V (or Go) you'd use a defer block for cleanup, but that's potentially buggy – you must never forget the defer line, otherwise you have a resource leak, an unreleased lock, or whatever.

Exactly that's the reason why I'm curious how would we implement the long running "background" tasks using the nursery concept in V as there are currently no means in V guaranteeing the existence of a proper defer. And having no guarantees totally defeats the purpose of the whole nursery concept 😉.

[smurfix]

Having no guarantees is detrimental to a whole lot of other constructs too. Locks for instance, or not leaving a file handle open when I'm done with using it.

So that's not an argument against nurseries, that's an argument for statically-bounded-visibility of objects – with a destructor that is guaranteed to be called exactly once. As V doesn't seem to have that concept, perhaps the first step should be to add it.

[elimisteve]

I understand pointer arithmetic is especially dangerous because it can enable security holes, but I would argue that thread synchronization bugs can also become security exploits.

@shelby3 How, specifically?

[krolaw]

I understand pointer arithmetic is especially dangerous because it can enable security holes, but I would argue that thread synchronization bugs can also become security exploits.

@shelby3 How, specifically?

Consider that a variable maintaining a value for security is being left in an indeterminate state from a data race. Targeted parallel calls cause races, causing variable to go undetermined, causing access to be granted when it shouldn't be. Attack may need to be sustained depending on likelihood of success. Memory is often reused in strange ways, the variable may not even be part of the race directly. Undefined behaviour, is undefined including leaving the vault unlocked.

[cristian-ilies-vasile]

The first 250 simple tasks successfully ran on the R U S H proof of concept (inspired by Andreas Prell's PhD thesis) .

fn x_sum(a int, b int, output_ch chan string)  {   // original function
	x:= a + b 
	output_ch <- ''
	output_ch <- strconv.v_sprintf("x_sum= %04d", x)
	output_ch <- ''
}

[dumblob]

@cristian-ilies-vasile could you put all the sources to one gist to make it easier to comment on and discuss it (with the nice side effect of not polluting this thread)? Thanks 😉.

[dumblob]

A recent note on the above-discussed topic of the difference between IO-bound computation and CPU-bound workloads by the author of Weave: https://nim-lang.org/blog/2021/02/26/multithreading-flavors.html

[cristian-ilies-vasile]

@dumblob
Thank you for the link.
I had parked the weave implementation due to some personal reasons.
However in 2021 the bottleneck is the memory bandwidth, not storage/disk/SSD see these fresh posts below. So still think that a Weave adjusted for IO could be a better approach to concurrency or no concurrency at all at the language level, and use new platforms like Microsoft dapr (dapr.io) or lunatic (https://lunatic.solutions/)

o Achieving 11M IOPS & 66 GB/s IO on a Single ThreadRipper Workstation https://tanelpoder.com/posts/11m-iops-with-10-ssds-on-amd-threadripper-pro-workstation

The new wave of thinking: One thread-per-core architecture
o Seastar is the first framework to bring together a set of extreme architectural innovations / http://seastar.io/
o The Impact of Thread-Per-Core Architecture on Application Tail Latency / https://helda.helsinki.fi//bitstream/handle/10138/313642/tpc_ancs19.pdf?sequence=1
o Glommio - a Thread-per-Core Crate for Rust & Linux / https://www.datadoghq.com/blog/engineering/introducing-glommio/
o What is io_uring? / https://unixism.net/loti/what_is_io_uring.html

[dumblob]

or no concurrency at all at the language level, and use new platforms like Microsoft dapr (dapr.io) or lunatic (https://lunatic.solutions/)

These platforms (and many other) need to be programmed though in some language which needs to do all the heavy lifting 😉.

The new wave of thinking: One thread-per-core architecture

Hm, how is this different from what we've discussed so far (i.e. one os-thread per physical core and then millions of fibers/tasks per such os-thread using work stealing with some hacks providing preemptivness to avoid starvation and some level of fairness)?

[cristian-ilies-vasile]

It is different a little bit.

• there are no user level threads/fibers -> the abstraction is called task, which at low level is just a function, a structure, few pointers and one or two channels.
• there is no preemption, all tasks are kept in stacks, one per logical CPU.
• the wave design is a good match for scientific / CPU bound applications.
• the scheduler is smart and is able to move one task from busy CPUs to the free ones.

That means once a task is put on a CPU, you cannot suspend that, just wait to finish. For a lot of tasks the load on each resource is fairy distributed due to work stealing algo.

[dumblob]

That means once a task is put on a CPU, you cannot suspend that, just wait to finish. For a lot of tasks the load on each resource is fairy distributed due to work stealing algo.

If it's really like this, then this has a serious issue with starvation - imagine writing few tasks each with an infinite loop (accidentally). It's also "not fair" and thus no real-time guarantees (required by games, audio/video calls, etc.) can be made.

Weave has some counter measures (has some "good enough" fairness and if it's not enough, it provides a shared input queue; regarding starvation I think Weave doesn't do anything, but there is an easy solution with longjmp to provide real-time guarantees on top), so it's not an issue.

But if you're talking about something else than Weave, then this starvation and unfairness is a show stopper for a default concurrency backend in V.

[elimisteve]

@dumblob Is it clear how much overhead Weave requires in order to do more sophisticated scheduling?

[dumblob]

Is it clear how much overhead Weave requires in order to do more sophisticated scheduling?

Yes - just see the benchmarks it Weave repo. It's actually basically fully amortized (not kidding!). So the only question is always: which Weave parameters should I choose for this particular set of tasks in order to trade (tail) latency for throughput and vice versa. Weave defaults are though pretty much usable even for games, so this parameter choosing shall happen only in extreme scenarios (e.g. someone writes her own kernel or audio/video signal processing server like JACK, etc.).

[cristian-ilies-vasile]

@dumblob
My RUSH project is 80% like the original design and implementation done by Andreas Prell, on his PhD thesis, so is a cousin of Weave,

I put here some non audited figures, just to have a perspective. Weave uses the word worker and I use the word robot for the same piece of code.
The figures are taken from different runs on different machines, do not try to correlate them.

A - load on each robot

robot	num_tasks_exec	robot_run_function_duration (micro sec)	delta tasks %	delta timing %
1	39,024	687,698	-2.44%	-0.61%
2	42,060	750,044	5.15%	8.40%
3	37,339	635,525	-6.65%	-8.15%
4	41,577	694,485	3.94%	0.37%
total	160000	2,767,752
avg	40000	691,938

B - tasks distribution spread by robot's state
If you do not account the last 3 entries, because the robot was sleeping, the overall overhead is less than 5%.

task	duration (micro secs)
robot_fsm_crunch_tasks_duration	302944
robot_fsm_move_tasks_on_deque_duration	8768
robot_fsm_1st_read_reqs_duration	946
send_notif_to_chief_robot_long_duration	635
send_req_to_peer_robot_duration	98
robot_fsm_1st_reqs_and_tasks_deq0_duration	64
robot_fsm_1st_fwd_reqs_duration	11
robot_fsm_ask_for_task_lr_duration	744
robot_fsm_wait_and_sleep_duration_reqs	14293
robot_fsm_wait_and_sleep_duration_tasks	16668

[dumblob]

On the way to an ultra low overhead equal-priority hard real time preemptive scheduler

Motivated (and surprised) by https://twitter.com/v_language/status/1388154640768851969 I've decided to finally research and write down my ideas I have in my head for about a year.

TL;DR It turns out V could have zero overhead full preemption on Linux and Windows Subsystem for Linux and bare metal (and maybe also some BSD) platforms.

As described in #1868 (comment) V could (should!) leverage combining cooperative scheduling of "go routines" among a dynamic pool (1:1 to number of currently powered on CPU cores) of system-level threads ("os threads") with os-triggered preemption (bare metal has counter/clock interrupt). This os-triggered preemption ("interrupt" - e.g. a signal) is though costly if not necessary (with cooperative scheduling majority is not necessary). It's the costlier the more real time responses are needed which is typical for low-latency scenarios like audio, video, games, etc. - all that are coincidentally domains which also utterly seek high-performance languages to leverage the HW up to the last bit and watt. And that's the domain where V shines or wants to shine.

Now, when WSL supports seamless Linux interaction (incl. games with high fps) through WSLg Microsoft announced support for eBPF directly in Windows (https://github.com/Microsoft/ebpf-for-windows ), it becomes viable to leverage eBPF in the Linux/Windows/BSD kernel (I'd recommend first reading some eBPF programs BCC - e.g. https://github.com/iovisor/bcc/blob/master/examples/tracing/sync_timing.py ).

The idea is, that user space can write to kernel space (thanks to eBPF) without any interrupt nor any context switch nor any locking nor any other restriction. Just write at the pointer address basically. eBPF app (to whoms kernel space memory the user space app can arbitrarily write) can be then run each time a kernel timer(s) fires (doesn't matter who has set up this timer - whether some kernel driver or some other user space app or whatever - as we just care about being woken up "frequently enough" - in case of NO_HZ there might be the need to set some in-kernel periodic timer according to the user space app needs though).

If there'll be a free running counter in eBPF app kernel space incremented only by a given user space app thread and the eBPF app will maintain a "cached" copy of this counter from last time the eBPF app ran together with monotonic timestamp of the cached value, then by comparing this timestamp it can decide whether it's already too long the user space app thread didn't increment the counter and can organize an interrupt of the given user space app thread. The user space app thread increments the counter each time the cooperative scheduling on that particular CPU (virtual) core happens. Note, that no slow atomic operations (reads, increments, etc.) are needed here as we don't care about the edge cases as in the worst case it'll just fire the interrupt negligibly more frequently.

Of course, for thousands of CPU cores there might arise the need to somehow increase efficiency of the eBPF app - maybe by grouping the timer interrupts (though hrtimers in Linux should support tens and hundreds of thousands of timers without performance degradation), but that's just an implementation detail.

Why should this be possible? Because eBPF nowadays supports:

1. maps (which is the term designating the shared memory address space between kernel space and user space)
2. attaching e.g. to perf:perf_hrtimer/timer:hrtimer_expire_entry (for periodic running of eBFP program; for multiple timers per PID struct perf_event_attr could be used to tell them apart)
3. sending a signal
4. running in non-root user space (eBPF was originally designed to be run only as root in user space) - this seems to be nowadays the default
5. running on FreeBSD (though probably with some restrictions potentially hindering this usage)
6. running on WSL (thus on Windows though indirectly - but that doesn't matter anyway to those wanting to squeeze the maximum performance out their HW) Windows natively

Implementation note: on *nix systems sending an interrupt signal to the given thread seems to be a bit more work than expected (first the signal is being sent to the process and the signal handler will most then most of the time need to "distribute" the signal to the appropriate thread: signal handlers are per-process but signal masks are per thread).

Note, this is a generic solution and I'm certain readers from other projects (incl. Go lang, D lang, Nim, Python, ... and other languages and frameworks) might jump on this and try to implement it as low hanging fruit (hey, an attribution would be nice guys 😉).

@mintsuki @UweKrueger @cristian-ilies-vasile thoughts?

Additional notes

1. The described scheduler is the simplest naive form and thus doesn't support e.g. priority groups which might (or migth not - depending on many other factors) be somewhat important instead of "blindly using it as os-level scheduler in in-V-written operating systems (i.e. big bare metal apps)".
2. This brings the burden of eBPF compiler, but no burden on distribution as eBPF apps shall be platform-agnostic if not using unstable trace points (trace points are basically hooks into various parts of Linux/BSD/Windows kernel).
3. There'll be some work needed for the scheduler to instruct the eBPF app to accommodate in running time after e.g. some CPU cores initially unavailable appeared (either not powered on or simple physically added or virtually added by the underlying hypervisor). This shouldn't be needed for CPU core removal/power_down (incl. readdition of the same CPU core) as there won't be much overhead with checking these "superfluous" stale counters in the eBPF app.

[dumblob]

Interesting - just 3 days after I published the above sketch, Microsoft announced support for eBPF directly in Windows - see https://github.com/Microsoft/ebpf-for-windows . And if they'll support some timer hooks (and I'm 100% sure they will), then I think there is no excuse to not writing a scheduler leveraging that sooner or later 😉.

[makeshyft-tom-g]

Hello Everyone,

I am super interested in trying out V to build something that uses the actor model like elixir.
is there anyone currently making such an effort using? Is V capable at this point of running such a system or is it missing something before an actor model library can be written?
Thanks for any insights.
Tom

[JalonSolov]

V has been tested with up to 100,000 goroutines, and the OS handles switching between the threads with a small amount of overhead.

True coroutines are coming.

[Wajinn]

...threads with a small amount of overhead.
True coroutines are coming.

An issue that I haven't seen brought up, but have become a bit curious about, is V's usage on small computing devices and embedded. With Go, their goroutines come at the cost of a significantly sized runtime. So with their non-optional GC and large runtime size, that causes issues for them. Thus their people were forced to come up with TinyGo to partially compensate.

Would it not perhaps be better if V had both options?

That is allow users to switch between the older (native os threads) and the newer method (green or virtual threads), or at least retire the older method to a library and make the newer method optional (so it can be switched out). That is, if there will be any issues with close to the metal or embedded type applications. Greatly appreciate any explanations to shed more light about this.

[medvednikov]

V will keep native os threads via spawn. Coroutines will be called via go.

[Wajinn]

V will keep native os threads via spawn. Coroutines will be called via go.

Excellent. Thanks for clearing that up. Was unsure if one would be chosen over the other. With both, this puts Vlang in a very nice position.

[Avey777]

Has the ongoing collaboration already arrived? Still waiting for V0.4?