From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.devel Subject: Re: [PATCH] add SRFI: srfi-121; generators Date: Fri, 22 Jan 2021 19:58:01 -0500 Message-ID: <87r1mcfozv.fsf@netris.org> References: Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="21237"; mail-complaints-to="usenet@ciao.gmane.io" Cc: srfi To: John Cowan , guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Sat Jan 23 01:59:44 2021 Return-path: Envelope-to: guile-devel@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 1l37HD-0005Ok-A6 for guile-devel@m.gmane-mx.org; Sat, 23 Jan 2021 01:59:43 +0100 Original-Received: from localhost ([::1]:34440 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1l37HC-0006HA-D1 for guile-devel@m.gmane-mx.org; Fri, 22 Jan 2021 19:59:42 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:43970) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1l37H2-0006Gi-Ah for guile-devel@gnu.org; Fri, 22 Jan 2021 19:59:32 -0500 Original-Received: from world.peace.net ([64.112.178.59]:51824) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1l37H0-0001ok-4v for guile-devel@gnu.org; Fri, 22 Jan 2021 19:59:32 -0500 Original-Received: from mhw by world.peace.net with esmtpsa (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1l37Gn-0001S8-G2; Fri, 22 Jan 2021 19:59:17 -0500 In-Reply-To: Received-SPF: pass client-ip=64.112.178.59; envelope-from=mhw@netris.org; helo=world.peace.net X-Spam_score_int: -18 X-Spam_score: -1.9 X-Spam_bar: - X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.io gmane.lisp.guile.devel:20646 Archived-At: Hi John, John Cowan writes: > Mark: I'm interested to know if you have a sketch of ideas for a more > efficient implementation of SRFI 121/158. You say it requires specific > knowledge of Guile internals, but are you willing to sketch how you might > do it? Thanks. Here are a few suggestions off the top of my head, looking only at the latest SRFI-121 reference implementation: * In 'gcombine', 'generator-fold', 'generator-for-each', and possibly also 'generator-unfold', it would be helpful to use 'case-lambda' to provide specialized code for cases where the 'dotted' tail in the argument list consists of 1 or 2 arguments. When a procedure with a dotted tail is called, it forces allocation of a new list, and last I checked Guile does not include optimizations to avoid that allocation where possible. Worse, the general case requires calling 'map' and allocating a new list every time a new item is requested. It's a great help to avoid these expenses in the most common cases. For example, see the definitions of 'map', 'for-each', and 'fold' in Guile: https://git.savannah.gnu.org/cgit/guile.git/tree/module/ice-9/boot-9.scm?id=75b0db1a286f936a90683973efc2315a07c03b21#n214 https://git.savannah.gnu.org/cgit/guile.git/tree/module/srfi/srfi-1.scm?id=75b0db1a286f936a90683973efc2315a07c03b21#n451 * Avoid using 'define-values' in internal lexical contexts in Guile for now. Hopefully some day Guile's implementation of 'define-values' will be more efficient, but for now it's implemented as a simple macro that expands into code that mutates variables, which prevents several other optimizations that could otherwise be done by Guile's compiler. In particular, in 'gcombine', better use 'call-with-values' or 'receive'. * Several procedures are defined in terms of more general higher-order procedures, or create intermediate lists/generators unnecessarily, for the sake of making the code simpler. In most contexts I would applaud this practice, but there will be a significant price to pay in efficiency. For example, 'generator->reverse-list' with 1 argument is implemented in terms of 'generator-fold', and with 2 arguments by creating an intermediate generator using 'gtake'. * To make matters worse: 'gtake', as well as 'make-for-each-generator' and 'make-unfold-generator', are defined in terms of coroutine generators. It's good to have coroutine generators available, but they are quite expensive, and best avoided where efficiency is desirable. * 'generator->vector' is defined using 'generator->list' and 'list->vector'. That's bad enough, but digging deeper we see that 'generator->list' is implemented by reversing the result of 'generator->reverse-list', which as I've already pointed out is defined using 'generator-fold', which currently involves calling 'map' and 'append' and allocating temporary lists for each item generated. In general, it's helpful to go through the mental exercise of tracing an evaluation of each of these procedures, and more importantly to trace calls to the produced generators, to get some idea of the expense involved. This is just a sampling of the problems I noticed from a quick skim of the code, by no means comprehensive. I acknowledge that following the suggestions above will make the code much larger, uglier, and more difficult to understand. I would not recommend such practices except in cases where efficiency is paramount. In this case, I think efficiency *is* paramount. My rationale is that, like hash tables, generators inevitably force code that uses them to be written in an imperative style, and therefore they are best avoided in my opinion, *except* in cases where efficiency is paramount. To avoid being forced to write code in an imperative style, I suggest that in most cases streams are preferable to generators. Regards, Mark