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: Wed, 12 Oct 2022 22:27:09 +0200 Message-ID: References: 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="38105"; mail-complaints-to="usenet@ciao.gmane.io" Cc: guile-user , guile-devel To: Maxime Devos Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Wed Oct 12 22:27:44 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 1oiiKO-0009mU-JS for guile-user@m.gmane-mx.org; Wed, 12 Oct 2022 22:27:44 +0200 Original-Received: from localhost ([::1]:36716 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oiiKN-0006O8-55 for guile-user@m.gmane-mx.org; Wed, 12 Oct 2022 16:27:43 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:59500) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oiiK6-0006NZ-77; Wed, 12 Oct 2022 16:27:26 -0400 Original-Received: from mail-ed1-x52d.google.com ([2a00:1450:4864:20::52d]:42661) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oiiK3-0003Rx-NN; Wed, 12 Oct 2022 16:27:25 -0400 Original-Received: by mail-ed1-x52d.google.com with SMTP id u21so25965288edi.9; Wed, 12 Oct 2022 13:27:22 -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=+TqHxDtAC+eUyJS8skOoV6jeqUhWbs4D/7SjATMiclk=; b=aSurvlTOFPQ+uWD7fKG9fKR/U7Hra4AuEAqE9nyiEeFTxSy8OIL9LwEtQylUYhFcim K4V/DrpKbX+JdLNk8RMN5n3As3pK3YSF+X6vdSFue/ifAow4Z26TNyLs2FXvl70/yDSe gT7bSDV7kwzx9MkBwE90vn2e9YnywjxrGejTwG5kEBmXsFDFKGMMd+chnsx2Kvx9G497 S4MfGV0cl7atVN32JEE2oVBnH/SZDajpHCca5ZqDc8C+jq4uGN7MH/gM1HZf3AsA3Z3q FilVsKKt7rwww1hlv3n+TI7L6wzm5zUILatWrant9wLxf/5ISFlr478yB9tcwW1ZjYv6 GeLQ== 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=+TqHxDtAC+eUyJS8skOoV6jeqUhWbs4D/7SjATMiclk=; b=qcfzjI2FQ/MvTVm3B6jZBqmvqvVNKujtYki9oho4lpFsjbEmArhkd4oAMKVoBZyf8h GSly36OW4s9u0fvL0Ainc43AU4d0DwDmvRj0cvEmkwEgSXnE89qT9R64rVXwNNufVVtf BFdrP3oEeR3H58XENSFLRNvQtOMcskHWFTgMfDDEFOGSQh9zZX2NainZ7igKiSdbXsQF /t6+zxLG4Iv/llzGXpcF6MJxkbHwjclYHLS0bh9wYefssoM2peWurVq4SkIrFueJ76Ot 8MPQIC4GszkGRe6Zhxk4OSl3JCV/3VZd1m8APpeVVqPUdp0/CHb8rBmfIvolSSNqx3rw R0Rw== X-Gm-Message-State: ACrzQf1NPhJDdZHE9W0ecpfE6NqM2vpJ4mK+4wX9SSuIovA2jx2vOESM mMMaAwzytE/tcJY7fmYQEK7RNyWDUAOBDrAwKiI= X-Google-Smtp-Source: AMsMyM4qZ69rzljAGU9TD8VhUkeuFLUZ68hCXyXd2sbUNwXLtckRZUbuZ7gh2l4oHqct1YqtKHMacR0ANH0Oy0fhlmw= X-Received: by 2002:a05:6402:27cd:b0:45c:db6f:7e77 with SMTP id c13-20020a05640227cd00b0045cdb6f7e77mr732950ede.149.1665606441104; Wed, 12 Oct 2022 13:27:21 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2a00:1450:4864:20::52d; envelope-from=damien.mattei@gmail.com; helo=mail-ed1-x52d.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:18627 gmane.lisp.guile.devel:21406 Archived-At: 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 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 , minter= ms > 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 > > it is not easy to read even by me because i wrote the code many years ag= o > 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 environmen= t > (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, w= e > 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 al= l > 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 on. >> (E.g., maybe it grabs a mutex). >> >> Greetings, >> Maxime. >> >