Inside the mind of the inliner

Inside the mind of the inliner

[Yaron Minsky]

[-- Attachment #1: Type: text/plain, Size: 1703 bytes --]

I've been doing some experiments with the OCaml inliner, and have
walked away from the process very confused.  It seems like inlining
can be prevented by very simple changes to the code of a function.
The main surprise for me is that adding a quite trivial allocation of
a list or a string literal defeats the inliner.

Does anyone have a better understanding of what's going on here?  I
feel like my intuition for this stuff is terrible.

I checked inlining using the following command line:

  ocamlopt -S -inline 10000 z.ml ; egrep 'call.*camlZ__f' z.s

And here are the different variants of z.ml I tried.

(* Simple arithmetic.  f is inlined *)
let f x = x + x
let g x = f x + f x

(* Add in allocation of a list, not inlined *)
let f x = ignore [1]; x + x
let g x = f x + f x

(* allocate a string, not inlined *)
let f x = ignore "foo"; x + x
let g x = f x + f x

(* reference to the empty list, inlined *)
let f x = ignore []; x + x
let g x = f x + f x

(* call a function that iterates over a list, inlined *)
let list = [1;2;3]
let plus x y = x + y
let f x = x * List.fold_left plus 0 list
let g x = f x + f x

(* Call a function that includes an infix operator in prefix form,
   not inlined. *)
let list = [1;2;3]
let f x = x * List.fold_left (+) 0 list
let g x = f x + f x

(* Allocate the list in the function, not inlined *)
let plus x y = x + y
let f x = x * List.fold_left plus 0 [1;2;3]
let g x = f x + f x

(* call a function to allocate your list, inlined *)
let plus x y = x + y
let create_list x = x :: x + 1 :: x + 2 :: []
let f x = x * List.fold_left plus 0 (create_list 1)
let g x = f x + f x

I've tried these experiments with ocaml 3.10.1 and 3.11.1, with similar
results.

y

[-- Attachment #2: Type: text/html, Size: 5509 bytes --]

Re: [Caml-list] Inside the mind of the inliner

[Xavier Leroy]

> I've been doing some experiments with the OCaml inliner, and have
> walked away from the process very confused.  It seems like inlining
> can be prevented by very simple changes to the code of a function.
> The main surprise for me is that adding a quite trivial allocation of
> a list or a string literal defeats the inliner.
> 
> Does anyone have a better understanding of what's going on here?  I
> feel like my intuition for this stuff is terrible.

The algorithm is very simple: a function is inlinable if

1- its code size (approximate) is below a certain threshold
    (governed by the -inline option)
2- and its body doesn't contain a function definition
    (fun x -> ..., let rec f x = ..., etc) nor a structured constant
    (string literal, [1;2;3], etc).

The reason for 2- is that the inliner is too stupid to inline a
function without duplicating the function definitions/structured
constants contained within.  Such a duplication can be very wasteful
in code and static data size.  (Cue the replies "but not if small
enough!" in 3...2...1...now.)

For your specific examples:

> (* Add in allocation of a list, not inlined *)
> let f x = ignore [1]; x + x
> let g x = f x + f x

"[1]" is not a run-time allocation: its a structured constant, built
at compile-time.  Hence you run into case 2 above.

> (* allocate a string, not inlined *)
> let f x = ignore "foo"; x + x
> let g x = f x + f x

Likewise (no allocation, but case 2).

> (* Call a function that includes an infix operator in prefix form,
>    not inlined. *)
> let list = [1;2;3]
> let f x = x * List.fold_left (+) 0 list
> let g x = f x + f x

Because (+) is really fun x y -> x + y, therefore case 2 again.

- Xavier Leroy