Hello
Here is the latest Caml Weekly News, for the week of 08 to 15 March, 2005.
Archive: http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/99d07c3f2722cd35b8caeab9c00d5d8a.en.html
Eijiro Sumii asked and Xavier Leroy answered:> 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.Eijiro Sumii added:
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
Deep in this thread, Daniel Yokomizo asked and Damien Doligez answered:> 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
Eric Stokes announced: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
Jon Harrop announced: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
Julien Boulnois announced: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!Christian Lindig asked and Julien Boulnois answered:
> 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
Maas-Maarten Zeeman announced: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
Eijiro Sumii asked: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 () (**********************************************************************)Thomas Fischbacher answered:
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.Eijiro Sumii then asked:
> 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%Kurt Welgehausen answered and Eijiro Sumii said:
> > 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!Damien Doligez answered the OP:
> 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'
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.
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.