From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Damien Mattei Newsgroups: gmane.lisp.guile.devel,gmane.lisp.guile.user Subject: Re: map-par slower than map Date: Tue, 25 Oct 2022 16:09:43 +0200 Message-ID: References: <5608809c-89a2-118c-5c05-c46ac3a0e21b@posteo.de> Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="00000000000067770105ebdc76e9" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="1314"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Zelphir Kaltstahl , guile-user , guile-devel To: mikael@djurfeldt.com Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Tue Oct 25 16:11:59 2022 Return-path: Envelope-to: guile-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1onKet-00006z-EQ for guile-devel@m.gmane-mx.org; Tue, 25 Oct 2022 16:11:59 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1onKd2-0001wN-M1; Tue, 25 Oct 2022 10:10:04 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1onKd0-0001RD-1J; Tue, 25 Oct 2022 10:10:02 -0400 Original-Received: from mail-ej1-x632.google.com ([2a00:1450:4864:20::632]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1onKcw-0001Ef-BP; Tue, 25 Oct 2022 10:10:01 -0400 Original-Received: by mail-ej1-x632.google.com with SMTP id t25so7285460ejb.8; Tue, 25 Oct 2022 07:09:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=tTLt+Sbaf5S2shrXTsjzKuOJ7SfpoPhvuUwZPVyOaqw=; b=ScMkfPlG0pJfro7D1N/a/hXDgwG67o2vi9Z5ICXnoZ6TPqMzIao8/dAqMZ7xCSmZuc 6WQfIi1E1X839vkqmtS1c13QduSPY5nUdA/6DD4/9a8lJ56FGSLHFFAM/HZHsS37sHGQ sQnc/RoVOr7rHzw24e5oc+gkT/iXcquUpFsYOEdaiXU6T0EuLJ6e+HMKxcAa9B8fd7V3 tGhURaqjoPyup2m90rIWWfrjzA39pG4nzX9z/ya1BHjX8MRoCClowv1ysI16njJ+4hAc iqOeMad5iCct1IoNZv7FxWPvVyq1fLUMToZ5oIYDGM0cUuZ4XbKVffD1uUkxFa7I4onL IEgQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=tTLt+Sbaf5S2shrXTsjzKuOJ7SfpoPhvuUwZPVyOaqw=; b=RGZ46FtZY3exStRMN9x8nDf+7g53PSxMpUHKcI+4v1x6MQpEuXx8R6KBogu8Gw/s+8 9k+q1xNbXL/dUdoKhVTQlYz1KIZZrSx04v11L0Nn4URCosS0WwBcrLLvRMFNG3jFIBb/ NHfs/GB8TzmRPBNdjwdDpXz6AwUagje6aaqHaj6gCYAnYrEZfnUXjDF1a57CmwxNHQba 9HFNyVYw6D7MrRjJ0ZE06TCR+x9JbdwP0/wBq6zTwlOV5Ko5FbSlf583emzSOm8Q0KmJ g+TnS/gbZBA04w8FxjbQWi1AGmIOLeaoaUJ7Y1NExMcoBkbMZOWGxkdZiyRLejCRrzVw BLrw== X-Gm-Message-State: ACrzQf0dBExYpB3gV3MTv1vSNqm7T+X9t5Cs36kEk384otKoBp2LpgIg B4ajllf99wt2jVDyskEEA+EF+R6zQKlcxxufjWM= X-Google-Smtp-Source: AMsMyM7Wj0/cpFv1BGs6dIJ3NixOr4O30G/49r5zBGjU/h3B4uMa3t/f2iSL7vR62+uJt2b/VDEiTrLqPi4K3ZowM1I= X-Received: by 2002:a17:906:844b:b0:7a9:f67e:a5d4 with SMTP id e11-20020a170906844b00b007a9f67ea5d4mr7400281ejy.136.1666706995376; Tue, 25 Oct 2022 07:09:55 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2a00:1450:4864:20::632; envelope-from=damien.mattei@gmail.com; helo=mail-ej1-x632.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: "guile-devel" Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.lisp.guile.devel:21454 gmane.lisp.guile.user:18682 Archived-At: --00000000000067770105ebdc76e9 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hello Mikael, your message comes very well because i decided yesterday,partly due to the discussion in mailing list, to review all the // method used in my code and to use them to perform benchmark to see which one is preferable to use with the algorithmic problem of putting a logic expression in its canonical minimal disjunctive or conjunctive form. I used 4 methods: -sequential (map with no //) -par-map (//) -threads (//) -futures (//) But, of course, the data structure is not the same now, it will be lists with sequential and par-map and vectors with threads and futures, as i already experimented problems (blocking, crashing,false results) with some (threads,futures) . Also i have solved the concurrent access problem to the hash table with lists or vectors depending if i use map or par-map or futures and threads, but the algorithm remains the same in all case. I computed from C1,C2,C3 ... to C12 (i do not write the logical expressions here, some peoples seeing those infix mathematical expression coming in the mailing list as drones in the peaceful sky of the lambda calculus expressions ;-) ) but here is the results: map: 10' 17" for C12 (5" for C10) par-map: 1'21" for C10, more than 2h 40' for C12 threads: blocks randomly before C7 (works but is not reentrant, perheaps a problem in the code i use with thread programming) futures:8" for C12, 25" for C13,2' for C14,7' for C15... the best performance are,from far, with futures and the code provided by Zelphir. on a 6 cores processor with 16Gb of memory.note at C15 computation the memory containing minterms and logical expression not simplified is about 3 Gb: PID UTIL. PR NI VIRT RES SHR S %CPU %MEM TEMPS+ COM. 61051 mattei 20 0 *3339388* 2,7g 22368 R 463,1 *17,2 * 33:27.92 *guile* cf : https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm#Complexity what i will do is write a Python version of the computation of Cn that uses the Sympy minimal disjunctive normal form procedure of the Sympy library , first to check my scheme code result and perheaps compare the speed, i know python is slow but as it is a library (compiled? but written in python as far as i know?), well, i'm a bit nervous to compare the speed between Python and Scheme... Best regards, Damien On Tue, Oct 25, 2022 at 11:11 AM Mikael Djurfeldt wrote: > 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 > 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 wa= s >> 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 o= f >> 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 f= air >> to say that it is still intended for coarse grained parallelism. There i= s >> 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/lo= giki%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 s= o >>> i >>> >> escape with a continuation: >>> >> >>> >> minterms-set =3D >>> >> { >>> >> ((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 =3D >>> >> { >>> >> ((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 <+ (=CE=BB (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 =3D (1 1 0 1 0 1 1 0) >>> >> ;; more-lists =3D ((1 1 0 1 1 1 1 1)) >>> >> ;; lists =3D ((1 1 0 1 0 1 1 0) (1 1 0 1 1 1 1 1)) >>> >> ;; clozure =3D # >>> >> >>> >> ;; #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 =3D (1 1 0 1 0 1 1 0) >>> >> ;; more-lists =3D ((1 1 0 1 1 1 1 0)) >>> >> ;; lists =3D ((1 1 0 1 0 1 1 0) (1 1 0 1 1 1 1 0)) >>> >> ;; clozure =3D # >>> >> >>> >> ;; '(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) =3D (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 >>> >> 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 o= n. >>> >>> (E.g., maybe it grabs a mutex). >>> >>> >>> >>> Greetings, >>> >>> Maxime. >>> I don't want to scare anyone, just maybe warn about parallel map. I onc= e >>> tried >>> to use Guile's parallel map function for a decision tree implementation >>> ( >>> https://notabug.org/ZelphirKaltstahl/guile-ml/src/cf666801fea91c9fa8fa2= 90764ff6c60b7f3949d/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 mat= h >>> 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 thi= s >>> 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 >>> >>> >>> --00000000000067770105ebdc76e9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hel= lo Mikael,

=
your message c= omes very well because i decided yesterday,partly due to the discussion in = mailing list, to review all the // method used in my code and to use them t= o perform benchmark to see which one is preferable to use with the algorith= mic problem of putting a logic expression in its canonical minimal disjunct= ive or conjunctive form.

= I used 4 methods:
-sequential (map with no //)
-par-map (//)
-threads=C2=A0 (//)
-futures (//)

But, of course, the data structure is not the same now, it w= ill be lists with sequential and par-map and vectors with threads and futur= es, as i already experimented problems (blocking, crashing,false results) w= ith some (threads,futures) . Also i have solved the concurrent access probl= em to the hash table with lists or vectors depending if i use map or par-ma= p or futures and threads, but the algorithm remains the same in all case.

I computed from C1,C2,C3 .= .. to C12 (i do not write the logical expressions here, some peoples seeing= those infix mathematical expression coming in the mailing list as drones i= n the peaceful sky of the lambda calculus expressions ;-) ) but here is the= results:

<= /div>
map: 10' 17= " for C12 (5" for C10)
par-map: 1'21" for C10, more than 2h 40'= for=C2=A0 C12
threads: blocks randomly before C7 (works but is not reentrant, perhea= ps a problem in the code i use with thread programming)
futures:8" for C12, 25&qu= ot; for C13,2' for C14,7' for C15...

the best performance are,from far, with futures and= the code provided by Zelphir.

on a 6 cores processor with 16Gb of memory.note at C15 computati= on the memory containing minterms and logical expression not simplified is = about 3 Gb:
=C2= =A0 PID UTIL. =C2=A0 =C2=A0 PR =C2=A0NI =C2=A0 =C2=A0VIRT =C2=A0 =C2=A0RES = =C2=A0 =C2=A0SHR S =C2=A0%CPU =C2=A0%MEM =C2=A0 =C2=A0TEMPS+ COM. =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0
=C2=A0 61051 mattei =C2=A0 =C2=A020 =C2=A0 0 33= 39388 =C2=A0 2,7g =C2=A022368 R 463,1 =C2=A017,2 =C2=A033:27.92 = guile =C2=A0=C2=A0

cf : https://en.wikipedia.org/wiki/Quine%E2%80%93McCluske= y_algorithm#Complexity

what i will do is write a Python version of the computation of Cn that us= es the Sympy minimal disjunctive normal form procedure of the Sympy library= , first to check my scheme code result and perheaps compare the speed, i k= now python is slow but as it is a library (compiled? but written in python = as far as i know?), well, i'm a bit nervous to compare the speed betwee= n Python and Scheme...

Be= st regards,
Dam= ien

On Tue, Oct 25, 2022 at 11:11 AM Mikael Djurfeldt <mikael@djurfeldt.com> wrote:
<= /div>
Als= o, 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 du= e to the Guile basic thread support itself.

On Tue, Oct 25, 2022 at 11:0= 7 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 pie= ce of work, however there was also a thread pool such that not all of the o= verhead of launching new threads always was required.

<= div>Since then, par-map has been rewritten (by others) to be based on futur= es. (And now the thread pool is localized in the futures implementation---a= s "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 hea= vy lifting going on with mutexes and condition variables as well as shuffli= ng 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 in= teresting if the code could be improved to support fine grained parallelism= . :-)

Best regards,
Mikael

On W= ed, 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 hap= pen, 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 =3D
>> {
>> ((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 =3D
>> {
>> ((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
>>
>>=C2=A0 =C2=A0it 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 <+ (=CE=BB (L) (apply
>> function-unify-two-minterms-and-tag L))}
>>
>> (define (unify-two-minterms mt1 mt2)
>>=C2=A0 =C2=A0 (function-map-with-escaping-by-kontinuation2
>>=C2=A0 =C2=A0(macro-function-compare-2-bits-with-continuation) mt1 = mt2))
>>
>> ;; (function-map-with-escaping-by-kontinuation2
>> (macro-function-compare-2-bits-with-continuation)=C2=A0 =C2=A0'= ;(1 1 0 1 0 1 1 0) '(1
>> 1 0 1 1 1 1 1))
>>
>> ;; list1 =3D (1 1 0 1 0 1 1 0)
>> ;; more-lists =3D ((1 1 0 1 1 1 1 1))
>> ;; lists =3D ((1 1 0 1 0 1 1 0) (1 1 0 1 1 1 1 1))
>> ;; clozure =3D #<procedure:...gos-DrRacket.scm:195:11>
>>
>> ;; #f
>> ;;
>> ;;=C2=A0 (function-map-with-escaping-by-kontinuation2
>> (macro-function-compare-2-bits-with-continuation)=C2=A0 =C2=A0 = 9;(1 1 0 1 0 1 1 0) '(1
>> 1 0 1 1 1 1 0))
>>
>> ;; list1 =3D (1 1 0 1 0 1 1 0)
>> ;; more-lists =3D ((1 1 0 1 1 1 1 0))
>> ;; lists =3D ((1 1 0 1 0 1 1 0) (1 1 0 1 1 1 1 0))
>> ;; clozure =3D #<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)
>>=C2=A0 =C2=A0 (call/cc (lambda (kontinuation)
>>=C2=A0 =C2=A0 =C2=A0 (let ((lists (cons list1 more-lists))
>>=C2=A0 =C2=A0 (funct-continu ;; this function have the kontinuation= in his environment
>>=C2=A0 =C2=A0 =C2=A0(lambda (arg1 . more-args)
>>=C2=A0 =C2=A0 =C2=A0 =C2=A0(let ((args (cons arg1 more-args)))
>> (apply clozure kontinuation args))))) ;; a tester: (apply clozure = (cons
>> conti args))
>>
>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0;; (newline)
>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0;; (dv list1)
>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0;; (dv more-lists)
>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0;; (dv lists)
>>=C2=A0 =C2=A0;; (dv clozure)
>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0;; (newline)
>>
>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 (apply map funct-continu lists)))))
>>
>> (define-syntax macro-function-compare-2-bits-with-continuation ;;<= br> >> continuation version of macro-compare-2-bits
>>=C2=A0 =C2=A0 ;; i need a macro because of external function to the= clozure
>>=C2=A0 =C2=A0 (syntax-rules ()
>>=C2=A0 =C2=A0 =C2=A0 ((_) (let ((cnt 0)) ;; counter
>>=C2=A0 =C2=A0 (lambda (continuation b1 b2) (if (equal? b1 b2)
>>=C2=A0 =C2=A0b1
>>=C2=A0 =C2=A0(begin
>>=C2=A0 =C2=A0 =C2=A0(set! cnt (add1 cnt)) ;; we leave with continua= tion in case cpt > 1, we
>> can have used a flag too instead of a counter
>>=C2=A0 =C2=A0 =C2=A0(when (> cnt 1) (continuation #f)) ;; escapi= ng with the continuation
>>=C2=A0 =C2=A0 =C2=A0'x))))))) ;; return x in case of (b1,b2) = =3D (O,1) or (1,0)
>>
>> what could have caused mutex if in the latter definition above (le= t ((cnt
>> 0)) ;; counter was defined at top level and shared by all threads!= !! yes
>> there could have be some mutex=C2=A0 but this is not the case, i t= hink 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 eleme= nt list , i
>>> got
>>>> 9s with map and 3min 30s with par-map on exactly the same = piece of
>>> code!?
>>>=C2=A0 =C2=A0> [...]
>>>=C2=A0 =C2=A0>
>>>> translated from Scheme+ to Scheme:
>>>> (define unified-minterms-set-1 (map function-unify-minterm= s-list
>>>> minterms-set)) ;;(par-map function-unify-minterms-list min= terms-set))
>>> The definition of 'function-unify-minterms-list' and &= #39;minterms-set' is
>>> missing.=C2=A0 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 onc= e tried
to use Guile's parallel map function for a decision tree implementation=
(https://notabug.org/ZelphirKaltstahl/guile-ml/src/cf666801fea91c9f= a8fa290764ff6c60b7f3949d/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 neve= r
figured out, what went wrong. All I had was pure function calls and math in= side
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. Recen= tly I
made a parallelization thing for solving exercises of Project Euler using <= br> multiple cores, so that some solutions are calculated faster. Maybe this ca= n
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. Usual= ly
ranges of numbers for Project Euler things. Here is the code to split a ran= ge
into segments:

https://notabug.org/ZelphirKaltstahl/guile-proje= ct-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 gues= s one
could change the way futures are used in `run-in-parallel`, to fit any othe= r
purpose.

Best regards,
Zelphir

--
repositories: https://notabug.org/ZelphirKaltstahl


--00000000000067770105ebdc76e9--