[gecode-users] performance issues

[Christian Schulte]

Hi Kish,

Yes that can be the case. The difference in efficiency actually is not
related to the variables themselves.

If you post constraints on the IntVars before their domain is reduced to
0..1 then some propagators might have to resort to a less efficient
representation. The difference can range from anything like 10% (linear
constraints, for example) to 50% (extensional constraints, for example). 

But do you post Gecode constraints on these IntVars? I would guess that
you'd post Gecode constraints on the channeled BoolVars instead. If the
latter is the case then I would not know where the difference in performance
could come from.

Cheers
Christian

--
Christian Schulte, web.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Kish Shen
Sent: Wednesday, July 14, 2010 8:56 PM
To: users at gecode.org
Subject: [gecode-users] performance issues

Hi,

I have been doing some comparisons between the updated code for the 
ECLiPSe interface to Gecode with the old code. The main changes in the 
new code is to deal properly with various forms of expressions at the 
ECLiPSe level, and I did not expect much changes to the calls made to 
Gecode.

I was therefore a little surprised that one example (roster example from 
ECLiPSe's web page) seem to show that the old code was measurably and 
consistently faster than the new code -- it is about 10% faster. This 
example does part of its search using Gecode's search engine, and part 
of it in ECLiPSe (where variables are labelled with values in ECLiPSe, 
but the propagation of such labelling is still done via Gecode). The 
execution time should be dominated by the search/propagation, so it 
seems very likely that the increased execution time is from Gecode, and 
not from ECLiPSe. The same Gecode libraries are used in both.

Looking at the way Gecode is called, the only difference I noticed is 
the way boolean variables are treated. In our interface, BoolVar is 
always linked to an IntVar, connected via a channel constraint, and
the variable is always accessed via the IntVar, which is linked to an 
ECLiPSe variable.

The difference in the new code is that the IntVar is created with an 
initial domain of -1000000 to 1000000, and then the domain is 
immediately reduced to 0..1. In the old code, the IntVar is created with 
an initial domain of 0..1. In both cases, the IntVar is linked to the 
BoolVar after this.

I remember the modelling manual stated variables with large domains will 
be less efficient. Can this explain the slowdown in the performance, 
even though the variable's domain is immediately reduced to 0..1?

Thanks in advance for any information!

Cheers,

Kish

-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users