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.user Subject: Re: map-par slower than map Date: Thu, 10 Nov 2022 14:36:40 +0100 Message-ID: References: <5608809c-89a2-118c-5c05-c46ac3a0e21b@posteo.de> <8a9b470f-44a4-ac85-c0d1-955724390235@posteo.de> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="5635"; mail-complaints-to="usenet@ciao.gmane.io" Cc: guile-user To: Zelphir Kaltstahl Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Thu Nov 10 14:38:14 2022 Return-path: Envelope-to: guile-user@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 1ot7l0-0001HY-CM for guile-user@m.gmane-mx.org; Thu, 10 Nov 2022 14:38:14 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ot7jv-0005BO-Th; Thu, 10 Nov 2022 08:37:07 -0500 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 1ot7jt-0005Ay-W2 for guile-user@gnu.org; Thu, 10 Nov 2022 08:37:06 -0500 Original-Received: from mail-ed1-x534.google.com ([2a00:1450:4864:20::534]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ot7jk-0006Uj-4f for guile-user@gnu.org; Thu, 10 Nov 2022 08:37:04 -0500 Original-Received: by mail-ed1-x534.google.com with SMTP id x2so3126573edd.2 for ; Thu, 10 Nov 2022 05:36:55 -0800 (PST) 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=xCwI9Bdai1ijPSSkRXhC1j8NtCIWx+RLlKvwXu09M+o=; b=EZpSOmHx/rvB7hYJf0I6/TQD+If/rJdfR8EBFpqyzhbfyghe0LoMLRwVqQY9MgFzEm OS88jo1fPzYE7pyR8y7lvP2fotvF+LTe+6SMhsruIQZz3zXJOUGfJcMd4l4eWxZigybT gYdQMreySSC2XJZ9LRzJggovXV6gTGe7LSimFiK4sI7hRZbGGm5HpvmgaI9rlu+GFANu IyxOQUlhYmi0TCsWF+vC5MakaP1a71MIlPe2aD9CCSlfJKGLeEgsCDdNJGzlKxiqs1b/ Wn5QYJUc6nGbhTKGqkq2/nvdzSVy6Iw3p/5FyyCXs3Hp5436VVC2cDEswikySm2Q9Udx VC0w== 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=xCwI9Bdai1ijPSSkRXhC1j8NtCIWx+RLlKvwXu09M+o=; b=jr3Dvnmha38/7PMohkbWdvInR1/hasW6Sk4ddBnwsTokV3XIMEAmBUJ3+GuaFW3nt5 G0TW2yYUrLoB8uW+oZLtLzTaX/lfN7q251fzPgHB6Q0NXCHbhjOh1v1Mk1SI4POEgibO UjShE+LiCx0Eo5aFtBBUe1O3+jTy6fOeNQxsVdzdWdRuL4cnzgxYcEVzfjUx9sI4Pe6Y V7RAocbjV5Domz3pZ+aOPgRNt7KFbA4Pd5w1T1TD+xyuyMdizMX2s//ad7KIymBpn8xA wTCLz7wFmFkQeytyIyf+l+hvQEgBgmrz8Foq0tlseDVs14pSznw9KNuC/Ev7xLiH7zKN 7cKg== X-Gm-Message-State: ACrzQf2bi6DBa9UAe9XAeS27tqss8ily27V2JxEC/N/K9N0YTtxG/fTh Mx4+PepwZ/OfgrrRXK+ukC4C0vPdpVghKbp66UQnU/TMGxI= X-Google-Smtp-Source: AMsMyM7Eh12WHkaK+wM/my98Tfg6k7TELB0WfpKaEDwcjivz1bgQGY3nVk1j39iR+mzdlpZd42nZJo+Vm7HfIU8uSZU= X-Received: by 2002:a05:6402:b6c:b0:461:c563:defa with SMTP id cb12-20020a0564020b6c00b00461c563defamr2281392edb.72.1668087411549; Thu, 10 Nov 2022 05:36:51 -0800 (PST) In-Reply-To: <8a9b470f-44a4-ac85-c0d1-955724390235@posteo.de> Received-SPF: pass client-ip=2a00:1450:4864:20::534; envelope-from=damien.mattei@gmail.com; helo=mail-ed1-x534.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, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Content-Filtered-By: Mailman/MimeDel 2.1.29 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Original-Sender: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.lisp.guile.user:18715 Archived-At: as it worked with your code it is incompatibility between my procedures and 'future. I read 'future require pure function,ok my function are not pure but the side effect they did are on partitioned sets of data, so there is no reason for concurrence accessing data between each threads. I will try to modify the code with a personal schema of // with thread or other. For now it fails with par-map,threads and future. The problem can not be recreate on a simple case becaus emy code needs: -the minimalizing procedures of logic (logiki+.scm and co) -Scheme+ (now with a modified version of 'def macro not online) -and the code used for benchmark,which is about unpublished science and experimental. Damien On Thu, Nov 10, 2022 at 11:53 AM Zelphir Kaltstahl < zelphirkaltstahl@posteo.de> wrote: > Hi Damien! > > I think Racket futures and Guile futures are a bit different. According t= o > the Racket documentation "The level of parallelism available from those > constructs, however, is limited by several factors, and the current > implementation is best suited to numerical tasks." ( > https://docs.racket-lang.org/guide/parallelism.html#%28part._effective-fu= tures%29). > So I am not sure, if they will work well for your use-case. I think I > remember there having been a discussion on the Guile mailing list, where = I > asked, whether the Guile futures suffer from the same limitations, but I = am > not sure, that this question was sufficiently answered. I personally > haven't noticed any blocking in my pure mathematical project Euler code. > > That said. If you can send me some example code, which does not require m= e > to set up the whole thing of Scheme+, then I can take a look and check on > my end, how what when blocks. Or at least send me some snippet, which I c= an > run without setting up lots of things, maybe with 1 simple command, where > the entry point to `run-in-parallel` is obvious. > > Regards, > Zelphir > On 11/10/22 11:41, Damien Mattei wrote: > > 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 > 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 2= 7 >> here: >> >> >> https://notabug.org/ZelphirKaltstahl/guile-project-euler-solutions/src/e= bb19b11b465903105924adb6252f1e2ecf63859/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 fi= rst >> 'touch >> >> unct-unify-minterms-set-1-unit-future : begin >> set1-length =3D 930 >> set2-length =3D 1270 >> before Cartesian product set >> after Cartesian product set >> minterms-set-length =3D 1181100 >> minterms-set-first =3D ((1 1 1 x x 0 0 0 0 1) (1 1 1 1 x x 0 0 0 1)) >> segmts =3D ((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 =3D 1181100 >> >> funct-unify-minterms-set-1-unit-future : end >> funct-unify-minterms-set-1-unit-future : begin >> set1-length =3D 1270 >> set2-length =3D 888 >> before Cartesian product set >> after Cartesian product set >> minterms-set-length =3D 1127760 >> minterms-set-first =3D ((1 1 1 1 x x 0 0 0 1) (1 1 1 1 1 x x 0 0 1)) >> segmts =3D ((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 >> (=CE=BB (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 (=CE=BB (seg) >> (display-nl "run-in-parallel : making future") >> (make-future >> ;; Need to wrap in a thunk, to not >> ;; immediately start evaluating. >> (=CE=BB () (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/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 >>> >>> -- > repositories: https://notabug.org/ZelphirKaltstahl > >