[gecode-users] Profiling examples using the Common Lisp Gecode wrapper

[Guido Tack]

Gustavo Gutierrez wrote:

> On Thu, Feb 21, 2008 at 2:52 AM, Mauricio Toro <mauriciotorob at gmail.com 
> > wrote:
>> Hello,
>>
>> I am doing some profiling to gecode examples under the Common Lisp  
>> wrapper.
>> For the examples alpha and eq20 it takes around 5 to 10 times more  
>> to be
>> executed.
>> But, when running queens with size = 30 it takes around 100 times  
>> more time
>> to be executed.
>>
>> What could be happening?
>
> That could depend on many things. Maybe you are introducing some
> overhead by the layer you are developing between CL and gecode, that
> is not for free. It may also depends on the CL implementation. My
> pinion is to see how much overhead occur when you take the same
> problem and change the size, queens is a good example for this. Try
> Queens with n=10, n=15, etc. and try to devise some constant relation
> between gecode and CL results. That constant relation can give you an
> impression f the overhead introduced. If that relation is not constant
> maybe there is something wrong with your implementation.

Not necessarily.  If search is done within Gecode, the overhead is  
entirely in the problem setup.  If, e.g., creating an IntVar through  
the wrapper is expensive, then scaling up the problem size will result  
in a bigger and bigger gap between native and wrapped solver.  If the  
wrapper does a lot of work in order to extract the values of the  
variables each time a solution is found, this may also be a  
significant factor.

One thing to watch out for is that the wrapped solver actually  
executes exactly the same problems.  E.g., are the IntConLevel  
arguments translated properly? Are the c_d and a_d arguments for the  
search engines the same?

Another thing is memory management.  How often are things copied  
around when passing them through the interface?  Are spaces freed  
early, or are they kept alive for too long (which might cause trashing)?

Then, finally, how do you measure the run time?  Our strategy is to  
run each problem a certain, problem-specific number of iterations, and  
then divide the overall runtime by the number of iterations to get the  
time for a single run.  That way you make sure that the resolution of  
the timer is actually accurate enough for your measurements.  In  
addition, we do these measurements for a number of samples, so that we  
can compare the coefficient of deviation, to make sure that we used  
enough iterations.

If all else fails, you'll have to run a version of your wrapped solver  
that was configured with profiling turned on (-pg switch for gcc), and  
then use gprof to find bottlenecks.

> Just a hint, be careful you built gecode without debugging support.

That's a very valuable hint, we've gone into that trap many times  
ourselves ;-)

Cheers,
	Guido

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2436 bytes
Desc: not available
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20080221/f9c0bd27/attachment.bin>