Re: Delimited continuations to the rescue of futures

[Nala Ginrut]

On Sat, 2012-11-17 at 00:36 +0100, Ludovic Courtès wrote:
> 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.
> 

Sorry, but this implementation seems to be a tail-recursive unsafe one.

------------------------------cut---------------------------
scheme@(guile-user)> (par-map 1+ (iota 10000))
ice-9/threads.scm:99:22: In procedure loop:
ice-9/threads.scm:99:22: Throw to key `vm-error' with args `(vm-run "VM:
Stack overflow" ())'.

Entering a new prompt.  Type `,bt' for a backtrace or `,q' to continue.
------------------------------end---------------------------

PS: I do know '1+' here may not be a proper test case, but it doesn't
related here anyway.
 


> 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’.
> 
>