# Performance comparison between (append (reverse a) b)) and (foldl cons b a))

**URL:** <https://racket.discourse.group/t/performance-comparison-between-append-reverse-a-b-and-foldl-cons-b-a/2903>\
**Category:** Questions & Answers\
**Tags:** question, performance\
**Created:** [May 4, 2024, 5:18pm UTC](https://racket.discourse.group/t/performance-comparison-between-append-reverse-a-b-and-foldl-cons-b-a/2903 "2024-05-04T17:18:34Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![NeraSnow](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/nerasnow/32/1782_2.png) [@NeraSnow](https://racket.discourse.group/u/NeraSnow)\
**Post date:** [May 4, 2024, 5:18pm UTC](https://racket.discourse.group/t/performance-comparison-between-append-reverse-a-b-and-foldl-cons-b-a/2903/1 "2024-05-04T17:18:34Z")

</div>

I have the following code example. I am wondering if `method1` is slower than `method2`?

I want to write a benchmark program, but I don't have any prior experience in this.

```scheme
#lang racket

(define (method1 a b) (append (reverse a) b))
(define (method2 a b) (foldl cons b a))

(define lst1-a '(1 2 3 4 5 6))
(define lst1-b '(7 8 9 10 11 12))

(method1 lst1-a lst1-b)
(method2 lst1-a lst1-b)

```

Thanks for the help in advance.

---

<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:** [May 4, 2024, 5:40pm UTC](https://racket.discourse.group/t/performance-comparison-between-append-reverse-a-b-and-foldl-cons-b-a/2903/2 "2024-05-04T17:40:51Z")

</div>

You should also compare [`append-reverse`](https://srfi.schemers.org/srfi-1/srfi-1.html#append-reverse) from the `srfi/1` module. I would expect method1 to be the slowest - it'll do more allocating and list traversals than the others.

* * *

You can use [`time`](https://docs.racket-lang.org/reference/time.html#%28form._%28%28lib._racket%2Fprivate%2Fmore-scheme..rkt%29._time%29%29) for rough benchmarking. There are profiler and better benchmark packages available too.

---

<div class="post-metadata">

**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\
**Post date:** [May 4, 2024, 5:45pm UTC](https://racket.discourse.group/t/performance-comparison-between-append-reverse-a-b-and-foldl-cons-b-a/2903/3 "2024-05-04T17:45:47Z")

</div>

Here’s a benchmark script:

```scheme
#lang racket

(define (method1 a b) (append (reverse a) b))
(define (method2 a b) (foldl cons b a))

(define N 10000)
(define ITER 10000)

(define lst1-a (range N))
(define lst1-b (range N))

(define (bench proc)
  (collect-garbage)
  (collect-garbage)
  (collect-garbage)

  (time
   (for ([i (in-range ITER)])
     (proc lst1-a lst1-b))))

(bench method1) ;=> cpu time: 545 real time: 615 gc time: 20
(bench method2) ;=> cpu time: 326 real time: 380 gc time: 10

```

So `method1` is slower.

And this makes total sense. In `method2`, you `cons` about `|a|` times. In `method1`, you first `cons` `|a|` times for the `reverse`, and then another `|a|` times for the `append`. That’s twice the amount of work.

---

<div class="post-metadata">

**Author:** ![NeraSnow](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/nerasnow/32/1782_2.png) [@NeraSnow](https://racket.discourse.group/u/NeraSnow)\
**Post date:** [May 4, 2024, 5:58pm UTC](https://racket.discourse.group/t/performance-comparison-between-append-reverse-a-b-and-foldl-cons-b-a/2903/4 "2024-05-04T17:58:10Z")

</div>

Using @sorawee 's script, I found out that the [`append-reverse`](https://srfi.schemers.org/srfi-1/srfi-1.html#append-reverse) has roughly the same performance as my `method2`.

```scheme
(bench method1) ;=> cpu time: 733 real time: 733 gc time: 22
(bench method2) ;=> cpu time: 367 real time: 367 gc time: 11
(bench append-reverse) ;=> cpu time: 369 real time: 369 gc time: 11

```

---

<div class="post-metadata">

**Author:** ![cadence](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/cadence/32/998_2.png) [@cadence](https://racket.discourse.group/u/cadence)\
**Post date:** [May 6, 2024, 6:51am UTC](https://racket.discourse.group/t/performance-comparison-between-append-reverse-a-b-and-foldl-cons-b-a/2903/5 "2024-05-06T06:51:24Z")

</div>

> [@sorawee](#):
>
> ```scheme
> (collect-garbage)
> (collect-garbage)
> (collect-garbage)
> 
> ```

Why collect garbage 3 times? Shouldn't it be the same as collecting garbage once? What's the difference?

---

<div class="post-metadata">

**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\
**Post date:** [May 6, 2024, 7:15am UTC](https://racket.discourse.group/t/performance-comparison-between-append-reverse-a-b-and-foldl-cons-b-a/2903/6 "2024-05-06T07:15:12Z")

</div>

I don’t know! I saw other people do it, and I just followed that.

You can in fact see this repeated `(collect-garbage)` throughout the code base, though it looks like twice would be enough.

- [https://github.com/racket/racket/blob/9048bafc919a3077518930da73a008183a6f6565/racket/src/expander/common/intern.rkt#L119](https://github.com/racket/racket/blob/9048bafc919a3077518930da73a008183a6f6565/racket/src/expander/common/intern.rkt#L119)
- [https://github.com/racket/racket/blob/9048bafc919a3077518930da73a008183a6f6565/pkgs/racket-test/tests/stress.rkt#L15](https://github.com/racket/racket/blob/9048bafc919a3077518930da73a008183a6f6565/pkgs/racket-test/tests/stress.rkt#L15)
- [https://github.com/racket/drracket/blob/7899052c860f3549b54b753144cd2c2519562012/drracket-test/tests/drracket/leak-on-run.rkt#L26](https://github.com/racket/drracket/blob/7899052c860f3549b54b753144cd2c2519562012/drracket-test/tests/drracket/leak-on-run.rkt#L26)

From my recollection, I heard (though without any deep understanding) that it’s related to the generational garbage collector. Running `(collect-garbage)` once might collect garbage in a way that has some leftover. So we should run it again a couple more times.

---

<div class="post-metadata">

**Author:** ![jjsimpso](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/jjsimpso/32/602_2.png) [@jjsimpso](https://racket.discourse.group/u/jjsimpso)\
**Post date:** [May 6, 2024, 2:30pm UTC](https://racket.discourse.group/t/performance-comparison-between-append-reverse-a-b-and-foldl-cons-b-a/2903/7 "2024-05-06T14:30:06Z")

</div>

Keep in mind that this is really only something you need to be concerned about when doing performance measurements. I've seen this idiom in other GC'd languages as well. GC is intended to work this way, but before running a targeted benchmark you want to make sure that everything is GC'd beforehand and not during the benchmark.

---

<div class="post-metadata">

**Author:** ![gus-massa](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/gus-massa/32/507_2.png) [@gus-massa](https://racket.discourse.group/u/gus-massa)\
**Post date:** [May 6, 2024, 2:40pm UTC](https://racket.discourse.group/t/performance-comparison-between-append-reverse-a-b-and-foldl-cons-b-a/2903/8 "2024-05-06T14:40:23Z")

</div>

> [@sorawee](#):
>
> I don’t know! I saw other people do it, and I just followed that.

Neither do I, but I think it's related to [will executors](https://docs.racket-lang.org/reference/willexecutor.html). IIRC, the first one cleans normal stuff, the second the objects that had will executors, and the third ?????