[mercury-users] Circular lists
Henk Vandecasteele
henkv at cs.kuleuven.ac.be
Thu Nov 27 23:19:11 AEDT 1997
Richard A. O'Keefe wrote:
>
> So what happens if you get stuck with an application Mercury
> does not give you the speed you need, and I am speaking of orders
> of magnitude!
>
> Show me one where (decimal) orders of magnitude are involved.
> (Binary orders of magnitude can easily show up in C with the
> same code compiled by different compilers.)
The application: A finite domain CLP solver.
In such a case a domain must be maintained for each finite
domain variable, also a list of constraints, to be actived when
a domain changes, must be maintained. During the search choices are made
and as a consequence of the choices the set of constraints and the
domains change. On backtracking these changes have to undone.
Mercury before 0.7.2 could only offer a data-stucture with
logarithmic access to the domains of variables and the constraints
connected to the variables, logarithmic in terms of the number of
finite domain-variables.
For such an application you want constant access in time.
But maybe worse, an update of the data-stucture will consume
memory proportional to the log(number of variables)* mean number
of constraints per variables.
As the number of finite domain variables can be quite large,
you can image the execution time will orders of (decimal) magnitudes
larger in such a pure implementation. This has been proven by
experiments.
> If you want dangerous things to happen quietly,
> if you don't want to make INFORMED choices about safety,
If I use the C-interface to implement things which cannot be done
efficiently in Mercury then probably it will be dirty. If such a
checker would be added it will always generate warnings.
So I won't look at it and probably find it annoying.
Of course this is only one application of the C-interface, in other
cases it could be usefull.
> if you assume that speed and safety cannot be had together,
not always I guess. But hopefully in most cases.
> then we have nothing to say to each other.
Henk
More information about the users
mailing list