Beginner question on code style in Base

Learning
1

I am reading the code in Base. https://github.com/janestreet/base/blob/master/src/array.ml has

  module Insertion_sort : Sort = struct
    let sort arr ~compare ~left ~right =
      (* loop invariant:
         [arr] is sorted from [left] to [pos - 1], inclusive *)
      for pos = left + 1 to right do
        (* loop invariants:
           1.  the subarray arr[left .. i-1] is sorted
           2.  the subarray arr[i+1 .. pos] is sorted and contains only elements > v
           3.  arr[i] may be thought of as containing v

           Note that this does not allocate a closure, but is left in the for
           loop for the readability of the documentation. *)
        let rec loop arr ~left ~compare i v =
          let i_next = i - 1 in
          if i_next >= left && compare (get arr i_next) v > 0
          then (
            set arr i (get arr i_next);
            loop arr ~left ~compare i_next v)
          else i
        in
        let v = get arr pos in
        let final_pos = loop arr ~left ~compare pos v in
        set arr final_pos v
      done
    ;;
  end

Questions:

  1. What does the comment “is left in the loop” refer to?
  2. What is the advantage to having let rec loop arr ~left ~compare i v when arr, left, compare, and v are constant? That is, why is the loop not simply let rec loop i?
2

I would guess it refers to the fact that loop is defined inside the for loop, rather than outside, even though in principle it could have been.

It’s for performance, I think. Writing it the second way would mean allocating a closure for the values of the variables that aren’t passed as arguments. Besides the direct cost of allocating, allocation gives the garbage collector a chance to run.

3

That’s exactly the idea. We are generally very careful about performances for such core functions.

That’s also why we are pushing for flambda at Jane Street: so that we can write nice simple code and let the compiler do all these optimisations for us :slight_smile: