Sounds good, but also feel free to reopen this one if you think this makes more sense.

We might have to rethink this when we make our current plans with the component interaction problem more concrete: The goal there was to no longer have task transformations as input to heuristics, but deal with cost transformations in specialized heuristics (like a "cost transforming evaluator" that has a nested evaluator). Once we implement this, I imagine that creating a PDB from just a task (not a task + a cost function) fits better. But we can open a new issue once we are there.

Is there still interest in integrating this? I would not have wanted to integrate the version of the code I reviewed, but I didn't review the last version, so we can certainly consider this newer version of the code if you like.

If someone wants to resurrect this, I can look at the code, but for this we first need a new pull request link because the old bitbucket link is dead. As with the other issues, I'll set this to "resolved" for now with the idea that anyone that thinks we should continue with this issue should set it back to open.

> Jendrik and I discussed this and decided to change the interface because all
users 
> of the class currently create an explicit copy just to move it into the 
> constructor.

I see.

I suggest we continue the discussion offline.

I think that leaves the question, whether we actually want to have this change.

On the positive side, it makes the code nicer. Previously, we passed two cost 
functions to the PDB (one in the task and one as a vector to overwrite it). We also 
already had a task transformation that was responsible for overwriting the cost 
function with a given one. Not using the class here would mean that we have two 
alternative implementations of the same functionality.

On the negative side, we introduce additional copies of the whole operator cost 
vector, even for small PDBs. As Malte pointed out (msg5559), this changes the big-O 
memory complexity of creating PDBs in the context of cost partitioning. 

>> Jendrik and I talked about whether we could still use the task interface in this
>> case. If we don't want to copy the array, the task should either allow to modify
>> the data or it should not own it. Both seemed wrong to us.
>
> I understand the concern. There are compromise solutions, but they do lead to
> complications. 

Should we consider one of these compromise solutions?

> Still, there are some new copies in the diff that seem unrelated
> to this, such as the fact that it is no longer possible to create a
> ModifedOperatorCostTask without copying the operator cost vector. This seems to
> be a change in the code that is unrelated to what the issue is about.

Jendrik and I discussed this and decided to change the interface because all users 
of the class currently create an explicit copy just to move it into the 
constructor. We considered using perfect forwarding to accept both lvalue and 
rvalue references but decided against it because there was no current use case 
(YAGNI). Do you prefer a constructor that takes an rvalue because it makes the copy 
more explicit?

The plots look mergeable to me :) The instances from trucks-strips might have 
produced different SAS+ tasks as the translator is not deterministic for them 
(due to timeouts).

The experiment had similar result as the first one. Memory is almost unaffected, while the total time 
is mostly within the 5% we expect as noise. There are some cases with a higher deviation in both 
directions (up to 13%).
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue598-v2-issue598-v2-base-issue598-v2-compare.html
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue598-v2-total_time-astar-gapdb.png
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue598-v2-total_time-astar-ipdb.png

The main performance hit is in the pdb creation time, specifically in the genetic algorithm that 
creates a lot of zero-one cost partitionings. These times increase by up to ~50% but they are usually 
below 10 seconds, so this does not affect the overall time score by much. There are also some strange 
outliers in the trucks-strips domain in both directions.
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue598-v2-pdb-time-compare.html
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue598-v2-pdb_generation_time-astar-gapdb.png

Now that issue676 is merged, the diff is much nicer. I'll repeat the experiment for 
the new code.

issue676 now handles all of the minor changes that are unrelated to this issue.

I always like such splits.

I just looked through the pull request again. Most changes are unrelated to the 
original issue and just update the way tasks and proxies are passed around to our 
new guidelines. Would it help to split off a issue that just contains all of these 
clean-up changes and merge this one first?

If we don't mind potentially introducing shared pointers now and then getting
rid of them again later on, then I think it makes sense to consider this a
separate issue.

I've just read up a bit on the overhead of using shared pointers, and the
overhead should only happen during construction, assignment and destruction
(this includes passing them by value as arguments), but not for access. So there
should be no performance penalty while using DelegatingTask, which dispels most
of my concerns.

Considering this, let's not open a new issue and just use shared_ptr here where
we have to. (If I understand correctly, that's just while creating the PDB but
not during search. That sounds fine to me.)

Yes, currently the base class DelegatingTask stores a shared pointer and uses it 
for to access the parent. We could change this (e.g., storing both the shared and a 
raw pointer, and using the raw pointer for access), but this seems out-of-scope for 
this issue. Should I open a new issue for that?

Do all delegating tasks delegate to their parents via shared pointers? This is
much more expensive than regular pointers. I'm not sure if this is ideal.

As we discussed offline, I changed some of the PDB classes that should not 
participate in the task ownership back to use TaskProxy instead of AbstractTask. 

One problem that this issue introduces is that ZeroOnePDBs (the computation class 
not the heuristic) did not have to participate in the ownership before. Now it 
creates ModifiedOperatorCostsTasks for cost partitioning, so it has to have (shared) 
ownership of the parent task. This means that the pattern collection generator 
"genetic" has to access the task in its "generate" method. And since this is an 
inherited method from the pattern collection generator interface, this also implies 
that all of the generators have to get the shared pointer. They only get it as a 
parameter (they don't store it), which makes some sense.

Regarding 1), there are several places in the diff where we used to have a
TaskProxy and now have a shared_ptr<AbstractTask> instead. (From looking a the
diff previously, I thought there were many places like this, but maybe it's only
a few.)

It's not clear to me why we want all these shared pointers (also, how is this
change related to the goal of this issue?). I'm less concerned about performance
here and more about the semantics. Passing a shared pointer means that the
callee is supposed to participate in the ownership of the object, and I don't
think this makes sense for things like the MatchTree, which is supposed to query
the task for information, not co-own it.

More generally, shared_ptr<AbstractTask> in "internal utility classes" like
MatchTree raises warning flags for me. I would expect that the shared pointers
show at the (few) places where different components interface with each other,
but not inside the core computations. Every change where we used to have a
TaskProxy and replace it with a shared_ptr<AbstractTask> means that our web of
ownership becomes more tangled, which is bad. (Sean Parent has some talks where
he speaks of "incidental data structures", and that's a good word for this
tangled web of ownership.)


Regarding 2), that's still many accesses because we can have hundreds of
thousands operators (or more) and tens of thousands of PDBs (or more). But let's
not worry about it for now.


Regarding 3), I have reread the code that generates the abstract operators to be
sure, and I don't think any abstract operators are created in the case where
there is no relevant effect. We loop over all operators, but nothing is created
in the cases where the operator is irrelevant. For N operators, looping over all
of them has O(N) run-time cost (so big-O runtime won't change if we copy an
operator-cost vector here), but previously at least the new memory used only
depends on the size of the abstract task, I think. Roughly speaking, I think we
now use O("concrete task representation size" + "no. abstract states") time and
memory, where previously I think memory usage was intentionally only O("no.
abstract states"). Writing to a lot of memory can be much more expensive than
reading from a lot of memory, so this may be noticeable even if it doesn't
affect big-O runtime.

> Jendrik and I talked about whether we could still use the task interface in this
> case. If we don't want to copy the array, the task should either allow to modify
> the data or it should not own it. Both seemed wrong to us.

I understand the concern. There are compromise solutions, but they do lead to
complications. Still, there are some new copies in the diff that seem unrelated
to this, such as the fact that it is no longer possible to create a
ModifedOperatorCostTask without copying the operator cost vector. This seems to
be a change in the code that is unrelated to what the issue is about.

> In general, the performance decrease didn't look all that bad (looks like less
> than 5%). If we cannot find a way to improve it, we could still consider merging
> the code. I think it makes the much nicer since we avoid passing two different
> cost functions to the PDB.

If no operation slows down by more than 5%, I don't think we have a serious
concern. But with whole-planner experiments, we cannot see this -- we might have
certain operations slowing down by a significant factor. This can be more of a
concern if these operations can become critical bottlenecks for other PDB-based
algorithms (ones we did not test or ones that don't exist yet).

For example, one typical use case we want to support well is to generate
1000-10000 very small PDBs (for example in our "systematic patterns"). Currently
I think we do not combine them with cost partitioning, but it would be a natural
thing to do.


On a more general level, I'm a bit worried that we copy giant objects around as
if it weren't a big deal. A clean algorithm should make sense when run by hand.
I think of the operator cost vector as a 1000-page stack of papers containing a
long list of numbers. (For our really large tasks, this is not an exaggeration.)
When executing the algorithm by hand, we wouldn't want to copy all these numbers
into more and more temporary 1000-page stacks of paper if we only really need a
single copy through the whole cost partitioning algorithm.

I'm not against merging this, but generally, it would be great if we could be a
bit more circumspect when making changes like these that are potentially
performance-critical. In an ideal world, the issue and/or code should explain
the performance impact of the changes, explain the rationale (e.g. outline some
possible alternatives and their drawbacks, such as complexity of
implementation), and include a micro-benchmark that measures the impact on the
key operations. Also, we shouldn't make too many unrelated changes at the same
time. Reviewing changes for performance is always difficult, and it really
becomes tougher when the patch touches many source files. (This one touches 25
source files.) I really like the fact we're making cleanup changes, but when
there is a substantial number of them, they should perhaps better be separated
from the main change we want to review so that we can see the main changes and
their impact more clearly.

> 1) The abstract task is now usually accessed via a shared pointer, where
> previously it was accessed via a regular pointer. Shared pointers are generally
> slower, but we can probably get away with this if we don't do it all the time.

I didn't find the code you are referring to here. In the constructor of ZeroOnePDBs the shared 
pointer is dereferenced only once. Do you mean the code inside ModifiedOperatorCostsTask?

> 2) Accessing operator costs via the task interface is more expensive than
> accessing them directly via an array. I'm not sure how frequently we access the
> operator costs; perhaps it's not an issue.

Within the PDB code, we access the cost of each operator exactly once to build a local 
representation of it. I also don't think it's an issue here.

> 3) It seems we may be copying around the vector of operator costs a lot more
> than previously. For small PDBs (and many of the PDBs we generate are small),
> this can change the big-O cost of generating the PDB, which is now at least
> linear in the number of *all* operators, whether or not they are relevant to the
> PDB.

Yes, we now make two copy for each PDB: the first inside the constructor of 
ModifiedOperatorCostsTask and the second while building the abstract operators.
The big-O notation shouldn't be affected, because we previously also constructed abstract 
operators for every operator (not only the relevant ones).

> For cost partitioning, we need to generate at
> least one vector<int> of operator costs during the creation process. Ideally, we
> should never generate a second one.

Jendrik and I talked about whether we could still use the task interface in this case.
If we don't want to copy the array, the task should either allow to modify the data or it 
should not own it. Both seemed wrong to us.

In general, the performance decrease didn't look all that bad (looks like less than 5%). If we 
cannot find a way to improve it, we could still consider merging the code. I think it makes the 
much nicer since we avoid passing two different cost functions to the PDB.

The GA-PDB configuration is currently the only one that uses the cost
partitioning features. If GA-PDB slows down, there may be a performance issue
with cost partitioning.

From a quick look at the diff, I see three potential issues:

1) The abstract task is now usually accessed via a shared pointer, where
previously it was accessed via a regular pointer. Shared pointers are generally
slower, but we can probably get away with this if we don't do it all the time.

2) Accessing operator costs via the task interface is more expensive than
accessing them directly via an array. I'm not sure how frequently we access the
operator costs; perhaps it's not an issue.

3) It seems we may be copying around the vector of operator costs a lot more
than previously. For small PDBs (and many of the PDBs we generate are small),
this can change the big-O cost of generating the PDB, which is now at least
linear in the number of *all* operators, whether or not they are relevant to the
PDB.

I think point #3 is the most likely culprit if things slow down, and it is also
not good design if we have to copy these large vectors around needlessly.
Simplifying a little bit, I think there is a problem whenever we copy
information that is indexed by-operator -- this is heavyweight data that should
ideally live in one place forever. For cost partitioning, we need to generate at
least one vector<int> of operator costs during the creation process. Ideally, we
should never generate a second one.

If you run further experiments, please also measure just the PDB generation time.

A pull request for this is on Bitbucket:

https://bitbucket.org/FlorianPommerening/downward-issues/pull-requests/22/issue598/diff

The experiments are somewhat mixed: memory, expansions, and search_time are not affected as 
expected. Total time shows a slight negative impact (-0.05 average score). The relative scatter 
plots show that times can get better and worse, most of the distribution is within 10% but there 
seems to be a negative trend for GA-PDBs.

http://ai.cs.unibas.ch/_tmp_files/pommeren/issue598-v1-issue598-v1-base-issue598-v1-compare.html

http://ai.cs.unibas.ch/_tmp_files/pommeren/issue598-v1-total_time-astar-gapdb.png

We should probably use tasks/modified_operator_costs_task.h (will be introduced 
in issue600) for this purpose.

Cost functions are currently passed as parameters to some PDB classes
(PatternDatabase, ZeroOnePDBsHeuristic, PDBHeuristic). We would like to
introduce a task transformation class that modifies the cost function and use it
in those places. This will hopefully lead to cleaner code.