note that it is not a Guile problem, the same code give also no speed up with
Racket 'future ,i have not already test it but it should block also on 'touch
future...
On Thu, Nov 10, 2022 at 11:32 AM Damien Mattei <damien.mattei@gmail.com> wrote:
Hello Zelphir,
i finally find a possible cause of no speed up of my code, i find that
using your code the procedure keep blocked on the first 'touch at line 27
here:
https://notabug.org/ZelphirKaltstahl/guile-project-euler-solutions/src/ebb19b11b465903105924adb6252f1e2ecf63859/lib/parallelism.scm#L27
if i add a 'display i got this output, see the second part ,i cut it
waiting the rest of output , it is blockers on the first 'touch until it
return ,after all the touch are fast as if all the job is done in the
first 'touch
unct-unify-minterms-set-1-unit-future : begin
set1-length = 930
set2-length = 1270
before Cartesian product set
after Cartesian product set
minterms-set-length = 1181100
minterms-set-first = ((1 1 1 x x 0 0 0 0 1) (1 1 1 1 x x 0 0 0 1))
segmts = ((0 . 196850) (196851 . 393701) (393702 . 590552) (590553 .
787403) (787404 . 984254) (984255 . 1181099))
before //
run-in-parallel : making future
run-in-parallel : making future
run-in-parallel : making future
run-in-parallel : making future
run-in-parallel : making future
run-in-parallel : making future
run-in-parallel : touching future
run-in-parallel : touching future
run-in-parallel : touching future
run-in-parallel : touching future
run-in-parallel : touching future
run-in-parallel : touching future
after //
unified-minterms-vector-1-length = 1181100
funct-unify-minterms-set-1-unit-future : end
funct-unify-minterms-set-1-unit-future : begin
set1-length = 1270
set2-length = 888
before Cartesian product set
after Cartesian product set
minterms-set-length = 1127760
minterms-set-first = ((1 1 1 1 x x 0 0 0 1) (1 1 1 1 1 x x 0 0 1))
segmts = ((0 . 187960) (187961 . 375921) (375922 . 563882) (563883 .
751843) (751844 . 939804) (939805 . 1127759))
before //
run-in-parallel : making future
run-in-parallel : making future
run-in-parallel : making future
run-in-parallel : making future
run-in-parallel : making future
run-in-parallel : making future
run-in-parallel : touching future
blocking just above
i find no explanation in Guile doc:
Scheme Procedure: *touch* /f/
Return the result of the expression embedded in future f.
If the result was already computed in parallel, |touch| returns
instantaneously. Otherwise, it waits for the computation to complete,
if it already started, or initiates it. In the former case, the
calling thread may process other futures in the meantime.
perheaps 'map is not the good way to "launch" futures?
here is my version of code with display that genrate the output above:
(define run-in-parallel
(λ (segments map-proc) ;;reduce-proc reduce-init)
"Use futures to run a procedure in parallel, if
multiple cores are available. Take a list of SEGMENTS as
input, which are ranges of values to work on. MAP-PROC is
applied to the SEGMENTS using map. When the MAP-PROC calls
for all segments finished and returned values, the
REDUCE-PROC is applied to the map result using reduce and
the REDUCE-INIT argument."
(let ([futures
(map (λ (seg)
(display-nl "run-in-parallel : making future")
(make-future
;; Need to wrap in a thunk, to not
;; immediately start evaluating.
(λ () (map-proc seg))))
segments)])
;;(let ([segment-results (map touch futures)])
(let ([segment-results (map (lambda (f)
(display-nl "run-in-parallel : touching future")
(touch f))
futures)])
segment-results
;; (reduce reduce-proc
;; reduce-init
;; segment-results)
))))
Best regards,
Damien
On Wed, Oct 12, 2022 at 11:29 PM Zelphir Kaltstahl
<zelphirkaltstahl@posteo.de> wrote:
Hi!
On 10/12/22 22:27, Damien Mattei wrote:
>
https://github.com/damien-mattei/library-FunctProg/blob/master/guile/logiki%2B.scm#L1674
>
> i commited the current version of code here with all files but it is
> huge.... :-/
>
> On Wed, Oct 12, 2022 at 10:20 PM Damien Mattei
<damien.mattei@gmail.com>
> wrote:
>
>> Mutex? i do not think code has situation where dead lock could
happen, it
>> is a code about minimalising logic expressions, it uses minterms ,
minterms
>> set is a set of minterms :like this:
>>
>> example:
>> ((1 1 0) (1 1 1)) will be unified : (1 1 x)
>> because 0 and 1 are replaced by x
>> the minterms-set could have thousands of pair (mathematic not lisp)
>> minterms to unify
>> if there is more than one x as result there is no need to continue
so i
>> escape with a continuation:
>>
>> minterms-set =
>> {
>> ((1 0 1 0) (1 1 1 0))
>> ((1 0 1 0) (1 1 0 1))
>> ((1 0 1 0) (1 0 1 1))
>> ((1 0 1 0) (0 1 1 1))
>> ((0 1 1 0) (1 1 1 0))
>> ((0 1 1 0) (1 1 0 1))
>> ((0 1 1 0) (1 0 1 1))
>> ((0 1 1 0) (0 1 1 1))
>> ((0 1 0 1) (1 1 1 0))
>> ((0 1 0 1) (1 1 0 1))
>> ((0 1 0 1) (1 0 1 1))
>> ((0 1 0 1) (0 1 1 1))
>> ((0 0 1 1) (1 1 1 0))
>> ((0 0 1 1) (1 1 0 1))
>> ((0 0 1 1) (1 0 1 1))
>> ((0 0 1 1) (0 1 1 1))
>> }
>>
>> replace { } by () to have the list, other example at another level :
>>
>> minterms-set =
>> {
>> ((0 x 1 1) (x 1 1 1))
>> ((0 x 1 1) (1 x 1 1))
>> ((0 x 1 1) (1 1 x 1))
>> ((0 x 1 1) (1 1 1 x))
>> ((x 0 1 1) (x 1 1 1))
>> ((x 0 1 1) (1 x 1 1))
>> ((x 0 1 1) (1 1 x 1))
>> ((x 0 1 1) (1 1 1 x))
>> ((0 1 x 1) (x 1 1 1))
>> ((0 1 x 1) (1 x 1 1))
>> ((0 1 x 1) (1 1 x 1))
>> ((0 1 x 1) (1 1 1 x))
>> ((x 1 0 1) (x 1 1 1))
>> ((x 1 0 1) (1 x 1 1))
>> ((x 1 0 1) (1 1 x 1))
>> ((x 1 0 1) (1 1 1 x))
>> ((0 1 1 x) (x 1 1 1))
>> ((0 1 1 x) (1 x 1 1))
>> ((0 1 1 x) (1 1 x 1))
>> ((0 1 1 x) (1 1 1 x))
>> ((x 1 1 0) (x 1 1 1))
>> ((x 1 1 0) (1 x 1 1))
>> ((x 1 1 0) (1 1 x 1))
>> ((x 1 1 0) (1 1 1 x))
>> ((1 0 1 x) (x 1 1 1))
>> ((1 0 1 x) (1 x 1 1))
>> ((1 0 1 x) (1 1 x 1))
>> ((1 0 1 x) (1 1 1 x))
>> ((1 x 1 0) (x 1 1 1))
>> ((1 x 1 0) (1 x 1 1))
>> ((1 x 1 0) (1 1 x 1))
>> ((1 x 1 0) (1 1 1 x))
>> }
>>
>> here we see some minterms are already unified
>>
>> it is not easy to read even by me because i wrote the code many
years ago
>> and is split in many files, but here it is:
>>
>> (par-map function-unify-minterms-list minterms-set)
>>
>> {function-unify-minterms-list <+ (λ (L) (apply
>> function-unify-two-minterms-and-tag L))}
>>
>> (define (unify-two-minterms mt1 mt2)
>> (function-map-with-escaping-by-kontinuation2
>> (macro-function-compare-2-bits-with-continuation) mt1 mt2))
>>
>> ;; (function-map-with-escaping-by-kontinuation2
>> (macro-function-compare-2-bits-with-continuation) '(1 1 0 1 0 1 1
0) '(1
>> 1 0 1 1 1 1 1))
>>
>> ;; list1 = (1 1 0 1 0 1 1 0)
>> ;; more-lists = ((1 1 0 1 1 1 1 1))
>> ;; lists = ((1 1 0 1 0 1 1 0) (1 1 0 1 1 1 1 1))
>> ;; clozure = #<procedure:...gos-DrRacket.scm:195:11>
>>
>> ;; #f
>> ;;
>> ;; (function-map-with-escaping-by-kontinuation2
>> (macro-function-compare-2-bits-with-continuation) '(1 1 0 1 0 1
1 0) '(1
>> 1 0 1 1 1 1 0))
>>
>> ;; list1 = (1 1 0 1 0 1 1 0)
>> ;; more-lists = ((1 1 0 1 1 1 1 0))
>> ;; lists = ((1 1 0 1 0 1 1 0) (1 1 0 1 1 1 1 0))
>> ;; clozure = #<procedure:...gos-DrRacket.scm:195:11>
>>
>> ;; '(1 1 0 1 x 1 1 0)
>> (define (function-map-with-escaping-by-kontinuation2 clozure list1 .
>> more-lists)
>> (call/cc (lambda (kontinuation)
>> (let ((lists (cons list1 more-lists))
>> (funct-continu ;; this function have the kontinuation in his
environment
>> (lambda (arg1 . more-args)
>> (let ((args (cons arg1 more-args)))
>> (apply clozure kontinuation args))))) ;; a tester: (apply clozure
(cons
>> conti args))
>>
>> ;; (newline)
>> ;; (dv list1)
>> ;; (dv more-lists)
>> ;; (dv lists)
>> ;; (dv clozure)
>> ;; (newline)
>>
>> (apply map funct-continu lists)))))
>>
>> (define-syntax macro-function-compare-2-bits-with-continuation ;;
>> continuation version of macro-compare-2-bits
>> ;; i need a macro because of external function to the clozure
>> (syntax-rules ()
>> ((_) (let ((cnt 0)) ;; counter
>> (lambda (continuation b1 b2) (if (equal? b1 b2)
>> b1
>> (begin
>> (set! cnt (add1 cnt)) ;; we leave with continuation in case cpt
> 1, we
>> can have used a flag too instead of a counter
>> (when (> cnt 1) (continuation #f)) ;; escaping with the
continuation
>> 'x))))))) ;; return x in case of (b1,b2) = (O,1) or (1,0)
>>
>> what could have caused mutex if in the latter definition above (let
((cnt
>> 0)) ;; counter was defined at top level and shared by all
threads!!! yes
>> there could have be some mutex but this is not the case, i think
even all
>> function are pure so why is it more slow with // than without?
>> Damien
>>
>> On Wed, Oct 12, 2022 at 8:45 PM Maxime Devos <maximedevos@telenet.be>
>> wrote:
>>
>>> On 12-10-2022 19:19, Damien Mattei wrote:
>>>> Hello,
>>>> all is in the title, i test on a approximately 30000 element list
, i
>>> got
>>>> 9s with map and 3min 30s with par-map on exactly the same piece of
>>> code!?
>>> > [...]
>>> >
>>>> translated from Scheme+ to Scheme:
>>>> (define unified-minterms-set-1 (map function-unify-minterms-list
>>>> minterms-set)) ;;(par-map function-unify-minterms-list
minterms-set))
>>> The definition of 'function-unify-minterms-list' and 'minterms-set'
is
>>> missing. Without a test case, we can only speculate what's going
on.
>>> (E.g., maybe it grabs a mutex).
>>>
>>> Greetings,
>>> Maxime.
I don't want to scare anyone, just maybe warn about parallel map. I
once tried
to use Guile's parallel map function for a decision tree implementation
(https://notabug.org/ZelphirKaltstahl/guile-ml/src/cf666801fea91c9fa8fa290764ff6c60b7f3949d/decision-tree.scm),
where each branch while learning the tree would call parallel map
again for sub
branches and so on. Somehow it made Guile crash (I don't have the
error message
any longer, but I did post about it on the mailing list back then.). I
never
figured out, what went wrong. All I had was pure function calls and
math inside
the thing that parallel map was supposed to run.
Ultimately I simply tried other parallelism constructs and when I
switched to
using futures instead, everything worked fine, no crashes, no errors.
Since that time, I did not use parallel map and instead used futures.
Recently I
made a parallelization thing for solving exercises of Project Euler
using
multiple cores, so that some solutions are calculated faster. Maybe
this can
help or can be adapted to another use case:
https://notabug.org/ZelphirKaltstahl/guile-project-euler-solutions/src/ebb19b11b465903105924adb6252f1e2ecf63859/lib/parallelism.scm#L11-L30
It expects ranges of things, which are called `segments` in the code.
Usually
ranges of numbers for Project Euler things. Here is the code to split
a range
into segments:
https://notabug.org/ZelphirKaltstahl/guile-project-euler-solutions/src/ebb19b11b465903105924adb6252f1e2ecf63859/lib/segment.scm
(Check any solution using it for an example.)
So this might be a bit too specific for general parallel things, but I
guess one
could change the way futures are used in `run-in-parallel`, to fit any
other
purpose.
Best regards,
Zelphir
--
repositories: https://notabug.org/ZelphirKaltstahl