[mercury-users] New to mercury: structure reuse and efficiency

[Ralph Becket]

diffense, Monday, 21 June 2004:
> Hi,
> 
> I'm just discovering mercury and I am very intrigued. I think it's one
> of the most elegant programming language I've ever seen. However, the
> c++ programmer in me is worried about the inefficiency that can result
> from frequent copying of datastructures. 

A few years ago I re-implemented the SPEC95 LZ compression benchmark
(129.compress, IIRC) which ran at about 66-77% of the speed of the C
implementation (the Mercury compiler might even do better than that
these days), which is so highly hand tuned that it might as well be in
assembly language.  If you need that level of performance, it's quite
possible to obtain it in a Mercury program.

You can code in an imperative fashion in Mercury (see e.g. the array.m
and store.m library modules, which should run at the same speed as
arrays and pointer graphs in C, modulo bounds checking etc.), although
it isn't necessarily comfortable to do so.  The thing is that then you
have all the problems that go with imperative programming, which often
necessitates making *explicit* copies of data structures.

Except for rare cases we simply don't notice performance as a problem in
practice.

> I have been reading papers on comple time garbage collection and
> structure reuse which date back from the late 90s. They suggest that
> work was well under way to include these optimizations into the
> compiler. I'm curious as to whether features such as automatic
> inference of di and ui modes and well as structure reuse have been
> implemented in the compiler yet. I'd really like to be able to learn
> mercury programming in the most natural way without worrying
> excessively about efficiency. Furthermore, I intend to use it for
> applications where efficiency will be important.

Nancy Mazur has been working on structure reuse for her PhD and I
believe this work is nearly complete; this work currently resides in an
experimental branch of the compiler source tree.

My next major project is to fix mode analysis so that the compiler
properly supports uniqueness.  The challenge here is to make the
analysis fast enough that it doesn't make the compiler unacceptably
slow.  We've had two previous attempts at tackling the problem (the
analyses worked, but were too slow) and I believe I now know how to do
it efficiently.  My aim is to have this working by the end of the year.

My sincerest advice is to not worry about efficiency: if you're going to
use a purely declarative language, we reckon Mercury is as good as
anything else that's out there.  In my experience, success comes from
first getting a naive, working program, then using the profiler to
identify where optimization effort should be spent.

-- Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------