[gecode-users] Analysing search performance

[Christian Schulte]

You can build Gecode also as static libraries: then profiling should be
easier.

And please make sure that the search space is really the same! Count the
nodes in both approaches and check that they are the same or at least in the
same order of magnitude. Otherwise you might be hunting ghosts.

Another thing is recomputation: do you use it? Is memory an isssue for your
application?

All the best
Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 

-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Lars Otten
Sent: Wednesday, March 01, 2006 5:53 PM
To: users at gecode.org
Subject: Re: [gecode-users] Analysing search performance


Hi all,

On 02/28/06 09:01, Christian Schulte wrote:
> For the time being, the only support you can get is by using a 
> standard C++ profiler. If you are using gcc for compiling just use 
> gprof the see what is happening. In order to compiler for gprog you 
> have to give -pg as option for gcc (just check the gcc doc).

Thanks to Guido and you for the hints. I did some reading about profiling:
The problem with gprof is that it only profiles the main executable but not
shared libraries -- or if it does, it's so cumbersome I couldn't get it to
work...

After some searching I came across oprofile [2] which seems to do the job
quite nicely, eve without any special compilation flags. I attach the first
few lines of the (filtered) system-wide profile of running my program for
some minutes. It seems that most of the time is spent cloning spaces,
specifically in Gecode::ViewArray<...>::update(...)

This is (percentage-wise) a lot more than what I get when I run e.g.  $
queens -c_d 1 -solutions 0 -mode stat for some minutes, but then again it's
a different problem so this comparison might not mean much.

> Did you at least check the search space? That is, how big is the 
> search tree with what you have and how big is that in [1]. If you are 
> talking vastly different trees there is no point in alayzing 
> performance but your model.

The underlying model I employ is (almost) the exact same as in [1], so in
principle the search trees should be very similar. I'm also using (almost)
the same variable/value selection heuristics. I just left out some more
complicated constraints, but I feel that shouldn't make such a difference
(rather it should make the problem easier).

Nevertheless I will talk to Mattias, the author of [1], to find out if there
are any major discrepancies I might not be aware of.

I will also migrate my changes to the fresh version 1.0.1, although the
changelog does not contain anything I'd relate to my observations.

Cheers,
/Lars

[1] http://publications.lib.chalmers.se/records/full_record/6207.html
[2] http://oprofile.sf.net/