#|
I Try to use futures for parallelization. I have 12 processors.
The task manager (Windows) tells me that only one processor is used.
Question: why aren't the futures run parallely?
I Run from the definitions window of DrRacket.
Here is a stripped snippet of my code. Sorry, can't strip further.
The time is in procedure posi. When I strip it away, execution times are 0 ms.
|#
;; Action compute short.
;; h : nr of disks
;; m : move number
;; f : starting peg
;; t : destination peg
;; Compute without recursion for move m of
;; the shortest path of moving all disks from peg f to peg t:
;; Which disk is moved.
;; From which peg.
;; To which peg.
;; Distribution of the disk among the pegs after the move.
#lang racket
(define (distribute n m)
(cond
((<= n m) (make-list n 1))
(else
(define-values (p q) (quotient/remainder n m))
(append (make-list (- m q) p) (make-list q (add1 p))))))
(define (ranges n)
(define d (distribute n (processor-count)))
(for/fold ((i 1) (r '()) #:result (reverse r)) ((k (in-list d)))
(values (+ i k) (cons (list (sub1 i) (+ i k -1)) r))))
(define-syntax (posi// stx)
(syntax-case stx ()
((_ m h f t posi)
#'(let ()
(define futures
(for/list ((r (in-list (ranges h))))
(future
(λ ()
(for/list ((d (in-range (car r) (cadr r))))
(posi m h d f t))))))
(apply append (map touch futures))))))
;========================================================================
(define (compute-short h m f t)
(define (exp2 n) (expt 2 n))
(define (mod2 n) (modulo n 2))
(define (mod3 n) (modulo n 3))
(define (pari n) (add1 (mod2 (add1 n))))
(define (rotd h d f t) (mod3 (* (- t f) (pari (- h d)))))
(define (rotr h f t) (rotd h 0 t f))
(define (mcnt m d) (quotient (+ m (exp2 d)) (exp2 (add1 d))))
(define (thrd m h f t) (mod3 (+ f (* m (rotr h f t)))))
(define (onto m h f t) (mod3 (- (thrd m h f t) (rotd h (disk m) f t))))
(define (from m h f t) (mod3 (+ (thrd m h f t) (rotd h (disk m) f t))))
(define (posi m h d f t) (mod3 (+ f (* (rotd h d f t) (mcnt m d)))))
(define (disk m) (sub1 (integer-length (bitwise-xor m (sub1 m)))))
(values
(disk m)
(from m h f t)
(onto m h f t)
(posi// m h f t posi)
#;(for/list ((d (in-range h))) (posi m h d f t))))
(define (test h)
(call-with-values
(λ () (compute-short h (sub1 (expt 2 h)) 0 1))
(λ (d f t distr) (writeln (list d f t (length distr) (apply = 1 distr))))))
(writeln (processor-count)); For my computer 12.
(for ((h (in-range 100000 500001 100000)))
(time (test h)))
;; Output:
;; 12
;; (0 2 1 100000 #t)
;; cpu time: 7500 real time: 7325 gc time: 1609
;; (0 2 1 200000 #t)
;; cpu time: 30390 real time: 29617 gc time: 6750
;; (0 2 1 300000 #t)
;; cpu time: 71312 real time: 69849 gc time: 16234
;; (0 2 1 400000 #t)
;; cpu time: 129890 real time: 127008 gc time: 28546
;; (0 2 1 500000 #t)
;; cpu time: 210140 real time: 206554 gc time: 46968
;; The results are correct (but take some time)
I ran my code wiih "no debugging" in the language menu.
When I run it with "debugging and profiling" enabled, (test 9999) goes well, but (test 10000) gives an error: ???
-: contract violation
expected: number?
given: #<void>
Futures block too easily. I expect them to block on for/list because it must allocate. I don't remember if most generic operations are future-friendly, but I guess it's necessary to use the fx version of all the primitives everywhere.
(I'm not sure if this is useful, but if possible I'd move the function disk above exp2 so there are no calls to functions defined later that may make the compiler cautious and produce safe slow code.)
My suggestion is to rewrite everything using the new threads Parallel Threads in Racket v9.0 that are easier to use.
PS: I got the same error with (test 10000) in version 9.2.
Thanks for your reply. I cannot use fixnums for they are limited to 63 bits. (expt 2 10000) has bitwise length 3010. The joy of my non-recursive functions is that they can handle very high towers of hanoi rapidly. I want it to work for millions of disks and (expt 2 1000000) needs 301029 bits. To use fixnums I would have to use lists or vectors of fixnums and to write code for arithmetic operations on them. I'll try to replace for/list by (let loop (etc) etc ...). Maybe that helps. As you suggest, maybe reordering the functions helps too.
I have similar non-recursive functions for the longest non self-crossing path (hamiltion path, circular hamilton path included). These functions need (expt 3 height). I assume the kernel of Racket already has operators that work with lists or vectors of fixnums, probably written in C++. Thanks again.
I took a look and note the (expt 2 (expt 2 10000)) hidden in plain sight, so fixnum is not an option.
I don't expect rewriting for/list to (let loop ...) to help. The problem is allocation and the list that is the result of the loop will be a problem and the allocation of bignums will be a problem too. I'd try with the new threads that are almost magic.
Reduced version of the error, tested in DrRacket 9.2 with debugging+profilling
#lang racket
(define futures
(for/list ([r (in-range 2)])
(future
(λ ()
(for/list ([d (in-range (expt 2 10000))])
7)))))
(touch (car futures))
I'll have a look into the new threads. Thanks. In my previous mail I confused bitwise length with order of magnitude.
The figures are orders of magnitude.
I reduced the example with the bug even further, but I think it's better to continue that part of the discussion in GitHub Bug with futures and debugging and profiling · Issue #5576 · racket/racket · GitHub Thanks for the report.
Did you try running your program without DrRacket? AFAIK, any debugging disables futures from running in parallel. Even with debugging off, the hooks still are there in DrRacket.
With CS I don't think allocations can serialize futures any longer, but certainly contentions for other data could. You can try using (would-be-future ...) to see if any of your code is causing a problem. Note that (would-be-future ...) also prevents parallel evaluation, so don't expect fast execution with large numbers of futures.
Yes, I did run with racket.exe. No difference.I have another program that parallelizes well, in DrRacket too.
https://github.com/joskoot/N-queens
I have replaced futures by threads and that works. They run parallely.using about 80% of the total capacity of my CPU. I have 6 cores, 2 logical processors for each core, in total 12 processors. I span 12 threads (in addition to the main thread, which is just thread-waiting). I don't know why they do not use 100% of the capacity.