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,gmane.lisp.guile.devel Subject: Re: map-par slower than map Date: Sat, 22 Oct 2022 18:01:22 +0200 Message-ID: References: <5608809c-89a2-118c-5c05-c46ac3a0e21b@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="28278"; mail-complaints-to="usenet@ciao.gmane.io" Cc: guile-user , guile-devel To: Zelphir Kaltstahl Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Mon Oct 24 01:04:29 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 1omk16-00078T-Ur for guile-user@m.gmane-mx.org; Mon, 24 Oct 2022 01:04:29 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1omiNQ-0000st-S8 for guile-user@m.gmane-mx.org; Sun, 23 Oct 2022 17:19:24 -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 1omGwS-0003X5-32; Sat, 22 Oct 2022 12:01:44 -0400 Original-Received: from mail-ed1-x52f.google.com ([2a00:1450:4864:20::52f]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1omGwM-0006Mw-DP; Sat, 22 Oct 2022 12:01:42 -0400 Original-Received: by mail-ed1-x52f.google.com with SMTP id a67so16382339edf.12; Sat, 22 Oct 2022 09:01:36 -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=EpOnRRfnDJKDT5E16TMBfBPsLjgCBvfAuwjoERGd4Pw=; b=Wi4xbsfoKZvcq/dhlp6qcKYr6qvXbHCWwHBs7QOkFxzCgWamacUvgVYnYlsvDCKKZ7 cInncCG32TYedIvAlsyEheUYwymTUtARLmWHIyGc6QRXVp3KaUhfJgJ/N2Fj0z8ODysK c6QGDBPztIpqOrclQm8WpomlhdpgMwmhG4Mc/UfEpZWLhPiB7ifz6kCdHDd4beB5gJTN 6Bfybn28uFk5DWGx0y+M1sKL4C9bsUBzuPBbJxEk4oTrCU1Ir5cXBrHj/SglJMO/Xbwt HOKiZs4XBZ76LjsUwYr4WonXnacw4TpMy1R9qYWvmrsYj/lZglpCRE3b9aENAcrQw/EB gbNA== 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=EpOnRRfnDJKDT5E16TMBfBPsLjgCBvfAuwjoERGd4Pw=; b=rIm4eJVF8vcXtiqbyIV0fknjnHhl5fKLoWNFKKR5jbeLZAeuLEa+3DJgqpq629wZ54 +tV9DfWEkIgv6YnCXopkFQg9bgnPcVDPer2oXYLh+Gee6UqUwH9tMbWlaz5Fkd4oaHm9 lsYTaLVTfP9aQcmwPZWH79XiLpWFz2ZrCGu5holmBt9SIFu6CgTcSj8jMULEOQorBe1J hC2NX/e+NV8RMtFbuTOLaOUuqNEfqFWOGqIepMneyAAfIRfXGgftfU+KGA5zusEmmJ5Z truf31hBTkMOaomWz7BUwwQvrDd7KSLAJv1a6+pzW3v8yjf8TLJx+xQ/cbx2MCk4UDhx EA0w== X-Gm-Message-State: ACrzQf1Wr3/LNI7+iUxBZsbNn3315aYlgDGaaTOES3sTSxwU2ooX1cob 3U1RrKKg8HDn8RwOX6c/Vhq+i7cHiI29v8UdhEQ= X-Google-Smtp-Source: AMsMyM5W7JNOizrSgyVyaLFqSfwdwGpAHT1pWqNtFeGliy6iL1tnahINgjFPgWFNKcPAGUDs6/oclp3XQPwe5Q7H3pQ= X-Received: by 2002:a17:906:ef8c:b0:78d:96b9:a0ad with SMTP id ze12-20020a170906ef8c00b0078d96b9a0admr20695075ejb.529.1666454494557; Sat, 22 Oct 2022 09:01:34 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2a00:1450:4864:20::52f; envelope-from=damien.mattei@gmail.com; helo=mail-ed1-x52f.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-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" Xref: news.gmane.io gmane.lisp.guile.user:18669 gmane.lisp.guile.devel:21450 Archived-At: just for the fun things, i just find that the parallelized results are false :-) even for low indices: the non // result: C5 =3D ((B1 =E2=88=A7 B3) =E2=88=A8 (B2 =E2=88=A7 B3) = =E2=88=A8 (B2 =E2=88=A7 B4)) is different than the parallelized result below: C5 =3D ((B1 =E2=88=A7 B3) =E2=88=A8 (B2 =E2=88=A7 B3) =E2=88=A8 (B2 =E2=88= =A7 B4) =E2=88=A8 (B3 =E2=88=A7 B4)) i have to check things again ,i think futures are easy to use but limited in solving acute // problems, such as using a global variable like an hash table... Damien On Mon, Oct 17, 2022 at 3:17 PM Damien Mattei wrote: > Hello, > > sorry for my late answer ( i wrote the code friday but i could only debug > today, being busy and on travel last week-end) > > i modified my code to works with 'futures' , the speed is now incredible > !!! (and it computes exact) > the speed seems multiplied by even more than the number of CPUs (6): > cat /proc/cpuinfo | grep processor > processor : 0 > processor : 1 > processor : 2 > processor : 3 > processor : 4 > processor : 5 > > > https://github.com/damien-mattei/library-FunctProg/blob/master/guile/logi= ki%2B.scm#L1900 > > (declare minterms-vector unified-minterms-vector-1) > > (define (funct-unify-minterms-set-1-unit-future set1 set2) > > {function-unify-minterms-list <+ (=CE=BB (L) (apply > function-unify-two-minterms-and-tag L))} > > ;; note : sorting is useless > > {minterms-set <+ (product-set-with-set-imperative-sorted set1 set2)} > ;;(product-set-with-set-imperative set1 set2)} ;;(product-set-with-set se= t1 > set2)} ;;(associate-set-with-set set1 set2)} ;; set multiplication : crea= te > list of pair of minterms > > {minterms-vector <- (list->vector minterms-set)} > > {minterms-vector-length <+ (vector-length minterms-vector)} > > {nb-procs <+ (current-processor-count)} > > {segmts <+ (segment 0 {minterms-vector-length - 1} nb-procs)} ;; comput= e > the segments > > {unified-minterms-vector-1 <- (make-vector minterms-vector-length #f)} > > (run-in-parallel segmts proc-unify-minterms-seg) ;; run the parallel co= de > > {unified-minterms-set-1 <+ (vector->list unified-minterms-vector-1)} > > {unified-minterms-set-2 <+ (filter (=CE=BB (x) x) unified-minterms-set-= 1)} ;; > remove #f results > > {unified-minterms-set <+ (remove-duplicates-sorted > unified-minterms-set-2)} ;; uniq > > unified-minterms-set) > > i keeped your 'segment' definitions to index an array of data after > convert it from list to vector (list->vector) which probably consume > additional time on big data list ( i had more than 1000000 element list > lengths at some point) > > i used a simplified version of run-in parallel (that do not do 'reduce > after processing data): > > > https://github.com/damien-mattei/library-FunctProg/blob/master/guile/logi= ki%2B.scm#L1794 > > the computation on a segment is done by those functions: > > > https://github.com/damien-mattei/library-FunctProg/blob/master/guile/logi= ki%2B.scm#L1842 > > {function-unify-minterms-list <+ (=CE=BB (L) (apply > function-unify-two-minterms-and-tag L))} > > ;; proc to be called with futures > (define (proc-unify-minterms-seg seg) > {start <+ (segment-start seg)} > {end <+ (segment-end seg)} > (for ({i <+ start} {i <=3D end} {i <- {i + 1}}) > {mtL <+ {minterms-vector[i]}} > {unified-minterms-vector-1[i] <- (function-unify-minterms-list > mtL)})) > > > i use those code in another program symbolically to compute a value named > Cn: > > C0 =3D T > C1 =3D T > C2 =3D T > C3 =3D (B1 =E2=88=A8 B2) > C4 =3D (B2 =E2=88=A8 (B1 =E2=88=A7 B3)) > C5 =3D ((B1 =E2=88=A7 B3) =E2=88=A8 (B2 =E2=88=A7 B3) =E2=88=A8 (B2 =E2= =88=A7 B4) =E2=88=A8 (B3 =E2=88=A7 B4)) > C6 =3D ((B1 =E2=88=A7 B3 =E2=88=A7 B5) =E2=88=A8 (B2 =E2=88=A7 B3 =E2=88= =A7 B5) =E2=88=A8 (B2 =E2=88=A7 B4) =E2=88=A8 (B3 =E2=88=A7 B4) =E2=88=A8 (= B4 =E2=88=A7 B5)) > C7 =3D ((B1 =E2=88=A7 B3 =E2=88=A7 B5) =E2=88=A8 (B2 =E2=88=A7 B3 =E2=88= =A7 B5) =E2=88=A8 (B2 =E2=88=A7 B4 =E2=88=A7 B6) =E2=88=A8 (B3 =E2=88=A7 B4= =E2=88=A7 B6) =E2=88=A8 > (B4 =E2=88=A7 B5) =E2=88=A8 (B5 =E2=88=A7 B6)) > C8 =3D ((B1 =E2=88=A7 B3 =E2=88=A7 B5 =E2=88=A7 B7) =E2=88=A8 (B2 =E2=88= =A7 B3 =E2=88=A7 B5 =E2=88=A7 B7) =E2=88=A8 (B2 =E2=88=A7 B4 =E2=88=A7 B6) = =E2=88=A8 (B3 =E2=88=A7 > B4 =E2=88=A7 B6) =E2=88=A8 (B4 =E2=88=A7 B5 =E2=88=A7 B7) =E2=88=A8 (B5 = =E2=88=A7 B6) =E2=88=A8 (B6 =E2=88=A7 B7)) > C9 =3D ((B1 =E2=88=A7 B3 =E2=88=A7 B5 =E2=88=A7 B7) =E2=88=A8 (B2 =E2=88= =A7 B3 =E2=88=A7 B5 =E2=88=A7 B7) =E2=88=A8 (B2 =E2=88=A7 B4 =E2=88=A7 B6 = =E2=88=A7 B8) =E2=88=A8 > (B3 =E2=88=A7 B4 =E2=88=A7 B6 =E2=88=A7 B8) =E2=88=A8 (B4 =E2=88=A7 B5 = =E2=88=A7 B7) =E2=88=A8 (B5 =E2=88=A7 B6 =E2=88=A7 B8) =E2=88=A8 (B6 =E2=88= =A7 B7) =E2=88=A8 (B7 =E2=88=A7 > B8)) > > from C1 to C9 used to be fast,less than a minute for the whole with or > without // > > C10 =3D ((B1 =E2=88=A7 B3 =E2=88=A7 B5 =E2=88=A7 B7 =E2=88=A7 B9) =E2=88= =A8 (B2 =E2=88=A7 B3 =E2=88=A7 B5 =E2=88=A7 B7 =E2=88=A7 B9) =E2=88=A8 (B2 = =E2=88=A7 B4 =E2=88=A7 B6 > =E2=88=A7 B8) =E2=88=A8 (B3 =E2=88=A7 B4 =E2=88=A7 B6 =E2=88=A7 B8) =E2= =88=A8 (B4 =E2=88=A7 B5 =E2=88=A7 B7 =E2=88=A7 B9) =E2=88=A8 (B5 =E2=88=A7 = B6 =E2=88=A7 B8) =E2=88=A8 (B6 =E2=88=A7 > B7 =E2=88=A7 B9) =E2=88=A8 (B7 =E2=88=A7 B8) =E2=88=A8 (B8 =E2=88=A7 B9)) > > C10 takes a few minutes > > but C11 used to take one day before // with 'future' and i got now the > result during less than one hour!!! > > C11 =3D ((B1 =E2=88=A7 B3 =E2=88=A7 B5 =E2=88=A7 B7 =E2=88=A7 B9) =E2=88= =A8 (B10 =E2=88=A7 B2 =E2=88=A7 B4 =E2=88=A7 B6 =E2=88=A7 B8) =E2=88=A8 (B1= 0 =E2=88=A7 B3 =E2=88=A7 > B4 =E2=88=A7 B6 =E2=88=A7 B8) =E2=88=A8 (B10 =E2=88=A7 B5 =E2=88=A7 B6 = =E2=88=A7 B8) =E2=88=A8 (B10 =E2=88=A7 B7 =E2=88=A7 B8) =E2=88=A8 (B10 =E2= =88=A7 B9) =E2=88=A8 (B2 =E2=88=A7 > B3 =E2=88=A7 B5 =E2=88=A7 B7 =E2=88=A7 B9) =E2=88=A8 (B4 =E2=88=A7 B5 =E2= =88=A7 B7 =E2=88=A7 B9) =E2=88=A8 (B6 =E2=88=A7 B7 =E2=88=A7 B9) =E2=88=A8 = (B8 =E2=88=A7 B9)) > > i never got C12 in the past ,even with 7 days of computation! and i got i= t > today during the lunchbreak !!! > > C12 =3D ((B1 =E2=88=A7 B11 =E2=88=A7 B3 =E2=88=A7 B5 =E2=88=A7 B7 =E2=88= =A7 B9) =E2=88=A8 (B10 =E2=88=A7 B11) =E2=88=A8 (B10 =E2=88=A7 B2 =E2=88=A7= B4 =E2=88=A7 B6 > =E2=88=A7 B8) =E2=88=A8 (B10 =E2=88=A7 B3 =E2=88=A7 B4 =E2=88=A7 B6 =E2= =88=A7 B8) =E2=88=A8 (B10 =E2=88=A7 B5 =E2=88=A7 B6 =E2=88=A7 B8) =E2=88=A8= (B10 =E2=88=A7 B7 =E2=88=A7 B8) > =E2=88=A8 (B10 =E2=88=A7 B9) =E2=88=A8 (B11 =E2=88=A7 B2 =E2=88=A7 B3 =E2= =88=A7 B5 =E2=88=A7 B7 =E2=88=A7 B9) =E2=88=A8 (B11 =E2=88=A7 B4 =E2=88=A7 = B5 =E2=88=A7 B7 =E2=88=A7 B9) =E2=88=A8 > (B11 =E2=88=A7 B6 =E2=88=A7 B7 =E2=88=A7 B9) =E2=88=A8 (B11 =E2=88=A7 B8 = =E2=88=A7 B9)) > > (note that a wise people can find a general formula for Cn based on Cn-1 > but that is another (mathematical) story....) > > i'm computing C13 but i see that it consumes 12gb out of 16gb of my syste= m > ! and stopped on the linux box : > GC Warning: Repeated allocation of very large block (appr. size 510935040= ): > May lead to memory leak and poor performance > Processus arr=C3=AAt=C3=A9 > but still running on the Mac laptop...ok will see that but i think that > the data set is now huge and there is noting that can be done with that..= . > > note that there is still an hash table used in > function-unify-two-minterms-and-tag and i will use another data structure > and algo to avoid that, i feared that the concurrent access to hash table > can cause the guile 'future' to crash or fails or to slow down the proces= s > but not! result is incredibly fast.Also i use continuation and i read it > can cause problem with 'future' i will improve that too... > > I will see where i can improve the algo and data structure to optimize > again but this is already really good. > > Thanks > > Damien > > > On Fri, Oct 14, 2022 at 10:39 AM Zelphir Kaltstahl < > zelphirkaltstahl@posteo.de> wrote: > >> Hello Damien, >> On 10/14/22 10:21, Damien Mattei wrote: >> >> yes Zelphir i think there is a problem in the threading part of guile, >> whatever the code is ,it run well the first time, and after is unstable. >> Long ago at the very begin of Java language on my master project at >> university i experienced same problem with Java "green" threads, under >> windows and/or linux ,i can't remember. >> >> I'm trying your code and future, which have perheaps also the portabilit= y >> with other schemes, future can provide "light" // , with carefull code i= t >> could be ok. >> >> in your segment.scm code ,is segment-count possibly replaced by the >> number of available CPUs or nodes, if i understand well? >> >> Regards, >> Damien >> >> Correct. For each segment one future is used. >> >> However, there are scenarios, where one would rather want to interleave >> the numbers of the whole range, to have a "fairer" workload per future, = for >> example: >> >> (1 2 3 4 5 6 7 8 9) >> >> -> (1 4 7), (2 5 8), (3 6 9) >> >> instead of >> >> -> (1 2 3) (4 5 6) (7 8 9) >> >> (I seem to remember this to be the case for Mandelbrot set calculations, >> but might be wrong.) >> >> But that is all a matter of forming some segments and what a segment is, >> not really part of the logic of creating futures. So one could create th= en >> in any way that fits ones use-case. I have not generalized that segment >> logic that far, but it is doable. >> >> Anyway, if anyone more knowledgeable could chime in on what the >> performance differences between futures and parallel map are, that would= be >> great! Or pointing out some flaws that this kind of future usage might >> have. Or when the point is reached to switch to guile-fibers library. >> >> Regards, >> Zelphir >> >> -- >> repositories: https://notabug.org/ZelphirKaltstahl >> >>