[Gecode] Memory management, where to alloc?

[Christian Schulte]

Well, let me elaborate a little bit on 1). This is just for caching and the
reason why it works well is subtle and relies on interaction (well, a
certain discipline) with search:

A propagator can have a cache. The cache is created on demand from some
other datastructure conatining the variables of interest (such as an
VarArray<*>). Each time the propagator is invoked, it checks wether there is
a cache. If not, it creates one. If there is already a cache, the cache is
updated to properly represent the modified variables. Propagation then is
performed on the cache.

When a propagator is created or copied, the cache is empty.

It is the propagators responsibility to delete the cache. This must be done
in the propagator's destructor. By default, destructors of propagators are
not called when a space fails. In order to enable it, you have to use
Propagator(true) as constructor (also the derived propagators take a boolean
argument, where true means delete on failure). This guarantees that the
destructor is called always, even if a space fails.

What makes the scheme work are the two following invariants:
 1) The cache is only constructed when the propagator is invoked. That is,
in a newly cloned space all caches
    are empty and require no space.
 2) Search engines must maintain that there is only one space on which
computation is performed. So,
    when cloning a space this space must be stored as backtrack point
(remember, empty caches). Search must
    continue with the original space (possibly non-empty caches).

Currently search engines must follow this protocol strictly. If that turns
out to be a problem (which I don't believe at all), then we need to equip
propagators with a flush method, just flushing the cache.

So, please consider whether 1) does the job. It works well. The variable
doubling is not an issue for two reasons:
 1) A variable (you mean a view actually) takes 4 byte.
 2) There is just one cache per search engine and per propagator created.

Otherwise, there is no need to use freelists. As you rightly say, the lists
shrink. That's fine. Freelists are very special beasts (there are only size
8 and 16 freelists). Don't use them if you don't have to. I use them for
rangelists as they have the property to grow and not to shrink.

Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 

-----Original Message-----
From: gecode-bounces at ps.uni-sb.de [mailto:gecode-bounces at ps.uni-sb.de] On
Behalf Of Guido Tack
Sent: Friday, June 18, 2004 1:00 PM
To: Technical Discussions about Gecode
Subject: [Gecode] Memory management, where to alloc?


Hi.

I'm trying to understand the whole memory management issue better. I'm at
the 
moment reimplementing the selection constraints, based on Christian's idea
to 
use a list rather than an array to store the variables (similar to his 
element propagator).
I'm considering three alternatives:
1) Use Memory::malloc, as in IdxValMap (element constraint), consider the
list 
just a cache and recreate it each time the propagator is copied
2) Use Space::alloc, with the list as the only data structure
3) Use FreeList, with the list as the only data structure

I think we just have to consider 2 and 3, as 1 would effectively double the 
space needed for the variables.
As the lists only shrink, 2 might be ok.
3 would let us reclaim the memory a little more dynamically, I guess.

Are there any drawbacks with the free list managed things? If not, I'd go
for 
that, I think.

Guido
_______________________________________________
Gecode mailing list
Gecode at ps.uni-sb.de http://www.ps.uni-sb.de/mailman/listinfo/gecode