Showing posts with label optimization. Show all posts
Showing posts with label optimization. Show all posts

Friday, 6 February 2009

Photos from OCaml Users Meeting, Grenoble, 2009

We had a very successful OCaml User Meeting this week, with 45 people coming from around Europe to Grenoble.



Xavier Leroy on progress made over 2008

Sylvain Le Gall OCamlCore.org and OCaml as fast as C

Maxence Guesdon Chamo and Cameleon

Florent Ouchet VHDL symbolic simulation

David Teller Batteries Included

Christophe Troestler pa_do (delimited overloading) syntax

Richard Jones (me) OCaml Windows cross-compiler

Christophe Raffalli Parsing with dypgen

Xavier Leroy on the right:



Dinner the evening before:

Saturday, 10 January 2009

ocsigen (OCaml web framework) benchmarked

This benchmark compares the OCaml web framework ocsigen against Ruby on Rails and lighttpd+C with some excellent results for the OCaml framework:
Reqs/sec Mem usage
Rails with mongrel, 1 process 260 49MB
Rails with mongrel via nginx (rev proxy), 1 proc 220 ~51MB
Rails with mongrel, 4 processes via nginx 430 ~200MB
OCaml ocsigen (1 process) 5800 4.5MB
lighttpd with FastCGI app in C, 20 procs 9300 4.5MB

OCaml is not just an order of magnitude faster and an order of magnitude more memory efficient, but it also provides complete compile-time safety, catching multiple errors at compile time which would otherwise only show up after extensive testing.

More discussion on this reddit thread.

There's a Fedora ocsigen package waiting for review here.

Saturday, 20 September 2008

What can OCaml do that you can't do in other programming languages?

Depressingly predictable comments on the Haskell story in Slashdot yesterday such as:
"I have *never* seen it being used since. To my mind they both belong in the category 'interesting, but pointless'."
and
"The point is that there's nothing those languages can do that can't be done, often more easily, with the current crop of popular languages. Elegance cannot beat convenience in the workplace, or in most at any rate."
and so on.

Here are some useful things you can do in OCaml which you cannot do in the "current crop of popular languages".

1. Change the language to suit your task.

In our case the task was to parse binary formats.

If you have a few hours to spare, try writing a C program to parse tcpdump files. Don't forget that the endianness in these files is variable so you'll need lots of if (..) { field1 = htonl (field1); ... }. OK so that's a bit hard. Let's say you want to parse a 6 bit length field 'n' followed by an n+1 bit data field (as a 1-64 bit int). Go and write it in C now.

Using our bitstring extension to OCaml, parsing binary structures is really effortless:

let bits = Bitstring.bitstring_of_file "input.data" in
bitmatch bits with
| { n : 6;
data : n+1 } -> data

This is the complete tcpdump parser, just 113 lines of code.

And it's fast too. The resulting code compiles down to machine code and inlines direct calls to C functions at every opportunity, so in practice you can parse data at speeds approaching C.

Another task we had was to check that hundreds of SQL statements in a modest sized web application actually matched with fields in the database, in other words that they didn't reference non-existent fields or treat a string field as an integer and so forth. Doing this by testing is almost impossible because many SQL statements are only used on rare error paths. We could contemplate doing it manually once but not routinely.

So instead we extended the OCaml language to do the checking for us every time we compiled the code. The resulting PG'OCaml project gives you compiled-time checked type-safe access to your database. It's used by mod_caml and ocsigen, or you can just use it in standalone programs. I won't go into detail because Dario Teixeira wrote a great introduction and tutorial to PG'OCaml.

Martin Jambon, author of Micmatch which adds regular expressions directly into the language, has an excellent tutorial. Browse the list of syntax extensions here.

2. Get the compiler to check for errors in your logic

Why can't your compiler check for errors like when you use a read-only database connection in a SQL INSERT statement, or you are supposed to call library function set_word_size because you try to call get_word?

In OCaml, using phantom types [tutorial] you can do exactly this.

3. Drop down to imperative code when you need speed like C

Scripting languages are expressive but slow ... and getting slower. But there's no need to compromise expressiveness to get real speed. Static typed languages with type inference (which excludes C, C++, Java, C# and most others, but includes SML, OCaml and F#) give you the expressiveness to write compact code but without compromising on speed.

OCaml programs are more than 10 - 15 times faster and less memory intensive than Python programs.

More about speed and optimizing OCaml programs. Comparison of a raytracer written in C++ and OCaml.

4. Large well-established standard libraries

OCaml comes with hundreds of packages for many tasks now.

If that's not enough you can directly call out to Perl, Java, Python and .Net [on Windows] libraries. Or you can call C functions directly.

You can compile the same code on Unix, Mac OS X and Windows.

So enough of this "elegance can't beat convenience" stuff please.

Saturday, 30 August 2008

Sharing a global variable between C and OCaml

I was asked today if it is possible to share a global variable between C and OCaml. This was my first response:

OCaml cannot just directly access C globals. At best you'd need to have a function that returns the address of the C global, _and_ the C global would need to be in a form that OCaml code could understand although that is pretty easy to arrange.
In a followup, I gave some example code:

------------------------------------------------------------ test_c.c
/* Variable shared between C and OCaml. */

#include <caml/mlvalues.h>

/* On the OCaml side, this will be made to look like a structure
* containing a single int (well, provided you don't look *too*
* closely at it).
*/
value shared_var = Val_int (0);

value
get_struct_addr (value unitv)
{
/* Return the address of the 'structure'. */
return ((value) &shared_var);
}

/* Increment the shared variable. */
value
increment_it (value unitv)
{
int i = Int_val (shared_var);
i++;
shared_var = Val_int (i);
return (Val_unit);
}
----------------------------------------------------------------------

------------------------------------------------------------ test.ml
(* Variable shared between C and OCaml. *)

type var = {
shared_var : int;
}

external get_struct_addr : unit -> var = "get_struct_addr" "noalloc"
external increment_it : unit -> unit = "increment_it" "noalloc"

let var = get_struct_addr () ;;

while true do
Printf.printf "value of the variable now is %d\n%!" var.shared_var;
increment_it ();
(* OCaml isn't expecting that increment_it modifies a variable, so
* there is no guarantee that we will see the changed value next
* time around.
*)
Unix.sleep 1;
done
----------------------------------------------------------------------

$ gcc -I /usr/lib/ocaml -c test_c.c
$ ocamlopt -c test.ml
$ ocamlopt unix.cmxa test_c.o test.cmx -o test
$ ./test
value of the variable now is 0
value of the variable now is 1
value of the variable now is 2
value of the variable now is 3
value of the variable now is 4
[etc.]

Before you use this code, be aware that it's a real hack.

Thursday, 21 August 2008

Tip: Calling C functions directly with "noalloc"

In OCaml you can call a C function by writing:

external call_1 : float -> float = "call_1"
then just using call_1. However these calls are not direct. They go via an OCaml runtime function called caml_c_call. This is a tiny bit of assembler, so the overhead isn't large, but it does use a computed jump which on many processors is quite slow.

Luckily this indirection is only needed in order to set up the garbage collector. If your C function won't perform any OCaml allocations, then you don't need this, and you can tell OCaml to jump directly to your C function like this:

external call_2 : float -> float = "call_2" "noalloc"

Let's compare the generated assembly code for the calls in both cases:


Normal "noalloc"

pushl %eax pushl %eax
movl $call_1, %eax call call_2
call caml_c_call addl $4, %esp
addl $4, %esp
...
caml_c_call:
movl (%esp), %edx
movl %edx, G(caml_last_return_address)
leal 4(%esp), %edx
movl %edx, G(caml_bottom_of_stack)
jmp *%eax


As you can see, the "noalloc" version is much shorter.

Wednesday, 7 May 2008

Optimizing, memory allocation and loops

Unlike C compilers such as gcc, ocamlopt doesn't do very much in the way of optimization. Really it compiles the program directly down to machine code pretty much the way you write it.

Accidental memory allocation and loops are a particular challenge. Consider for example:

let n = 100_000
let fib = Array.make n 1 ;;
for i = 2 to n-1 do
let a, b = fib.(i-2), fib.(i-1) in
fib.(i) <- a + b
done
ocamlopt takes the code literally, and let a, b = ... allocates a tuple (a, b) before discarding it. Simply rewriting the problematic statement as:

let a = fib.(i-2) and b = fib.(i-1) in
makes the whole loop run in half the time.

The second problem with this loop is that we have lots of unnecessary references to the array fib. Each time we write fib.(i), the compiler has to emit code to calculate fib + i*sizeof(int), and unlike C, ocamlopt doesn't use code motion to simplify and share the repeated references.

We nearly halve the loop time again by accessing the array only once:

let a = ref 1 and b = ref 1 in
for i = 2 to n-1 do
let c = !a + !b in
a := !b; b := c; fib.(i) <- c
done
Overall these two simple optimizations reduce the total running time of this loop more than three-fold.