# Optimize a simple piece of code

**URL:** <https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421>\
**Category:** Community\
**Created:** [February 26, 2022, 11:12am UTC](https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421 "2022-02-26T11:12:08Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Butanium](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/butanium/32/2930_2.png) [@Butanium](https://discuss.ocaml.org/u/Butanium)\
**Post date:** [February 26, 2022, 11:12am UTC](https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421/1 "2022-02-26T11:12:08Z")

</div>

Hi,

I have this piece of code that I already tried to optimize

```ocaml
and loop2 i j =
    if
      (if !last_time_check > check_time then (
       last_time_check := 0;
       true)
      else (
        incr last_time_check;
        false))
      && max_time <> infinity
      && Unix.gettimeofday () -. start_time > max_time
    then raise Timed_Out;
    j >= bound - max (2 * partial) (1 - i)
    || (let diff =
          adj_matrix.(path.(i)).(path.(j))
          + adj_matrix.(path.(i + 1)).(path.(bounded (j + 1)))
          - adj_matrix.(path.(i)).(path.(i + 1))
          - adj_matrix.(path.(j)).(path.(bounded (j + 1)))
        in
        if diff < 0 then (
          invertPath i j path;
          if debug then Printf.printf "\ninverted %d and %d, diff : %d" i j diff;
          false)
        else true)
       && loop2 i (j + 1)
  in

```

I already used the `-unsafe` flag which made me win some time, but now I don’t know if there is anything else I can do. I’m also using a switch with the lambda optimizer but with no flag appart from `-unsafe`

Here is my `perf` report :

 ![image](https://us1.discourse-cdn.com/flex020/uploads/ocaml/original/2X/4/461ff2b0ff77041130dbcfd1fc653f43fb843ecd.png)

Is there something I can do to speed up my code ?

Thanks for your answers,

Clément

PS : full code available [here](https://github.com/Butanium/monte-carlo-tree-search-TSP/blob/960f5b3e37b94e586636bf99f5cc75fe8fe3cb89/tsp_solvers/Two_Opt.ml#L40)

---

<div class="post-metadata">

**Author:** ![vlaviron](https://avatars.discourse-cdn.com/v4/letter/v/ec9cab/32.png) [@vlaviron](https://discuss.ocaml.org/u/vlaviron)\
**Post date:** [February 26, 2022, 2:06pm UTC](https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421/2 "2022-02-26T14:06:28Z")

</div>

The `max` function appears quite high in your profile. It’s one of these annoying little details: the polymorphic comparison functions (`<`, `=` and so on) can be specialised when used on base types like `int`, and compiled efficiently, but `max` and `min` are regular OCaml functions, so they don’t get specialised.

I remember some recent work in the compiler to handle this case better, but I don’t remember if it made it to a release version. For now, you can work around the issue by redefining your own `max` function with stricter type constraints:

```ocaml
let max (x : int) (y : int) = if x < y then y else x

```

From the profile you’ve posted, it looks that this could save you almost half of the time.

EDIT: If you’re using OCaml 4.13 or later, you can use `Int.max` directly.

---

<div class="post-metadata">

**Author:** ![art-w](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/art-w/32/4728_2.png) [@art-w](https://discuss.ocaml.org/u/art-w)\
**Post date:** [February 26, 2022, 3:05pm UTC](https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421/3 "2022-02-26T15:05:07Z")

</div>

You could do with less calls to `Unix.gettimeofday` and precompute some constants like `adj_matrix.(path.(i)).(path.(i + 1))`, but in reality your code is slow because of the part you didn’t quote:

```ocaml
let rec rec_while i =
  (i < max_iter || max_iter < 0)
  && (not (loop1 lower_bound))
  && rec_while (i + 1)
and loop1 i = i >= bound - 3 - partial || (loop2 i (i + 2) && loop1 (i + 1))

```

These two loops have a huge impact on the complexity `O(max_iter * N²)` !

- Rather than aborting the search as soon as you find a shortcut, and restarting from scratch, you can keep going: if all the optimizations are at the end of the path, this skips re-iterating so much on the start of the path.

- But you’ll see even better gain if you invest in some space partitionning for your points: It’s not really useful to check every pair `(i,j)` since most are too far apart to yield any shortcut!

---

<div class="post-metadata">

**Author:** ![Butanium](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/butanium/32/2930_2.png) [@Butanium](https://discuss.ocaml.org/u/Butanium)\
**Post date:** [February 26, 2022, 4:01pm UTC](https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421/4 "2022-02-26T16:01:22Z")

</div>

Thanks for your advice, it almost doubled the amount of simulation done, I have this perf graph now :

 ![image](https://us1.discourse-cdn.com/flex020/uploads/ocaml/original/2X/9/94e377d472d1c8cb9c4c31ccf825a46af0a91f54.png)

I’ll try to reimplement my function as @art-w suggested, seeing if it leads to something even faster

---

<div class="post-metadata">

**Author:** ![Butanium](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/butanium/32/2930_2.png) [@Butanium](https://discuss.ocaml.org/u/Butanium)\
**Post date:** [February 26, 2022, 4:08pm UTC](https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421/5 "2022-02-26T16:08:00Z")

</div>

What do you mean by

> [@art-w](#):
>
> precompute some constants like `adj_matrix.(path.(i)).(path.(i + 1))`

?

---

<div class="post-metadata">

**Author:** ![Butanium](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/butanium/32/2930_2.png) [@Butanium](https://discuss.ocaml.org/u/Butanium)\
**Post date:** [February 26, 2022, 4:18pm UTC](https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421/6 "2022-02-26T16:18:41Z")

</div>

@vlaviron by the way I’m using a Flambda switch, isn’t it supposed to optimize things like that ?

 ![image](https://us1.discourse-cdn.com/flex020/uploads/ocaml/original/2X/0/0e8d7fc842d1e2c363a1d284f43d0a1122aa8f24.png)

---

<div class="post-metadata">

**Author:** ![art-w](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/art-w/32/4728_2.png) [@art-w](https://discuss.ocaml.org/u/art-w)\
**Post date:** [February 26, 2022, 5:08pm UTC](https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421/7 "2022-02-26T17:08:33Z")

</div>

The argument `i` of the function `loop2` doesn’t change during its recursion, so you could precompute the array accesses that depend on `i`:

```ocaml
and loop2 i j =
  let path_i = path.(i) in
  let path_i1 = path.(i + 1) in
  let cost_edge_i = adj_matrix.(path_i).(path_i1) in
  let rec inner_loop2 j =
     ... || (... && inner_loop2 (j + 1))
  in
  inner_loop2 j

```

It’s unlikely to yield a significant improvement though, you should really focus on performing less “useless” iterations.

---

<div class="post-metadata">

**Author:** ![vlaviron](https://avatars.discourse-cdn.com/v4/letter/v/ec9cab/32.png) [@vlaviron](https://discuss.ocaml.org/u/vlaviron)\
**Post date:** [February 26, 2022, 6:23pm UTC](https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421/8 "2022-02-26T18:23:03Z")

</div>

> [@Butanium](#):
>
> by the way I’m using a Flambda switch, isn’t it supposed to optimize things like that ?

Unfortunately not. Currently the choice of which implementation to use for the comparison function is done just after type-checking. The rest of the program then sees whatever code the type-checker choosed to use, and in the case of a generic comparison that’s just a call to a C function, which are opaque to Flambda.

We do have an experimental Flambda 2 branch where we have added the ability to specialise these generic comparison functions after inlining, but it’s not released yet.

---

<div class="post-metadata">

**Author:** ![Butanium](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/butanium/32/2930_2.png) [@Butanium](https://discuss.ocaml.org/u/Butanium)\
**Post date:** [February 26, 2022, 9:41pm UTC](https://discuss.ocaml.org/t/optimize-a-simple-piece-of-code/9421/9 "2022-02-26T21:41:37Z")

</div>

Ok so now my code is… 15 times faster with `N = 100`. Thanks a lot for your advice, I didn’t realize I was doing a lot of useless calculation.

 ![image](https://us1.discourse-cdn.com/flex020/uploads/ocaml/original/2X/e/ee915c53e45cb1cc23bf121f61d247542e2dfbad.jpeg)  
Here is the associated perf graph and the new code (I committed the changes so full code will be in the same file as `opt_fast` function :

```ocaml
let opt_fast ?(debug = false) ?(partial_path = false) ?(max_iter = -1)
    ?(max_time = infinity) ?(lower_bound = 0) ?(upper_bound = -1)
    ?(check_time = 1000) adj_matrix path =
  (* If [partial_path] is set to true the algorithm won't try to optimize the edge between the end of the path and the beginning.
     It's useful if you want to optimize the part of a path *)
  let bound =
    if upper_bound < 0 then Array.length path
    else min upper_bound @@ Array.length path
  in
  let bounded i = if i >= bound then i - bound else i in
  let partial = if partial_path then 1 else 0 in
  let last_time_check = ref 0 in
  let start_time = if max_time = infinity then 0. else Unix.gettimeofday () in

  (* SI max_time = infinity ne pas appeler Unix.gettimeofday () *)
  let rec rec_while i =
    (i < max_iter || max_iter < 0)
    && (not (loop1 lower_bound true))
    && rec_while (i + 1)
  and loop1 i is_opt =
    if i >= bound - 3 - partial then is_opt
    else loop1 (i + 1) (loop2 i (i + 2) is_opt)
  and loop2 i j is_opt =
    if
      max_time <> infinity
      && (if !last_time_check > check_time then (
          last_time_check := 0;
          true)
         else (
           incr last_time_check;
           false))
      && Unix.gettimeofday () -. start_time > max_time
    then raise Timed_Out;
    if j >= bound - max (2 * partial) (1 - i) then is_opt
    else
      let diff =
        adj_matrix.(path.(i)).(path.(j))
        + adj_matrix.(path.(i + 1)).(path.(bounded (j + 1)))
        - adj_matrix.(path.(i)).(path.(i + 1))
        - adj_matrix.(path.(j)).(path.(bounded (j + 1)))
      in
      if diff < 0 then (
        invertPath i j path;
        if debug then Printf.printf "\ninverted %d and %d, diff : %d" i j diff);
      loop2 i (j + 1) (is_opt && diff >= 0)
  in

  try
    let is_opt = loop1 lower_bound true in
    (if not is_opt then
     let _ = rec_while 1 in
     ());
    is_opt
  with Timed_Out -> false

```