[gecode-users] Peak memory and recomputation

[Christian Schulte]

Hmmm, that looks strange but not necessarily a bug: due to last alternative
optimization it might be that c_d = 4 is a lucky case. But I will look more
closely into it as soon as I have time.

Christian

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

-----Original Message-----
From: Grégoire Dooms [mailto:dooms at info.ucl.ac.be] 
Sent: Saturday, April 01, 2006 11:06 AM
To: schulte at imit.kth.se
Cc: users at gecode.org
Subject: Re: [gecode-users] Peak memory and recomputation


Christian Schulte wrote:
> What values did you use for a_d: adaptive recomputation might kick in 
> an use some memory for intermediate copies?
No I set it to 1000 to not have to bother about it.
>  For a discussion of that see my PhD
> thesis ;-)
>   
I did. Figure 7.6 page 66 confirms the intuition that increasing 
recomputation distance monotonically decreases the memory consumption.

With the previously attached problem, a_d=1000 c_d=1 to 10 gives the 
following peak memory: 17, 13, 9, 1, 8, 8, 8, 7, 6 (the number of 
commits grows monotonically until it stabilizes at c_d=10 which seems to 
indicate full)

With c_d = 4, varying the number of solutions searched (with -solutions 
on the command line) affects the memory a lot: for solutions in [1,563], 
memory is 8kB while when solutions is in [564,567], memory is 1kB.

This is very strange. I don't know how peak memory can decrease between 
the time the search engine finds the 563th sol and the 564th.

The same shifts appears when running the program with size 4 and c_d=4 : 
somewhere in between the 66000th and 67000th solution memory drops from 
13kB to 1kB. The number of solutions is 67689.

Trying all c_d from 1 to 22 gives (on size 4):
31, 1, 16, 1, 1, 1, 11, 1, 1, 1, 10, 10, 1, 10, 10, 10, 9, 9, 8, 8, 8, 8
here the number of commits is not monotonic: 135376, 157852, 185875, 214639,
256635, *256151*, 328674, 419662, 
*368716, 327912, 307864*, 323726, 389382, 529974, 753642, 1003034, 
1015057, 1015803, 1015875, 1015875, 1015875, 1015875.

Am I missing something or this looks like a bug ?

Best,
--
Grégoire


> All the best
> Christian
>
> --
> Christian Schulte, http://web.imit.kth.se/~schulte/
>
>
>
>
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On 
> Behalf Of Grégoire Dooms
> Sent: Friday, March 31, 2006 4:35 PM
> To: users at gecode.org
> Subject: [gecode-users] Peak memory and recomputation
>
>
> Hello,
>
> I have observed the following effect which seems counter-intuitive to
> me: Using less recomputation can save memory.
> Can you help me figure out what happens ?
>
> The attached file models this simple problem using sets: generate all
> subgraphs of a complete labeled digraph (with loops).
> The following runs are done with increasing fixed recomputation 
> distance, very high (1000) adaptive distance and size 3.
> The depth of the search tree  is from 9 to 12 (depending on the
solutions).
>
> I observe that with c_d = 4, the peak memory is much lower than with 3
> and 5:
>
> When running it with -c_d 3, I get:
> Summary
>         runtime:      10
>         solutions:    567
>         propagations: 2449
>         failures:     0
>         clones:       566
>         commits:      1548
>         peak memory:  9 KB
>
> With -c_d 4 :
> Summary
>         runtime:      0
>         solutions:    567
>         propagations: 3167
>         failures:     0
>         clones:       566
>         commits:      1848
>         peak memory:  1 KB
>
> With -c_d 5 :
> Summary
>         runtime:      10
>         solutions:    567
>         propagations: 3648
>         failures:     0
>         clones:       566
>         commits:      1935
>         peak memory:  8 KB
>
>
> Best,
> --
> Grégoire Dooms
>
>
>
>
>