OCaml Coding Considerations: Difference between revisions
Lars.kurth (talk | contribs) (Migrated) |
m (Removed superfluous <nowiki></nowiki> tag pairs.) |
||
Line 24: | Line 24: | ||
[http://en.wikipedia.org/wiki/Tail_recursion Tail-recursion] is a very important notion to understand in order to make recursive calls efficients. Basically, a function is tail recursive if all the recursive call is not followed by any operations - if there are some operations left, the compiler will store them in the stack to finish them later, which is not good for performances. For example, this function which sum up the element of a list is not tail-recursive : the function fun x -> h + x need to be stored in the stack, waiting for the return of sum t to be totally applied: if your run this example on a big list, you will obtain Stack overflow as too many elements will be stored on the stack, waiting for the recursive calls to return. |
[http://en.wikipedia.org/wiki/Tail_recursion Tail-recursion] is a very important notion to understand in order to make recursive calls efficients. Basically, a function is tail recursive if all the recursive call is not followed by any operations - if there are some operations left, the compiler will store them in the stack to finish them later, which is not good for performances. For example, this function which sum up the element of a list is not tail-recursive : the function fun x -> h + x need to be stored in the stack, waiting for the return of sum t to be totally applied: if your run this example on a big list, you will obtain Stack overflow as too many elements will be stored on the stack, waiting for the recursive calls to return. |
||
<pre |
<pre> |
||
let rec sum l = |
let rec sum l = |
||
| [] -> 0 |
| [] -> 0 |
||
| h::t -> h + (sum t) |
| h::t -> h + (sum t) |
||
</pre> |
|||
A basic transformation of non tail-recursive function to tail-recursive function is with the help of an accumulator which carry the intermediate computation and which is passed through the recursive calls. Using that, we can re-write the last function into: |
A basic transformation of non tail-recursive function to tail-recursive function is with the help of an accumulator which carry the intermediate computation and which is passed through the recursive calls. Using that, we can re-write the last function into: |
||
<pre |
<pre> |
||
let sum l = |
let sum l = |
||
let rec aux accu = |
let rec aux accu = |
||
Line 39: | Line 39: | ||
in |
in |
||
aux 0 l |
aux 0 l |
||
</pre> |
|||
More examples can be found [http://alan.petitepomme.net/cwn/2003.06.17.html#2 here]. |
More examples can be found [http://alan.petitepomme.net/cwn/2003.06.17.html#2 here]. |
||
==== Good Usage of List Operations ==== |
==== Good Usage of List Operations ==== |
||
Complexity of pattern-matching and :: is O(1), and complexity of List.rev and @ is O. Thus, instead of doing |
Complexity of pattern-matching and :: is O(1), and complexity of List.rev and @ is O. Thus, instead of doing |
||
<pre |
<pre> |
||
let rec rev = function |
let rec rev = function |
||
| [] -> [] |
| [] -> [] |
||
| h::t -> rev t @ [h] |
| h::t -> rev t @ [h] |
||
</pre> |
|||
which is quadratic (and not tail-recursive), use the following code which is linear: |
which is quadratic (and not tail-recursive), use the following code which is linear: |
||
<pre |
<pre> |
||
let rev l = |
let rev l = |
||
let aux accu = function |
let aux accu = function |
||
| [] -> accu |
| [] -> accu |
||
| h::t -> aux (h :: accu) t |
| h::t -> aux (h :: accu) t |
||
</pre> |
|||
Line 70: | Line 70: | ||
indeed, if you compile the following program test.ml: |
indeed, if you compile the following program test.ml: |
||
<pre |
<pre> |
||
print_string ("hello " ^ "world!\n") |
print_string ("hello " ^ "world!\n") |
||
</pre> |
|||
using 'ocamlopt -S test.ml -o test' in order to see the resulting assembly file test.s, you will find out that it results in two different .data fields: |
using 'ocamlopt -S test.ml -o test' in order to see the resulting assembly file test.s, you will find out that it results in two different .data fields: |
||
<pre |
<pre> |
||
.data |
.data |
||
.long 2300 |
.long 2300 |
||
Line 88: | Line 88: | ||
.ascii "world!\12" |
.ascii "world!\12" |
||
.byte 0 |
.byte 0 |
||
</pre> |
|||
and a simple visualization of the resulting test binary using 'less' shows the unoptimized two constant strings in different locations, instead of one single constant string. |
and a simple visualization of the resulting test binary using 'less' shows the unoptimized two constant strings in different locations, instead of one single constant string. |
||
Line 94: | Line 94: | ||
This behavior is unfortunate but the compiler is not able to detect pure functional functions from side-effects functions. As example, the following function cannot be optimized, which is why the last example is also not optimized: |
This behavior is unfortunate but the compiler is not able to detect pure functional functions from side-effects functions. As example, the following function cannot be optimized, which is why the last example is also not optimized: |
||
<pre |
<pre> |
||
let c = ref true |
let c = ref true |
||
let (^) s t = if !c then s^t else t^s |
let (^) s t = if !c then s^t else t^s |
||
let x () = print_string ("hello " ^ "world!\n") |
let x () = print_string ("hello " ^ "world!\n") |
||
let _ = x (); c := false; c ; x () (* this prints "hello world\n!world!\nhello " *) |
let _ = x (); c := false; c ; x () (* this prints "hello world\n!world!\nhello " *) |
||
</pre> |
|||
Line 107: | Line 107: | ||
For instance, the following ocaml function |
For instance, the following ocaml function |
||
<pre |
<pre> |
||
let max (a:int) (b:int) = if a > b then a else b |
let max (a:int) (b:int) = if a > b then a else b |
||
</pre> |
|||
is compiled to a simple instruction "cmpl" in assembly to compare a and b, whereas the following ocaml function |
is compiled to a simple instruction "cmpl" in assembly to compare a and b, whereas the following ocaml function |
||
<pre |
<pre> |
||
let max a b = if a > b then a else b |
let max a b = if a > b then a else b |
||
</pre> |
|||
is compiled to a complex and inefficient call to a polymorphic comparison written as a C library, because the ocaml operator > is polymorphic, with type 'a -> 'a -> bool. This tendency to compile to polymorphic code by default is present regardless if the function is exported as an external symbol to be used outside the module or if the function is restricted to local usage. |
is compiled to a complex and inefficient call to a polymorphic comparison written as a C library, because the ocaml operator > is polymorphic, with type 'a -> 'a -> bool. This tendency to compile to polymorphic code by default is present regardless if the function is exported as an external symbol to be used outside the module or if the function is restricted to local usage. |
Revision as of 21:27, 28 November 2011
OCaml Coding Considerations
This page is a collection of things worth bearing in mind while developing in OCaml.
Garbage Collection
Read information from the tutorial here.
Performance Issues
Read information from the tutorial here.
Use Tail-Recursive Functions when Possible
Tail-recursion is a very important notion to understand in order to make recursive calls efficients. Basically, a function is tail recursive if all the recursive call is not followed by any operations - if there are some operations left, the compiler will store them in the stack to finish them later, which is not good for performances. For example, this function which sum up the element of a list is not tail-recursive : the function fun x -> h + x need to be stored in the stack, waiting for the return of sum t to be totally applied: if your run this example on a big list, you will obtain Stack overflow as too many elements will be stored on the stack, waiting for the recursive calls to return.
let rec sum l = | [] -> 0 | h::t -> h + (sum t)
A basic transformation of non tail-recursive function to tail-recursive function is with the help of an accumulator which carry the intermediate computation and which is passed through the recursive calls. Using that, we can re-write the last function into:
let sum l = let rec aux accu = | [] -> accu | h::t -> aux (h+accu) t in aux 0 l
More examples can be found here.
Good Usage of List Operations
Complexity of pattern-matching and :: is O(1), and complexity of List.rev and @ is O. Thus, instead of doing
let rec rev = function | [] -> [] | h::t -> rev t @ [h]
which is quadratic (and not tail-recursive), use the following code which is linear:
let rev l = let aux accu = function | [] -> accu | h::t -> aux (h :: accu) t
Do Not Allocate Big Data-Structure Whose Lifetime is Very Short
as in List.filter f (List.map g l) if l is very long.
Avoid Concatenating Constant Strings with Operator ^
The optimizing compiler will not optimize them to a single constant string, requiring the resulting binary to concatenate them every time.
indeed, if you compile the following program test.ml:
print_string ("hello " ^ "world!\n")
using 'ocamlopt -S test.ml -o test' in order to see the resulting assembly file test.s, you will find out that it results in two different .data fields:
.data .long 2300 camlTest__1: .ascii "hello " .space 1 .byte 1 .data .long 2300 camlTest__2: .ascii "world!\12" .byte 0
and a simple visualization of the resulting test binary using 'less' shows the unoptimized two constant strings in different locations, instead of one single constant string.
This behavior is unfortunate but the compiler is not able to detect pure functional functions from side-effects functions. As example, the following function cannot be optimized, which is why the last example is also not optimized:
let c = ref true let (^) s t = if !c then s^t else t^s let x () = print_string ("hello " ^ "world!\n") let _ = x (); c := false; c ; x () (* this prints "hello world\n!world!\nhello " *)
Specify Types for Function Arguments as Much as Possible
Otherwise, the compiler will try to find the largest polymorphic type for the argument, resulting in very inefficient assembly code.
For instance, the following ocaml function
let max (a:int) (b:int) = if a > b then a else b
is compiled to a simple instruction "cmpl" in assembly to compare a and b, whereas the following ocaml function
let max a b = if a > b then a else b
is compiled to a complex and inefficient call to a polymorphic comparison written as a C library, because the ocaml operator > is polymorphic, with type 'a -> 'a -> bool. This tendency to compile to polymorphic code by default is present regardless if the function is exported as an external symbol to be used outside the module or if the function is restricted to local usage.