Thread overview
Threading challenge: calculate fib(45) while spinning
Oct 15, 2021
jfondren
Oct 15, 2021
Ali Çehreli
Oct 15, 2021
jfondren
Oct 15, 2021
Ali Çehreli
Oct 15, 2021
Imperatorn
Oct 15, 2021
Ali Çehreli
Oct 16, 2021
Sebastiaan Koppe
October 15, 2021

The book, "The Go Programming Language" has this simple goroutine example:

func main() {
    go spinner(100 * time.Millisecond)
    const n = 45
    fibN := fib(n) // slow
    fmt.Printf("\rFibonacci(%d) = %d\n", n, fibN)
}

func spinner(delay time.Duration) {
    for {
        for _, r := range `-\|/` {
            fmt.Printf("\r%c", r)
            time.Sleep(delay)
        }
    }
}

func fib(x int) int {
    if x < 2 {
        return x
    }
    return fib(x-1) + fib(x-2)
}

Attempt #1, with std.concurrency:

import std.concurrency : spawn;
import core.thread : Thread;
import std.stdio : writefln, writef, stdout;
import std.datetime : msecs, Duration;

void main() @safe {
    (() @trusted { spawn(&spinner, 100.msecs); })();
    const n = 45;
    const fibN = fib(n); // slow
    writefln!"\rFibonacci(%d) = %d"(n, fibN);
}

void spinner(Duration delay) @safe {
    (() @trusted { Thread.getThis.isDaemon(true); })();
    while (true) {
        foreach (char c; `-\|/`) {
            writef!"\r%c"(c);
            (() @trusted { stdout.flush; })();
            (() @trusted { Thread.sleep(delay); })();
        }
    }
}

int fib(int x) pure @safe @nogc {
    if (x < 2)
        return x;
    return fib(x - 1) + fib(x - 2);
}

This version has two problems:

  1. a race condition with isDaemon: if main() ends before isDaemon(true) is called, then the program never ends because the kill-non-daemon-threads module destructor is called while the new thread isn't a daemon thread.

  2. it crashes about 10% of the time on exit (in dmd, gdc, and ldc). valgrind on a gdc build complains about "Conditional jump or move depends on uninitialised value(s)" early on.

Attempt #2, with std.parallelism:

import std.parallelism : task, taskPool;
import core.thread : Thread;
import std.stdio : writefln, writef, stdout;
import std.datetime : msecs, Duration;

void main() @safe {
    auto spin = task!spinner(100.msecs);
    taskPool.put(spin);
    const n = 45;
    const fibN = fib(n); // slow
    writefln!"\rFibonacci(%d) = %d"(n, fibN);
}

void spinner(Duration delay) @safe {
    while (true) {
        foreach (char c; `-\|/`) {
            writef!"\r%c"(c);
            (() @trusted { stdout.flush; })();
            (() @trusted { Thread.sleep(delay); })();
        }
    }
}

int fib(int x) pure @safe @nogc {
    if (x < 2)
        return x;
    return fib(x - 1) + fib(x - 2);
}

This version continues to spin after the Fibonacci result is printed, despite https://dlang.org/phobos/std_parallelism.html#.taskPool saying that taskPool worker threads are daemon by default, and despite various attempts to add isDaemon(true) calls.

Is there a d version without these problems, and without varying substantially from the go (by e.g. having the spinner poll to see if it should exit gracefully).

October 14, 2021
On 10/14/21 8:35 PM, jfondren wrote:
> The book, "The Go Programming Language" has this simple goroutine example:

Here is one that uses receiveTimeout and OwnerTerminated:

import std.stdio;
import std.concurrency;
import core.thread;

void main() {
  spawnLinked(&spinner, 100.msecs);
  enum n = 45;
  const fibN = fib(n); // slow
  writefln!"\rFibonacci(%d) = %d"(n, fibN);
}

void spinner(const(Duration) delay) {
  for (;;) {
    foreach (r; `-\|/`) {
      writef!"\r%c"(r);
      stdout.flush();
      bool done;
      receiveTimeout(delay,
                     (OwnerTerminated msg) {
                       done = true;
                     });
      if (done) {
        return;
      }
    }
  }
}

auto fib(int x) {
  if (x < 2) {
    return x;
  }
  return fib(x-1) + fib(x-2);
}

Ali
October 15, 2021
On Friday, 15 October 2021 at 03:54:17 UTC, Ali Çehreli wrote:
> On 10/14/21 8:35 PM, jfondren wrote:
>> The book, "The Go Programming Language" has this simple goroutine example:
>
> Here is one that uses receiveTimeout and OwnerTerminated:
>

Very nice, replacing Thread.sleep with receiveTimeout and getting graceful interruption for free. This also doesn't crash.
October 14, 2021
On 10/14/21 9:17 PM, jfondren wrote:
> On Friday, 15 October 2021 at 03:54:17 UTC, Ali Çehreli wrote:
>> On 10/14/21 8:35 PM, jfondren wrote:
>>> The book, "The Go Programming Language" has this simple goroutine example:
>>
>> Here is one that uses receiveTimeout and OwnerTerminated:
>>
> 
> Very nice, replacing Thread.sleep with receiveTimeout and getting graceful interruption for free. This also doesn't crash.

Cool. :)

Actually, it can be shorter by checking the return value of receiveTimeout:

      if (receiveTimeout(delay, (OwnerTerminated msg) {})) {
        return;
      }

I didn't use this method earlier because I was afraid an unexpected message might make receiveTimeout return 'true'. But I've tested just now: Only the expected OwnerTerminated makes it return 'true'.

Ali

October 15, 2021
On Friday, 15 October 2021 at 03:54:17 UTC, Ali Çehreli wrote:
> On 10/14/21 8:35 PM, jfondren wrote:
>> [...]
>
> Here is one that uses receiveTimeout and OwnerTerminated:
>
> import std.stdio;
> import std.concurrency;
> import core.thread;
>
> void main() {
>   spawnLinked(&spinner, 100.msecs);
>   enum n = 45;
>   const fibN = fib(n); // slow
>   writefln!"\rFibonacci(%d) = %d"(n, fibN);
> }
>
> void spinner(const(Duration) delay) {
>   for (;;) {
>     foreach (r; `-\|/`) {
>       writef!"\r%c"(r);
>       stdout.flush();
>       bool done;
>       receiveTimeout(delay,
>                      (OwnerTerminated msg) {
>                        done = true;
>                      });
>       if (done) {
>         return;
>       }
>     }
>   }
> }
>
> auto fib(int x) {
>   if (x < 2) {
>     return x;
>   }
>   return fib(x-1) + fib(x-2);
> }
>
> Ali

This is a "similar" approach to what Erlang does. I have always liked it ☀️
October 15, 2021

On 10/14/21 11:35 PM, jfondren wrote:

>

The book, "The Go Programming Language" has this simple goroutine example:

func main() {
     go spinner(100 * time.Millisecond)
     const n = 45
     fibN := fib(n) // slow
     fmt.Printf("\rFibonacci(%d) = %d\n", n, fibN)
}

func spinner(delay time.Duration) {
     for {
         for _, r := range `-\|/` {
             fmt.Printf("\r%c", r)
             time.Sleep(delay)
         }
     }
}

func fib(x int) int {
     if x < 2 {
         return x
     }
     return fib(x-1) + fib(x-2)
}

Attempt #1, with std.concurrency:

import std.concurrency : spawn;
import core.thread : Thread;
import std.stdio : writefln, writef, stdout;
import std.datetime : msecs, Duration;

void main() @safe {
     (() @trusted { spawn(&spinner, 100.msecs); })();
     const n = 45;
     const fibN = fib(n); // slow
     writefln!"\rFibonacci(%d) = %d"(n, fibN);
}

void spinner(Duration delay) @safe {
     (() @trusted { Thread.getThis.isDaemon(true); })();
     while (true) {
         foreach (char c; `-\|/`) {
             writef!"\r%c"(c);
             (() @trusted { stdout.flush; })();
             (() @trusted { Thread.sleep(delay); })();
         }
     }
}

int fib(int x) pure @safe @nogc {
     if (x < 2)
         return x;
     return fib(x - 1) + fib(x - 2);
}

This version has two problems:

  1. a race condition with isDaemon: if main() ends before isDaemon(true) is called, then the program never ends because the kill-non-daemon-threads module destructor is called while the new thread isn't a daemon thread.

You can also just spawn a thread directly with Thread, which I believe allows you to set the daemon-ness from main.

>
  1. it crashes about 10% of the time on exit (in dmd, gdc, and ldc). valgrind on a gdc build complains about "Conditional jump or move depends on uninitialised value(s)" early on.

The crash is likely because you are using D i/o utilities, and the runtime is shut down. Technically it shouldn't cause a problem, but possibly there are things that are needed deep inside writef.

If you switch to printf, it will probably work.

-Steve

October 15, 2021
On 10/14/21 8:54 PM, Ali Çehreli wrote:

>    writefln!"\rFibonacci(%d) = %d"(n, fibN);

That '\r' bothered me because the actual work needs to know what the spinner is doing to clear its remaining character.

>        receiveTimeout(delay,
>                       (OwnerTerminated msg) {

And there is a race condition because the spinner can print an extra character by the time it receives the OwnerTerminated message. (You can observe this by adding e.g. Thread.sleep(300.msecs) after the "\rFibonnacci..." line above.)

So, I improved it by removing both of those concerns as well as adding the following:

- An optional message when spinning (it can be further improved because there is an extra space character if the message is empty)

- A withSpinner() function to work with any delegate

The only requirement is that the delegate should not output to stdout if we want a clean output.

import std.stdio : stdout, writef, writefln;
import std.concurrency : receiveTimeout, send, spawn;
import std.traits : ReturnType;
import core.thread : Duration, msecs, Thread;
import std.range : cycle, repeat, walkLength;
import std.format : format;

void main() {
  enum n = 45;

  int fibN; // Left mutable not to complicate the example

  withSpinner({
      fibN = fib(n); // slow
    },
    format!"Calculating fib(%s)"(n));

  writefln!"Fibonacci(%d) = %d"(n, fibN);
}

// The delegate 'dg' should not output to stdout.
void withSpinner(Dg)(Dg dg,
                     string message = null,
                     Duration delay = 100.msecs) {
  shared(bool) spinnerDone = false;
  auto s = spawn(&spinner, message, delay, &spinnerDone);

  // Do work while spinning
  dg();

  // Tell the spinner to stop (the value does not matter)
  s.send(0x0FF);

  // Busy(ish) wait until the spinner is done
  while (!spinnerDone) {
    Thread.yield();
  }
}

void spinner(string message,
             Duration delay,
             shared(bool) * done) {
  foreach (c; `-\|/`.cycle) {
    if (receiveTimeout(delay, (int _) {})) {
      // Stop request received

      // Clear the spinning message
      writef("\r%s  \r", " ".repeat(walkLength(message)));

      // Tell the user we are done
      *done = true;
      return;
    }
    writef!"\r%s %c"(message, c);
    stdout.flush();
  }
}

auto fib(int x) {
  if (x < 2) {
    return x;
  }
  return fib(x-1) + fib(x-2);
}

Ali


October 15, 2021

On 10/15/21 10:01 AM, Ali Çehreli wrote:

> >

    writefln!"\rFibonacci(%d) = %d"(n, fibN);

That '\r' bothered me because the actual work needs to know what the spinner is doing to clear its remaining character.

I would expect the original go code had the same problem.

-Steve

October 16, 2021

On Friday, 15 October 2021 at 03:35:44 UTC, jfondren wrote:

>

The book, "The Go Programming Language" has this simple goroutine example:

[...]

Here is a similar implementation using the concurrency library:

import concurrency;
import concurrency.stream;
import concurrency.sender : justFrom;
import concurrency.operations : via, race;
import concurrency.thread : ThreadSender;
import core.time : msecs;
import std.stdio : writef, writefln, stdout;
import core.thread : Thread;

void main() @safe {
    enum chars = `-\|/`;
    auto spinner = infiniteStream(0)
        .scan((int acc, int _) => acc + 1, 0)
        .collect((int i) shared @trusted {
            writef("\r%c", chars[i % chars.length]);
            stdout.flush();
            Thread.sleep(100.msecs);
        })
        .via(ThreadSender());

    enum n = 45;
    auto work = justFrom(() => fib(n));

    auto result = race(spinner, work).syncWait.value;
    writefln("\rFibonacci(%d) = %d", n, result.get);
}

int fib(int x) pure @safe @nogc {
    if (x < 2)
        return x;
    return fib(x - 1) + fib(x - 2);
}

Go has language support so it is a bit unfair to compare it.

But this code will properly handle errors (in case writef or flush throws), and as well as having an explicit synchronization point so that the final writeln is always after the spinner is done.