From: "Linus Björnstam" <linus.bjornstam@veryfast.biz>
To: guile-devel@gnu.org
Subject: Re: [PATCH] Make vector-map and vector-for-each in (rnrs base) fast
Date: Fri, 19 Feb 2021 10:08:43 +0100 [thread overview]
Message-ID: <66c58621-c3d7-4ba9-af3c-ccf5e04ae8f6@www.fastmail.com> (raw)
In-Reply-To: <d5549555-238b-40c4-9405-35f7c3eb1e91@www.fastmail.com>
As suspected: the eq? optimization does nothing.
I will write some tests for (r6rs base) to test the multi-vector behaviour of this. Currently only (vector-map proc vec1) is tested in there. That 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 (only proper lists of the same length), but the boot-9 one seems faster with worse error messages - probably due to some offloading to C.
Wouldn't one definition be a better choice, and if so: which one?
--
Linus Björnstam
On Thu, 18 Feb 2021, at 08:34, Linus Björnstam wrote:
> Hi there!
>
> I was spelunking through the guile source tree and found (rnrs base).
> The vector-map and vector-for-each in there are horribly inefficient.
> They are doing (list->vector (apply map PROC (map vector->list
> vectors))), which 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
> memory 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
> vector-map to go back-to-front (order is unspecified in r6rs) we can
> easily do (eq? -1 index) as a stop condition to avoid any eventual
> overhead of type checking with =. (If those are not elided, which I
> suspect might be 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.
> --
> Linus Björnstam
> Attachments:
> * 0001-Write-a-proper-vector-map-and-vector-for-each-for-rn.patch
prev parent reply other threads:[~2021-02-19 9:08 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-02-18 7:34 [PATCH] Make vector-map and vector-for-each in (rnrs base) fast Linus Björnstam
2021-02-19 9:08 ` Linus Björnstam [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=66c58621-c3d7-4ba9-af3c-ccf5e04ae8f6@www.fastmail.com \
--to=linus.bjornstam@veryfast.biz \
--cc=guile-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).