Friday, 28 September 2007

Book review: OCaml for Scientists

The following review of the book OCaml for Scientists was posted on Digg by Lloyd Moore:

"This is one of the most informative books on any subject. After reading Practical Ocaml and being thoroughly disappointed, I almost gave up on finding that 'helping hand' when coming to terms with a new language - especially one that introduces some of the more lesser known concepts in the world of functional programming. In stark contrast to the Practical Ocaml tome, from physical make-up of the book, logical sequencing of information and chapters from start to finish, to the beautifully crafted illustrations exactly placed where relevant, this ocaml masterpiece will enable to not only master the ocaml language but also to appreciate functional programming constructs and much better programming style (clarity, shorter, reusable, less bugs). There is even a brief, but pragmatic treatment of lexing and parsing which will open the doors to anyone wishing to save and retrieve obscure data formats, including their own DSL language. Visualization is dealt with in chapter 6 which explains the use of the GLUT (openGL) library in an extremely efficient manner and the later chapters on optimization complete this master class on ocaml and some very powerful programming techniques."

Thursday, 27 September 2007

Using lex and yacc

The OCaml Journal just published an article describing how the ocamllex and ocamlyacc tools can be used to create parsers:

"The tool stack bundled with the OCaml distribution provides some awesome functionality. The ocamllex and ocamlyacc tools provide a mainstream approach to the parsing of data. This article introduces the concepts of lex and yacc-based parsing and describes the use of these tools in implementing robust and efficient parsers quickly and easily..."

To read this article and more, subscribe to The OCaml Journal today!

Monday, 24 September 2007

Book Reviews

Andrei Formiga has been kind enough to write a thorough and impartial review of our book OCaml for Scientists.

Also, we were thrilled to discover that Amazon (who do not even sell OCaml for Scientists) are hosting a book review for Practical OCaml that states "I bought OCaml for Scientists from Flying Frog Consultancy, and it makes for a much better grounding in OCaml...".

OCaml Summer projects at Jane St.

Jane St. Capital are unquestionably one of the most influential industrial players in the OCaml world. They were kind enough to fund a variety of student projects this summer and a set of talks about the projects was recently put on-line. Makes for an interesting read!

More controversy from O'Reily

O'Reily are usually only a publisher of cheap books but they recently diversified into posters. Specifically, they are selling their own rehash of the famous Computer Language History poster in the form of a bigger, color poster that only includes languages that O'Reilly publish books on and omits almost all of the inheritance relationships.

Although the original clearly shows that OCaml is one of the most up-to-date languages in existence, O'Reily's poster indicates that OCaml died five years ago! Perhaps this is when "Développement d'applications avec Objective Caml" stopped selling?

Wednesday, 19 September 2007

XenSource sell for $500M

XenSource, one of the world's most prominent players in virtualization and a customer of Flying Frog Consultancy, recently announced their sale to Citrix for $500M. The core value-add of XenSource's product line over the open source Xen virtualization package is a sophisticated management tool stack written almost entirely in OCaml.

Following the announcement of the sale, Anil Madhavapeddy of XenSource posted an advertisement asking for OCaml programmers to join their team. We were fortunate enough to consult at the Cambridge branch of XenSource last year and I can tell you that they have the most talented engineering team I have ever seen. If you are an expert OCaml programmer I would not hesitate to recommend a position at this company.

If your company uses OCaml, let us know and we can tell the world about your successes!

Saturday, 15 September 2007

Spectral norm

The Computer Language Shootout is a well-known set of benchmarks that is still gradually evolving. Although the shootout is infamous because most of its benchmark tasks are trivially reducible (e.g. computing constants like pi and prime numbers) and that creates a strong subjective bias because submissions must be rejected or selectively crippled, a few contributors have created better benchmark tasks such as k-nucleotide and spectral-norm.

Our primary machines for high performance computing using OCaml are based upon Athlon 64 CPUs. At least on these machines, the current OCaml implementation of the spectral-norm benchmark can be made significantly faster. This post describes how.

The core of the spectral-norm benchmark is a pair of nested loops. For no particular reason, the shootout requires that this functionality be replicated in two separate functions. Let us focus on the first such function as the other is virtually identical:

let eval_A_times_u u v =
let n = Array.length v - 1 in
for i = 0 to n do
v.(i) <- 0.0;
for j = 0 to n do
v.(i) <- v.(i) + eval_A i j * u.(j)
done
done
This implementation, currently on the shootout, takes 14.4s to run with n=5500 on this machine (4400+ Athlon64).

Most of the time is, of course, spent in the inner loop over j. However, the current implementation on the shootout does not hoist the subexpression v.(i) from the inner loop. This can be done by accumulating the result of the inner loop in a variable and storing it in v.(i) only once, after the inner loop completes:

let eval_A_times_u u v =
let n = Array.length v - 1 in
for i = 0 to n do
let vi = ref 0.0 in
for j = 0 to n do
vi := !vi +. eval_A i j *. u.(j)
done;
v.(i) <- !vi
done
This brings the time taken down to 12.0s.

The next most important optimization in the OCaml is to remove bounds checking. Although this can be done globally using the -unsafe flag as the shootout does, this is very bad practice. Specifically, many OCaml programs assume that out of bounds array accesses incur an appropriate exception and compiling them with -unsafe renders such code invalid, essentially changing the semantics of the language.

Using explicitly unsafe array accesses on minimal performance-critical portions of code is much more preferable and this benchmark is a good illustration of how this can be done. Specifically, there is only one array access in the inner loop, to u.(j), and this can be made unsafe. To ensure correctness, we can simply derive n from the length of u rather than v:

let eval_A_times_u u v =
let n = Array.length u - 1 in
for i = 0 to n do
let vi = ref 0.0 in
for j = 0 to n do
vi := !vi +. eval_A i j *. Array.unsafe_get u j
done;
v.(i) <- !vi
done
This brings the time down to 9.4s, over 50% faster than the original.

The forms of optimization described here are generally-applicable and may be used to improve the performance of a wide variety of OCaml programs. For detailed and comprehensive information on high-performance OCaml, read the book OCaml for Scientists. For general information on the OCaml programming language and tutorial articles, read the OCaml Journal.

Friday, 14 September 2007

Combinator Heaven

The OCaml Journal published an article discussing the unique way that functions may be composed in functional languages using combinators:

"The ability to write higher-order functions that compose other functions in interesting ways is one of the most powerful forms of abstraction provided by the functional programming paradigm. Such functions are known as combinators . This article describes the basic concepts behind combinators with a variety of examples to demonstrate how practically useful this form of functional abstraction can be..."

To read this article and more, subscribe to The OCaml Journal today!