# Stdlib.List loop unrolling

**URL:** <https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262>\
**Category:** Learning\
**Created:** [January 27, 2023, 10:49am UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262 "2023-01-27T10:49:49Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![BikalGurung](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bikalgurung/32/5105_2.png) [@BikalGurung](https://discuss.ocaml.org/u/BikalGurung)\
**Post date:** [January 27, 2023, 10:49am UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/1 "2023-01-27T10:49:49Z")

</div>

I can see the loop unrolling technique applied for `Stdlib.List.map` function ([ocaml/list.ml at trunk · ocaml/ocaml · GitHub](https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml#L80-L88)). However, I don’t see the same technique being applied for `Stdlib.List.find` - [ocaml/list.ml at trunk · ocaml/ocaml · GitHub](https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml#L231-L233). Can `find` not benefit from loop unrolling similar to `map`?

---

<div class="post-metadata">

**Author:** ![nojb](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nojb/32/519_2.png) [@nojb](https://discuss.ocaml.org/u/nojb)\
**Post date:** [January 27, 2023, 11:40am UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/2 "2023-01-27T11:40:44Z")

</div>

There is a tension between speed and code size (typically smaller code will positively affect performance), as well as clarity (unrolling harms readability and makes the code less maintanable).

`List.map` was made tail-recursive recently, and, after benchmarking, its implementation was hand-unrolled in order for the new version to have performance no worse than the previous one in most or all cases.

Manual unrolling was justified by the central place `List.map` occupies in practically any OCaml program, but would not be in most other cases.

Cheers,  
Nicolas

---

<div class="post-metadata">

**Author:** ![BikalGurung](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bikalgurung/32/5105_2.png) [@BikalGurung](https://discuss.ocaml.org/u/BikalGurung)\
**Post date:** [January 27, 2023, 12:17pm UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/3 "2023-01-27T12:17:11Z")

</div>

Thanks. The justification makes sense. If in some other use cases `find` was the predominant usage, do you think it makes sense to manually unroll `find` implementation as in the case of `map`?

---

<div class="post-metadata">

**Author:** ![K\_N](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/k_n/32/2793_2.png) [@K\_N](https://discuss.ocaml.org/u/K_N)\
**Post date:** [January 27, 2023, 12:45pm UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/4 "2023-01-27T12:45:11Z")

</div>

Hi,  
I think it could make sense. However, `List.map` is used to create a new fresh collection. On the other hand, `List.find` is used to return a single element, so maybe there are other directions to explore e.g. using an auxiliary data-structure where look-up for your particular kind of predicates is fast. This comes with its own problems of course like maintenance of indexes etc…).

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [January 27, 2023, 12:48pm UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/5 "2023-01-27T12:48:08Z")

</div>

If `List.find` dominates the execution time, it might be worth considering a better data structure than list.

And just to reiterate what @nojb said, `List.map` was not unrolled to make it faster. It was unrolled so that it did not become slower due to the tail-call-modulo-cons transformation.

---

<div class="post-metadata">

**Author:** ![BikalGurung](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bikalgurung/32/5105_2.png) [@BikalGurung](https://discuss.ocaml.org/u/BikalGurung)\
**Post date:** [January 27, 2023, 1:21pm UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/6 "2023-01-27T13:21:13Z")

</div>

> If `List.find` dominates the execution time, it might be worth considering a better data structure than list.

Yes, I did consider AVL data structure like map, but didn’t like the insert performance (O(log n)), so settled for list since List.add is 0(1). `find` is a secondary consideration to `add` in my use case. However, I was wondering if re-implementing find using loop unrolling would make `find` use case also not too bad i.e. 0(n/2) or 0(n/3) rather than O(n).

> [@silene](#):
>
> And just to reiterate what @nojb said, `List.map` was not unrolled to make it faster. It was unrolled so that it did not become slower due to the tail-call-modulo-cons transformation.

Interesting. I am not too sure how loop unrolling helps tail-call-modulo-cons transformation. `find` is tail-recursive, shouldn’t loop unrolling make it a tad faster than not unrolling it?

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [January 27, 2023, 1:34pm UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/7 "2023-01-27T13:34:16Z")

</div>

> [@BikalGurung](#):
>
> 0(n/2) or 0(n/3) rather than O(n).

O(n/2) and O(n/3) are still O(n), by definition of O.

> [@BikalGurung](#):
>
> I am not too sure how loop unrolling helps tail-call-modulo-cons transformation.

It does not help the transformation itself. It just helps with performance. A modulo-cons tail call is slow (slower than a tail call or a standard call); by unrolling the loop, you do only half of them.

> [@BikalGurung](#):
>
> shouldn’t loop unrolling make it a tad faster than not unrolling it?

Sure. But you still do the same amount of (predicted) branches. So, the gain might be negligible if the test function itself is not inlined. (Moreover, unrolling might actually block inlining, since the function now needs to be inlined twice.)

---

<div class="post-metadata">

**Author:** ![BikalGurung](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bikalgurung/32/5105_2.png) [@BikalGurung](https://discuss.ocaml.org/u/BikalGurung)\
**Post date:** [January 28, 2023, 11:02am UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/8 "2023-01-28T11:02:44Z")

</div>

> O(n/2) and O(n/3) are still O(n), by definition of O.

I should have clarified. I meant to say `n` loops since we are discussing loop unrolling.

> A modulo-cons tail call is slow (slower than a tail call or a standard call); by unrolling the loop, you do only half of them.

So halving the number of times you do loop does positively affect performance, right?

Since TMC is slower than a recursive call, wouldn’t it make sense to make `List.map` a tail recursive one? What actually is the benefit of TMC? Is it mostly a list allocation per call compared to a tail-recursive call?

---

<div class="post-metadata">

**Author:** ![K\_N](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/k_n/32/2793_2.png) [@K\_N](https://discuss.ocaml.org/u/K_N)\
**Post date:** [January 28, 2023, 12:30pm UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/9 "2023-01-28T12:30:41Z")

</div>

The benefit of TRMC is that your function is tail recursive, so won’t blow-up the stack for large lists. Doing a tail-recursive map _which retains the performances of the non-tail-recursive one_ is quite the challenge (the [following thread](https://discuss.ocaml.org/t/a-new-list-map-that-is-both-stack-safe-and-fast/865) has all the info). A very crude summary:

- Usual `List.map` : fast calls (which can further be unrolled) but not tail recursive, you may blow up the stack for long lists.
- Simple tail-recursive `List.map` by doing reverse at the end: the cost of reversing hurts quite a bit in practice and makes this non competitive for medium sized lists.
- Unsafe tail-recursive `List.map` by using `Obj.magic` and casting a mutable list that is allocated and modified in place. This relies on assumptions on unsafe features, which may be invalidated if you change backend or runtime (flambda, multicore,…).
- Clever safe tail-recursive `List.map` (as explained in the linked discussion). Very clever, needs to be hand-tuned (to recover the performances of non tail-rec) and the code is quite complex which becomes a maintenance problem, especially if you want several versions hand tuned for several architectures.

TRMC, to simplify, translates the simple natural `List.map` (and other similar functions) to the version that creates a mutable structure. But the translation is done by the compiler. There is still a maintenance burden (the TRMC transform itself within the compiler) but it’s more general so the cost is deemed worth it (since now you don’t have to maintain a gazillion of unsafe tail recursive functions doing `Obj.magic` all over the place for `map`, `concat`, etc…).

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [January 28, 2023, 2:58pm UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/10 "2023-01-28T14:58:17Z")

</div>

> [@BikalGurung](#):
>
> So halving the number of times you do loop does positively affect performance, right?

You missed the point. It is not the tail call that is costly. It is the “modulo cons” part.

In a nutshell, a `map` function over lists looks as follows:

```ocaml
let rec map f (h::t) = (f h) :: (map f t)

```

First, there is a recursive call to `map` then a memory block is initialized with the result of `map`. Obviously, this function is not tail recursive, since the block is (allocated and) initialized after the call.

The tail recursive version is as follows, assuming a variant of OCaml where you can mutate things arbitrarily:

```ocaml
let rec map_trmc f (h::t) (_::t') =
  let res = f h :: dummy in
  t' <- res;
  map_trmc f t res

```

Now the function is tail recursive. The compiler performs this transformation whenever you use the attribute `[@tail_mod_cons]`. But notice a few things. First, the new function now receives one more argument. But more importantly, while the assignment `t' <- res` might look like a cheap memory write, it is actually a costly call to the function `caml_initialize`.

To summarize, the purpose of unrolling `List.map` is not to halve the number of recursive calls. It is to halve the number of calls to `caml_initialize`.

And in case it was not clear, neither the non-tail-recursive `List.map` nor`List.find` need to call `caml_initialize`.

---

<div class="post-metadata">

**Author:** ![gasche](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gasche/32/4_2.png) [@gasche](https://discuss.ocaml.org/u/gasche)\
**Post date:** [January 28, 2023, 3:49pm UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/11 "2023-01-28T15:49:10Z")

</div>

I’m not sure the cost of calling `caml_initialize` is so high, it’s a “noalloc” call and the code is pretty simple (an assignment and a well-predicted branch). It is probably sensibly less costly than the indirect call to `f` itself (even without taking the computation time of `f` into account, just the caller-side cost of organizing the call).

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [January 28, 2023, 4:57pm UTC](https://discuss.ocaml.org/t/stdlib-list-loop-unrolling/11262/12 "2023-01-28T16:57:43Z")

</div>

Let us try it:

```ocaml
let[@tail_mod_cons] rec map1 f = function
  | [] -> []
  | a::l ->
      let r = f a in
      r::map1 f l

let () =
  let l = List.init 1000 (fun i -> i) in
  for j = 0 to 100000 do
    ignore (map1 (fun v -> v + 1) l);
  done

```

With a minor heap of 1G words (just to avoid any garbage collection), `perf` reports that 20% of the time is spent in `caml_initialize`.

By the way, even perfectly predicted branches have to be considered with a grain of salt. Once the branch buffer is full (e.g., 48 entries on recent x86 processors), the processor will just stop. Calling `caml_initialize` incurs three speculative branches per loop iteration. By comparison, the call to the anonymous function incurs only two speculative branches. And `map1` has two more. In other words, `caml_initialize` accounts for 40% of all the speculative branches of this code.