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.