Delimited continuations to the rescue of futures

[Ludovic Courtès]

Hello!

As was reported recently by Mark and others, ‘par-map’ would only use
ncores - 1, because the main thread was stuck in a
‘wait-condition-variable’ while touching one of the futures.

The obvious fix is to write ‘par-map’ like this (as can be seen from
Chapter 2 of Marc Feeley’s PhD thesis):

  (define (par-mapper mapper cons)
    (lambda (proc . lists)
      (let loop ((lists lists))
        (match lists
          (((heads tails ...) ...)
           (let ((tail (future (loop tails)))
                 (head (apply proc heads)))
             (cons head (touch tail))))
          (_
           '())))))

However, our futures did not support “nested futures”.  That is, if a
future touched another future, it would also wait on a condition
variable until the latter completes.  Thus, the above code would only
use one core.

So the fix is to support nested futures, by properly scheduling futures
that are active, and adding those that are waiting to a wait queue.
Those added to the wait queue have their continuation captured (yeah!),
so that they can be later rescheduled when their “waitee” has completed.

But then there’s still the problem of the main thread: it’s silly to let
it just wait on a condition variable when it touches a future that has
not completed yet.  So now it behaves as a worker, processing futures
until the one it’s waiting for has completed.

Figures from my 2-core/4-thread laptop:

--8<---------------cut here---------------start------------->8---
$ time ./meta/guile -c '(begin (use-modules (ice-9 threads)) (define (fibo n) 
(if (<= n 1) n (+ (fibo (- n 1)) (fibo (- n 2))))) (pk "r" (map fibo (make-list 
4 30))))'

;;; ("r" (832040 832040 832040 832040))

real    0m27.864s
user    0m27.773s
sys     0m0.031s

$ time ./meta/guile -c '(begin (use-modules (ice-9 threads)) (define (fibo n) 
(if (<= n 1) n (+ (fibo (- n 1)) (fibo (- n 2))))) (pk "r" (par-map fibo 
(make-list 4 30))))'

;;; ("r" (832040 832040 832040 832040))

real    0m10.899s
user    0m42.487s
sys     0m0.051s
--8<---------------cut here---------------end--------------->8---

The speedup is not optimal, but there’s room for optimization.

I’ve pushed the result in ‘wip-nested-futures’.  Please review and test!

Thanks,
Ludo’.