Function Inlining

Function Inlining

[Jonathan Bryant]

What is the deal with the -inline option for ocamlopt?  I've turned it
off (0), turned it on (1), turned it up (10 - 100) and gone crazy
(10000) with it.  Yet my executable says exactly the same size and runs
in exactly the same time.  I know inlining functions leads to code
bloating and (usually) performance increases, so I'm confused.  Is it
not working?  I have both large and small functions so it's not that
they are all getting inlined any time it is on.  Besides turning it off
makes no difference.

What's going on here?

-- 
+=*===================_OX=+
| Jonathan Bryant       |^|
| jtbryant@valdosta.edu | |
| AIM: JonBoy3182       | |
| (229) 834-4400        | |
+=========================+

"If the colleges were better, if they really had it, you would need to
get the police at the gates to keep order in the inrushing multitude.
See in college how we thwart the natural love of learning by leaving the
natural method of teaching what each wishes to learn, and insisting that
you shall learn what you have no taste or capacity for. The college,
which should be a place of delightful labour, is made odious and
unhealthy, and the young men are tempted to frivolous amusements to
rally their jaded spirits. I would have the studies elective.
Scholarship is to be created not by compulsion, but by awakening a pure
interest in knowledge. The wise instructor accomplishes this by opening
to his pupils precisely the attractions the study has for himself. The
marking is a system for schools, not for the college; for boys, not for
men; and it is an ungracious work to put on a professor."
-- Ralph Waldo Emerson

Re: [Caml-list] Function Inlining

[Ville-Pertti Keinonen]

Jonathan Bryant wrote:
> What is the deal with the -inline option for ocamlopt?  I've turned it
> off (0), turned it on (1), turned it up (10 - 100) and gone crazy
> (10000) with it.  Yet my executable says exactly the same size and runs
> in exactly the same time.  I know inlining functions leads to code
> bloating and (usually) performance increases, so I'm confused.  Is it
> not working?  I have both large and small functions so it's not that
> they are all getting inlined any time it is on.  Besides turning it off
> makes no difference.

> What's going on here?

You're probably running into restrictions other than size that OCaml has 
on function inlining, such as function definitions inside the function, 
structured constants and let rec.

Getting rid of these restrictions could potentially improve OCaml code 
generation considerably, but as far as I can tell, that would require 
some additional features in the code generation such as sharing 
structured constants, explicitly transforming tail calls to loops etc.

Re: [Caml-list] Function Inlining

[John Carr]

> You're probably running into restrictions other than size that OCaml has 
> on function inlining, such as function definitions inside the function, 
> structured constants and let rec.
> 
> Getting rid of these restrictions could potentially improve OCaml code 
> generation considerably, but as far as I can tell, that would require 
> some additional features in the code generation such as sharing 
> structured constants, explicitly transforming tail calls to loops etc.

I have been working on part of this.

My 64 bit SPARC code generator produces bad assembly code when
compiling the TK library.  The failure is caused by poor code
generation in the intermediate phase of the compiler.  There is a
nested (not top level) module named Tkintf containing hundreds of
values.  The code generated to initialize Tk.Tkintf looks like:

	1. compute the hundreds of values to be stored in the Tkintf module
	2. allocate a block to hold Tkintf
	3. store the hundreds of values computed earlier into the Tkintf block
	4. store a pointer to the Tkintf block into the appropriate field of Tk

This sequence results in hundreds of live values.  Most have to be
spilled to the stack between 1 and 3, but the stack can only hold
about 256 values.  (Because ocamlopt does not use register windows
it is limited to a 2 kilobyte stack frame.)  The assembler fails
with address offset out of range errors.

The ocaml developers were aware of this sort of problem and a
different method is used to initialize top level modules, though
there is a separate inefficiency there because it isn't necessary to
compute at runtime the majority of module values which are constant,
either integer constants or pointers to statically allocated blocks.

I have been experimenting with making both constant closures and
structured constants shareable and (for top level modules) compiling
constant initializers into the data section.  So given a module like

	let x = 1 let y = (1,2,3) let rec f x = ... and g x = ...

the assembly code would look like (with tag values omitted for clarity):

	.data
L1:	# begin three value tuple
	.word	3	# integer 1
	.word	5	# integer 2
	.word	7	# integer 3
L2:	# begin block describing mutually recursive functions f and g
	.word	1	# f arity
	.word	f	# pointer to function f
	.word	1	# g arity
	.word	g	# pointer to function g
module:
	.word	3	# integer 1
	.word	L1	# pointer to (1,2,3)
	.word	L2	# pointer to closure for f
	.word	L2+8	# pointer to closure for g

Values not computable at compile time cause a .skip directive and the
module entry code computes the initial value as in the current compiler.

This solves the stack overflow problem.  I'm not convinced that
the asmcomp phase of the compiler is the right place to do this
optimization.  Perhaps it should be moved to the intermediate
phase where the top level module optimization is done now.

(This is more than just optimizing the performance of code that is
executed once.  For TK a substantial fraction of the code size is
the module entry point.  Also, a few jobs ago I cut the startup time
of a product I worked on by several seconds by optimizing the dynamic
loading process, which is similarly a one time act.)

Re: [Caml-list] Function Inlining

[Ville-Pertti Keinonen]

John Carr wrote:

> the assembly code would look like (with tag values omitted for clarity):

  ...

That definitely looks good.

> This solves the stack overflow problem.  I'm not convinced that
> the asmcomp phase of the compiler is the right place to do this
> optimization.  Perhaps it should be moved to the intermediate
> phase where the top level module optimization is done now.

One problem with this might be that you don't even have any kind of 
constant folding done at that point (I assume you're referring to the 
transl* phase), so you'd either have to duplicate that functionality or 
limit it to simple constants.