[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH] Make vector-map and vector-for-each in (rnrs base) fast
From: |
Linus Björnstam |
Subject: |
[PATCH] Make vector-map and vector-for-each in (rnrs base) fast |
Date: |
Thu, 18 Feb 2021 08:34:23 +0100 |
User-agent: |
Cyrus-JMAP/3.5.0-alpha0-141-gf094924a34-fm-20210210.001-gf094924a |
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
0001-Write-a-proper-vector-map-and-vector-for-each-for-rn.patch
Description: Text Data
- [PATCH] Make vector-map and vector-for-each in (rnrs base) fast,
Linus Björnstam <=