Today I struggled once again to build a simple library with ocamlbuild, so once for all I decided to write something about it. I’m sure next time, googling for an answer I’ll find this post and shake my head in despair :)

The library in question is parmap written by Roberto Di Cosmo to speed up computations on modern multi processors computers. We want to build everything: cma, cmxa and cmxs. Moreover, we want to build a shared library that contains stubs for a couple of bindings to C functions. On top of that, I want to use configure to make sure that the platform I’m using supports a specific syscall.

We start by copying ocaml.m4, the more or less standard autoconf macros for OCaml ( source here ). I prefer to copy this file in my source tree as I don’t want to impose to download it from a website to compile my library. This file ends up in the directory m4. Then to use it, I need to invoke aclocal as follows aclocal -I m4. This will take care of making the m4 macros known to the configure script.

Next step is the configure script. I need check for the standard ocaml utils, if extlib is known by ocamlfind and if the function sched_setaffinity is available on the system. This is the standard autoconf way to detect if a specific function is available. Together with the AC_CONFIG_HEADERS([config.h]) call, this will define the variable HAVE_DECL_SCHED_SETAFFINITY to 1 in the file config.h that can be later used in the C source code.

AC_INIT(parmap, 0.9.4, roberto@dicosmo.org)

AC_PROG_OCAML
if test "$OCAMLC" = "no"; then
 AC_MSG_ERROR([You must install the OCaml compiler])
fi

AC_PROG_CAMLP4
AC_SUBST(CAMLP4O)
if test "$CAMLP4" = "no"; then
 AC_MSG_ERROR([You must install the Camlp4 pre-processor])
fi

AC_PROG_FINDLIB
AC_SUBST(OCAMLFIND)
if test "$OCAMLFIND" = "no"; then
 AC_MSG_ERROR([You must install OCaml findlib (the ocamlfind command)])
fi

AC_CHECK_OCAML_PKG([extlib])
if test "$OCAML_PKG_extlib" = "no"; then
 AC_MSG_ERROR([Please install OCaml findlib module 'extlib'.])
fi

AC_HEADER_STDC
AC_CHECK_HEADERS([sched.h],,AC_MSG_ERROR([missing sched.h]))
AC_CHECK_DECLS([sched_setaffinity], [], [], [[
                #define _GNU_SOURCE 1
                #include <sched.h>
                ]])

AC_CONFIG_HEADERS([config.h])
AC_CONFIG_FILES([Makefile])
AC_OUTPUT

Once this is done I’ve to generate the config .h.in with autoreconf and then run autoconf to generate my configure script. If this go through, you should be able to run your configure script as usual. So far so good. Now it time to convince ocamlbuild to play nice with us.

First we need to write a small myocamlbuild file to set few dependencies and compilation flags. The first rule we add is a dependency to convince ocamlbuild to copy the config.h file in the _build directory. Without this rule, ocamlbuild is unable to figure out the dependency just by looking at the C source file (I’ve found a [bug http://caml.inria.fr/mantis/view.php?id=5107] on the inria bts about this problem).

The second rule adds a couple of compilations options to compile our C code. I think this can be done on a file basis, but since these options make no harm, I use to compile all my C objects.

The third rule is there to make aware ocamlbuild that is I want to compile a library that uses libparmap, I must specify that libparmap is a dynamically linked library. The forth rule is an analogues rule for native libraries.

The fifth and sixth rule are one to compile the .a and then to link it. This is need to correctly generate cmxs objects.

open Ocamlbuild_plugin ;;

let _ = dispatch begin function
  | After_rules ->
      dep  ["compile"; "c"] ["config.h"];

      flag ["compile"; "c"] & S[ A"-ccopt"; A"-D_GNU_SOURCE"; A"-ccopt"; A"-fPIC" ];

      flag ["link"; "library"; "ocaml"; "byte"; "use_libparmap"] &
        S[A"-dllib"; A"-lparmap_stubs";];
      flag ["link"; "library"; "ocaml"; "native"; "use_libparmap"] &
          S[A"-cclib"; A"-lparmap_stubs"];
      dep ["link"; "ocaml"; "use_libparmap"] ["libparmap_stubs.a"];
      flag ["link"; "ocaml"; "link_libparmap"] (A"libparmap_stubs.a");

  | _ -> ()
end

But of course this is only part of the ocamlbuild configuration. We also need to specify how to build these libraries and what to include. To build the stubs library we specify a .clib file in which we tell to ocamlbuild the C objects it has to link together.

This is accomplish with by adding the file libparmap_stubs.clib :

$cat libparmap_stubs.clib
bytearray_stubs.o
setcore_stubs.o

To build parmap.cm{x,}a and parmap.cmxs I need to other files, respectively :

$cat parmap.mllib
Parmap
Bytearray

$cat parmap.mldylib
Parmap
Bytearray

and at last we write the _tags file to correctly associate different flags to each component.

$cat _tags 
<*>: annot
<parmap.cm{x,}a>: use_libparmap
<parmap.cmxs>: link_libparmap
<*.{ml,mli}>: package(extlib), package(unix), package(bigarray)

This should build all you goodies in one go :

$ocamlbuild -use-ocamlfind parmap.cma  parmap.cmxa  parmap.cmxs parmap.a -classic-display
/usr/bin/ocamlfind ocamlopt -I /usr/lib/ocaml/ocamlbuild unix.cmxa /usr/lib/ocaml/ocamlbuild/ocamlbuildlib.cmxa myocamlbuild.ml /usr/lib/ocaml/ocamlbuild/ocamlbuild.cmx -o myocamlbuild
/usr/bin/ocamlfind ocamlc -ccopt -D_GNU_SOURCE -ccopt -fPIC -c bytearray_stubs.c
/usr/bin/ocamlfind ocamlc -ccopt -D_GNU_SOURCE -ccopt -fPIC -c setcore_stubs.c
/usr/bin/ocamlmklib -o parmap_stubs bytearray_stubs.o setcore_stubs.o
/usr/bin/ocamlfind ocamldep -package bigarray -package extlib -package unix -modules parmap.mli > parmap.mli.depends
/usr/bin/ocamlfind ocamlc -c -annot -package bigarray -package extlib -package unix -o parmap.cmi parmap.mli
/usr/bin/ocamlfind ocamldep -package bigarray -package extlib -package unix -modules parmap.ml > parmap.ml.depends
/usr/bin/ocamlfind ocamldep -package bigarray -package extlib -package unix -modules bytearray.mli > bytearray.mli.depends
/usr/bin/ocamlfind ocamldep -package bigarray -package extlib -package unix -modules setcore.mli > setcore.mli.depends
/usr/bin/ocamlfind ocamlc -c -annot -package bigarray -package extlib -package unix -o bytearray.cmi bytearray.mli
/usr/bin/ocamlfind ocamlc -c -annot -package bigarray -package extlib -package unix -o setcore.cmi setcore.mli
/usr/bin/ocamlfind ocamldep -package bigarray -package extlib -package unix -modules bytearray.ml > bytearray.ml.depends
/usr/bin/ocamlfind ocamlc -c -annot -package bigarray -package extlib -package unix -o parmap.cmo parmap.ml
/usr/bin/ocamlfind ocamlc -c -annot -package bigarray -package extlib -package unix -o bytearray.cmo bytearray.ml
/usr/bin/ocamlfind ocamlc -a -dllib -lparmap_stubs bytearray.cmo parmap.cmo -o parmap.cma
/usr/bin/ocamlfind ocamlopt -c -annot -package bigarray -package extlib -package unix -o bytearray.cmx bytearray.ml
/usr/bin/ocamlfind ocamlopt -c -annot -package bigarray -package extlib -package unix -o parmap.cmx parmap.ml
/usr/bin/ocamlfind ocamlopt -a -cclib -lparmap_stubs bytearray.cmx parmap.cmx -o parmap.cmxa
/usr/bin/ocamlfind ocamlopt -shared libparmap_stubs.a bytearray.cmx parmap.cmx -o parmap.cmxs

Relevant files: http://gitorious.org/parmap/parmap/blobs/pipes/myocamlbuild.ml http://gitorious.org/parmap/parmap/blobs/pipes/configure.ac http://gitorious.org/parmap/parmap/blobs/pipes/Makefile.in  http://gitorious.org/parmap/parmap/blobs/pipes/_tags

All the source code is in Git parmap - in the pipes branch. If I’m doing something wrong, or not in the standard way, please tell !!!

I’ve just released the new version of ocaml-buddy, my ocaml bindings to the buddy BDD c library. Thanks to a fruitful interaction with Jimmy Thomson, I’ve fixed a couple of memory leaks and cleaned up the code a bit.

grab it when is still hot : https://github.com/abate/ocaml-buddy/tree/0.5

comments a testers are welcome. A debian package is on the way

Thanks to Ralf’s work, dose3 has been just accepted in debian experimental !!! yuppiiiii \o/

Dose3 is a framework made of several OCaml libraries for managing distribution packages and their dependencies.

Though not tied to any particular distribution, dose3 constitutes a pool of libraries which enable analyzing packages coming from various distributions.

Besides basic functionality for querying and setting package properties, dose3 also implements algorithms for solving more complex problems (monitoring package evolutions, correct and complete dependency resolution, repository-wide uninstallability checks).

For the ocaml affectionados the API of the library is available here (there is still a bit of work to do here…) . The source code shipped in each release does not include a vast range of applications sitting in the experimental directory. You can have a look at these in our svn.

if you want to get a copy of the development / bleeding edge / unstable version from svn, you can check it out from the svn

svn co https://gforge.info.ucl.ac.be/svn/mancoosi/trunk/dose3

user/pass : mancoosi/mancoosi

A simple module to parse a uri (well, a small subset of the RFC 3986). The Ocamlnet library contains a better implementation, but it also comes with a lot of dependencies…

Grab it, use it, change it, give it away but remember me :) …

(* ref : http://labs.apache.org/webarch/uri/rfc/rfc3986.html#collected-abnf *)
(* ref : http://stackoverflow.com/questions/161738/what-is-the-best-regular-expression-to-check-if-a-string-is-a-valid-url *)

type authority = {
  userinfo : string option;
  host : string;
  port : int option
}

type url = {
  url : string;
  scheme : string;
  authority : authority option;
  path   : string; 
  query  : (string * string) list; 
};;

let try_with f =
  try Some(Lazy.force f) with Not_found -> None
;;

let parse_authority s =
  let re_s = 
    "(?:(?P<userinfo>(?:[A-Za-z0-9\\-._~!$&\\'()*+,;=:]|%[0-9A-Fa-f]{2})*)@)?" ^
    "(?P<host>(?:[A-Za-z0-9\\-._~!$&\\'()*+,;=]|%[0-9A-Fa-f]{2})+)" ^
    "(?::(?P<port>[0-9]*))?"
  in
  let rex = Pcre.regexp re_s in
  let res = Pcre.exec ~rex s in
  {
    userinfo = try_with (lazy(Pcre.get_substring res 1));
    host = Pcre.get_substring res 2;
    port = try_with (lazy(int_of_string (Pcre.get_substring res 3)))
  }
;;

let parse_query s = 
  let re_s = 
    "(?:\\?(?P<query>(?:[A-Za-z0-9\\-._~!$&\\'()*+,;=:@\\\\/?]|%[0-9A-Fa-f]{2})*))?"
  in
  let rex = Pcre.regexp re_s in
  let res = Pcre.exec ~rex s in
  List.map (fun s ->
    let a = Pcre.asplit ~rex:(Pcre.regexp "=") s in
    (a.(0),a.(1))
  )
  (Pcre.split ~rex:(Pcre.regexp ";") (Pcre.get_substring res 1))
;;

(* we parse uri of type schema://user:pass@machine:port/path/to/file?a=1;b=2 *)
let parse_remote_uri s =
  let re_s = "^(([^:/?#]+):)?(//([^/?#]*))?([^?#]*)(\\?([^#]*))?(#(.*))?" in
  let rex = Pcre.regexp re_s in
  let res = Pcre.exec ~rex s in
  try
    {
      url = Pcre.get_substring res 1;
      scheme = Pcre.get_substring res 2;
      authority = try_with (lazy(parse_authority (Pcre.get_substring res 4)));
      path = Pcre.get_substring res 5;
      query = try parse_query (Pcre.get_substring res 6) with Not_found -> []
    }
  with Not_found -> failwith (Printf.sprintf "Malformed Url : %s" s)
;;

(* we parse uri of the type schema:/path/to/file *)
let parse_local_uri s =
  let re_s = "^(([^:/?#]+):)?(([^/?#]*))?([^?#]*)(\\?([^#]*))?(#(.*))?" in
  let rex = Pcre.regexp re_s in
  let res = Pcre.exec ~rex s in
  try
    {
      url = Pcre.get_substring res 1;
      scheme = Pcre.get_substring res 2;
      authority = None;
      path = (Pcre.get_substring res 4)^(Pcre.get_substring res 5);
      query = []
    }
  with Not_found -> failwith (Printf.sprintf "Malformed Url : %s" s)
;;

let parse_uri ?(local=true) s =
  if local then parse_local_uri s
  else parse_remote_uri s
;;

# parse_url "sqlite://user:secret@machine:42/a:c/b/c?a=1;b=2";;
- : url =
{url = "sqlite:"; scheme = "sqlite";
 authority =
  Some {userinfo = Some "user:secret"; host = "machine"; port = Some 42};
 path = "/a:c/b/c"; query = [("a", "1"); ("b", "2")]}

# parse_url "file:/aa/vv/bb";;
- : url =
{url = "file:"; scheme = "file"; authority = None; path = "/aa/vv/bb"; query = []}

Lately I’ve been concerned about the performances of dose3. Soon we will have a package in the official debian archive (containing the new distcheck) and we also plan to use dose3 as foundation of an upcoming apt-get future (external solvers !). This week I tackled a couple of problems.

First I wanted to understand the poor performances of my parser for the debian Packages format. The parser itself (written by J. Voullion for dose2) is a home brewed parser, it uses a Str based tokenizer and it is pretty efficient. On the top of it I built the rest of the parsing infrastructure. Because of laziness (well, I followed the [http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf “avoid premature optimization”] mantra) I used a lot of regular expressions using the standard library (Str) module to parse various chunks of the file. Since Str has the reputation of not being the fastest reg exp library in the world (I know I should use Pcre), I started my journey by removing all calls to this library and substituting the with calls to the module String.

====Lesson n. 1==== If you do not need a regular expression to parse a string, you are better off using String.index, String.sub and friends instead. Maybe your function will be a bit longer, but certainly faster. Sscanf is also your friend.

This was only the tip of the iceberg. Second I noticed I used String.lowercase (I use ExtLib.String) a bit every where… I realized I could simply remove all these calls and have a bit more faith in the user input. If the user does not respect the standard it’s his problem, not mine.

====Lesson n. 2==== Calling a String function a zillion times slow you down considerably !!!!

I knew there was something more to do. Following the advices of my colleges, we decided to take a look at what really was happening under the wood. Using ocamlbuild and gproof, this is easily done.

first you need to rebuild your binary using debug and the profiling tags. This can be done once off from the command line :

ocamlbuild -tag debug -tag profile apt-backend.native

Then you have to run the binary as you normally do, to collect profiling information, and in the end you fire up gprof to see what’s going on.

$gprof apt-backend.native | less
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
  8.52      0.79     0.79 63008857     0.00     0.00  caml_gc_set
  5.61      1.31     0.52   934076     0.00     0.00  _fini
  5.07      1.78     0.47 55818126     0.00     0.00  caml_MD5Transform
  4.53      2.20     0.42   296139     0.00     0.00  caml_gc_stat
  4.21      2.59     0.39 10910905     0.00     0.00  caml_parse_engine
  2.91      2.86     0.27                             compare_val
  2.48      3.09     0.23 11707884     0.00     0.00  caml_final_register

compare_val !!! This is a bad sign. It means I’m using the generic comparing function instead of a monomorphic comparison function. After a bit of head scratching I realized that in one of my data structures I was using a generic List.assoc . This function uses compare_val ! Bingo.

rewriting the assoc function lowered the number of calls to compare_val ten-folds giving me a considerable speed-up

let rec assoc (n : string) = function
  |(k,v)::_ when k = n -> v
  |_::t -> assoc n t
  |[] -> raise Not_found
;;

====Lesson n.3==== Before using a generic function think twice !

On the same vein, I specialized also a couple of hash tables (for integers and strings) with their monomorphic counterparts.

During my tests I’ve also noticed that I was spending a lot of time resizing my hash tables. In my case this was easily avoidable using a more sensitive default when creating the hash table. This is not always the case because sometimes the default is tied to a value that in not known in advance.

The only think left in the parsing function is to get rid of the last call to Str that I use to tokenize my stream. I think writing few lines of ocamllex would give me an additional speedup, but I’ll leave this for next week…

Since was in the mood for hacking I decided to understand what was wrong in a different part of dose3, that is, the translation from debian Packages format to propositional logic (that will be then used by a SAT solver to perform various installability analysis).

What I immediately noticed looking at my code, is that I had a couple of List.unique functions called by a very important function. Ah ! My first naive solution to this problems was to use the ExtLib List.unique function that forces you to pass a comparison function with it. With this change I noticed a small speed-up (compare_val strikes back), but it was clearly not enough. The obvious solution was to rewrite the routine using a set (of integers in this case) and drop completely the List.unique.

====Lesson n.4 ==== List.unique is slow, ExtLib.List.unique is better, If you can, use Sets.

Last improvement is related to the SAT solver we use. It’s a very specialized and optimized SAT solver (inherited from dose2) and it is written in ocaml. Using again grpof I noticed that the Gc overhead was substantial enough to warrant a bit of Gc tweaking.

    Gc.set { (Gc.get()) with
      Gc.minor_heap_size = 4 * 1024 * 1024; (*4M*)
      Gc.major_heap_increment = 32 * 1024 * 1024; (*32M*)
      Gc.max_overhead = 150;
    } ;

This corresponds to CAMLRUNPARAM=s=4M,i=32M,o=150

====Lesson n.5 ==== Gc tweaking can make the difference sometimes !

After all this work I was quite pleased of the result:

Before (r2454) :
abate@zed.fr:~/Projects/git-svn-repos/dose3/applications$time
./distcheck.native deb://tests/lenny.packages
background-packages: 22311
foreground-packages: 22311
broken-packages: 0

real    0m11.535s
user    0m11.409s
sys     0m0.112s
abate@zed.fr:~/Projects/git-svn-repos/dose3/applications$time
./distcheck.native deb://tests/sid.packages
background-packages: 29589
foreground-packages: 29589
broken-packages: 143

real    0m19.799s
user    0m19.621s
sys     0m0.152s

After (r2467) :
abate@zed.fr:~/Projects/git-svn-repos/dose3/applications$time
./distcheck.native deb://tests/lenny.packages
background-packages: 22311
foreground-packages: 22311
broken-packages: 0

real    0m8.738s
user    0m8.589s
sys     0m0.132s
abate@zed.fr:~/Projects/git-svn-repos/dose3/applications$time
./distcheck.native deb://tests/sid.packages
background-packages: 29589
foreground-packages: 29589
broken-packages: 143

real    0m14.026s
user    0m13.817s
sys     0m0.172s

I shaved about 4 seconds from my processing time. Considering that these applications are going to be called many times per day on the entire debian archive or thousand or times during our experiments, 4 seconds here and there can save quite a bit of time.