From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Olivier Dion via General Guile related discussions Newsgroups: gmane.lisp.guile.user Subject: Re: escaping from a recursive call Date: Thu, 10 Nov 2022 12:03:36 -0500 Message-ID: <87pmduoi6v.fsf@laura> References: <8735asoytw.fsf@laura> <87y1sknhb5.fsf@laura> <87v8nnoba8.fsf@laura> Reply-To: Olivier Dion Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="12957"; mail-complaints-to="usenet@ciao.gmane.io" Cc: guile-user To: Damien Mattei , Zelphir Kaltstahl Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Thu Nov 10 18:04:40 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 1otAyl-00038k-SR for guile-user@m.gmane-mx.org; Thu, 10 Nov 2022 18:04:39 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1otAy2-0002gc-Cg; Thu, 10 Nov 2022 12:03:54 -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 1otAxz-0002fo-PW for guile-user@gnu.org; Thu, 10 Nov 2022 12:03:51 -0500 Original-Received: from smtp.polymtl.ca ([132.207.4.11]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1otAxx-0001oM-Nd for guile-user@gnu.org; Thu, 10 Nov 2022 12:03:51 -0500 Original-Received: from localhost (modemcable094.169-200-24.mc.videotron.ca [24.200.169.94]) by smtp.polymtl.ca (8.14.7/8.14.7) with ESMTP id 2AAH3aIl030891; Thu, 10 Nov 2022 12:03:41 -0500 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp.polymtl.ca 2AAH3aIl030891 In-Reply-To: X-Poly-FromMTA: (modemcable094.169-200-24.mc.videotron.ca [24.200.169.94]) at Thu, 10 Nov 2022 17:03:36 +0000 Received-SPF: pass client-ip=132.207.4.11; envelope-from=olivier.dion@polymtl.ca; helo=smtp.polymtl.ca X-Spam_score_int: -41 X-Spam_score: -4.2 X-Spam_bar: ---- X-Spam_report: (-4.2 / 5.0 requ) BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action 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:18717 Archived-At: On Thu, 10 Nov 2022, Damien Mattei wrote: > will it work well in // code with future or thread ,i'm having already > problem with // code that,compute well but show no speed up, is it because > of continuation? not being compatible with //,does macro generates > functions that causes unknown problem to // code, i try to get rid of > macros and continuation in // code but i always fall back using > them... There's many problem that arise when you play with continuation in multi-threads environment. See the scheduler of my library guile-parallel for example. > but since i have problem with // speed up i try other procedure: > below you see the need of having to sort of escape ,'return from the > current level in case of end of lists,and 'return-rec from the full stack > of recursions in cas of #f result. > > (define (unify-two-minterms-rec mt1 mt2) > > {err <+ #f} > > (def (unify-two-lists-tolerant-one-mismatch mt1 mt2) > > (if {(null? mt1) and (null? mt2)} > (return '())) > > (if {{(null? mt1) and (not (null? mt2))} or {(not (null? mt1)) > and (null? mt2)}} > (return-rec #f)) > > > {fst-mt1 <+ (first mt1)} > {fst-mt2 <+ (first mt2)} > > (if (equal? fst-mt1 fst-mt2) (return (cons fst-mt1 > (unify-two-lists-tolerant-one-mismatch (rest mt1) (rest mt2))))) > (if err (return-rec #f)) > > {err <- #t} > (cons 'x > (unify-two-lists-tolerant-one-mismatch (rest mt1) (rest mt2)))) > > (unify-two-lists-tolerant-one-mismatch mt1 mt2)) If you make your algorithm tail recursive, you should be able to espace from any level of recursion without penalty. From what I've read here, your algorithm is not tail recursive and so a frame is made a each level of recursion, requiring an unwinding of it after. Keep in mind that delimited continuation are not free. It's kind of like a userspace context switching. It involves memory load/store and stack unwinding, probably also other implementation dependant details in the runtime. I would not advice to use them in critical performant scenario nor in parallelized algorithm. > i have tested but still no speed up with 'futures, i have test it with > Guile but the same problem is with Racket. Seems 'furure makes no speed up > , it is hard to share the benchmarks now that i have updated the 'def of > Scheme+ but i then i have to release a new version and update all the > github and documentation online.Soon i hope... I haven't tackle your minterm problem directly here, but from a glimpse of it, I don't see which part can be parallelize? Furthermore, you have a global state `err` that will impose penalty for sure. Maybe doing a divide and conquer approach? In that case I would highly recommend using vector instead of list, but you would still have problem with the global state that should be an atomic box. -- Olivier Dion oldiob.dev