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: [PATCH] Make vector-map and vector-for-each in (rnrs base) fast Date: Thu, 18 Feb 2021 08:34:23 +0100 Message-ID: Mime-Version: 1.0 Content-Type: multipart/mixed; boundary=234f3b0943a14e9abb9df6b76b2047c8 Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="24804"; 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 Thu Feb 18 08:35:04 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 1lCdq3-0006Jy-HB for guile-devel@m.gmane-mx.org; Thu, 18 Feb 2021 08:35:04 +0100 Original-Received: from localhost ([::1]:60752 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lCdq1-000067-VI for guile-devel@m.gmane-mx.org; Thu, 18 Feb 2021 02:35:02 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:46652) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lCdpq-00005w-EB for guile-devel@gnu.org; Thu, 18 Feb 2021 02:34:50 -0500 Original-Received: from out4-smtp.messagingengine.com ([66.111.4.28]:54981) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lCdpo-0006lX-Aj for guile-devel@gnu.org; Thu, 18 Feb 2021 02:34:50 -0500 Original-Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 803145C0164 for ; Thu, 18 Feb 2021 02:34:46 -0500 (EST) Original-Received: from imap1 ([10.202.2.51]) by compute4.internal (MEProxy); Thu, 18 Feb 2021 02:34:46 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=veryfast.biz; h= mime-version:message-id:date:from:to:subject:content-type; s= fm1; bh=0RjVQubUrkn4bNEQPh5uutd6lQ4eDCyUuWkeDTzC9wU=; b=nwo0pdTF oUiqGrLYnCn1b9jITZp4Eb5Re7QgHG5ME/+DLTt7Rx4AgDhDWEdlEgcfm2KXeSSV qCMVL4Zp9R91q+8iLn0ecmDctRFaUbbnsx/b29Q6HJl3Bc6g0nqwnh61ycfAioZP AnHJbTkVc0QR/80hWGsNlV5SQF+ngQHeEkE+aGHzDtEy14sGs6kBIqlIG6ziwf4E 5Uo+3PjpKo6CccAtsG3GAvtXBd1FwqZCtDGMK4ZZa/9ZggLJTpwN+cRs3aT+T32v P8vJZXISgGXToZtbz9//eE4rPkmhtOy7PPf6dD+sxihuVzeH+H+N6AOkb/uogjc9 An1LPRf4UL3leg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-type:date:from:message-id :mime-version:subject:to:x-me-proxy:x-me-proxy:x-me-sender :x-me-sender:x-sasl-enc; s=fm2; bh=0RjVQubUrkn4bNEQPh5uutd6lQ4eD CyUuWkeDTzC9wU=; b=ne9ZDfLNVkM0TY3ZN5uAxo1+H/hT+O06UK7Rbn+1C2Z2u pyb/2145KAM+P9PB6GVKdaFPw/AkkYimsXB/fBCMTUUuY5zQitjPIbew5LypXIyl KCy7KyWzJlW9QWdcUT9fgSYNOLI6oG16EveV7/7jxateZ85tkIe3eD1FHROHXpG3 2E7nDuu9NyuywuGApMZCdxFY1C5MxdNU/p52/8Xti+WpU/J8OBo2nvtGgZBIK3rJ PC0JjPdGWWowzLTRRC6tcUuyantrhG3Cf4sGC75sXtwGsQc2j13xwVpHA4mRQQNH okcCjhRA4973NKywTyHMBgwjY5IFF9++UquzLRT6w== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduledrjeefgddutdekucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfffhffvufgtsehmtderre erreejnecuhfhrohhmpefnihhnuhhspgeujhpnrhhnshhtrghmuceolhhinhhushdrsghj ohhrnhhsthgrmhesvhgvrhihfhgrshhtrdgsihiiqeenucggtffrrghtthgvrhhnpeeihf etgefgveefgfeggeeiffeuleeiieehueehleffieekfefgfeevjeffffdtudenucevlhhu shhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehlihhnuhhsrdgsjh horhhnshhtrghmsehvvghrhihfrghsthdrsghiii X-ME-Proxy: Original-Received: by mailuser.nyi.internal (Postfix, from userid 501) id 3C6ED13004A7; Thu, 18 Feb 2021 02:34:46 -0500 (EST) X-Mailer: MessagingEngine.com Webmail Interface Received-SPF: pass client-ip=66.111.4.28; envelope-from=linus.bjornstam@veryfast.biz; helo=out4-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_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-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:20667 Archived-At: --234f3b0943a14e9abb9df6b76b2047c8 Content-Type: text/plain;charset=utf-8 Content-Transfer-Encoding: quoted-printable Hi there! I was spelunking through the guile source tree and found (rnrs base). Th= e vector-map and vector-for-each in there are horribly inefficient. They= are doing (list->vector (apply map PROC (map vector->list vectors))), w= hich means it spends quite some time checking for circular references. This fixes that. The speedup is surprisingly small, considering we pass = through the elements 2 fewer times and don't chase pointers through memo= ry trying to find cycles. Anywhere from 30 to 300% depending on how the = stars are aligned on things like (vector-map + vec vec) One potential speedup we could do is using eq? to compare numbers, but I= don't know how well fixnums in guile overlap size_t, regardless of how = realistic such a limitation would be. If I change the behaviour of vecto= r-map to go back-to-front (order is unspecified in r6rs) we can easily d= o (eq? -1 index) as a stop condition to avoid any eventual overhead of t= ype checking with =3D. (If those are not elided, which I suspect might b= e the case. ). I did not look at that, since I have too little computer = time these days. As an added bonus, this speeds up quicksort.scm in ecraven's benchmarks = by a little. --=20 Linus Bj=C3=B6rnstam --234f3b0943a14e9abb9df6b76b2047c8 Content-Disposition: attachment;filename="0001-Write-a-proper-vector-map-and-vector-for-each-for-rn.patch" Content-Type: text/x-patch; name="0001-Write-a-proper-vector-map-and-vector-for-each-for-rn.patch" Content-Transfer-Encoding: BASE64 RnJvbSA2ZGM3MWVlZWMxYjBlZmFkOWJlMjNjNmY3MjMyM2NkYzU4Y2FmMjZiIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBMaW51cyA8Ympvcm5zdGFtLmxpbnVzQGZhc3RtYWls LnNlPgpEYXRlOiBXZWQsIDE3IEZlYiAyMDIxIDIyOjI4OjE5ICswMTAwClN1YmplY3Q6IFtQ QVRDSF0gV3JpdGUgYSBwcm9wZXIgdmVjdG9yLW1hcCBhbmQgdmVjdG9yLWZvci1lYWNoIGZv ciAocm5ycyBiYXNlKQoKICogbW9kdWxlL3JucnMvYmFzZS5zY20gKHZlY3Rvci1tYXAgdmVj dG9yLWZvci1lYWNoKTogUmV3cml0ZSB0byBub3QgYmUgc2xvdy4KLS0tCiBtb2R1bGUvcm5y cy9iYXNlLnNjbSB8IDgwICsrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysr KysrLS0tCiAxIGZpbGUgY2hhbmdlZCwgNzYgaW5zZXJ0aW9ucygrKSwgNCBkZWxldGlvbnMo LSkKCmRpZmYgLS1naXQgYS9tb2R1bGUvcm5ycy9iYXNlLnNjbSBiL21vZHVsZS9ybnJzL2Jh c2Uuc2NtCmluZGV4IDkyMDUwMTZiZC4uY2QyMzI3ZTQ5IDEwMDY0NAotLS0gYS9tb2R1bGUv cm5ycy9iYXNlLnNjbQorKysgYi9tb2R1bGUvcm5ycy9iYXNlLnNjbQpAQCAtMjMxLDEwICsy MzEsODIgQEAKICAgIChhbmQgKHJhdGlvbmFsLXZhbHVlZD8geCkKICAgICAgICAgKD0geCAo Zmxvb3IgKHJlYWwtcGFydCB4KSkpKSkKIAotIChkZWZpbmUgKHZlY3Rvci1mb3ItZWFjaCBw cm9jIC4gdmVjcykKLSAgIChhcHBseSBmb3ItZWFjaCAoY29ucyBwcm9jIChtYXAgdmVjdG9y LT5saXN0IHZlY3MpKSkpCi0gKGRlZmluZSAodmVjdG9yLW1hcCBwcm9jIC4gdmVjcykKLSAg IChsaXN0LT52ZWN0b3IgKGFwcGx5IG1hcCAoY29ucyBwcm9jIChtYXAgdmVjdG9yLT5saXN0 IHZlY3MpKSkpKQorIDs7IEF1eGlsaWFyeSBwcm9jZWR1cmUgZm9yIHZlY3Rvci1tYXAgYW5k IHZlY3Rvci1mb3ItZWFjaAorIChkZWZpbmUgKHZlY3Rvci1sZW5ndGhzIHdobyAuIHZzKQor ICAobGV0ICgobGVuZ3RocyAobWFwIHZlY3Rvci1sZW5ndGggdnMpKSkKKyAgICAodW5sZXNz IChhcHBseSA9IGxlbmd0aHMpCisgICAgICAoYXBwbHkgZXJyb3IKKyAgICAgICAgICAgICAo c3RyaW5nLWFwcGVuZCAoc3ltYm9sLT5zdHJpbmcgd2hvKQorICAgICAgICAgICAgICAgICAg ICAgICAgICAgICI6IFZlY3RvcnMgb2YgdW5ldmVuIGxlbmd0aC4iKQorICAgICAgICAgICAg IHZzKSkKKyAgICAoY2FyIGxlbmd0aHMpKSkKKworKGRlZmluZSB2ZWN0b3ItbWFwCisgIChj YXNlLWxhbWJkYQorICAgICIodmVjdG9yLW1hcCBmIHZlYzIgdmVjMiAuLi4pIC0+IHZlY3Rv cgorCitSZXR1cm4gYSBuZXcgdmVjdG9yIG9mIHRoZSBzaXplIG9mIHRoZSB2ZWN0b3IgYXJn dW1lbnRzLCB3aGljaAorbXVzdCBiZSBvZiBlcXVhbCBsZW5ndGguIEVhY2ggZWxlbWVudCBh dCBpbmRleCBAdmFye2l9IG9mIHRoZSBuZXcgCit2ZWN0b3IgaXMgbWFwcGVkIGZyb20gdGhl IG9sZCB2ZWN0b3JzIGJ5IEBjb2RleyhmICh2ZWN0b3ItcmVmIHZlYzEgaSkKKyh2ZWN0b3It cmVmIHZlYzIgaSkgLi4uKX0uICBUaGUgZHluYW1pYyBvcmRlciBvZiBhcHBsaWNhdGlvbiBv ZiAKK0B2YXJ7Zn0gaXMgdW5zcGVjaWZpZWQuIgorICAgICgoZiB2KQorICAgICAobGV0KiAo KGxlbiAodmVjdG9yLWxlbmd0aCB2KSkKKyAgICAgICAgICAgIChyZXN1bHQgKG1ha2UtdmVj dG9yIGxlbikpKQorICAgICAgIChsZXQgbG9vcCAoKGkgMCkpCisgICAgICAgICAodW5sZXNz ICg9IGkgbGVuKQorICAgICAgICAgICAodmVjdG9yLXNldCEgcmVzdWx0IGkgKGYgKHZlY3Rv ci1yZWYgdiBpKSkpCisgICAgICAgICAgIChsb29wICgrIGkgMSkpKSkKKyAgICAgICByZXN1 bHQpKQorICAgICgoZiB2MSB2MikKKyAgICAgKGxldCogKChsZW4gKHZlY3Rvci1sZW5ndGhz ICd2ZWN0b3ItbWFwIHYxIHYyKSkKKyAgICAgICAgICAgIChyZXN1bHQgKG1ha2UtdmVjdG9y IGxlbikpKQorICAgICAgIChsZXQgbG9vcCAoKGkgMCkpCisgICAgICAgICAodW5sZXNzICg9 IGkgbGVuKQorICAgICAgICAgICAodmVjdG9yLXNldCEgcmVzdWx0CisgICAgICAgICAgICAg ICAgICAgICAgICBpCisgICAgICAgICAgICAgICAgICAgICAgICAoZiAodmVjdG9yLXJlZiB2 MSBpKSAodmVjdG9yLXJlZiB2MiBpKSkpCisgICAgICAgICAgIChsb29wICgrIGkgMSkpKQor ICAgICAgICAgcmVzdWx0KSkpCisgICAgKChmIHYgLiB2cykKKyAgICAgKGxldCogKCh2cyAo Y29ucyB2IHZzKSkKKyAgICAgICAgICAgIChsZW4gKGFwcGx5IHZlY3Rvci1sZW5ndGhzICd2 ZWN0b3ItbWFwIHZzKSkKKyAgICAgICAgICAgIChyZXN1bHQgKG1ha2UtdmVjdG9yIGxlbikp KQorICAgICAgIChsZXQgbG9vcCAoKGkgMCkpCisgICAgICAgICAodW5sZXNzICg9IGkgbGVu KQorICAgICAgICAgICAodmVjdG9yLXNldCEgcmVzdWx0CisgICAgICAgICAgICAgICAgICAg ICAgICBpCisgICAgICAgICAgICAgICAgICAgICAgICAoYXBwbHkgZiAobWFwIChsYW1iZGEg KHYpICh2ZWN0b3ItcmVmIHYgaSkpIHZzKSkpCisgICAgICAgICAgIChsb29wICgrIGkgMSkp KSkKKyAgICAgICByZXN1bHQpKSkpCisKKyhkZWZpbmUgdmVjdG9yLWZvci1lYWNoCisgIChj YXNlLWxhbWJkYQorICAgICIodmVjdG9yLWZvci1lYWNoIGYgdmVjMSB2ZWMyIC4uLikgLT4g dW5zcGVjaWZpZWQKKworQ2FsbCBAY29kZXsoZiAodmVjdG9yLXJlZiB2ZWMxIGkpICh2ZWN0 b3ItcmVmIHZlYzIgaSkgLi4uKX0gZm9yIGVhY2ggaW5kZXgKKyBpbiB0aGUgcHJvdmlkZWQg dmVjdG9ycywgd2hpY2ggaGF2ZSB0byBiZSBvZiBlcXVhbCBsZW5ndGguIFRoZSBpdGVyYXRp b24KK2lzIHN0cmljdGx5IGxlZnQtdG8tcmlnaHQuIgorICAgICgoZiB2KQorICAgICAobGV0 ICgobGVuICh2ZWN0b3ItbGVuZ3RoIHYpKSkKKyAgICAgICAobGV0IGxvb3AgKChpIDApKQor ICAgICAgICAgKHVubGVzcyAoPSBpIGxlbikKKyAgICAgICAgICAgKGYgKHZlY3Rvci1yZWYg diBpKSkKKyAgICAgICAgICAgKGxvb3AgKCsgaSAxKSkpKSkpCisgICAgKChmIHYxIHYyKQor ICAgICAobGV0ICgobGVuICh2ZWN0b3ItbGVuZ3RocyAndmVjdG9yLWZvci1lYWNoIHYxIHYy KSkpCisgICAgICAgKGxldCBsb29wICgoaSAwKSkKKyAgICAgICAgICh1bmxlc3MgKD0gaSBs ZW4pCisgICAgICAgICAgIChmICh2ZWN0b3ItcmVmIHYxIGkpICh2ZWN0b3ItcmVmIHYyIGkp KQorICAgICAgICAgICAobG9vcCAoKyBpIDEpKSkpKSkKKyAgICAoKGYgdiAuIHZzKQorICAg ICAobGV0KiAoKHZzIChjb25zIHYgdnMpKQorICAgICAgICAgICAgKGxlbiAoYXBwbHkgdmVj dG9yLWxlbmd0aHMgJ3ZlY3Rvci1mb3ItZWFjaCB2cykpKQorICAgICAgIChsZXQgbG9vcCAo KGkgMCkpCisgICAgICAgICAodW5sZXNzICg9IGkgbGVuKQorICAgICAgICAgICAoYXBwbHkg ZiAobWFwIChsYW1iZGEgKHYpICh2ZWN0b3ItcmVmIHYgaSkpIHZzKSkKKyAgICAgICAgICAg KGxvb3AgKCsgaSAxKSkpKSkpKSkKKwogCiAgKGRlZmluZS1zeW50YXggZGVmaW5lLXByb3h5 CiAgICAoc3ludGF4LXJ1bGVzIChAKQotLSAKMi4yNS4xCgo= --234f3b0943a14e9abb9df6b76b2047c8--