Re: [eclipse-clp-users] Integer Set Library: Performance related to initial domain size?

Ulrich Scholz wrote:
> Dear Marco and all,
> 
> some simple tests show that the performance of the fd_sets library is
> related to domain size:
> 
> Consider the three clauses below.  All require a non-empty set to have an
> empty intersection with itself, thus they all should fail.
> 
> t1 does not fail but yields delayed goals.  So to detect the inconsistency,
> we have to search for a solution.
> 
> t2 does this search and fails as expected.
> 
> t3 is the same clause as t2, with the difference of using a largely extended
> domain.  Unfortunately, the inconsistency is found much slower that for
> clause t2.

Sorry for not joining the discussion earlier.  As you noticed, the solution
time is dependent of the domain sizes.  This is because in {fd,ic}_sets the
domains are represented with a flag for each element that indicates whether
the element is included the set, excluded from the set, or unknown.
At the beginning of the computation, membership for every element is unknown,
and at the end every element is decided.  So (at least in the success case),
every element membership flag must be set in the course of the computation,
therefore the time is proportional to the domain sizes.

It would be quite a nice project to change the representation such that ranges
of elements can be included/excluded in constant time!


-- Joachim