[Choco-users] Choco Speed

[Mark U. <ma...@cs...>]

Hi,

I am working for a commercial company (Leirios Technologies), using CLP
techniques with multiple constraint solvers for test generation purposes. 
We have been using SICStus Prolog clpfd for the integer solver, but are
investigating the possibility of using Choco/Java instead.
[
 because we need an integer solver that we can closely integrate with
 our other solvers -- eg. we want to modify the integer solver to
 communicate with the other solvers whenever it reduces the domain
 of an integer variable.
]

I've used the N queens problem (ALL solutions -- details below) to
benchmark various integer/finite-domain solvers to compare their basic
efficiency of triggering constraints, labeling and backtracking.

RESULTS                N = 4   5   6   7   8   9   10    11    12    
13    14
=======
SICStus Prolog clpfd:      0   0   0   0   0   0   .1    .5   1.8   
8.7    47
 (compiled with 3.11.2)
Choco/C++ (Claire)         0   0   0   0   0  .1   .3   1.5   7.6  
42.8   248
 (Choco1.326, Claire3.3.40)
Choco.sf.net/Java client  .3  .3  .4  .5  .6 1.1  3.1  12.2  64.0 396.0  
2002
 (choco-0.9, JDK 1.4.2_03)
Choco.sf.net/Java server  .4  .4  .4  .8 1.2 2.1  3.8  10.3  44.2 226.2  
1323
 (choco-0.9, JDK 1.4.2_03 -server)
CHR with domain.pl        .5 5.0 265 --- --- ---  ---   ---   ---   
---   ---
 (SICstus chr/examples/domain.pl)
          
Ratio of ChocoJava(client) / ChocoC++ :       14   10   8.2   8.4   
9.3   8.1
Ratio of ChocoJava(server) / ChocoC++ :       26   12   6.9   5.8   
5.3   5.3


CONCLUSIONS
===========
1. ChocoJava is about 8-9 times slower than the earlier C++ version!
   (Or 5 times slower if you use the Java server JVM,
    rather than the default client JVM).

2. SICStus clpfd is very fast in comparison to both versions of Choco.
   (but it is also very complex and hard to extend with hooks so that it can
    be integrated more closely with other solvers -- this is why we are
    looking for alternatives).


QUESTIONS
=========

1. How much of this slowdown is because the Java version is relatively new
   and not yet optimized, and how much is due to Java versus C++ speed?

2. Is this slowdown a known issue? 
   Are there ideas/plans for improving performance?

3. Is Choco.sf.net likely to be a good option for us, if we want to use
   just its integer solver, but extend it with hooks to report changes
   in domains etc?


BENCHMARK DETAILS: All the versions of the N queens are similar,
   with N membership constraints (Qi in 1..N)
   and 3*N*(N-1)/2 inequality constraints (Qi /= Qj + k)
   Then I'm using labeling (backtracking search) to produce ALL solutions.
   This was done on a Pentium 4 2.8GHz with 1G ram, running Windows XP.
   The Java JVMs were run with the default memory size.
   The Claire Choco was run with -s 6 6, which I think sets its max memory
   size to about 64Mb -- it uses much less than that.


Thanks!
Mark.

Senior Lecturer, Department of Computer Science
The University of Waikato, Private Bag 3105, Hamilton, NZ.
http://www.cs.waikato.ac.nz/~marku