I have merged and pushed the patch and created issue575 for speeding up the PDB 
evaluation.

I have no objections to merging this, but I'm not convinced that it completely
resolves this issue. Using the task interface definitely degraded the
performance because of the GlobalState to State transformation, which is still
used. If you want to merge this now, maybe create a new issue to "make PDB
evaluation fast again". I think this is also touched on in issue348.

The early break is included in versions B and C, but not version A. Since 
versions A and B have similar performance, it's very unlikely that the early 
break is responsible for the speed gain.

If you don't object, I'll merge this tomorrow.

I had a look at the code. The changes are straight-forward, but they also
include some break statements, that also could have been used in the old code
(return DEAD_END if one of the components reports a dead end). Did you
experiments include this trick also for the base version?

I'm surprised to see that version C is fastest, but I'm even more surprised that
it apparently recovers all the lost tasks. I thought one major issue for pdb
heuristics would be that the full state is copied/unpacked for each heuristic
evaluation (GlobalState -> State) where the old code only looked at a couple of
values (msg4325). That time would probably show up for tasks with large states ,
and be more visible in the search than in the hill-climbing.

Florian, could you please have a look at the patch?

Looks great! :-) If you don't think it should be code reviewed or if you can
find a code reviewer (other than me ;-)), please merge.

Somewhat surprisingly, version C is fastest for all domains, not just pegsol:
http://ai.cs.unibas.ch/_tmp_files/seipp/issue536-ipdb.html

Version C solves 19 tasks in pegsol-opt11-strips again. Do you think we still need 
to compare version C to a default branch revision which doesn't include the 
issue77 code? If so, I'd start an experiment comparing Version C to revision 
76790c40f91d (last default branch revision before issue77 was merged).

The code is here: 
https://bitbucket.org/jendrikseipp/downward/pull-requests/35
It also includes two bugfixes for correctly handling dead ends in 
is_heuristic_improved().

The changes from issue529 recovered only 3 of the 19 tasks in pegsol-opt11-strips although now the PDB code 
doesn't use evaluation contexts anymore.

Profiling of the current code in the default branch shows that 99% of the time during hill-climbing is spent 
in is_heuristic_improved() which in turn spends 65% of its time in 
CanonicalPDBsHeuristic::compute_heuristic(). It seems that caching the PDB h-values is worse than recomputing 
the PDB h-values for the pegsol domain. 

I have started an experiment comparing three code versions:

A) current default branch
B) only cache PDB h-values for each sample once (by passing the cache to the CanonicalPDBsHeuristic)
C) don't cache PDB h-values

The evaluation contexts introduced in issue77 made the hill-climbing procedure in iPDB 
significantly slower (e.g. coverage dropped from 19 to 0 in pegsol-opt11-strips). We need to 
think about how we can make the procedure faster again. To evaluate success, we should do a 
comparison to a revision of the default branch that does not yet include the issue77 code.