Hello

Here is the latest Caml Weekly News, for the week of 08 to 15 March, 2005.

1. MinCaml English Documentation
2. GC questions
3. ocamldap 2.1.0
4. 2D maze generator
5. pocengine
6. Ocaml-Expat-0.9.1
7. how to "disable" GC?

Archive: http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/99d07c3f2722cd35b8caeab9c00d5d8a.en.html

> In fact, I'm looking for a good (as simple and efficient as
> possible) algorithm of pattern matching.  Any suggestions, anyone?

There are hard trade-offs between simplicity, execution speed and
size of generated code.  However, the compilation scheme I used in
Caml Light is a reasonable starting point.  It was inspired by
Phil Wadler's chapter in Simon Peyton Jones's book "The implementation of
functional programming languages" (out of print, but a scanned version
is available from SPJ's Web page), and described in details in the
"ZINC report", http://pauillac.inria.fr/~xleroy/publi/ZINC.ps.gz

Luc Maranget has some papers describing much more sophisticated
approaches used in the OCaml compiler, if you find so inclined.
    

Thanks a lot for the references - and yes, that reminds me what I
forgot to mention:

If anybody is interested in a compiler of the complexity "between"
OCaml and MinCaml (and generating byte code or C), it may be good to
take a look at Caml Light, Camlot, or Bigloo.

  http://caml.inria.fr/distrib-caml-light-eng.html
    

Archive: http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/c2f161f0d98362e787fa3a553deb34f9.en.html

> AFAIK it doesn't force the GC to respect the dependencies. A object is
> garbage if it can't be reached from any root references, it doesn't 
> matter
> if other garbage objects still reference it. So if we have:
>
>
> ROOT -> A -> B -> C
>
> D -> E -> F
>
> G -> B
>
> H -> C
>
>
> the GC can collect any of [D, E, F, G, H], in any order it wants, 
> because
> they're all garbage. An incremental collector could collect first [F, 
> G, H]
> because they are (say) large objects, and don't recycle the memory for 
> [D,
> E] until the next collection.

As far as _collecting_ is concerned, the GC can do it in any order it 
wants,
and the current implementation is likely to do it in order of increasing
addresses (i.e. in some unpredictable order).

> IIUC the current OCaml GC implementation may exhibit such properties 
> (i.e.
> respect dependencies) but it isn't required to do so.

What I did specify and implement for 3.08 is the following:

If you call Gc.finalise on your values in the same order as they are
allocated, and if you don't introduce new depedencies afterward (with
assignments), then the finalisation functions will be called in the
right order (i.e. D before E before F, etc).

On the other hand, it means that a non-terminating finalisation function
must call Gc.finalise_release in order to let the GC run other
finalisation functions.
    

Archive: http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/8e2aab76580bd5f6f367ad1942c5e4f8.en.html

I am pleased to announce the release of ocamldap 2.1.0.  If you ever 
have to interact with an ldap server (or you need to write one), you 
can do now it in Ocaml in a highly painless way. Note, for those people 
who still believe that C is always faster (no one on this list I know, 
but I vent my frustration), I am proud to announce that in this release 
ocamldap's ldap decoder is faster than the one included with OpenLDAP 
2.2.x. Thank you INRIA for making a compiler/runtime that doesn't suck.

http://ocamldap.sourceforge.net/

Because I did not announce the release of 2.0 I will include the 
changelog back to 2.0.0.
2.1.0
    * ocaml-ssl is now required
    * BER Decoder
      - Improved decoding performance, 2x speedup. Beats OpenLDAP 2.2's
        decoder by about 5% (tested on PPC Mac OS X, and Intel Linux)
      - Fixed decoding of negative integers
      - Fixed decoding of error codes to comply with rfc2251. Unknown error
        codes will now be returned as `UNKNOWN_ERROR of int according to the rfc.
      - Fixed buggy decoding of ldap controls. They were not well tested
        until now, and several misinterpertations of the standard existed.
      - Fixed a bug which only happens when controls are asserted, some
        operations with optional values at the end would fail to decode
        when the control was present because of improper boundry setting.
        Boundries are now set at the end of each operation.
    * BER Encoder
      - Fixed several bugs in the encoding of two's complement integers
        where the sign bit was not being handled correctly. This never
        effected ldap clients, but severly limited the functionality of ldap
        servers. They would be unable to respond to requests with message id
        128, which would cause most clients to hang
      - Fixed discrepancies between the ldap_errorcode variant type, and the
        type recognized by encode_ldapresultcode. They are now the same type,
        and no exception can be raised, the compiler will now prove that client
        code doesn't send a variant which cannot be recognized.
    * ldap_funclient
      - Studied OpenLDAP's client library in depth, and adapted msgid
        allocation to look exactly like theirs. This will expose fewer
        bugs in ldap servers.
      - Changed the msgid type to an int32 (this should not be a visible
        change, it is an opaque type).
      - Refactored readbyte implementations, moved them to lber.ml, and
        tightened their exception handling.
    * ldap_ooclient
      - connect_timeout is now available as an optional argument to
        ldapcon.
      - added a method called "diff" to the ldapentry higharchy. It
        takes an entry and returns a list of differences between itself
        and the specified entry in the form of a modify record.
    * ldap_funserver
      - Deal with protocol errors according to rfc2251
      - Use the new readbyte implementations in lber.ml instead of a
        custom one
      - Implemented a logging harness. You pass in a function (optional) to
        init which takes a log level, and a string. The server will send your
        function log lines which exactly match the log format of OpenLDAP.
        The default function does nothing with the log lines. A parser for
        this log format is in the works and will be released as a seperate
        library.
    * LDIF Parser improvements
      - Improved the performance of write_entry, and to_string in Ldif_oo
      - Fixed a bug in the LDIF parser which could cause it to return
        the wrong line count when it finds a syntax error.
    * RFC 2252 schema parser/lexer
      - Fixed a typo in the lexer which would cause it
        not to correctly lex non numeric OIDs
      - Fixed bad lexing of X- attributes. There was an error in
        the definition of qdstring which would cause the lexer to eat
        all of the X- attributes in one pass. Tested fix
        with Active Directory 2003, OpenLDAP, and Novell eDirectory.
      - Changed the type of the attribute length field in the attribute
        record of the schema parser to be an Int64. The standard
        does not define the numeric range, and vendors
        (Novell) use huge numbers.
    * Schema Checker
      - Handled the case where the entry being checked does not have the
        objectclass attribute. Objectclass: top will be now be added in
        this case.
      - Fixed a bug in the "of_entry" method. It did not do a full schema
        check after importing the entry, so after calling of_entry the
        scldapentry was not proven to be valid.
    * Url Parser
      - Fixed a bug which could cause the url parser to return the wrong
        hostname if the hostname specified contained illegal characters.
    * Error Handling
      - moved err2string to a new module Ldap_error, which will contain
        functions for doing various things with LDAP_Failure exceptions.
        This WILL break existing applications which use err2string,
        however it is a simple matter of opening Ldap_error to fix them.
      - Implemented ldap_perror, and ldap_strerror functions, which
        either print, or return nicely formatted strings describing an
        LDAP_Failure exception.
2.0.3
    * Handle additional Unix_error exceptions as reconnection events,
      including EPIPE, ECONNRESET, and ECONNABORTED. Not handling these
      exceptions caused the library not to autoreconnect when the connection
      was dropped under certian circumstances.
2.0.2
    * Fixed a bug in the way delete was encoded which prevented it from working
2.0.1
    * Fixed a major bug in async calls.
2.0
    * Complete reimplementation of the low levels.
      - Pure Ocaml lber, and ldap protocol implementation. Ocamldap is
        no longer a C binding.
      - Server side as well as client side encoding/decoding
        functions. You can now make ldap servers with Ocamldap,
        as well as be a client!
      - No code optimization has been done yet, however the decoding
        performance is within 50% of the C library on the same hardware!
        Encoding performance has not been tested yet.
    * Some api changes to support additional error information, referrals
      and enhanced client side reliability. Minimal OO api changes,
      fairly significant lower level api changes
    * Module name reorganization. Painful, but it can only get worse
      if we let it stay the way it was. These two changes are the main
      reason for the 2.0 stamp.
    * Greatly simplified build system
    * All portions of the library are now covered by the LGPL license
    

Archive: http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/7ae599360e1c47901e580017be59124b.en.html

For anyone who is interested: following a post on comp.lang.functional asking 
for a 2D maze generator, I wrote a little OCaml program to generate random 2D 
mazes, render them using OpenGL and generate PostScript output. The program 
is available here:

  http://www.ffconsultancy.com/free/maze/

Hopefully this will serve as an intermediate between the ackermann function 
and min-caml for people wanting to learn OCaml. ;-)
    

Archive: http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/a6d8327f4976ef14a6453df1bcf9dab7.en.html

After having developped the game Battle For Rashitoul (http://rashitoul.net),
I started to write a game engine to help us creating more games more easily.
The engine is written mainly in Ocaml with some XML and LUA.
After some years of work, a first working version has been released
with a sample game: duck hunt. For more information, here is the link:
http://williamkramps.rashitoul.net/pocengine
(the website is only in French for now but the code is in English)
Feedback is most welcome!
    

> I am just curious. Are you using the C implementation of Lua? There is 
> also an OCaml of Lua, albeit only for Lua 2.5. I am using it for my own 
> projects.
> 
> http://www.cminusminus.org/code.html#luaml

I'm using the very good OCaml implementation, because interaction with lua data
is easier and Lua 2.5 is suffisant for our needs
    

Archive: http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/49c43fbb933075e4183e4314f3209d95.en.html

I'd like to announce Ocaml-Expat-0.9.1, Ocaml bindings for the Expat XML 
Parser.

http://www.xs4all.nl/~mmzeeman/ocaml/
 
Support was added for XML_SetBase, XML_GetBase and 
XML_ExternalEntityParserCreate.
    

Archive: http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/eaca75b29d80b5dd3d3ed34cbf7e7afe.en.html

I'm trying some very unfair:-) comparisons between OCaml and MinCaml
(min-caml.sf.net), and wondering how to _disable_ GC in OCaml (on
SPARC).  I've tried

  setenv OCAMLRUNPARAM 's=1000000000,v=0x1ff'

and its variants, but none of them seem to stop GC from happening -
and once it happens, it's MUCH slower of course!  By the way, the
machine has 8GB main memory.

So, my questions are:

1. How does the GC happen at all when the minor heap is so huge?  The
   programs don't seem to use so much memory anyway...

2. Some programs get much slower for larger heaps, even though they
   don't seem to trigger any GC.  An example is such programs is given
   below.  Why is this?  (There also exist programs that are not
   affected at all, so this is not because of the initialization
   overhead of the runtime system.)

(**********************************************************************)
let rec tak x y z =
  if y >= x then z else
  tak (tak (x -. 1.0) y z) (tak (y -. 1.0) z x) (tak (z -. 1.0) x y) in
let n = 10.0 in
print_int (int_of_float (1000000.0 *. tak (n *. 3.0) (n *. 2.0) (n *. 1.0)));
print_newline ()
(**********************************************************************)
    

Quite in general, Cache hierarchy may be an issue here. The CPU can only 
hold a small amount of data in its L1 cache, which is quite fast. Next, 
there are L2 and then L3 caches (should you have that), but if you have to 
do a lot of real memory access, that usually will kill you. Especially if 
your address space is so badly scrambled that the CPU constantly needs to 
re-load its address translation cache (called translation lookaside buffer 
for x86). Worst case situation on a 3-level MMU system is that you will
have to do four memory reads for one word of data.

So, as a quite general rule when doing computationally challenging 
algebraic stuff in a functional language: try hard to design your data 
representation in such a way that you minimize RAM access. If you can 
e.g. encode short lists of small integers into a fixnum-integer, then do 
so. A few shift and masking operations do not matter much for many 
pipelined processors, provided the code can be held in the cache. Memory 
access does. One can overdo it, though: if you need ten times more code to 
get rid of a simple memory access, you're on the wrong track. Code also 
has to be transported to the CPU core.
    

> Quite in general, Cache hierarchy may be an issue here.

This is right, but let me clarify my question: Why is _anything_
heap-allocated, for example in the program below (given in my previous
message)?  According to the assembly and intermediate code in
ocamlopt, there is indeed something heap-allocated in the else-clause
of tak, but I don't know what this is for...  Are floting-point
numbers heap-allocated in ocamlopt on sparc??

| (**********************************************************************)
| let rec tak x y z =
|   if y >= x then z else
|   tak (tak (x -. 1.0) y z) (tak (y -. 1.0) z x) (tak (z -. 1.0) x y) in
| let n = 10.0 in
| print_int (int_of_float (1000000.0 *. tak (n *. 3.0) (n *. 2.0) (n *. 1.0)));
| print_newline ()
| (**********************************************************************)

> setenv OCAMLRUNPARAM 's=1000'
> time ./tak.ocamlopt
11000000
3.54u 0.01s 0:03.56 99.7%
> setenv OCAMLRUNPARAM 's=1000000000'
> time ./tak.ocamlopt
11000000
6.83u 1.50s 0:08.80 94.6%
    

> > Are floting-point numbers heap-allocated in ocamlopt on sparc?
> 
> Yes, I believe FP values are boxed on all platforms. You could
> try keeping your values in an array, and see if that makes any
> difference.
> 
> Also, see http://caml.inria.fr/archives/200501/msg00125.html
> and related messages.

I see - so it seems to me that FP numbers are heap-allocated at least
when they are passed or returned as function arguments or results (to
support polymorphism, I suppose).  This explains well the behaviors of
ocamlopt (and its GC) that I've been experiencing.  Thanks for the
information!
    

>   setenv OCAMLRUNPARAM 's=1000000000,v=0x1ff'
>
> and its variants, but none of them seem to stop GC from happening -
> and once it happens, it's MUCH slower of course!  By the way, the
> machine has 8GB main memory.
>
> So, my questions are:
>
> 1. How does the GC happen at all when the minor heap is so huge?  The
>    programs don't seem to use so much memory anyway...

Look for "caml_check_urgent_gc" in the runtime sources and you'll see
that minor collections can be triggered even if the minor heap is not
full if needed, in order to do a slice of major GC.

So if you allocate some things that go directly into the major heap
(for example reasonably large arrays or strings) you need a big major
heap as well as a big minor heap:

   setenv OCAMLRUNPARAM 's=500M,h=500M,v=0x1ff'
    

Using folding to read the cwn in vim 6+

Here is a quick trick to help you read this CWN if you are viewing it using vim (version 6 or greater).

:set foldmethod=expr
:set foldexpr=getline(v:lnum)=~'^=\\{78}$'?'<1':1
zM

If you know of a better way, please let me know.

Old cwn

If you happen to miss a CWN, you can send me a message and I'll mail it to you, or go take a look at the archive or the RSS feed of the archives.

If you also wish to receive it every week by mail, you may subscribe online.

Alan Schmitt