unofficial mirror of guile-devel@gnu.org 
 help / color / mirror / Atom feed
* [PATCH] Make vector-map and vector-for-each in (rnrs base) fast
@ 2021-02-18  7:34 Linus Björnstam
  2021-02-19  9:08 ` Linus Björnstam
  0 siblings, 1 reply; 2+ messages in thread
From: Linus Björnstam @ 2021-02-18  7:34 UTC (permalink / raw)
  To: guile-devel

[-- Attachment #1: Type: text/plain, Size: 1209 bytes --]

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

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Write-a-proper-vector-map-and-vector-for-each-for-rn.patch --]
[-- Type: text/x-patch; name="0001-Write-a-proper-vector-map-and-vector-for-each-for-rn.patch", Size: 3545 bytes --]

From 6dc71eeec1b0efad9be23c6f72323cdc58caf26b Mon Sep 17 00:00:00 2001
From: Linus <bjornstam.linus@fastmail.se>
Date: Wed, 17 Feb 2021 22:28:19 +0100
Subject: [PATCH] Write a proper vector-map and vector-for-each for (rnrs base)

 * module/rnrs/base.scm (vector-map vector-for-each): Rewrite to not be slow.
---
 module/rnrs/base.scm | 80 +++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 76 insertions(+), 4 deletions(-)

diff --git a/module/rnrs/base.scm b/module/rnrs/base.scm
index 9205016bd..cd2327e49 100644
--- a/module/rnrs/base.scm
+++ b/module/rnrs/base.scm
@@ -231,10 +231,82 @@
    (and (rational-valued? x)
         (= x (floor (real-part x)))))
 
- (define (vector-for-each proc . vecs)
-   (apply for-each (cons proc (map vector->list vecs))))
- (define (vector-map proc . vecs)
-   (list->vector (apply map (cons proc (map vector->list vecs)))))
+ ;; Auxiliary procedure for vector-map and vector-for-each
+ (define (vector-lengths who . vs)
+  (let ((lengths (map vector-length vs)))
+    (unless (apply = lengths)
+      (apply error
+             (string-append (symbol->string who)
+                            ": Vectors of uneven length.")
+             vs))
+    (car lengths)))
+
+(define vector-map
+  (case-lambda
+    "(vector-map f vec2 vec2 ...) -> vector
+
+Return a new vector of the size of the vector arguments, which
+must be of equal length. Each element at index @var{i} of the new 
+vector is mapped from the old vectors by @code{(f (vector-ref vec1 i)
+(vector-ref vec2 i) ...)}.  The dynamic order of application of 
+@var{f} is unspecified."
+    ((f v)
+     (let* ((len (vector-length v))
+            (result (make-vector len)))
+       (let loop ((i 0))
+         (unless (= i len)
+           (vector-set! result i (f (vector-ref v i)))
+           (loop (+ i 1))))
+       result))
+    ((f v1 v2)
+     (let* ((len (vector-lengths 'vector-map v1 v2))
+            (result (make-vector len)))
+       (let loop ((i 0))
+         (unless (= i len)
+           (vector-set! result
+                        i
+                        (f (vector-ref v1 i) (vector-ref v2 i)))
+           (loop (+ i 1)))
+         result)))
+    ((f v . vs)
+     (let* ((vs (cons v vs))
+            (len (apply vector-lengths 'vector-map vs))
+            (result (make-vector len)))
+       (let loop ((i 0))
+         (unless (= i len)
+           (vector-set! result
+                        i
+                        (apply f (map (lambda (v) (vector-ref v i)) vs)))
+           (loop (+ i 1))))
+       result))))
+
+(define vector-for-each
+  (case-lambda
+    "(vector-for-each f vec1 vec2 ...) -> unspecified
+
+Call @code{(f (vector-ref vec1 i) (vector-ref vec2 i) ...)} for each index
+ in the provided vectors, which have to be of equal length. The iteration
+is strictly left-to-right."
+    ((f v)
+     (let ((len (vector-length v)))
+       (let loop ((i 0))
+         (unless (= i len)
+           (f (vector-ref v i))
+           (loop (+ i 1))))))
+    ((f v1 v2)
+     (let ((len (vector-lengths 'vector-for-each v1 v2)))
+       (let loop ((i 0))
+         (unless (= i len)
+           (f (vector-ref v1 i) (vector-ref v2 i))
+           (loop (+ i 1))))))
+    ((f v . vs)
+     (let* ((vs (cons v vs))
+            (len (apply vector-lengths 'vector-for-each vs)))
+       (let loop ((i 0))
+         (unless (= i len)
+           (apply f (map (lambda (v) (vector-ref v i)) vs))
+           (loop (+ i 1))))))))
+
 
  (define-syntax define-proxy
    (syntax-rules (@)
-- 
2.25.1


^ permalink raw reply	[flat|nested] 2+ messages in thread

* Re: [PATCH] Make vector-map and vector-for-each in (rnrs base) fast
  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
  0 siblings, 0 replies; 2+ messages in thread
From: Linus Björnstam @ 2021-02-19  9:08 UTC (permalink / raw)
  To: guile-devel

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



^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2021-02-19  9:08 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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 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 NNTP newsgroup(s).