# How to speed up this function?

**URL:** <https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286>\
**Category:** Learning\
**Created:** [August 10, 2022, 1:46am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286 "2022-08-10T01:46:17Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Mng12345](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/mng12345/32/3682_2.png) [@Mng12345](https://discuss.ocaml.org/u/Mng12345)\
**Post date:** [August 10, 2022, 1:46am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/1 "2022-08-10T01:46:17Z")

</div>

I have written this function in three versions with ocaml, rescript and rust. The time spend in js and rust are about 15s, but 35+s in ocaml. I know this is because `float` is boxed in ocaml, do we have a way to fix it?

In ocaml

```ocaml
let rec fib n result = match n with 0. -> result | n -> fib (n -. 1.) (n +. result)
let start_time = Sys.time () in
let result = fib 10000000000. 0. in
let end_time = Sys.time () in
"time use: "
^ (end_time -. start_time |> string_of_float)
^ "; result: "
^ (result |> string_of_float)
|> print_endline

```

In rescript.

```nohighlight
let rec fib = (n, result) => {
  switch n {
  | 0. => result
  | n => fib(n -. 1., result +. n)
  }
}

let timeStart = Js.Date.now()
fib(10000000000., 0.)->Js.log2(`fib: `, _)
let tiemEnd = Js.Date.now()
((tiemEnd -. timeStart) /. 1000.)->Js.log2(`time use: `, _)

```

In rust

```nohighlight
use std::time;

fn fib(n: f64, result: f64) -> f64 {
    if n == 0. {
        result
    } else {
        fib(n - 1., result + n)
    }
}

fn main() {
    let start_time = time::SystemTime::now();
    let result = fib(10000000000., 0.);
    let end_time = time::SystemTime::now();
    let time_use = end_time.duration_since(start_time).unwrap().as_secs();
    println!("time use: {time_use}, result: {result}");
}

```

---

<div class="post-metadata">

**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\
**Post date:** [August 10, 2022, 2:12am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/2 "2022-08-10T02:12:14Z")

</div>

I tried this:

```ocaml
let n = 10000000000.

let rec fib1 n result = match n with
  | 0. -> result
  | n -> fib1 (n -. 1.) (n +. result)

let fib2 n =
  let n = ref n in
  let res = ref 0. in
  while !n > 0. do
    res := !res +. !n;
    n := !n -. 1.;
  done;
  !res

let timeit f =
  let start = Unix.gettimeofday() in
  let res = f () in
  let t = Unix.gettimeofday() -. start in
  t, res

let () =
  let t1, r1 = timeit (fun () -> fib1 n 0.) in
  Printf.printf "fib1: %f in %.4fs\n%!" r1 t1;
  let t2, r2 = timeit (fun () -> fib2 n) in
  Printf.printf "fib2: %f in %.4fs\n%!" r2 t2;
  ()

```

and it’s much faster (1/4th of the time):

```auto
fib1: 50000000009992404992.000000 in 43.7277s
fib2: 50000000009992404992.000000 in 11.6772s

```

I think it’s indeed due to the fact that OCaml can unbox local floats but might have more difficulty doing that when passing the floats to a recursive function.

---

<div class="post-metadata">

**Author:** ![pdonadeo](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/pdonadeo/32/6309_2.png) [@pdonadeo](https://discuss.ocaml.org/u/pdonadeo)\
**Post date:** [August 10, 2022, 8:15am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/3 "2022-08-10T08:15:32Z")

</div>

By the way, why using floats? Using integers is much faster and for `n > 134217727` the result is mathematically wrong using floats.

---

<div class="post-metadata">

**Author:** ![fccm](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/fccm/32/1587_2.png) [@fccm](https://discuss.ocaml.org/u/fccm)\
**Post date:** [August 10, 2022, 8:27am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/4 "2022-08-10T08:27:37Z")

</div>

> [@pdonadeo](#):
>
> By the way, why using floats? Using integers is much faster and for `n > 134217727` the result is mathematically wrong using floats.

The real function that this person tries to optimise is probably using floats, since this person talks about floats that are boxed in ocaml. This is probably just a shorter example here.

---

<div class="post-metadata">

**Author:** ![fccm](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/fccm/32/1587_2.png) [@fccm](https://discuss.ocaml.org/u/fccm)\
**Post date:** [August 10, 2022, 8:34am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/5 "2022-08-10T08:34:28Z")

</div>

If your real function that you try to get faster is more complex than just a fib, you can also use rescript to see how to rewrite it with a `while` loop (as c-cube said):

```auto
$ cat fib.ml
let rec fib n result =
  match n with
  | 0. -> result
  | n -> fib (n -. 1.) (n +. result)

$ bsc fib.ml
// Generated by ReScript, PLEASE EDIT WITH CARE
'use strict';

function fib(_n, _result) {
  while(true) {
    var result = _result;
    var n = _n;
    if (n === 0) {
      return result;
    }
    _result = n + result;
    _n = n - 1;
    continue ;
  };
}

exports.fib = fib;
/* No side effect */

```

Notice that you can give the plain ocaml syntax to the rescript compiler, you don’t need to rewrite it with the rescript syntax.

---

<div class="post-metadata">

**Author:** ![Mng12345](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/mng12345/32/3682_2.png) [@Mng12345](https://discuss.ocaml.org/u/Mng12345)\
**Post date:** [August 10, 2022, 8:43am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/6 "2022-08-10T08:43:55Z")

</div>

> [@fccm](#):
>
> c-cube

Thanks, i actually want to write it in ocaml, just tested it in js and rust. And, can we unbox the float manually in ocaml? I am a new bee in ocaml, thanks again.

---

<div class="post-metadata">

**Author:** ![fccm](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/fccm/32/1587_2.png) [@fccm](https://discuss.ocaml.org/u/fccm)\
**Post date:** [August 10, 2022, 9:07am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/7 "2022-08-10T09:07:22Z")

</div>

> [@Mng12345](#):
>
> Thanks, i actually want to write it in ocaml, just tested it in js and rust. And, can we unbox the float manually in ocaml? I am a new bee in ocaml, thanks again.

Yes, I understood, but as c-cube said, a while loop will be faster. If you want to rewrite a loop made with a `let rec` function into a `while` loop, you can see how the rescript compiler optimise it, and rewrite it in plain ocaml to follow c-cube’s suggestion. (And this is something that you can do giving plain ocaml syntax to the rescript compiler, you don’t have to rewrite it with rescript syntax.)

---

<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:** [August 10, 2022, 4:57pm UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/8 "2022-08-10T16:57:20Z")

</div>

> And, can we unbox the float manually in ocaml?

short version: Not currently, no. It may be in the future.

long version: Some people have worked on making this possible (more precisely: on explicitly asking for a function parameter to take an _unboxed_ float parameter, which would do the trick here), but there is not a lot of people for which this is a critical need (it’s often not too hard to rewrite without needing this) and they haven’t pushed very hard. In case people are curious, I wrote [a summary](https://github.com/ocaml/ocaml/issues/5894#issuecomment-826686147) of compiler PRs about this last year.

---

<div class="post-metadata">

**Author:** ![dbuenzli](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/dbuenzli/32/18_2.png) [@dbuenzli](https://discuss.ocaml.org/u/dbuenzli)\
**Post date:** [August 10, 2022, 5:56pm UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/9 "2022-08-10T17:56:09Z")

</div>

> [@gasche](#):
>
> short version: Not currently, no. It may be in the future.

Putting aside the more general occurence (which is known to me, floats gets boxed when they cross functions) I’m still a bit surprised by the result here.

My intuition would have been: this function is going to be turned into a loop by the compiler (which an `(fib1[@tailcall])` annotation can confirm) and that means the floats are going to be locally unboxed.

But as far as my rusty assembly goes that doesn’t seem to be [the case](https://godbolt.org/z/E6sszhssf) (at least on 4.12).

---

<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:** [August 10, 2022, 8:16pm UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/10 "2022-08-10T20:16:40Z")

</div>

> [@dbuenzli](#):
>
> My intuition would have been: this function is going to be turned into a loop by the compiler (which an `(fib1[@tailcall])` annotation can confirm) and that means the floats are going to be locally unboxed.

A tail call is not a loop; it is a function call. No optimization will remove this call until the very end of the compilation pipeline. In particular, the compiler has to respect the calling convention of the recursive function, because it will end up generating a jump to its entry point (modulo some stack adjustment). In other words, this looks a lot like a peephole optimization that would replace the assembly sequence `call foo; return` by the single opcode `branch foo`.

---

<div class="post-metadata">

**Author:** ![dbuenzli](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/dbuenzli/32/18_2.png) [@dbuenzli](https://discuss.ocaml.org/u/dbuenzli)\
**Post date:** [August 10, 2022, 8:30pm UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/11 "2022-08-10T20:30:34Z")

</div>

Thanks for the explanation. It seems I have quite a bunch of recursive functions to rewrite as loops now that you corrected my wrong understanding…

---

<div class="post-metadata">

**Author:** ![Mng12345](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/mng12345/32/3682_2.png) [@Mng12345](https://discuss.ocaml.org/u/Mng12345)\
**Post date:** [August 11, 2022, 12:08am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/12 "2022-08-11T00:08:10Z")

</div>

Hmm，i also tested the int version of this function, the time cost of ocaml, js and rust were both about 10s. If the tailcall is not optimized into loop in ocaml, why it is so fast?

---

<div class="post-metadata">

**Author:** ![dbuenzli](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/dbuenzli/32/18_2.png) [@dbuenzli](https://discuss.ocaml.org/u/dbuenzli)\
**Post date:** [August 11, 2022, 12:19am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/13 "2022-08-11T00:19:44Z")

</div>

Because `int` values in OCaml are always unboxed (that’s the reason why their size is your architecture’s word size minus one bit, you need a bit so that the gc can distinguish them from pointers).

Also as you can see in the link I provided, tail calls do get eventually optimized into a loop, however as @silene mentioned when it does so it’s too late for the local unboxed float optimizations to quick in.

---

<div class="post-metadata">

**Author:** ![Jon\_Harrop](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/jon_harrop/32/2015_2.png) [@Jon\_Harrop](https://discuss.ocaml.org/u/Jon_Harrop)\
**Post date:** [August 11, 2022, 3:40am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/14 "2022-08-11T03:40:24Z")

</div>

I’d caution selection bias here. The OCaml community consists of people who tolerate OCaml’s shortcomings including this one.

Try going to another language community and suggesting they box individual floats and see how they respond! 😀

If there is genuine interest in fostering adoption it would be good to quantify what proportion of developers in general would want or expect such features. I suspect a few features would make a huge difference to many people who do not currently use OCaml.

---

<div class="post-metadata">

**Author:** ![Chet\_Murthy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/chet_murthy/32/1501_2.png) [@Chet\_Murthy](https://discuss.ocaml.org/u/Chet_Murthy)\
**Post date:** [August 11, 2022, 4:13am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/15 "2022-08-11T04:13:44Z")

</div>

[just asking here]  
I remember when I brought up Rust iterators, one response was “we can do the same thing with Seq and aggressive flambda, etc, etc, etc”. But this seems to suggest that if I write a bunch of code with unboxed floats that uses Seq and such, maybe lots of lambda-abstractions, the code might not get flattened-down into loops soon enough for unboxing to happen ?

Which would argue that if I care about performance, I’d want my iterator “tower” to consist in operations that didn’t need significant analysis to be squashed down into loops.

Just asking.

---

<div class="post-metadata">

**Author:** ![bluddy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bluddy/32/104_2.png) [@bluddy](https://discuss.ocaml.org/u/bluddy)\
**Post date:** [August 11, 2022, 6:18am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/16 "2022-08-11T06:18:13Z")

</div>

I would love to have an ability to vote on areas where the community would like the core devs to focus on next. In my mind, this is a very big issue that needs to be addressed, as it means that if you happen to work with floats, you need to use completely different coding paradigms (non functional ones) to get reasonable performance.

---

<div class="post-metadata">

**Author:** ![Mng12345](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/mng12345/32/3682_2.png) [@Mng12345](https://discuss.ocaml.org/u/Mng12345)\
**Post date:** [August 11, 2022, 6:28am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/17 "2022-08-11T06:28:38Z")

</div>

I choose ocaml for the performance, but it seems it’s not better than js(rescript) in some places.

---

<div class="post-metadata">

**Author:** ![bluddy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bluddy/32/104_2.png) [@bluddy](https://discuss.ocaml.org/u/bluddy)\
**Post date:** [August 11, 2022, 6:59am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/18 "2022-08-11T06:59:26Z")

</div>

The choices made when designing the language were very much for specific aspects such as symbolic programming, privileging integers and reducing allocation as much as possible. The downside is that other aspects, which are very common in general programming, such as floating point math, are second class citizens.

---

<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:** [August 11, 2022, 9:26am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/19 "2022-08-11T09:26:16Z")

</div>

The situation is not that simple. There are multiple ways of encoding datatypes and it is not that obvious that some other encoding that favor floating-point numbers would actually cripple symbolic programming. For instance, several javascript engines rely on NaN-boxing, which makes it possible to unbox both 64-bit floating-point numbers and 32-bit integers (while still keeping an OCaml-like garbage collector). If you were to ask symbolic programmers which of 63-bit integers (but no 64-bit integers) or floating-point numbers should be unboxed, what would be the consensus?

---

<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:** [August 11, 2022, 9:51am UTC](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286/20 "2022-08-11T09:51:22Z")

</div>

I think that the good long-term approach to those issues is to add expressivity in the source language to talk about unboxed floats and other “value types”, which is a topic that @lpw25, @stedolan and Antal Spector-Zabusky are working on. It will not magically solve all float-performance issues, but it will give a clear, modular language to express solutions, manually-written by the user (requires some expertise) or automated by the optimizer. I don’t know if/when their work will be proposed for upstreaming, but I have come to accept that these things take time, especially given that many of the people contributing their work on OCaml are working on many things at once.

(I think that we should keep growing the set of people contributing to the language and implementation, rather than trying to redirect the workforce of people already contributing.)

[Next page](https://discuss.ocaml.org/t/how-to-speed-up-this-function/10286.md?page=2)