`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

1 Like
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))
4

Thank you for the information and suggestions! I wasn't aware of vector-reverse! in srfi/43 or vector-shuffle! in your soup-lib package—both look very useful.

5

Measuring this a bit more directly, it looks like using for/vector and vector->treelist is consistently faster than using for/treelist directly, and so an implementation revision is probably a good idea.


'for-mutable
(time
 (mutable-treelist-length
  (for/mutable-treelist ([i (in-range N)])
    (+ 17 i))))
'for-immutable
(time
 (treelist-length
  (for/treelist ([i (in-range N)])
    (+ 17 i))))
'for-vector-mutable
(time
 (mutable-treelist-length
  (vector->mutable-treelist
   (for/vector ([i (in-range N)])
     (+ 17 i)))))
'for-vector-immutable
(time
 (treelist-length
  (vector->treelist
   (for/vector ([i (in-range N)])
     (+ 17 i)))))

produces:

'for-mutable
cpu time: 273 real time: 273 gc time: 19
1000000
'for-immutable
cpu time: 260 real time: 260 gc time: 16
1000000
'for-vector-mutable
cpu time: 148 real time: 148 gc time: 31
1000000
'for-vector-immutable
cpu time: 142 real time: 142 gc time: 31
1000000
6

I replied on the PR but to follow up here:

  • The internal state used by for/vector can be exposed by continuations. I don't think for/treelist should be stateful in that sense.

  • Most programs create short lists. Lists of length 0, 1, and 2 are especially common, and for forms are used on short lists all the time. Lists of length 1000000 or 10000000 are rare. A performance argument needs to take short lists into account.

2 Likes