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

**URL:** <https://racket.discourse.group/t/for-treelist-vs-vector-treelist/3441>\
**Category:** Questions & Answers\
**Created:** [December 24, 2024, 10:12am UTC](https://racket.discourse.group/t/for-treelist-vs-vector-treelist/3441 "2024-12-24T10:12:47Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![NoahStoryM](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/noahstorym/32/17_2.png) [@NoahStoryM](https://racket.discourse.group/u/NoahStoryM)\
**Post date:** [December 24, 2024, 10:12am UTC](https://racket.discourse.group/t/for-treelist-vs-vector-treelist/3441/1 "2024-12-24T10:12:47Z")

</div>

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

```scheme
(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:

```scheme
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)?

---

<div class="post-metadata">

**Author:** ![shawnw](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/shawnw/32/1031_2.png) [@shawnw](https://racket.discourse.group/u/shawnw)\
**Post date:** [December 24, 2024, 6:48pm UTC](https://racket.discourse.group/t/for-treelist-vs-vector-treelist/3441/2 "2024-12-24T18:48:51Z")

</div>

fwiw, `vector-reverse!` is in the [`srfi/43` module](https://docs.racket-lang.org/srfi/srfi-43.html) that comes with Racket (And in [`srfi/133`](https://srfi.schemers.org/srfi-133/srfi-133.html) that's in my [`extra-srfi-libs` package](https://docs.racket-lang.org/extra-srfi-libs/index.html)). I also have a [`vector-shuffle!`](https://docs.racket-lang.org/soup-lib/index.html#%28def._%28%28lib._soup-lib%2Fvector..rkt%29._vector-shuffle%21%29%29) in my [`soup-lib` package](https://docs.racket-lang.org/soup-lib/index.html). /blatant-self-promotion

---

<div class="post-metadata">

**Author:** ![shawnw](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/shawnw/32/1031_2.png) [@shawnw](https://racket.discourse.group/u/shawnw)\
**Post date:** [December 24, 2024, 6:57pm UTC](https://racket.discourse.group/t/for-treelist-vs-vector-treelist/3441/3 "2024-12-24T18:57:21Z")

</div>

(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!`:

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

```

---

<div class="post-metadata">

**Author:** ![NoahStoryM](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/noahstorym/32/17_2.png) [@NoahStoryM](https://racket.discourse.group/u/NoahStoryM)\
**Post date:** [December 25, 2024, 3:27am UTC](https://racket.discourse.group/t/for-treelist-vs-vector-treelist/3441/4 "2024-12-25T03:27:25Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![samth](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/samth/32/3_2.png) [@samth](https://racket.discourse.group/u/samth)\
**Post date:** [January 2, 2025, 10:08pm UTC](https://racket.discourse.group/t/for-treelist-vs-vector-treelist/3441/5 "2025-01-02T22:08:41Z")

</div>

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.

```scheme

'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:

```scheme
'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

```

---

<div class="post-metadata">

**Author:** ![mflatt](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/mflatt/32/6_2.png) [@mflatt](https://racket.discourse.group/u/mflatt)\
**Post date:** [January 10, 2025, 3:41pm UTC](https://racket.discourse.group/t/for-treelist-vs-vector-treelist/3441/6 "2025-01-10T15:41:56Z")

</div>

I replied on the [PR](https://github.com/racket/racket/pull/5172) 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.