Re: map-par slower than map

[Mikael Djurfeldt <mikael@djurfeldt.com>]

[-- Attachment #1: Type: text/plain, Size: 9889 bytes --]

Also, I would believe that any crashes in this context are neither due to
the futures implementation nor par-map et al. I would think that crashes
are due to the Guile basic thread support itself.

On Tue, Oct 25, 2022 at 11:07 AM Mikael Djurfeldt <mikael@djurfeldt.com>
wrote:

> A piece of background on par-map:
>
> When I introduced par-map et al the only ambition was to have simple
> language constructs to invoke parallelism. The use case I had in mind was
> course grained parallelism where each piece of work is somewhat
> substantial. Back then, a thread was launched for each piece of work,
> however there was also a thread pool such that not all of the overhead of
> launching new threads always was required.
>
> Since then, par-map has been rewritten (by others) to be based on futures.
> (And now the thread pool is localized in the futures implementation---as
> "workers".) Looking in the code now, I think it is fair to say that it is
> still intended for coarse grained parallelism. There is some heavy lifting
> going on with mutexes and condition variables as well as shuffling around
> with list pairs.
>
> So, applying par-map on a huge list with small amount of work per item was
> never and still isn't the intended use case.
>
> It would of course be interesting if the code could be improved to support
> fine grained parallelism. :-)
>
> Best regards,
> Mikael
>
> On Wed, Oct 12, 2022 at 11:30 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
>>
>>
>>

[-- Attachment #2: Type: text/html, Size: 12781 bytes --]