Dynamic allocation

32 views
Skip to first unread message

marcus...@gmail.com

unread,
Jun 23, 2022, 11:50:15 AM6/23/22
to Gecode
Hi all,

I have a question to Gecode's creators :

I would like to know if Gecode can work in constrained memory space ?

Also, could we make it work :
1) by doing one and only one dynamic memory preallocation
2) or, by using only static memory allocation

And make him solve several different problems in this way.
If it is not possible in the state, what would be the effort to provide?

Thanks for your help,
Marcus

Mikael Zayenz Lagerkvist

unread,
Jun 27, 2022, 2:54:54 AM6/27/22
to gec...@googlegroups.com
Hi,

In general, Gecode has no support for working within a set amount of
memory. Any backtracking search (whether it is Gecode, some other
constraint programming system, or some other type of solver for
combinatorial problems) may need memory that is proportional within
some constant to the depth of the tree, and the representation of the
problem will naturally depend on the size of the problem. Neither of
these are knowable beforehand, so the simple answer is that it is not
possible.

There are some things that you can do though that might work well
enough depending on the problems that you solve:
* You can change the memory allocator that Gecode uses to one that
allocates from a pre-allocated slab of memory, and fails if Gecode
requests more memory than what is available.
* By changing the copying distance and the adaptive copying distance
to very large numbers, you can ensure that the search engine
essentially only keeps the root Space and the current Space used for
exploration. This will be a full recomputation search, which might
take more time, but might also be usable still.

See more about memory and search configuration in MPG.

Cheers,
Mikael
> --
> You received this message because you are subscribed to the Google Groups "Gecode" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to gecode+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/0e9174a0-7d1e-420f-81dc-4a39a584ab6an%40googlegroups.com.



--
Mikael Zayenz Lagerkvist

Marcus Vilain

unread,
Jul 13, 2022, 5:41:11 PM7/13/22
to gec...@googlegroups.com

Hi,


Thank you for this expertise. It basically corresponds to what I imagined and I think it can actually work. 


The challenge is interesting and stimulating (eg, creating a memory allocator.  I actually imagine that during a resolution, deallocations can occurs and these deallocations/reallocations in a pre allocated memory space is not so simple. Such an allocator in open source can already exists)


I would like to be able to deal with this subject but it is not a priority for the moment.


Thanks,

Cheers,

Marcus 


Reply all
Reply to author
Forward
0 new messages