HN Explorer

14 comments

[ 4.7 ms ] story [ 32.8 ms ] thread
xhgdvjky
if the stacks are mostly the same and you have far fewer processors than frames, you could use copy on write to share stacks

not useful but maybe interesting if you're into this kind of thing

kjeetgill
I'd imagine most stacks get written to almost immediately on the first function call.
rdtsc
> Can you have 1 million entities and let them all think with stackful coroutines and achieve acceptable frame rates?

Yes. With Erlang (or Elixir). Even have them preempt each others, accept connections and respond in a timely manner. If any crash, I they can be restarted without much of an issue. Just saw a few cluster nodes spike to above 1 millions processes recently, then recover, no big deal.

new_realist
You can also have them with C++, per TFA.
rdtsc
But they are not pre-emptable, and of course, they run in the same process space. So arbitrarily killing and restarting them is not as simple.

The comment was tongue in cheek, obviously, since it's different type of language and environment completely. But there is one interesting insight I learned and it is about how memory quickly becomes a bottleneck. It maybe be obvious to many here but it's still interesting to see it in practice.

I think the Erlang VM authors have arrived at that conclusion as well. There is a quite complicated allocator involved - it there are multiple carriers (large segments) for different types of memory, inside there are blocks. There are different strategies to fit the allocations (the blocks), different options share or not share free lists between different scheduler threads.

https://blog.stenmans.org/theBeamBook/#SS-Memory_Allocators

norswap
Well the above proves it's doable in C++ too. The issue hit upon is the time required to run a million of coroutines to completion (8s in the most optimized scenario). Would Erlang/Elixir do better? I don't know, but I wouldn't be so sure.
rdtsc
> Would Erlang/Elixir do better? I don't know, but I wouldn't be so sure.

Pretty sure it can. Let's give it a try:

    #!/usr/bin/env escript
    %%! +P 2000000

    %% run with ./spawn_n 1000000

    -mode(compile).

    main([NStr]) ->
        N = list_to_integer(NStr),
        T0 = erlang:system_time(millisecond),
        Parent = self(),
        Waiter = spawn(fun() -> Parent ! {final_result, wait(N, 0)} end),
        spawn_n(N, Waiter),
        Res = receive {final_result, R} -> R end,
        Dt = erlang:system_time(millisecond) - T0,
        io:format("Done in ~p sec result:~p~n", [Dt/1000.0, Res]),
        ok.

    wait(0, Acc) ->
        Acc;
    wait(N, Acc) ->
        receive {result, R} -> ok end,
        wait(N - 1, Acc + R).

    spawn_n(0, _Waiter) ->
        ok;
    spawn_n(N, Waiter) ->
        spawn(fun() -> Waiter ! {result, 1} end),
        spawn_n(N - 1, Waiter).
And it outputs:

    ./spawn_n 1000000
    Done in 1.613 sec result:1000000
In summary, it started 1M processes, all with isolated heaps, pre-emptable, with only a few KB of stack size. They didn't execute much just sent their result to a collector process and then exited. All in about 5x as fast as C++.
norswap
A most excellent answer :)
alexeiz
If the C++ code in comparison uses boost.coroutine2 library, then it's not surprising it performs poorly. Boost.coroutine2 library has an architectural flaw which causes it to throw (and then catch) an exception on coroutine completion. https://github.com/boostorg/coroutine2/issues/25
rapsey
If you need that many you must use either a higher level language (Erlang/Go) or Rust futures.
kabdib
I've seen C++ based systems that regularly harbor hundreds of thousands of stacks using quite minimal heap, 2M+ stacks when things get really busy (this, on a machine with 64GB of RAM). The primitives are a few hundred lines of pretty tame C++.

As much as I like Erlang/Go/Rust/etc., it's not a requirement.

cbetti
How quickly could the process perform a simple operation, say compare or move, across all 2m+ stacks? I.e. how long is the latest stack frozen before it is given an opportunity to work?
lossolo
Check out libdill[1] (in C): "Generally speaking, though, libdill's concurrency primitives are only a bit slower than basic C flow control statements. A context switch has been seen to execute in as little as 6 ns, with coroutine creation taking 26 ns. Passing a message through a channel takes about 40 ns."

Check also libmill[2] (from the same author), it's more Go'ish:

"It can execute up to 20 million coroutines and 50 million context switches per second."

1. http://libdill.org

2. http://libmill.org