`for/treelist` vs `vector->treelist`

Questions & Answers
1

While working on a package, I encountered a performance issue that I'd like to
illustrate with the following example code:

(time
 (define mtl (mutable-treelist 'x))
 (define d* (build-list 10000000 values))
 (define f reverse) ; adjust the order, `reverse` is used as an example
 (for ([d (in-list (f d*))])
   (mutable-treelist-cons! mtl d)))

(time
 (define mtl (mutable-treelist 'x))
 (define d* (build-vector 10000000 values))
 (define f! vector-reverse!)
 (f! d*)
 (for ([d (in-vector d*)])
   (mutable-treelist-cons! mtl d)))

(time
 (define mtl (mutable-treelist 'x))
 (define d* (build-vector 10000000 values))
 (define f! vector-reverse!)
 (f! d*)
 (vector-reverse! d*)
 (mutable-treelist-prepend! mtl (vector->treelist d*)))

Here are the results:

cpu time: 16336 real time: 16416 gc time: 2497
cpu time: 13286 real time: 13332 gc time: 573
cpu time: 515 real time: 517 gc time: 255

Currently, both for/treelist and treelist-reverse are implemented using
iterative element insertion. For example, for/treelist relies on for/fold
and treelist-add. Could these operations be re-implemented to take advantage
of vectors for more efficient execution? For example, re-implement for/treelist
using for/vector and vector->treelist.

On the other hand, My library requires functions like vector-reverse! and
vector-shuffle!. These functions are currently not provided in racket/vector
but could be used to implement other operations, such as treelist-reverse,
treelist-shuffle, and shuffle. I plan to open a new PR to provide these vector
functions. I recall that Racket prefers not to include treelist-shuffle in
racket/treelist. If I create a PR for vector-shuffle!, should it belong in a
separate module (e.g., a shuffle-related module)?

2

fwiw, vector-reverse! is in the srfi/43 module that comes with Racket (And in srfi/133 that's in my extra-srfi-libs package). I also have a vector-shuffle! in my soup-lib package. /blatant-self-promotion

3

(I don't seem to be able to edit my own post to add stuff I thought of later? Strange)

You might also be interested in a sequence that directly iterates over a vector in reverse order instead of using vector-reverse!:

(define v '#(1 2 3 4 5))
(for ([elem (in-vector v (sub1 (vector-length v)) -1 -1)])
  (println elem))