From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: =?UTF-8?Q?Linus_Bj=C3=B6rnstam?= Newsgroups: gmane.lisp.guile.devel Subject: Re: [PATCH] Make vector-map and vector-for-each in (rnrs base) fast Date: Fri, 19 Feb 2021 10:08:43 +0100 Message-ID: <66c58621-c3d7-4ba9-af3c-ccf5e04ae8f6@www.fastmail.com> 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="26933"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Cyrus-JMAP/3.5.0-alpha0-141-gf094924a34-fm-20210210.001-gf094924a To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Fri Feb 19 10:09:29 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 1lD1mu-0006m0-3t for guile-devel@m.gmane-mx.org; Fri, 19 Feb 2021 10:09:24 +0100 Original-Received: from localhost ([::1]:59142 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lD1ms-0004hh-Nc for guile-devel@m.gmane-mx.org; Fri, 19 Feb 2021 04:09:22 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:36084) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lD1mh-0004hW-OK for guile-devel@gnu.org; Fri, 19 Feb 2021 04:09:11 -0500 Original-Received: from wout5-smtp.messagingengine.com ([64.147.123.21]:56281) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lD1mf-0008S7-T7 for guile-devel@gnu.org; Fri, 19 Feb 2021 04:09:11 -0500 Original-Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.west.internal (Postfix) with ESMTP id C0CA4C8B for ; Fri, 19 Feb 2021 04:09:06 -0500 (EST) Original-Received: from imap1 ([10.202.2.51]) by compute4.internal (MEProxy); Fri, 19 Feb 2021 04:09:06 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=veryfast.biz; h= mime-version:message-id:in-reply-to:references:date:from:to :subject:content-type:content-transfer-encoding; s=fm1; bh=RF+zQ W+YCzUg4XdEUqFLwj3TnulxYP3tvwUaEbPR8xc=; b=bS/y4Sxv0VEtqytHC3M/M 439jOYQ7aQqxKowAUAEjveCsJ2QHf6Xyg44ZCRn5QJ5Gr5zLl1RQ7ArpFNtKLu6k EnltsL1arkdHsp5jqmdAzsX1Iv60PEqNqm9QDeGMvKPpyOTfCHgmVYt3Zo2RFle3 NAGsFaRygliTNMusPsL/aoaU3ZuPpkYGm1P51J/6jROziAhhCQZA3GgIPpFrFYSJ T1FJ2bmCmQ0pgEIO/ZH+45zw6iS0E6PkZQh8EQnne7uzjhJdbYUimaSq6gvg9lds VAFhW2wbH7gEt8E410FEcdp78TVN73dTcuyv3hzoMTb1i8MHnXP8c3YLhOmzNsE/ w== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm2; bh=RF+zQW+YCzUg4XdEUqFLwj3TnulxYP3tvwUaEbPR8 xc=; b=lYsYz8KJ3I4wNbA2h7+SrmPTdyZ46wO+a37AVTf31tkE9NOcL72OV4Qn8 lh7JSh0C1F4YTq8LZTkPezMKMtIXfJNq/ymQGtdDfmLriZBrEJWFgxVt2g+be3x3 Lxam+2RByr9Lm4Ydnm2fE8n45NuIi3cJemWquyUd/l/BbuPg5kUMd/uptzaLXut6 DcsY66h34UwzLQTRzsRUVOUmfjDHw1O4Gwmq/RRp25xZ5J9dZY1dJN+Un4CBc7xe FWQQdnTchss6c37B1yL9JwJIb6K7upRKGm3XFpwe3Gnl9PDlS5HlhpSlzIbeRvUG VEibqgl3B/4e13vMuwg45mksBdWFg== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduledrjeeiucetufdoteggodetrfdotffvucfrrh hofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgenuceurghi lhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesthhqredtre erjeenucfhrhhomhepnfhinhhushgpuehjnphrnhhsthgrmhcuoehlihhnuhhsrdgsjhho rhhnshhtrghmsehvvghrhihfrghsthdrsghiiieqnecuggftrfgrthhtvghrnheptedvue etheeukeethfduvdejleetffeuvddvueduieeuvdettdeuheehvdejieffnecuvehluhhs thgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomheplhhinhhushdrsghjoh hrnhhsthgrmhesvhgvrhihfhgrshhtrdgsihii X-ME-Proxy: Original-Received: by mailuser.nyi.internal (Postfix, from userid 501) id 3B45713004A9; Fri, 19 Feb 2021 04:09:06 -0500 (EST) X-Mailer: MessagingEngine.com Webmail Interface In-Reply-To: Received-SPF: pass client-ip=64.147.123.21; envelope-from=linus.bjornstam@veryfast.biz; helo=wout5-smtp.messagingengine.com X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 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, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_PASS=-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:20669 Archived-At: As suspected: the eq? optimization does nothing. I will write some tests for (r6rs base) to test the multi-vector behavio= ur of this. Currently only (vector-map proc vec1) is tested in there. Th= at comes whenever I get my next computer time. It might be weeks, though= . Also regarding (r6rs base): the two maps in guile seem compatible: (ice-= 9 boot-9) and (rnrs base) map both seem to have the same limitations (on= ly proper lists of the same length), but the boot-9 one seems faster wit= h worse error messages - probably due to some offloading to C.=20 Wouldn't one definition be a better choice, and if so: which one?=20 --=20 Linus Bj=C3=B6rnstam On Thu, 18 Feb 2021, at 08:34, Linus Bj=C3=B6rnstam wrote: > Hi there! >=20 > I was spelunking through the guile source tree and found (rnrs base).=20= > The vector-map and vector-for-each in there are horribly inefficient.=20= > They are doing (list->vector (apply map PROC (map vector->list=20 > vectors))), which means it spends quite some time checking for circula= r=20 > references. >=20 > This fixes that. The speedup is surprisingly small, considering we pas= s=20 > through the elements 2 fewer times and don't chase pointers through=20= > memory trying to find cycles. Anywhere from 30 to 300% depending on ho= w=20 > the stars are aligned on things like (vector-map + vec vec) >=20 > One potential speedup we could do is using eq? to compare numbers, but= =20 > I don't know how well fixnums in guile overlap size_t, regardless of=20= > how realistic such a limitation would be. If I change the behaviour of= =20 > vector-map to go back-to-front (order is unspecified in r6rs) we can=20= > easily do (eq? -1 index) as a stop condition to avoid any eventual=20 > overhead of type checking with =3D. (If those are not elided, which I=20= > suspect might be the case. ). I did not look at that, since I have too= =20 > little computer time these days. >=20 > As an added bonus, this speeds up quicksort.scm in ecraven's benchmark= s=20 > by a little. > --=20 > Linus Bj=C3=B6rnstam > Attachments: > * 0001-Write-a-proper-vector-map-and-vector-for-each-for-rn.patch