[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 --------------
samples  %        image name               app name                 symbol name
680895   32.2674  libgecodeset.so          libgecodeset.so          Gecode::ViewArray<Gecode::Int::IntView>::update(Gecode::Space*, bool, Gecode::ViewArray<Gecode::Int::IntView>&)
122384    5.7997  libgecodeint.so          libgecodeint.so          Gecode::Int::IntVarImp::perform_copy(Gecode::Space*, bool)
93544     4.4330  libgecodeint.so          libgecodeint.so          Gecode::Int::Element::ViewDom<Gecode::Int::IntView, Gecode::Int::IntView>::propagate(Gecode::Space*)
70344     3.3336  libgecodeint.so          libgecodeint.so          Gecode::VarTypeProcessor<(Gecode::VarTypeId)0, 2>::update(Gecode::Space*, Gecode::VarBase*)
58604     2.7772  libgecodeint.so          libgecodeint.so          Gecode::Int::IntVarImp::in_full(int) const
47418     2.2471  libgecodekernel.so       libgecodekernel.so       Gecode::Space::propagators()
42882     2.0322  libgecodeint.so          libgecodeint.so          Gecode::Int::Inverse::InversePair::propagate(Gecode::Space*)
40234     1.9067  libgecodeint.so          libgecodeint.so          Gecode::Int::IntVarImp::subscribe(Gecode::Space*, Gecode::Propagator*, int)
39013     1.8488  libgecodeint.so          libgecodeint.so          Gecode::VarTypeProcessor<(Gecode::VarTypeId)0, 2>::process(Gecode::Space*, Gecode::VarBase*)
30591     1.4497  libgecodeint.so          libgecodeint.so          Gecode::Int::Tunneling::TunnelingVeh::propagate(Gecode::Space*)
23706     1.1234  libgecodeint.so          libgecodeint.so          Gecode::ViewValBranching<Gecode::Int::IntView, int, Gecode::Int::Branch::ByDegreeMin, Gecode::Int::Branch::ValMin>::branch()
23526     1.1149  libgecodeint.so          libgecodeint.so          Gecode::Iter::Ranges::Inter<Gecode::Iter::Ranges::NaryUnion<Gecode::Int::ViewRanges<Gecode::Int::IntView>>, Gecode::Int::IntVarImpFwd>::operator++()
21190     1.0042  libgecodeint.so          libgecodeint.so          void Gecode::Int::Element::scan<Gecode::Int::IntView, Gecode::Int::IntView, 2, Gecode::Int::Element::RelTestBnd<Gecode::Int::IntView>>(Gecode::Space*, Gecode::Int::Element::IdxView<Gecode::Int::IntView>*, int&, Gecode::Int::IntView, Gecode::Int::IntView, Gecode::Propagator*, Gecode::Int::Element::RelTestBnd<Gecode::Int::IntView>)
20957     0.9931  tailassi                 tailassi                 Tail::copy(bool)
20815     0.9864  libgecodekernel.so       libgecodekernel.so       Gecode::Space::Space(bool, Gecode::Space&)
17177     0.8140  libgecodeint.so          libgecodeint.so          Gecode::Int::Rel::EqDom<Gecode::Int::IntView>::propagate(Gecode::Space*)