[mercury-users] Re: (the lack of) unique modes

Fergus Henderson fjh at cs.mu.OZ.AU
Fri Nov 5 03:38:25 AEDT 1999


On 03-Nov-1999, Tomas By <tomas at research.nj.nec.com> wrote:
> 
> There is a program I'm writing that uses a database, implemented in
> the following way (the xxx's are self-defined types that only contain
> simple things like ints and strings).
> 
> | :- type state ---> state(map(int,c),int,map(int,d),int).
> |
> | :- type c ---> c(bool,string,set(int),xxx).
> |
> | :- type d ---> d(bool,string,xxx,xxx,maybe(pair(string,a)),xxx).
> |
> | :- type a ---> a(map(int,xxx),map(string,set(int)),
> |                  map(int,set(int)),map(int,set(int)),
> |                  map(int,set(int)),int,int,set(string),int).
> 
> In general, there will be many items in the maps in the a's but not
> that many a's and d's and only a few c's (typically just one).
> 
> The `state' is threaded through the code using the modes `in' and `out'.
> 
> After not very long the program gets very very slow, and it uses a lot
> of memory. I assume this is because there is a lot of copying going on
> and that using unique modes instead of `in' and `out' would be a good idea.

Sounds likely, but I suggest you try profiling your program
with both time profiling and memory profiling (including
calling io__report_full_memory_stats from the end of main/2),
so that you can be sure about what is slowing it down.

> But the `LIMITATIONS' file says that unique modes are not fully
> implemented, so my question is: would the functionality that unique
> modes currently have help me and if not, how likely is it that you
> will implement it fully?

Yes, unique modes would probably help.  If all of those map(int, ...)
are dense, then you could use arrays rather than maps.  That would
probably help a lot.

It is quite likely that we will implement nested unique modes sometime
soonish, i.e. within the next year.  (No promises, of course...)

However, there will still be some issues with regard to unique modes
and polymorphic types; if you're using polymorphic data structures such
as `map' then you may need to add additional mode declarations for
your particular use (which would thus require cut-and-paste reuse of the
`map' module).  Solving that is still a research issue, so I couldn't
give any ETA for that one.

There's some other things you could try that might improve
efficiency in the absence of unique modes.  If those int maps are
dense, you could try using `bt_array', or implementing version arrays
and using them.  Or you could try using `array' and using
`unsafe_promise_unique' (in the `builtin' standard library module)
to work around the cases where the compiler's uniqueness analysis is
overly conservative.

Also, we've also been doing some other optimizations that may improve
performance for programs like that.  Our latest development version
includes improvements to the efficiency of compare/3 on polymorphic
types, which is used heavily by the `map' implementation.
We've also added support for user-guided type specialization, so
that you can add pragmas to get the compiler to specialize such
polymorphic data types for the particular cases that you use,
thus avoiding the costs of polymorphism.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------



More information about the users mailing list