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: Mon, 24 Oct 2022 06:39:08 +0200 Message-ID: References: <5608809c-89a2-118c-5c05-c46ac3a0e21b@posteo.de> <87860c1f-e590-8e16-e031-dedc99cd3864@posteo.de> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="2692"; 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 Mon Oct 24 07:13:38 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 1ompmM-0000XZ-A7 for guile-user@m.gmane-mx.org; Mon, 24 Oct 2022 07:13:38 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ompFF-0002Rw-T3; Mon, 24 Oct 2022 00:39:25 -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 1ompFE-0002QJ-M5 for guile-user@gnu.org; Mon, 24 Oct 2022 00:39:24 -0400 Original-Received: from mail-ed1-x52a.google.com ([2a00:1450:4864:20::52a]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ompFC-0006D7-9H for guile-user@gnu.org; Mon, 24 Oct 2022 00:39:24 -0400 Original-Received: by mail-ed1-x52a.google.com with SMTP id e18so26860702edj.3 for ; Sun, 23 Oct 2022 21:39:21 -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=2c0h5GYnhrdbYBm/evgik9ow2XXbGjVpTzoJQMy7Wh8=; b=WXebShSgtYtp95RL5AWQYR9/d3Q6AIh6UTboDlMnSFV3DlSk9c2xLU3TsAzJDtTIEu Jg5vLun/KdhsIV8W7GXaYA+YDv0s+isBhT3N6DFL112JYo7H8w8/1+oHEz0xFhdbkKFf /SW5y3kIBwGYWgDmdnsqoAVNullPykEmf2lXyLkkAdFYcmtWB9gBV8D77U5hNBnUZFvs SJNiLkuphXi8TUOtzFc7jTcLxWUkBMpSevYO90U3IS0m6tsHo1gJ3UBCwGnX68Dl2kL0 pUVzFXKCDy7PH6ex8F4Wi9Eu1pBd9gKkqccDvv4OOoPLmvV1DLgBdRpXrOZlguSsRVNT kk9w== 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=2c0h5GYnhrdbYBm/evgik9ow2XXbGjVpTzoJQMy7Wh8=; b=vj62ScvHn1H8wENrSePBB/nKAQLWd8t+cFv6PGGWel4lsCSMwohvlt12d6gWQiKKeP Ydsm8EsxuM+C/xJ6p4VhFR4rCvm2A3h4MHqWvRIw4MocnkDlPbNAoFZw8wC4DUcaHJ8o Pyy2HpnLwNzYx2oavtzUohG6TWp9qBGLfcWVO3QEo1NsqAdGWJ2hIsWFpveNAvCWUQz/ gd6dAxizT1Xxc+EwFBkpCSO4IyzMsw/7UD6SwgdKhj8VrOisLdljIYqLInzHH6humIgE nPHChPEYOSzeU7ew/N+DT9X8OLGnyvHDQrl+9Qz2Ub6uSjRAvs1OMzPO1KhAiLaQU/yu +Fdg== X-Gm-Message-State: ACrzQf0zmu+L38HzysI6atE9TCAHSRhYcnyJ0x+HuG8ztmkcIlkD46O1 TCh/7lKiBZss3ljs2H2l0c9FRrLf2PghsnRgI48= X-Google-Smtp-Source: AMsMyM55d70Xj2nUIkqHFe8rG8V6RG1a0HOILZopWgsrHNxa6LiEhPpkOK9OP2GT387zUP3oMTVmk8vu4UsnJEZq8b0= X-Received: by 2002:a17:907:2d91:b0:78d:8747:71b4 with SMTP id gt17-20020a1709072d9100b0078d874771b4mr25920792ejc.545.1666586360158; Sun, 23 Oct 2022 21:39:20 -0700 (PDT) In-Reply-To: <87860c1f-e590-8e16-e031-dedc99cd3864@posteo.de> Received-SPF: pass client-ip=2a00:1450:4864:20::52a; envelope-from=damien.mattei@gmail.com; helo=mail-ed1-x52a.google.com X-Spam_score_int: 0 X-Spam_score: -0.1 X-Spam_bar: / X-Spam_report: (-0.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, URI_DOTEDU=1.997 autolearn=no 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: , Original-Sender: "guile-user" Errors-To: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.lisp.guile.user:18675 Archived-At: Hello Zelphir, i should had written first about the mathematical problem first but i did not want to go into other than computer things. But i expose here the main idea briefly: i try to solve a mathematical conjecture ( https://en.wikipedia.org/wiki/Conjecture ) using logic expressions but not in the common sense of Boole's algebra, at some point i shift to Probability logic and i need to simplify, minimalize logic expressions in disjunctive form, this is my idea. I will give a few link for the curious and i hope to publish something in the next year. At the beginning it is a computer problem well know in logic: the minterms of the hash table i use are described here: https://en.wikipedia.org/wiki/Canonical_normal_form#Minterms and the algorithms are here: https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm https://en.wikipedia.org/wiki/Petrick%27s_method The minterms come from a set product : https://en.wikipedia.org/wiki/Cartesian_product (space complexity is polynomial) but the whole logic problem is an NP-hard problem so i do not expect it to be fast for more than 10 variables, it works well on one processor, and i'm now checking it on multiple core. I could have used Mathematica or Python sympy but i choosed many years ago to build a system in Scheme because there is no free software, Maxima does not support well logic (there was a no more supported module for Zhegalkin polynomials https://en.wikipedia.org/wiki/Zhegalkin_polynomial ) i did not want to use a commercial product such as Mathematica and i did not know Python Sympy ten years ago... but now i will use it to cross-check my Scheme results. I hope to do that this week, if it is ok i will not modify the Scheme code any more. The hash table was the more obvious structure to use due to the nature of algoritms here, i can not use arrays. I did not expected the compiler to solve the concurrent access to the hash table, i know i was going into problems, and i solve the problem with arrays in the // region and put back data after in the hash table in a non // region.It is okay now. For the one interested (i apologize because this is out of subject in the Guile mailing list) here is a few interesting links about Probability and Logic: Theodore Hailperin wrote the best articles in my opinion: https://projecteuclid.org/journals/notre-dame-journal-of-formal-logic/volume-25/issue-3/Probability-logic/10.1305/ndjfl/1093870625.full https://plato.stanford.edu/entries/logic-probability/ https://www.amazon.fr/Booles-logic-probability-contemporary-foundations/dp/0444110372 Best regards, Damien On Mon, Oct 24, 2022 at 1:18 AM Zelphir Kaltstahl < zelphirkaltstahl@posteo.de> wrote: > Hello Damien! > On 10/23/22 03:06, Damien Mattei wrote: > > after intense coding i finally got the good results, > my assumption about the global variable hash table was true ,it is > incompatible with 'future : the competition for the writing into the hash > table breaks the code. > > If i do writing in hash table out of // region all is ok: > > a simple function to extract the hash table access: > > (define (tag-minterms i umt) > (when umt > {mt1 <+ (first {minterms-vector[i]})} > {mt2 <+ (second {minterms-vector[i]})} > {minterms-ht[mt1] <- #t} > {minterms-ht[mt2] <- #t})) > [...] > > I am not sure what exactly the problem is, which you are trying to > calculate, but it looks fairly mathematical to me. Maybe you do not need to > share state globally at all? Maybe you can find a way to avoid global > shared state? I am guessing, that you want to avoid duplicated computation > of part terms? > > Of course,if you have global state and do not have a synchronization > construct (!) for accessing the hash table, I would expect things to go > wrong at some point, with non-reproducible results. I do not think that > futures are to blame here, or parallel map in that case. > > With a synchronization construct, some kind of mutex, your bottle neck > might just become that mutex. Up to you to measure that ; ) > > Would be nice, if you found a clever way to separate the problems into > disjunct parts and then solve them without global state. > > Regards, > Zelphir > > -- > repositories: https://notabug.org/ZelphirKaltstahl > >