[gecode-users] Analysing search performance

[Lars Otten]

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/


-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: prof.txt
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20060301/e655ba27/attachment.txt>