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