Re: [eclipse-users] Stack overflow in simple example

From: Joachim Schimpf (Independent Contractor) <jschimpf_at_cisco.com>
Date: Tue, 01 May 2007 01:04:38 +0100
DougPatterson.49193539_at_bloglines.com wrote:
 >...
> I also noted that:
> 
> [eclipse 68]: Xs :: [0, 9^9]
 >
> Xs = Xs{[0, 3874200489]}
> Yes (0.14s cpu)
> 
> takes measurably longer to run than:
> 
> [eclipse 69]: Xs :: [0..9^9].
> 
> Xs = Xs{0 .. 387420489}
> Yes (0.00s cpu)
> 
> Why is that?

Because the first one uses much more memory, which also
explains your stack overflow:

% a domain with only 2 elements, far apart
?- X :: [0, 9 ^ 9], statistics(global_stack_used, Bytes).
X = X{[0, 387420489]}
Bytes = 48429000
Yes (0.31s cpu)

% a domain containing all integers between 0 and 9^9
?- X :: 0 .. 9 ^ 9, statistics(global_stack_used, Bytes).
X = X{0 .. 387420489}
Bytes = 2720
Yes (0.00s cpu)


lib(ic) stores with every domain variable a representation of its
domain, i.e. the values the variable can (still) take.  If this is
a simple interval like 0..387420489, then only the lower and upper
bound are stored.  As soon as the domain has "holes", a bitmap is
used to represent the possible/impossible values, which can take a
lot of space for large domains.  This was an implementation choice
for lib(ic), which favours pure interval domains and discrete domains
of medium size.  You should either choose a different problem model,
or try the older lib(fd), which uses a list-of-intervals representation
and has different performance characteristics.


-- Joachim
Received on Tue May 01 2007 - 01:04:34 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET