# Why are struct constructors accessed through a parameter 10-20% faster than using the constructor directly?

**URL:** <https://racket.discourse.group/t/why-are-struct-constructors-accessed-through-a-parameter-10-20-faster-than-using-the-constructor-directly/3364>\
**Category:** Questions & Answers\
**Tags:** question, performance\
**Created:** [November 27, 2024, 10:11pm UTC](https://racket.discourse.group/t/why-are-struct-constructors-accessed-through-a-parameter-10-20-faster-than-using-the-constructor-directly/3364 "2024-11-27T22:11:22Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![780nm](https://avatars.discourse-cdn.com/v4/letter/7/a9adbd/32.png) [@780nm](https://racket.discourse.group/u/780nm)\
**Post date:** [November 27, 2024, 10:11pm UTC](https://racket.discourse.group/t/why-are-struct-constructors-accessed-through-a-parameter-10-20-faster-than-using-the-constructor-directly/3364/1 "2024-11-27T22:11:22Z")

</div>

Hi!

I was looking at the performance impacts of parameters for use in a language project and ran into some odd performance characteristics: accessing struct constructors through a `parameterize`-introduced binding appears to be 10-20% faster than using them directly, while struct accesses are about 10-20% slower when the accessor procedure is referenced through a parameter.

Take the following file:

```scheme
#lang racket

(struct tree (l r v))

(define (rand-tree depth)
    (if (<= depth 1)
        (tree #f #f (random 1000))
        (tree (rand-tree (sub1 depth))
           (rand-tree (sub1 depth))
           (random 1000))))

(define (sum todo acc)
    (match todo
        ['() acc]
        [(cons h t)
            (if h
                (sum (cons (tree-l h) (cons (tree-r h) t))
                     (+ acc (tree-v h)))
                (sum t acc))]))

(define (print-time) (println (current-inexact-monotonic-milliseconds)))

(print-time)
(define t1 (rand-tree 25))
(print-time)
(println (sum `(,t1) 0))
(print-time)

```

This spits out:

```scheme
364.5869
4900.0113
16759036712
5286.0855

```

So, about 4.5s to construct a complete binary tree of depth 25, and about .4s to compute its sum. If, instead, we access the struct constructors and accessors through a parameter binding:

```scheme
#lang racket

(define m-p (make-parameter #f))
(define l-p (make-parameter #f))
(define r-p (make-parameter #f))
(define v-p (make-parameter #f))

(define (memo fun)
    (let ([cache #f])
    (lambda () (if cache cache
        (begin (set! cache (fun))
            cache)))))

(define m (memo m-p))
(define l (memo l-p))
(define r (memo r-p))
(define v (memo v-p))

(define (rand-tree depth)
    (if (<= depth 1)
        ((m) #f #f (random 1000))
        ((m) (rand-tree (sub1 depth))
           (rand-tree (sub1 depth))
           (random 1000))))

(define (sum todo acc)
    (match todo
        ['() acc]
        [(cons h t)
            (if h
                (sum (cons ((l) h) (cons ((r) h) t))
                     (+ acc ((v) h)))
                (sum t acc))]))

(define (print-time) (println (current-inexact-monotonic-milliseconds)))

(struct tree (l r v))

(parameterize ([m-p (lambda (l r v) (tree l r v))]
               [l-p (lambda (node) (tree-l node))]
               [r-p (lambda (node) (tree-r node))]
               [v-p (lambda (node) (tree-v node))])
    (print-time)
    (define t1 (rand-tree 25))
    (print-time)
    (println (sum `(,t1) 0))
    (print-time))

```

We get these timings:

```scheme
403.0528
4562.1506
16759097702
5176.3364

```

4.1s to construct the tree, .6s to traverse and compute the sum.

A longer sum computation time makes sense, as there's an additional layer of indirection when accessing the parameter procedure, but... why is construction faster?

Any insight would be appreciated.

Cheers,

Sean

---

<div class="post-metadata">

**Author:** ![780nm](https://avatars.discourse-cdn.com/v4/letter/7/a9adbd/32.png) [@780nm](https://racket.discourse.group/u/780nm)\
**Post date:** [November 27, 2024, 10:29pm UTC](https://racket.discourse.group/t/why-are-struct-constructors-accessed-through-a-parameter-10-20-faster-than-using-the-constructor-directly/3364/2 "2024-11-27T22:29:08Z")

</div>

To thicken the plot, it seems that just wrapping the code block in `parameterize` _with some dummy parameter_ is sufficient to get performance improvements on construction:

```scheme
#lang racket

(define p (make-parameter #f))
(struct tree (l r v))

(define (rand-tree depth)
    (if (<= depth 1)
        (tree #f #f (random 1000))
        (tree (rand-tree (sub1 depth))
           (rand-tree (sub1 depth))
           (random 1000))))

(define (sum todo acc)
    (match todo
        ['() acc]
        [(cons h t)
            (if h
                (sum (cons (tree-l h) (cons (tree-r h) t))
                     (+ acc (tree-v h)))
                (sum t acc))]))

(define (print-time) (println (current-inexact-monotonic-milliseconds)))

(parameterize ([p #f])
    (print-time)
    (define t1 (rand-tree 25))
    (print-time)
    (println (sum `(,t1) 0))
    (print-time))

```

This has timings of:

```scheme
354.8463
4192.6203
16761484464
4550.8924

```

So, about 3.9s to construct. This consistently outperforms the parameter-less version.  
Maybe these are threading/cache related behaviors?

---

<div class="post-metadata">

**Author:** ![notjack](https://avatars.discourse-cdn.com/v4/letter/n/e47774/32.png) [@notjack](https://racket.discourse.group/u/notjack)\
**Post date:** [November 27, 2024, 11:39pm UTC](https://racket.discourse.group/t/why-are-struct-constructors-accessed-through-a-parameter-10-20-faster-than-using-the-constructor-directly/3364/3 "2024-11-27T23:39:16Z")

</div>

I see some memoization code in the fast example that's not in the slow example. Is that intentional? It's probably the reason for the performance 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:** [November 27, 2024, 11:43pm UTC](https://racket.discourse.group/t/why-are-struct-constructors-accessed-through-a-parameter-10-20-faster-than-using-the-constructor-directly/3364/4 "2024-11-27T23:43:17Z")

</div>

Use this one weird trick to speed up your program by 25%!

This is a really great puzzle. Here’s a simplification of your first version:

```scheme
#lang racket

(struct tree (l r v))

(define (rand-tree depth)
  (if (<= depth 1)
      (tree #f #f (random 1000))
      (tree (rand-tree (sub1 depth))
            (rand-tree (sub1 depth))
            (random 1000))))

(time (rand-tree 25))
;; cpu time: 3468 real time: 3518 gc time: 1795

```

(Tip: use `time`. No need to roll your own time measurement!)

And your second version is:

```scheme
#lang racket

(define dummy (make-parameter #f))

(struct tree (l r v))

(define (rand-tree depth)
  (if (<= depth 1)
      (tree #f #f (random 1000))
      (tree (rand-tree (sub1 depth))
            (rand-tree (sub1 depth))
            (random 1000))))

(parameterize ([dummy 0])
  (time (rand-tree 25)))
;; cpu time: 2545 real time: 2582 gc time: 1752

```

Here’s my third version, which has no `parameterize`, but with even greater speed up!

```scheme
#lang racket

(struct tree (l r v))

(define gen (current-pseudo-random-generator))

(define (rand-tree depth)
  (if (<= depth 1)
      (tree #f #f (random 1000 gen))
      (tree (rand-tree (sub1 depth))
            (rand-tree (sub1 depth))
            (random 1000 gen))))

(time (rand-tree 25))
;; cpu time: 2230 real time: 2242 gc time: 1781

```

The issue is that every time that you call `random` without the second argument, Racket has to look up for the generator parameter. My understanding is that in the first version, Racket has to traverse multiple frames to find the parameter, while in the second version the usage of `parameterize` copies the parameter to a frame that can be accessed faster. But if you access the parameter directly, as done in the third version, then there’s no need to look up anything (in the loop).

---

<div class="post-metadata">

**Author:** ![ryanc](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ryanc/32/71_2.png) [@ryanc](https://racket.discourse.group/u/ryanc)\
**Post date:** [November 28, 2024, 12:01am UTC](https://racket.discourse.group/t/why-are-struct-constructors-accessed-through-a-parameter-10-20-faster-than-using-the-constructor-directly/3364/5 "2024-11-28T00:01:20Z")

</div>

Based on a quick look at the implementation of parameters in racket/src/cs/rumble/parameter.ss, I don't think the speed difference is due to the nearest parameterization containing an entry for the `current-pseudo-random-generator` parameter. The parameterization appears to start out as an empty hasheq and only contains the parameters added by `parameterize`.

My best guess is that the difference is due to the continuation-mark lookup step that fetches the parameterization.

Update: Here's a version that lets you insert extra frames to push the `parameterize` continuation-mark frame as far away as you like:

```scheme
#lang racket

(define dummy (make-parameter #f))

(struct tree (l r v))

(define (rand-tree depth)
    (if (<= depth 1)
        (tree #f #f (random 1000))
        (tree (rand-tree (sub1 depth))
           (rand-tree (sub1 depth))
           (random 1000))))

(define (grow-stack-and-call depth proc)
  (cond [(zero? depth)
         (proc)]
        [else
         (with-continuation-mark depth
           'just-taking-up-space
           (begin0 (grow-stack-and-call (sub1 depth) proc)))]))

(define (go)
  (time (rand-tree 25)))

(parameterize ((dummy 0))
  ;;(grow-stack-and-call 5 go)
  (grow-stack-and-call 50 go)
  (void))

```

---

<div class="post-metadata">

**Author:** ![780nm](https://avatars.discourse-cdn.com/v4/letter/7/a9adbd/32.png) [@780nm](https://racket.discourse.group/u/780nm)\
**Post date:** [November 28, 2024, 12:17am UTC](https://racket.discourse.group/t/why-are-struct-constructors-accessed-through-a-parameter-10-20-faster-than-using-the-constructor-directly/3364/6 "2024-11-28T00:17:46Z")

</div>

Fascinating. I've just confirmed that after eliding `random` things behave about as expected:

```scheme
#lang racket

(struct tree (l r v))

(define (make-tree depth)
  (if (<= depth 1)
      (tree #f #f 500)
      (tree (make-tree (sub1 depth))
            (make-tree (sub1 depth))
            500)))

(time (make-tree 28))

```

gives

```scheme
cpu time: 19875 real time: 40510 gc time: 19531

```

while

```scheme
#lang racket

(define p (make-parameter #f))

(struct tree (l r v))

(define (make-tree depth)
  (if (<= depth 1)
      (tree #f #f 500)
      (tree (make-tree (sub1 depth))
            (make-tree (sub1 depth))
            500)))

(parameterize ([p #f])
    (time (make-tree 28)))

```

gives

```scheme
cpu time: 19718 real time: 38212 gc time: 19343

```

which is practically the same. (also, holy gc workload) Thanks for the heads-up about `time`.

The memoization in the second example was intentional, otherwise running the parameter procedure seems to eat quite a few cycles. This is probably why @sorawee's third example is so much faster, assuming `random`  
does the dereference each loop. Still not clear on why @sorawee's second example is faster, though @sorawee and @ryanc's hypotheses are very much appreciated.

---

<div class="post-metadata">

**Author:** ![780nm](https://avatars.discourse-cdn.com/v4/letter/7/a9adbd/32.png) [@780nm](https://racket.discourse.group/u/780nm)\
**Post date:** [November 28, 2024, 12:28am UTC](https://racket.discourse.group/t/why-are-struct-constructors-accessed-through-a-parameter-10-20-faster-than-using-the-constructor-directly/3364/7 "2024-11-28T00:28:23Z")

</div>

Ah, awesome. yep, with `random`, growing the stack from 50 to 500 before calling makes it about 5x slower:

```scheme
50: cpu time: 1312 real time: 5711 gc time: 640
500: cpu time: 8234 real time: 24295 gc time: 812

```

Without `random`, there seems to be no degradation:

```scheme
50: cpu time: 625 real time: 2350 gc time: 562
500: cpu time: 578 real time: 2324 gc time: 562

```

---

<div class="post-metadata">

**Author:** ![780nm](https://avatars.discourse-cdn.com/v4/letter/7/a9adbd/32.png) [@780nm](https://racket.discourse.group/u/780nm)\
**Post date:** [November 28, 2024, 12:32am UTC](https://racket.discourse.group/t/why-are-struct-constructors-accessed-through-a-parameter-10-20-faster-than-using-the-constructor-directly/3364/8 "2024-11-28T00:32:05Z")

</div>

Thanks everyone for taking a look.