www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Threading challenge: calculate fib(45) while spinning

reply jfondren <julian.fondren gmail.com> writes:
The book, "The Go Programming Language" has this simple goroutine 
example:

```go
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)
}
```



```d
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.



```d
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).
Oct 14 2021
next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
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
Oct 14 2021
next sibling parent reply jfondren <julian.fondren gmail.com> writes:
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.
Oct 14 2021
parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/14/21 9:17 PM, jfondren wrote:

 On Friday, 15 October 2021 at 03:54:17 UTC, Ali =C3=87ehreli wrote:

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

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


 Here is one that uses receiveTimeout and OwnerTerminated:


=20
 Very nice, replacing Thread.sleep with receiveTimeout and getting=20
 graceful interruption for free. This also doesn't crash.


Cool. :)

Actually, it can be shorter by checking the return value of receiveTimeou=
t:

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

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

Ali
Oct 14 2021
prev sibling next sibling parent Imperatorn <johan_forsberg_86 hotmail.com> writes:
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 ☀️
Oct 15 2021
prev sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/14/21 8:54 PM, Ali =C3=87ehreli wrote:


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


That '\r' bothered me because the actual work needs to know what the=20
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=20
character by the time it receives the OwnerTerminated message. (You can=20
observe this by adding e.g. Thread.sleep(300.msecs) after the=20
"\rFibonnacci..." line above.)

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

- An optional message when spinning (it can be further improved because=20
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 =3D 45;

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

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

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

// The delegate 'dg' should not output to stdout.
void withSpinner(Dg)(Dg dg,
                      string message =3D null,
                      Duration delay =3D 100.msecs) {
   shared(bool) spinnerDone =3D false;
   auto s =3D 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 =3D 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
Oct 15 2021
parent Steven Schveighoffer <schveiguy gmail.com> writes:
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
Oct 15 2021
prev sibling next sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 10/14/21 11:35 PM, jfondren wrote:

 The book, "The Go Programming Language" has this simple goroutine example:
 
 ```go
 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)
 }
 ```
 

 
 ```d
 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`.


 
 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.



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
Oct 15 2021
prev sibling parent Sebastiaan Koppe <mail skoppe.eu> writes:
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:

```d
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.
Oct 16 2021