Re: [PATCH] Make vector-map and vector-for-each in (rnrs base) fast

[Linus Björnstam]

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