We fixed the last few open points live and merged the code.

You can see the diff on bitbucket:
https://bitbucket.org/FlorianPommerening/downward-issues/pull-requests/44

This is now equivalent to v3 without the debug code and what I suggested to
merge. We can discuss the alternatives live if you have time now.

The runtimes for v3 look fine to me. If that is the one you prefer, it would be 
good if you could send us a link that lets us look at the code diff.

All other things being equal, evaluating on unpacked states would have the 
advantage that we have a clearer code path towards a world where (optionally or 
always) we don't store derived variables in the packed states at all. But that 
is an idea for the future, so we don't necessarily need to consider it here.

I would appreciate if we could have a short live discussion on the various 
alternatives and how they work.

I worked on a templated way of overloading the method for packed and unpacked
states. I ran two experiments to test both code paths:

v3 uses the overload for packed states and we can compare this to the default
branch (this is the version, I suggest merging):
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue794-v3-opt-issue794-base-issue794-v3-compare.html
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue794-v3-opt-axiom_time_inner-blind-issue794-base-issue794-v3.png

v4 always unpacks states and uses the overload for unpacked states. This doesn't
make sense but allows us to test the overload by comparing it to v1 which did
the same thing without the templated method:
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue794-v4-opt-issue794-v1-issue794-v4-compare.html
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue794-v4-opt-axiom_time_inner-blind-issue794-v1-issue794-v4.png

In both cases, times vary a lot but overall, I think the differences average out
more or less. If you are ok with the results, I'll roll the code back to v3,
take out the debug code and then this could be reviewed.

I ran another experiment with the opposite implementation, i.e. the axiom
evaluator always works on packed data. In the overload for unpacked data, the
data is packed first and unpacked after the axiom evaluation. I expected the
measurements to be almost the same as the baseline since the overload for
unpacked data is only used once for the initial state. Strangely, the
measurements for axiom evaluation time varies a lot. Could this be because of
inaccurate measurements of small runtimes? Over all, the differences seem to
cancel out.

http://ai.cs.unibas.ch/_tmp_files/pommeren/issue794-v2-opt-axiom_time_inner-blind-issue794-base-issue794-v2.png
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue794-v2-opt-issue794-base-issue794-v2-compare.html

Since I suspect that we don't want to intentionally slow down the overload for
unpacked data by packing it first, I'll work on another version now where that
overload is fast as well. To test it, I'll unpack all states and send them to
the overload for unpacked data. This should then be comparable to v1 where we
measured the overhead of unpacking everything.

Here is the link to the report:
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue794-v1-opt-issue794-base-issue794-v1-compare.html

I updated the pull request with the changes from issue774 and issue824. In this
iteration, I fully unpacked the state before evaluating the axioms.

An experiment comparing the current default version with this code had a pretty
clear result: evaluating on the unpacked data is much faster, but
packing/unpacking takes up so much time that overall the time to evaluate axioms
increases noticeably (details below). I think this is good to note for issue348.
I'll add a message there that we will save time if can rewrite the search code
so the state is only unpacked once. But for this issue, I'd be happy to reach
the previous performance while removing the code duplication. I'll implement a
solution based on packed states again and evaluate it.


Experiment details:
The experiment uses two timers that both accumulate values over the whole
search. One timer ("axiom_time_outer") measures the total time spent in the
AxiomEvaluator::evaluate() method. The other timer ("axiom_time_inner") only
measures the time of the evaluation on unpacked data (i.e., without (un)packing
the states). In the baseline, where there is no unpacking, both timers measure
the total time spent in the evaluate method. This way, comparing the "inner"
timer compares just the actual axiom evaluation speed, while comparing the
"outer" compares the overall speed.

This may be one of the few cases where virtual method accesses have a
significant runtime effect because they appear in all kinds of tight inner
loops, so we will need experiments. The experiments should only consider domains
that heavily exercise derived predicates.

We should test both code paths (packed states and unpacked states). It would be
great if we could specifically measure the time spent evaluating axioms, using a
dedicated timer. I wouldn't mind if this were added in a hacky way and removed
before merging.

I think that's a good plan.

We discussed this before in issue348 and issue420. It might be worth unpacking
the state for evaluation but it might be even better to only unpack it once in
the search and only pack it shortly before storing it. The latter would require
a larger redesign of the way states are handled.

Since we already have issue348 for the larger design question, I'd keep this one
simple by testing three options: 
1) the code as issue774 leaves it (with code duplication)
2) the current patch (accessing both types using the StateData class)
3) unpacking each state just before evaluating axioms and packing the result
afterwards.

Have we ever evaluated the performance impact of unpacking global states before 
evaluating axioms? If the impact is small, we might not need the StateData class.

The code looks good to me.

The following pull request is against issue774 because it has to be merged
before we can consider this issue.

https://bitbucket.org/FlorianPommerening/downward-issues/pull-requests/44

issue774 introduces some code duplication in the axiom evaluator class because
axioms are evaluated on packed states and unpacked states. I propose we add an
internal class that represents the interface to access both kinds of states,
switch the duplicated code to one method that uses the interface, and then
change the two evaluate methods to use the common method.