Issue 6461087: issue344 introduced state handles

karpase

Hi Florian, Overall, this looks pretty good. I have a few minor comments, and also ...

11 years, 8 months ago (2012-08-16 09:00:04 UTC) #1

Malte

Hi everyone, so far I only read Erez's comments, not the actual code. Will be ...

11 years, 8 months ago (2012-08-17 14:12:31 UTC) #2

Malte

OK, I went over it. Looks very good! I only have one (slightly) major worry, ...

11 years, 8 months ago (2012-08-20 15:16:34 UTC) #3

Florian

Thanks for all your helpful comments. I did a first pass through them today and ...

11 years, 8 months ago (2012-08-30 16:38:32 UTC) #4

Thanks for all your helpful comments. I did a first pass through them today and
fixed the smaller issues. For everything that should be done after the first
benchmarking I added TODOs in the code.

The way I see it, there are now three larger issues remaining, before I start
the benchmarking. I left the comments mentioning them unanswered and will send
another mail once they are fixed:

1) The ownership of the actual data (state_var_t*) is not handled correctly. I
talked to Malte about this and will fix this as the next step.
2) After this I'll look at the construction/destruction of StateHandles again.
There might be an unnecessary indirection there
3) Finally I'll move the hashing and semantic comparison out of the StateHandle
class and into the StateRegistry as Malte suggested.

http://codereview.appspot.com/6461087/diff/1/src/search/axioms.cc
File src/search/axioms.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/axioms.cc#newcode51
src/search/axioms.cc:51: void AxiomEvaluator::evaluate(state_var_t
*state_buffer) {
Created issue348 and added a TODO in the code

http://codereview.appspot.com/6461087/diff/1/src/search/globals.cc
File src/search/globals.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/globals.cc#newcode248
src/search/globals.cc:248: // state in the output format
On 2012/08/20 15:16:34, Malte wrote:
> I think this is fine as is -- we generally try to break the output format only
> if the benefit is really large.
I talked to Gabi about this and she said that there is an upcoming change in the
output format that would break compatibility with older versions anyway. If
there are no other reasons to keep this order, this might be a good time to
change it.

http://codereview.appspot.com/6461087/diff/1/src/search/landmarks/landmark_st...
File src/search/landmarks/landmark_status_manager.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/landmarks/landmark_st...
src/search/landmarks/landmark_status_manager.cc:15: for (int i = 0; i <=
g_state_registry.size(); ++i) {
Ok, I reverted back to reached_lms.clear() here and added this method to
PerStateInformation. It replaces all elements by the default value as Erez
suggested. This should also fix the memory issue that Malte mentioned since the
destructors of the old entries are called. We cannot save the space the
PerStateInformation vector itself uses, since it will be increased to its
virtual size the next time it is accessed anyway

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information.h
File src/search/per_state_information.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information...
src/search/per_state_information.h:10: #include <assert.h>
On 2012/08/20 15:16:34, Malte wrote:
> Should be <cassert>. (We avoid the old-fashioned <foo.h>, which puts things
into
> the global namespace. Doesn't actually make a difference for assert, but it's
> the general policy.)

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information...
src/search/per_state_information.h:16: mutable std::vector<Entry> entries;
Added the comment:
// This is mutable so it can automatically grow to hold one element for each
registered state.

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information...
src/search/per_state_information.h:35: ensure_virtual_size();
On 2012/08/20 15:16:34, Malte wrote:
> OK, I guess this is why we need entries to be mutable.
> An alternative here would be not to call virtual_size and return
"default_value"
> when we're out of bounds.

I don't see how this would work with references, e.g. for the SearchNodeInfo
class.
In this case we also would have to increase the size from somewhere else
(otherwise it would never increase). Maybe a good way would be to use a
register-and-notify mechanism that ties the PerStateInformation to a
StateRegistry. I don't think this is worth the effort right now. Maybe later
when there actually exists more than one StateRegistry.

...

Ahh, after writing this down, I think I got it. It would work when we would call
ensure_virtual_size only in the not-const case but not in the const case. With
this we wouldn't need the mutable anymore. Should I do that?

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information...
src/search/per_state_information.h:44: PerStateInformation(const Entry
&_default_value)
On 2012/08/20 15:16:34, Malte wrote:
> Our convention for constructor arguments with name clashes is to use a
trailing
> _: "default_value_".

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information...
src/search/per_state_information.h:49: return this->at(state.get_id());
On 2012/08/20 15:16:34, Malte wrote:
> We don't usually write this->...; why not just "return at (...);"?
> 
> (Same for the following ones.)

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information...
src/search/per_state_information.h:70: }
On 2012/08/20 15:16:34, Malte wrote:
> It's convenient to have methods for all three of State, StateHandle and
> state_id, but eventually we should have a clearer separation of which class is
> responsible for what. For example, the numerical IDs should be implementation
> details in as many places as possible.
> 
> I think that the StateHandle-based methods are the most sensible ones here
> (state IDs are an implementation detail, and some states stored in State don't
> have an ID), and I'd like to have a (deferred?) TODO to get rid of the other
two
> access styles.

Added TODOs for now. I'll look into this later. I think getting rid of the
accessor for State will not be a big deal, but the id accessor might need some
work.

http://codereview.appspot.com/6461087/diff/1/src/search/search_space.h
File src/search/search_space.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/search_space.h#newcode61
src/search/search_space.h:61: PerStateInformation<SearchNodeInfo *>
search_node_infos;
Ok, added a TODO for now. Will check back after benchmarking.

http://codereview.appspot.com/6461087/diff/1/src/search/search_space.h#newcode67
src/search/search_space.h:67: SearchNode get_node(const StateHandle &handle);
We don't actually need both. I just added the State accessor for convenience,
since get_node was often called with something like:
successor_state.get_handle()

I removed it again for a cleaner interface.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc
File src/search/state.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode19
src/search/state.cc:19: for (int i = 0; i < g_variable_domain.size(); i++)
I changed the occurrences of this within my patch. Doing a search for "i++"
showed over 340 results, most of them for loops like this one. Should I fix
those in a different branch?

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode24
src/search/state.cc:24: State::State(state_var_t *buffer) :
borrowed_buffer(true), vars(buffer) {
On 2012/08/20 15:16:34, Malte wrote:
> Is there a way to make explicit how handle is initialized here?
Is this what you meant?

    State::State(state_var_t *buffer)
        : borrowed_buffer(true), vars(buffer), handle() {
    }

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode38
src/search/state.cc:38: State::State(const StateHandle &_handle) :
borrowed_buffer(true), handle(_handle) {
On 2012/08/20 15:16:34, Malte wrote:
> _handle => handle_

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode49
src/search/state.cc:49: vars = 0;
I used abort here and added some asserts to the other constructors. What's the
reason we use abort here instead of assert?

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode54
src/search/state.cc:54: g_axiom_evaluator->evaluate(initial_state_vars);
On 2012/08/20 15:16:34, Malte wrote:
> Given the slightly tricky dependency on the construction order here (can only
> create the initial state once g_axiom_evaluator has been constructed), it
might
> make sense to add something like assert(g_axiom_evaluator); before this line.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode58
src/search/state.cc:58: return new State(registered_state);
On 2012/08/20 15:16:34, Malte wrote:
> Given that we're already thinking of getting rid of the global state registry
at
> some point and that create_initial_state is only called once, it may be a good
> idea to have this one generated and return an unregistered state instead, and
> have the search algorithms register it.

I'm not sure about this, but I had the feeling that the g_initial_state variable
is used a lot in some searches and heuristics. If the search would register the
initial state, should it also replace the unregistered state in g_initial_state
with a registered one?
* If so, I guess this could be a problem if the state would be registered by the
search _and_ the heuristic, or someone accesses and stores g_initial_state
before it is registered.
* If not, then wouldn't this mean that each search/heuristic that uses
g_initial_state would instead have to use their own registered copy of it? Does
it still make sense to keep it as a global variable then?
* If it should just be registered on demand, this could lead to an overhead
because the initial state is registered again and again.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode107
src/search/state.cc:107: return handle.get_id();
On 2012/08/20 15:16:34, Malte wrote:
> It would be nice if this method could go. State IDs are an implementation
> detail, and it would be nice if State wouldn't need to worry about them.
The only place this was used, was in the PerStateInformation accessor we wanted
to get rid of anyway. I removed it and will use state.get_handle().get_id() in
the accessor until I figure out how to get rid of it.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode111
src/search/state.cc:111: return handle;
On 2012/08/20 15:16:34, Malte wrote:
> This might be a good candidate to inline (i.e., put into the class definition)
> for efficiency?

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state.h
File src/search/state.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.h#newcode28
src/search/state.h:28: // TODO why is g_initial_state a pointer?
On 2012/08/20 15:16:34, Malte wrote:
> Probably because we can't initialize it before having read the initial state
> (and axioms), so we don't know what to put into it at the time the variable
> comes into life.
I see. Is it strange to have this "constructor" return a pointer, while the
others return a value?

http://codereview.appspot.com/6461087/diff/1/src/search/state.h#newcode34
src/search/state.h:34: const StateHandle get_handle() const;
On 2012/08/20 15:16:34, Malte wrote:
> Can we return a StateHandle instead? "const X" is not usually a useful return
> type since it offers inconvenience but no real protection against anything.
(For
> pointer types there is a difference, but I'm not sure we want to make it so
> explicit to everyone that StateHandle is basically a pointer.)

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc
File src/search/state_handle.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:12: explicit StateRepresentation(const state_var_t
*_data);
On 2012/08/20 15:16:34, Malte wrote:
> We generally declare a destructor whenever we declare a constructur, even if
it
> doesn't do anything special.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:14: // into a hash_set, i.e. the state registry
On 2012/08/20 15:16:34, Malte wrote:
> Full sentences should end in a period. (Not a big thing, but there's a few
> comments next to each other in some places where it's not actually clear to me
> how the sentences are split.)

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:16: // This will later be replaced by packed state
data
On 2012/08/20 15:16:34, Malte wrote:
> Ditto.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:22: id(INVALID_HANLDE), data(0) {
On 2012/08/20 15:16:34, Malte wrote:
> typo (as Erez noted)

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:38: for (int i = 0; i < g_variable_domain.size();
i++)
On 2012/08/20 15:16:34, Malte wrote:
> size_t ... ++i

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:45: : representation(new StateRepresentation()) {
On 2012/08/20 15:16:34, Malte wrote:
> should have no parentheses: new StateRepresentation

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:46: // do nothing
On 2012/08/20 15:16:34, Malte wrote:
> I'd remove the
>     // do nothing
> comments; we don't have them elsewhere in similar places. (Also, we do
> something, it's just not necessarily between the braces but in the initializer
> lists.)

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:55: : representation(new
StateRepresentation(*(other.representation))) {
On 2012/08/20 15:16:34, Malte wrote:
> Hmmm... big conceptual mismatch for me here.
> 
> My intuition of copying a handle is not that the associated data is copied.
I'd
> expect the initialization "representation(other.representation)" here.
> 
> If we really need a copy here, I think there's something fishy with our use of
> these handles.

Right now the actual data is not copied, only the StateRepresentation object
which contains a pointer to the data. This might be one indirection to much or
just a bad name for the StateRepresentation class. I'll think about this again
after I fixed the ownership issue that we talked about before. I copied the
basic template for the PIMPL pattern from Wikipedia. There the implementation
object (*representation in our case) is deep copied because the handle has
ownership of it. I reckon this will be clearer once I figured out how to manage
the ownership of the data correctly in our case.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:60: std::swap(this->representation,
other.representation);
On 2012/08/17 14:12:31, Malte wrote:
> On 2012/08/16 09:00:05, karpase wrote:
> > Should this change other?
> > Seems strange to me, but I don't have the complete picture yet.
> 
> Agreed. If this is intentional, it needs explanation.

This was also part of the Wikipedia implementation. I guess the reasoning is
that "other" is given by value and so we can change the copy. By swapping the
pointers we ensure the correct destruction of anything that was previously in
"this". For now, I added a comment explaining this, but this method might be
unnecessary altogether if the Handle doesn't have ownership of the
representation.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:65: delete representation;
On 2012/08/20 15:16:35, Malte wrote:
> Related to the issue above: getting rid of a handle shouldn't get rid of the
> data. I'd expect the destructor to do nothing.
> 
> (The main reason we have handles is that we can cheaply move states around --
> but if every copying/destruction of a handle essentially involves
> copying/destroying the state info, we lose this possibility.)
As mentioned above, this doesn't really delete the data, only the
StateRepresentation object, which contains but does not own the state_var_t
pointer. So at the moment it does the right thing, but will probably change with
the ownership issue

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:89: return get_id() == other.get_id();
On 2012/08/20 15:16:35, Malte wrote:
> We should never have two state representations with the same ID (after all,
it's
> an ID), so I'd prefer to just compare representation instead. (We should only
> rely on the ID when we need a contiguously numbered index into some vector.)

See comment in state_registry.h

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:108: return
::hash_number_sequence(representation->data, g_variable_domain.size());
On 2012/08/20 15:16:35, Malte wrote:
> Do we need to hash at all? After all, we introduced the IDs to get rid of the
> need to hash. If we need to hash: can't we use the IDs instead? (Or does the
> StateRegistry itself use this method in some way?)
see comment in state_registry.h

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.h
File src/search/state_handle.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.h#newcode18
src/search/state_handle.h:18: enum { INVALID_HANLDE = -1 };
On 2012/08/16 09:00:05, karpase wrote:
> Is this typo on purpose (INVALID_HANDLE)
No, it wasn't, thanks.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.h#newcode32
src/search/state_handle.h:32: int get_id() const;
On 2012/08/17 14:12:31, Malte wrote:
> On 2012/08/16 09:00:05, karpase wrote:
> > I don't think we need a 64-bit state_id, which would happen on a 64-bit
> > compilation.
> 
> On 64-bit PC architectures, int is 32 bit. I'd suggest going without the
typedef
> for the time being.
> 
> (And I wouldn't be worried about losing the negative range -- it'll be a long
> time until we can store more than 1 billion states, and at that time it'd be
> better to change this to a 64-bit quantity like a size_t anyway.)
Left it as an int for now.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.h#newcode33
src/search/state_handle.h:33: bool is_valid() const;
On 2012/08/20 15:16:35, Malte wrote:
> Would be nice not to have invalid handles. (I now see why we have them --
> because we have both registered and unregistered states within State. Given
that
> we already thought about splitting these into two classes, it would be good to
> write down somewhere that if we end up splitting these, we can/should get rid
of
> invalid handles.)
Added a TODO for this.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.h#newcode46
src/search/state_handle.h:46: }
On 2012/08/20 15:16:35, Malte wrote:
> See comments on hashing in C++ file.

See comment in state_registry.h

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.cc
File src/search/state_registry.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.cc#new...
src/search/state_registry.cc:7: StateRegistry::StateRegistry(): next_id(0) {
On 2012/08/20 15:16:35, Malte wrote:
> I think we generally do a line break before initializers (or at least we
should)
> so that it's not so easy to miss the code.
> 
> But do we need next_id at all? Seems to be redundant with
> registered_states.size(), and I think it's generally better to avoid
redundancy.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.cc#new...
src/search/state_registry.cc:17: it->make_permanent(next_id++);
On 2012/08/20 15:16:35, Malte wrote:
> If we get rid of next_id (I think we should). This should be
> registered_states.size() - 1 then (considering that the state set has already
> grown here).

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h
File src/search/state_registry.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newc...
src/search/state_registry.h:16: StateRegistry();
On 2012/08/20 15:16:35, Malte wrote:
> If it has a constructor, it should have a destructor.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newc...
src/search/state_registry.h:17: // Lookup of state. If the same state was
previously looked up, a state with
On 2012/08/20 15:16:35, Malte wrote:
> I'd prefer a blank line before this to make it clearer that the comment
applies
> to what comes below, not after. Also, I think it makes sense to make a logical
> break between construction/destruction and lookup. With a long comment like
> this, I'd prefer /* c-style comments */.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newc...
src/search/state_registry.h:23: // and has a valid handle
On 2012/08/20 15:16:35, Malte wrote:
> Should end in a period. Also, maybe reverse the order: first give a short
> summary, and then the details?

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newc...
src/search/state_registry.h:24: State get_registered_state(const State &state);
On 2012/08/20 15:16:35, Malte wrote:
> Maybe clearer (as a later TODO?) to have this return a StateHandle? And maybe
> call it "get_state_handle" or "get_handle"?

Added a TODO for now. An alternative would be to leave it like this until we
split up the State class and then change it to:
RegisteredState get_registered_state(const UnregisteredState
&unregistered_state);

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newc...
src/search/state_registry.h:28: }
On 2012/08/20 15:16:35, Malte wrote:
> size() methods should probably return size_t.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newc...
src/search/state_registry.h:32: }
On 2012/08/20 15:16:35, Malte wrote:
> New line between methods.

Done.

Sign in to reply to this message.

Malte

A few more replies to the replies. Looking good! http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information.h File src/search/per_state_information.h (right): http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information.h#newcode35 src/search/per_state_information.h:35: ...

11 years, 8 months ago (2012-08-30 18:35:54 UTC) #5

A few more replies to the replies. Looking good!

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information.h
File src/search/per_state_information.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information...
src/search/per_state_information.h:35: ensure_virtual_size();
On 2012/08/30 16:38:32, flo.pom wrote:

> Ahh, after writing this down, I think I got it. It would work when we would
call
> ensure_virtual_size only in the not-const case but not in the const case. With
> this we wouldn't need the mutable anymore. Should I do that?

That's what I meant, yes. I think it would be good to do that.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc
File src/search/state.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode19
src/search/state.cc:19: for (int i = 0; i < g_variable_domain.size(); i++)
On 2012/08/30 16:38:32, flo.pom wrote:
> I changed the occurrences of this within my patch. Doing a search for "i++"
> showed over 340 results, most of them for loops like this one. Should I fix
> those in a different branch?

Not sure -- maybe discuss it with the others in one of our next meetings? The
main drawback I see is that it might make outstanding merges fail to apply
cleanly, but I'm not sure how many larger merges are currently outstanding.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode24
src/search/state.cc:24: State::State(state_var_t *buffer) :
borrowed_buffer(true), vars(buffer) {
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:34, Malte wrote:
> > Is there a way to make explicit how handle is initialized here?
> Is this what you meant?
> 
>     State::State(state_var_t *buffer)
>         : borrowed_buffer(true), vars(buffer), handle() {
>     }

I guess, if that's the preferred way to create an invalid handle. Something like
handle(0) or handle(StateHandle::invalid) might be even clearer about the intent
-- maybe we don't want a public default constructor for StateHandle in the first
place. In any case, do this the way you prefer; I'm mostly thinking aloud here.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode49
src/search/state.cc:49: vars = 0;
On 2012/08/30 16:38:32, flo.pom wrote:
> I used abort here and added some asserts to the other constructors. What's the
> reason we use abort here instead of assert?

Our default builds disable assertions for efficiency, hence we tend to
occasionally use abort in places where there's no performance hit and it'd be
good to have the test available also when assertions are disabled.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode58
src/search/state.cc:58: return new State(registered_state);
> If the search would register the initial state, should it
> also replace the unregistered state in g_initial_state
> with a registered one?

No, g_initial_state should be considered constant. (It would make sense for it
to be const if that didn't complicate initialization.)

I guess we should look at how g_initial_state is used. I think that the searches
shouldn't do more with it than put it into the open list at the start of the
search at the moment. So for me, it would make sense for them to register it
like they register everything else they put into open. I don't think they need
to hang on to the initial state for any other purpose, but I'm not really sure.

The heuristics that use it probably use it for generating random walks in the
state space (Erez's learning stuff and the iPDB code) and don't want registered
states.

So, in short, I don't think there should be that many accesses to
g_initial_state in the first place. Maybe I'm missing something.

http://codereview.appspot.com/6461087/diff/1/src/search/state.h
File src/search/state.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.h#newcode28
src/search/state.h:28: // TODO why is g_initial_state a pointer?
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:34, Malte wrote:
> > Probably because we can't initialize it before having read the initial state
> > (and axioms), so we don't know what to put into it at the time the variable
> > comes into life.
> I see. Is it strange to have this "constructor" return a pointer, while the
> others return a value?

It is a bit fishy, I guess. Having a create_... function that returns a pointer
because it generates an object on the heap is quite common, though. Maybe we
should reserve create_... for this feature and use something else (build_...,
make_..., ?) for other purposes?

Having a function that returns a State work as a kind of constructor is also a
bit unfortunate because it involves copying. But I don't have a concrete
suggestion for improvement at the moment.

Sign in to reply to this message.

Florian

No need to read this, I just marked a few things as "Done." so I ...

11 years, 8 months ago (2012-08-31 08:49:29 UTC) #6

No need to read this, I just marked a few things as "Done." so I can easier see
which issues are still open.

http://codereview.appspot.com/6461087/diff/1/src/search/axioms.cc
File src/search/axioms.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/axioms.cc#newcode51
src/search/axioms.cc:51: void AxiomEvaluator::evaluate(state_var_t
*state_buffer) {
On 2012/08/30 16:38:32, flo.pom wrote:
> Created issue348 and added a TODO in the code

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/landmarks/landmark_st...
File src/search/landmarks/landmark_status_manager.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/landmarks/landmark_st...
src/search/landmarks/landmark_status_manager.cc:15: for (int i = 0; i <=
g_state_registry.size(); ++i) {
On 2012/08/30 16:38:32, flo.pom wrote:
> Ok, I reverted back to reached_lms.clear() here and added this method to
> PerStateInformation. It replaces all elements by the default value as Erez
> suggested. This should also fix the memory issue that Malte mentioned since
the
> destructors of the old entries are called. We cannot save the space the
> PerStateInformation vector itself uses, since it will be increased to its
> virtual size the next time it is accessed anyway

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information.h
File src/search/per_state_information.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information...
src/search/per_state_information.h:16: mutable std::vector<Entry> entries;
On 2012/08/30 16:38:32, flo.pom wrote:
> Added the comment:
> // This is mutable so it can automatically grow to hold one element for each
> registered state.

No longer mutable because accessor changed.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information...
src/search/per_state_information.h:35: ensure_virtual_size();
On 2012/08/30 18:35:54, Malte wrote:
> On 2012/08/30 16:38:32, flo.pom wrote:
> 
> > Ahh, after writing this down, I think I got it. It would work when we would
> call
> > ensure_virtual_size only in the not-const case but not in the const case.
With
> > this we wouldn't need the mutable anymore. Should I do that?
> 
> That's what I meant, yes. I think it would be good to do that.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/search_space.h
File src/search/search_space.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/search_space.h#newcode67
src/search/search_space.h:67: SearchNode get_node(const StateHandle &handle);
On 2012/08/30 16:38:32, flo.pom wrote:
> We don't actually need both. I just added the State accessor for convenience,
> since get_node was often called with something like:
> successor_state.get_handle()
> 
> I removed it again for a cleaner interface.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc
File src/search/state.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode19
src/search/state.cc:19: for (int i = 0; i < g_variable_domain.size(); i++)
On 2012/08/30 18:35:54, Malte wrote:
> On 2012/08/30 16:38:32, flo.pom wrote:
> > I changed the occurrences of this within my patch. Doing a search for "i++"
> > showed over 340 results, most of them for loops like this one. Should I fix
> > those in a different branch?
> 
> Not sure -- maybe discuss it with the others in one of our next meetings? The
> main drawback I see is that it might make outstanding merges fail to apply
> cleanly, but I'm not sure how many larger merges are currently outstanding.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode24
src/search/state.cc:24: State::State(state_var_t *buffer) :
borrowed_buffer(true), vars(buffer) {
On 2012/08/30 18:35:54, Malte wrote:
> On 2012/08/30 16:38:32, flo.pom wrote:
> > On 2012/08/20 15:16:34, Malte wrote:
> > > Is there a way to make explicit how handle is initialized here?
> > Is this what you meant?
> > 
> >     State::State(state_var_t *buffer)
> >         : borrowed_buffer(true), vars(buffer), handle() {
> >     }
> 
> I guess, if that's the preferred way to create an invalid handle. Something
like
> handle(0) or handle(StateHandle::invalid) might be even clearer about the
intent
> -- maybe we don't want a public default constructor for StateHandle in the
first
> place. In any case, do this the way you prefer; I'm mostly thinking aloud
here.

I went with StateHandle::invalid and removed the default constructor.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode49
src/search/state.cc:49: vars = 0;
On 2012/08/30 18:35:54, Malte wrote:
> On 2012/08/30 16:38:32, flo.pom wrote:
> > I used abort here and added some asserts to the other constructors. What's
the
> > reason we use abort here instead of assert?
> 
> Our default builds disable assertions for efficiency, hence we tend to
> occasionally use abort in places where there's no performance hit and it'd be
> good to have the test available also when assertions are disabled.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode107
src/search/state.cc:107: return handle.get_id();
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:34, Malte wrote:
> > It would be nice if this method could go. State IDs are an implementation
> > detail, and it would be nice if State wouldn't need to worry about them.
> The only place this was used, was in the PerStateInformation accessor we
wanted
> to get rid of anyway. I removed it and will use state.get_handle().get_id() in
> the accessor until I figure out how to get rid of it.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc
File src/search/state_handle.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:89: return get_id() == other.get_id();
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > We should never have two state representations with the same ID (after all,
> it's
> > an ID), so I'd prefer to just compare representation instead. (We should
only
> > rely on the ID when we need a contiguously numbered index into some vector.)
> 
> See comment in state_registry.h

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:108: return
::hash_number_sequence(representation->data, g_variable_domain.size());
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > Do we need to hash at all? After all, we introduced the IDs to get rid of
the
> > need to hash. If we need to hash: can't we use the IDs instead? (Or does the
> > StateRegistry itself use this method in some way?)
> see comment in state_registry.h

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.h
File src/search/state_handle.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.h#newcode33
src/search/state_handle.h:33: bool is_valid() const;
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > Would be nice not to have invalid handles. (I now see why we have them --
> > because we have both registered and unregistered states within State. Given
> that
> > we already thought about splitting these into two classes, it would be good
to
> > write down somewhere that if we end up splitting these, we can/should get
rid
> of
> > invalid handles.)
> Added a TODO for this.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.h#newcode46
src/search/state_handle.h:46: }
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > See comments on hashing in C++ file.
> 
> See comment in state_registry.h

Done.

Sign in to reply to this message.

Florian

Started working on the ownership issue. Looks good so far, but its too big a ...

11 years, 8 months ago (2012-08-31 17:48:36 UTC) #7

Started working on the ownership issue. Looks good so far, but its too big a
change to describe it in the comments, so I'll post a new patch set here on
Monday.

The following comments are in response to Malte's last message and some other
open issues. Sorry for the long email.

http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_...
File src/search/learning/probe_state_space_sample.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_...
src/search/learning/probe_state_space_sample.cc:90:
samp[s].resize(heuristics.size());
samp and temporary_samp are of type map<State, vector<int> >.
Would it make sense to use a StateRegistry object here, register the states and
use a PerStateInformation instead of that map? If we did not use the global
StateRegistry but a local object we could delete it and the PerStateInformation
after sampling.
See also: my comment on state.cc#newcode75

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc
File src/search/state.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode58
src/search/state.cc:58: return new State(registered_state);
On 2012/08/30 18:35:54, Malte wrote:
> I guess we should look at how g_initial_state is used. I think that the
searches
> shouldn't do more with it than put it into the open list at the start of the
> search at the moment. So for me, it would make sense for them to register it
> like they register everything else they put into open. I don't think they need
> to hang on to the initial state for any other purpose, but I'm not really
sure.

You were right, its not a big problem for the searches. There are two
exceptions,
however: In lazy and eager search there are two situations were we need a valid
SearchNode and use the node of the initial state:
 * In lazy search we need the node as a dummy parent node for the initial state.
 * In eager search it is used as a dummy return type in case the search fails.
Both cases are only technical dependencies that stem from the fact that
SearchNode
has no default constructor. The actual state is never used. Both cases are also
only called once per search so they are not time critical.

For now I registered the inital state again just before it is used to get the
SearchNode to keep the hack as local as possible.

> The heuristics that use it probably use it for generating random walks in the
> state space (Erez's learning stuff and the iPDB code) and don't want
registered
> states.

Right again. The only two things I ran into here were:
 * When I started introducing the search context (issue77) I assumed that
heuristic evaluations were always on registered states (so we could use the
state_id as context). This assumption is obviously wrong for heuristics like
selective_max, merge_and_shrink, pattern_generation_haslum and
probe_state_space_sample. But since this belongs to issue77 its probably best to
defer this until issue344 is done.
 * An idea for probe_state_space_sample --> see my comment there.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode75
src/search/state.cc:75: assert(handle.is_valid());
On 2012/08/16 09:00:05, karpase wrote:
> This assertion does not hold when running selective max:
> downward-1-debug --search
>
"astar(selmax([lmcut(),lmcount(lm_merged([lm_hm(m=1),lm_rhw()]),admissible=true)],training_set=1000),mpd=true)"
> 
> This is probably because the state space sample creates unregistered states,
but
> I'm not familiar enough with the code to fix it.

I had a look at the issue with selective max. The problem seems to be the
following:
During training the selective max heuristic uses a landmark count heuristic.
The latter uses a PerStateInformation to save landmarks. Since the training
states
are not registered, they do not have a valid handle or id.

There seems to be an underlying problem here: A heuristic can be used in
training
mode or with registered states from the search engine. If each heuristic would
be
responsible for registering its own states it would create a duplicate of the
search engine's state registry in the second case. Obviously registering
everything
globally would defeat the purpose of having unregistered states and multiple
state registries.

One option would be to have the selective max heuristic use its own
state registry for training and remove it after the training. However this would
somehow need to be propagated to all participating heuristics (e.g. the landmark
count heuristic in this case). Those can be nested again (e.g. in a max
evaluator).
I propose to introduce a new method in the class Heuristic for this, that makes
sure this heuristic and all subheuristics use a given registry. However, It is
not
clear to me how to reset this later. In particular when the heuristics could
have
used different registries before the training.

An alternative would be to have the selective max heuristic register the state
before passing it to heuristics[i]->evaluate(). The problem there could be that
the PerStateInformation classes contained in the landmark heuristic would update
their size according to the wrong registry, and states registered by the
heuristic
itself would use the wrong registry, e.g. at the moment it registers the initial
state.

http://codereview.appspot.com/6461087/diff/1/src/search/state.h
File src/search/state.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.h#newcode28
src/search/state.h:28: // TODO why is g_initial_state a pointer?
> > I see. Is it strange to have this "constructor" return a pointer, while the
> > others return a value?
> 
> It is a bit fishy, I guess. Having a create_... function that returns a
pointer
> because it generates an object on the heap is quite common, though. Maybe we
> should reserve create_... for this feature and use something else (build_...,
> make_..., ?) for other purposes?

Since this is a named constructor, how do you like
"construct_(un)registered_successor"

> Having a function that returns a State work as a kind of constructor is also a
> bit unfortunate because it involves copying. But I don't have a concrete
> suggestion for improvement at the moment.

From what I read, all modern compilers should be able to avoid the additional
temporary copy as long as it is used like a constructor.
http://www.parashift.com/c++-faq-lite/named-ctor-idiom.html (At the very end of
the article)
http://www.parashift.com/c++-faq-lite/return-by-value-optimization.html

That is, there should be no copy operation if it is used like this:
  State succ = State::construct_registered_successor(...);
But there has to be a copy operation (even with a normal constructor) if it is
used like this:
  State succ;
  /* succ used in some other way */
  succ = State::construct_registered_successor(...);

Sign in to reply to this message.

karpase

I think this is starting to look really good. See a few responses below. On ...

11 years, 7 months ago (2012-09-02 07:30:01 UTC) #8

I think this is starting to look really good.
See a few responses below.

On Fri, Aug 31, 2012 at 8:48 PM, <flo.pom@gmx.de> wrote:

> Started working on the ownership issue. Looks good so far, but its too
> big a change to describe it in the comments, so I'll post a new patch
> set here on Monday.
>
> The following comments are in response to Malte's last message and some
> other open issues. Sorry for the long email.
>
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
learning/probe_state_space_**sample.cc<http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_space_sample.cc>
> File src/search/learning/probe_**state_space_sample.cc (right):
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
learning/probe_state_space_**sample.cc#newcode90<http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_space_sample.cc#newcode90>
> src/search/learning/probe_**state_space_sample.cc:90:
> samp[s].resize(heuristics.**size());
> samp and temporary_samp are of type map<State, vector<int> >.
> Would it make sense to use a StateRegistry object here, register the
> states and use a PerStateInformation instead of that map? If we did not
> use the global StateRegistry but a local object we could delete it and
> the PerStateInformation after sampling.
> See also: my comment on state.cc#newcode75


Sounds like a good idea to me.
Let me know if you have any problems with this.


>
>
>
http://codereview.appspot.com/**6461087/diff/1/src/search/**state.cc<http://c...
> File src/search/state.cc (right):
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state.cc#newcode58<http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode58>
> src/search/state.cc:58: return new State(registered_state);
> On 2012/08/30 18:35:54, Malte wrote:
>
>> I guess we should look at how g_initial_state is used. I think that
>>
> the searches
>
>> shouldn't do more with it than put it into the open list at the start
>>
> of the
>
>> search at the moment. So for me, it would make sense for them to
>>
> register it
>
>> like they register everything else they put into open. I don't think
>>
> they need
>
>> to hang on to the initial state for any other purpose, but I'm not
>>
> really sure.
>
> You were right, its not a big problem for the searches. There are two
> exceptions,
> however: In lazy and eager search there are two situations were we need
> a valid
> SearchNode and use the node of the initial state:
>  * In lazy search we need the node as a dummy parent node for the
> initial state.
>  * In eager search it is used as a dummy return type in case the search
> fails.
> Both cases are only technical dependencies that stem from the fact that
> SearchNode
> has no default constructor. The actual state is never used. Both cases
> are also
> only called once per search so they are not time critical.
>
> For now I registered the inital state again just before it is used to
> get the
> SearchNode to keep the hack as local as possible.
>
>
>
>  The heuristics that use it probably use it for generating random walks
>>
> in the
>
>> state space (Erez's learning stuff and the iPDB code) and don't want
>>
> registered
>
>> states.
>>
>
> Right again. The only two things I ran into here were:
>  * When I started introducing the search context (issue77) I assumed
> that heuristic evaluations were always on registered states (so we could
> use the state_id as context). This assumption is obviously wrong for
> heuristics like selective_max, merge_and_shrink,
> pattern_generation_haslum and probe_state_space_sample. But since this
> belongs to issue77 its probably best to defer this until issue344 is
> done.
>  * An idea for probe_state_space_sample --> see my comment there.
>

> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state.cc#newcode75<http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode75>
> src/search/state.cc:75: assert(handle.is_valid());
>
> On 2012/08/16 09:00:05, karpase wrote:
>
>> This assertion does not hold when running selective max:
>> downward-1-debug --search
>>
>
> "astar(selmax([lmcut(),**lmcount(lm_merged([lm_hm(m=1),**
> lm_rhw()]),admissible=true)],**training_set=1000),mpd=true)"
>
>  This is probably because the state space sample creates unregistered
>>
> states, but
>
>> I'm not familiar enough with the code to fix it.
>>
>
> I had a look at the issue with selective max. The problem seems to be
> the following:
> During training the selective max heuristic uses a landmark count
> heuristic.
> The latter uses a PerStateInformation to save landmarks. Since the
> training states
> are not registered, they do not have a valid handle or id.
>
> There seems to be an underlying problem here: A heuristic can be used in
> training
> mode or with registered states from the search engine. If each heuristic
> would be
> responsible for registering its own states it would create a duplicate
> of the
> search engine's state registry in the second case. Obviously registering
> everything
> globally would defeat the purpose of having unregistered states and
> multiple
> state registries.
>
> One option would be to have the selective max heuristic use its own
> state registry for training and remove it after the training. However
> this would
> somehow need to be propagated to all participating heuristics (e.g. the
> landmark
> count heuristic in this case). Those can be nested again (e.g. in a max
> evaluator).
> I propose to introduce a new method in the class Heuristic for this,
> that makes
> sure this heuristic and all subheuristics use a given registry. However,
> It is not
> clear to me how to reset this later. In particular when the heuristics
> could have
> used different registries before the training.
>
> An alternative would be to have the selective max heuristic register the
> state
> before passing it to heuristics[i]->evaluate(). The problem there could
> be that
> the PerStateInformation classes contained in the landmark heuristic
> would update
> their size according to the wrong registry, and states registered by the
> heuristic
> itself would use the wrong registry, e.g. at the moment it registers the
> initial
> state.



I think it's a good idea to be able to have heuristics (and
ScalarEvaluators in general) change their StateRegistry.
This also (sometimes) makes sense for iterated searches, when we don't want
the new search to use information that was gathered during the old search.
So I think your first option is a good idea.




>
>
>
http://codereview.appspot.com/**6461087/diff/1/src/search/**state.h<http://co...
> File src/search/state.h (right):
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state.h#newcode28<http://codereview.appspot.com/6461087/diff/1/src/search/state.h#newcode28>
> src/search/state.h:28: // TODO why is g_initial_state a pointer?
>
>> > I see. Is it strange to have this "constructor" return a pointer,
>>
> while the
>
>> > others return a value?
>>
>
>  It is a bit fishy, I guess. Having a create_... function that returns
>>
> a pointer
>
>> because it generates an object on the heap is quite common, though.
>>
> Maybe we
>
>> should reserve create_... for this feature and use something else
>>
> (build_...,
>
>> make_..., ?) for other purposes?
>>
>
> Since this is a named constructor, how do you like
> "construct_(un)registered_**successor"
>
>
>  Having a function that returns a State work as a kind of constructor
>>
> is also a
>
>> bit unfortunate because it involves copying. But I don't have a
>>
> concrete
>
>> suggestion for improvement at the moment.
>>
>
> From what I read, all modern compilers should be able to avoid the
> additional temporary copy as long as it is used like a constructor.
>
http://www.parashift.com/c++-**faq-lite/named-ctor-idiom.html<http://www.para...
the very
> end of the article)
> http://www.parashift.com/c++-**faq-lite/return-by-value-**
>
optimization.html<http://www.parashift.com/c++-faq-lite/return-by-value-optimization.html>
>
> That is, there should be no copy operation if it is used like this:
>   State succ = State::construct_registered_**successor(...);
> But there has to be a copy operation (even with a normal constructor) if
> it is used like this:
>   State succ;
>   /* succ used in some other way */
>   succ = State::construct_registered_**successor(...);
>
>
http://codereview.appspot.com/**6461087/<http://codereview.appspot.com/6461087/>
>



-- 

--------------------------------------------------------------
"Adventure is just bad planning."
    Roald Amundsen
    Norwegian Arctic & Antarctic explorer
    (1872 - 1928)
--------------------------------------------------------------

Sign in to reply to this message.

Florian

No need to read this. Marked some things as "Done" again. http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information.h File src/search/per_state_information.h (right): ...

11 years, 7 months ago (2012-09-03 09:25:06 UTC) #9

No need to read this. Marked some things as "Done" again.

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information.h
File src/search/per_state_information.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/per_state_information...
src/search/per_state_information.h:70: }
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:34, Malte wrote:
> > It's convenient to have methods for all three of State, StateHandle and
> > state_id, but eventually we should have a clearer separation of which class
is
> > responsible for what. For example, the numerical IDs should be
implementation
> > details in as many places as possible.
> > 
> > I think that the StateHandle-based methods are the most sensible ones here
> > (state IDs are an implementation detail, and some states stored in State
don't
> > have an ID), and I'd like to have a (deferred?) TODO to get rid of the other
> two
> > access styles.
> 
> Added TODOs for now. I'll look into this later. I think getting rid of the
> accessor for State will not be a big deal, but the id accessor might need some
> work.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc
File src/search/state_handle.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:55: : representation(new
StateRepresentation(*(other.representation))) {
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:34, Malte wrote:
> > Hmmm... big conceptual mismatch for me here.
> > 
> > My intuition of copying a handle is not that the associated data is copied.
> I'd
> > expect the initialization "representation(other.representation)" here.
> > 
> > If we really need a copy here, I think there's something fishy with our use
of
> > these handles.
> 
> Right now the actual data is not copied, only the StateRepresentation object
> which contains a pointer to the data. This might be one indirection to much or
> just a bad name for the StateRepresentation class. I'll think about this again
> after I fixed the ownership issue that we talked about before. I copied the
> basic template for the PIMPL pattern from Wikipedia. There the implementation
> object (*representation in our case) is deep copied because the handle has
> ownership of it. I reckon this will be clearer once I figured out how to
manage
> the ownership of the data correctly in our case.
> 

Done. See new patch set.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:60: std::swap(this->representation,
other.representation);
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/17 14:12:31, Malte wrote:
> > On 2012/08/16 09:00:05, karpase wrote:
> > > Should this change other?
> > > Seems strange to me, but I don't have the complete picture yet.
> > 
> > Agreed. If this is intentional, it needs explanation.
> 
> This was also part of the Wikipedia implementation. I guess the reasoning is
> that "other" is given by value and so we can change the copy. By swapping the
> pointers we ensure the correct destruction of anything that was previously in
> "this". For now, I added a comment explaining this, but this method might be
> unnecessary altogether if the Handle doesn't have ownership of the
> representation. 

Done. See new patch set.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:65: delete representation;
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > Related to the issue above: getting rid of a handle shouldn't get rid of the
> > data. I'd expect the destructor to do nothing.
> > 
> > (The main reason we have handles is that we can cheaply move states around
--
> > but if every copying/destruction of a handle essentially involves
> > copying/destroying the state info, we lose this possibility.)
> As mentioned above, this doesn't really delete the data, only the
> StateRepresentation object, which contains but does not own the state_var_t
> pointer. So at the moment it does the right thing, but will probably change
with
> the ownership issue

Done. See new patch set.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:77: return representation->id != INVALID_HANLDE;
On 2012/08/20 15:16:35, Malte wrote:
> I don't like "invalid" representations. I'd much prefer if a state
> representations always actually represents a state.
> 
> Would it be possible to use representation == 0 to signify invalid handles
> instead, assuming that we need invalid handles at all. (Actually I'd like to
get
> rid of invalid handles, too.)

Done. See new patch set.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:93: // This case happens during state registration.
On 2012/08/20 15:16:35, Malte wrote:
> Do we have to do it this way? I'd much prefer if a handle was *always* a
pointer
> to an already registered state (or 0 if invalid), so that operator== would
> really just be a comparison of representation.

Done. See new patch set.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:97: } else {
On 2012/08/20 15:16:35, Malte wrote:
> "contains no data" for me should be the same as "invalid"; it'd be good to be
> consistent in terminology.

Done. See new patch set.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:101: }
On 2012/08/20 15:16:35, Malte wrote:
> In summary, I think this method should be:
>     return representation == other.representation;
> (and should maybe be inlined?).

Done. See new patch set.

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h
File src/search/state_registry.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newc...
src/search/state_registry.h:10: typedef __gnu_cxx::hash_set<StateHandle>
HandleSet;
On 2012/08/20 15:16:35, Malte wrote:
> OK, now I see why StateHandle has the value-based comparisons in the equality
> function and in the hashing code. I'd prefer to keep this functionality out of
> StateHandle -- which is a user-facing class -- and have it inside the
> StateRegistry implementation instead.
> 
> One way to do this is to use the three-argument form of hash_set. Then the
> hashing and value-based comparison code could live inside the state registry
> code, and there would be no trace of them in the interface of StateHandle.
> 
> I also think it might be clearer to replace HandleSet with a
> hash_set<StateRepresentation *, ...> instead, since it makes its clear that
> we're really doing something different from storing handles here.

Done. See new patch set.

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newc...
src/search/state_registry.h:24: State get_registered_state(const State &state);
On 2012/08/30 16:38:32, flo.pom wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > Maybe clearer (as a later TODO?) to have this return a StateHandle? And
maybe
> > call it "get_state_handle" or "get_handle"?
> 
> Added a TODO for now. An alternative would be to leave it like this until we
> split up the State class and then change it to:
> RegisteredState get_registered_state(const UnregisteredState
> &unregistered_state);

Done. See new patch set.

http://codereview.appspot.com/6461087/diff/15002/src/search/Makefile
File src/search/Makefile (right):

http://codereview.appspot.com/6461087/diff/15002/src/search/Makefile#newcode233
src/search/Makefile:233: LINKOPT_DEBUG  += -Wl,--no-as-needed -lrt
This is just a local change I need to compile in debug mode (see
http://ubuntuforums.org/showthread.php?t=1870586). This is just in my working
copy not committed as part of the patch. Rietveld's upload tool just uploaded it
along with the other files.

Sign in to reply to this message.

Malte

Another short round of comments. http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_space_sample.cc File src/search/learning/probe_state_space_sample.cc (right): http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_space_sample.cc#newcode90 src/search/learning/probe_state_space_sample.cc:90: samp[s].resize(heuristics.size()); On 2012/08/31 17:48:36, ...

11 years, 7 months ago (2012-09-07 10:33:03 UTC) #10

Another short round of comments.

http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_...
File src/search/learning/probe_state_space_sample.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_...
src/search/learning/probe_state_space_sample.cc:90:
samp[s].resize(heuristics.size());
On 2012/08/31 17:48:36, flo.pom wrote:
> samp and temporary_samp are of type map<State, vector<int> >.
> Would it make sense to use a StateRegistry object here, register the states
and
> use a PerStateInformation instead of that map? If we did not use the global
> StateRegistry but a local object we could delete it and the
PerStateInformation
> after sampling.
> See also: my comment on state.cc#newcode75

Sounds reasonable, but as a general note, I don't know the learning code well
enough to comment and am generally happy to let Erez make all decisions there
without additional coordination.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc
File src/search/state.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode75
src/search/state.cc:75: assert(handle.is_valid());
This sounds potentially nasty; none of the solution is really appealing. My
suggestion is to go with whatever you prefer, but we might want to revisit this
later to clean things up.

http://codereview.appspot.com/6461087/diff/1/src/search/state.h
File src/search/state.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.h#newcode28
src/search/state.h:28: // TODO why is g_initial_state a pointer?
On 2012/08/31 17:48:36, flo.pom wrote:
> Since this is a named constructor, how do you like
> "construct_(un)registered_successor"

I had the same thought and only neglected to mention it because of the length of
the word "construct", which is probably a stupid reason. So yes, fine with me.

> From what I read, all modern compilers should be able to avoid the additional
> temporary copy as long as it is used like a constructor.
> http://www.parashift.com/c++-faq-lite/named-ctor-idiom.html (At the very end
of
> the article)
> http://www.parashift.com/c++-faq-lite/return-by-value-optimization.html
> 
> That is, there should be no copy operation if it is used like this:
>   State succ = State::construct_registered_successor(...);

Sounds good.

> But there has to be a copy operation (even with a normal constructor) if it is
> used like this:
>   State succ;
>   /* succ used in some other way */
>   succ = State::construct_registered_successor(...);

I think State shouldn't have a default constructor anyway (does it currently?),
so this shouldn't compile.

Sign in to reply to this message.

Florian

As we discussed yesterday, here is a list of comment threads that are still open ...

11 years, 7 months ago (2012-09-27 09:48:55 UTC) #11

As we discussed yesterday, here is a list of comment threads that are still open
or are handled in the second patch set.
I didn't email my last set of comments where I also marked a few things as
handled in patch set 2. To make this email comprehensive I repeated those
comments here. With 2 exceptions everything that is still open is in this email.
The exceptions are:

* How to handle unregistered states: We have already discussed this in the
comments. I'll tackle this together with your next batch of comments and publish
a third patch set including it. I'll post another comment about it then.

* TODOs that are already in the code but that should be done after the first
evaluation: I'll send comments about those once I finished the evaluation.

http://codereview.appspot.com/6461087/diff/1/src/search/globals.cc
File src/search/globals.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/globals.cc#newcode248
src/search/globals.cc:248: // state in the output format
On 2012/08/30 16:38:32, Florian wrote:
> On 2012/08/20 15:16:34, Malte wrote:
> > I think this is fine as is -- we generally try to break the output format
only
> > if the benefit is really large.
> I talked to Gabi about this and she said that there is an upcoming change in
the
> output format that would break compatibility with older versions anyway. If
> there are no other reasons to keep this order, this might be a good time to
> change it.
> 

Should I leave the TODO?

http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_...
File src/search/learning/probe_state_space_sample.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_...
src/search/learning/probe_state_space_sample.cc:90:
samp[s].resize(heuristics.size());
On 2012/09/07 10:33:03, Malte wrote:
> On 2012/08/31 17:48:36, flo.pom wrote:
> > samp and temporary_samp are of type map<State, vector<int> >.
> > Would it make sense to use a StateRegistry object here, register the states
> and
> > use a PerStateInformation instead of that map? If we did not use the global
> > StateRegistry but a local object we could delete it and the
> PerStateInformation
> > after sampling.
> > See also: my comment on state.cc#newcode75
> 
> Sounds reasonable, but as a general note, I don't know the learning code well
> enough to comment and am generally happy to let Erez make all decisions there
> without additional coordination.

Done. Its not in Patchset 2 yet, but I'll try this.

http://codereview.appspot.com/6461087/diff/1/src/search/search_node_info.h
File src/search/search_node_info.h (left):

http://codereview.appspot.com/6461087/diff/1/src/search/search_node_info.h#ol...
src/search/search_node_info.h:14: int h : 31; // TODO:CR - should we get rid of
it
On 2012/08/16 09:00:05, karpase wrote:
> The PerStateInformation class gives us the chance to get rid of this
(finally).
> We can discuss this in more detail later.

Done. I'll mark this as "Done" because there already is an issue for this in the
tracker (issue339).

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc
File src/search/state.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode58
src/search/state.cc:58: return new State(registered_state);
On 2012/08/31 17:48:36, Florian wrote:
> On 2012/08/30 18:35:54, Malte wrote:
> > I guess we should look at how g_initial_state is used. I think that the
> searches
> > shouldn't do more with it than put it into the open list at the start of the
> > search at the moment. So for me, it would make sense for them to register it
> > like they register everything else they put into open. I don't think they
need
> > to hang on to the initial state for any other purpose, but I'm not really
> sure.
> 
> You were right, its not a big problem for the searches. There are two
> exceptions,
> however: In lazy and eager search there are two situations were we need a
valid
> SearchNode and use the node of the initial state:
>  * In lazy search we need the node as a dummy parent node for the initial
state.
>  * In eager search it is used as a dummy return type in case the search fails.
> Both cases are only technical dependencies that stem from the fact that
> SearchNode
> has no default constructor. The actual state is never used. Both cases are
also
> only called once per search so they are not time critical.
> 
> For now I registered the inital state again just before it is used to get the
> SearchNode to keep the hack as local as possible.
> 
> 
> > The heuristics that use it probably use it for generating random walks in
the
> > state space (Erez's learning stuff and the iPDB code) and don't want
> registered
> > states.
> 
> Right again. The only two things I ran into here were:
>  * When I started introducing the search context (issue77) I assumed that
> heuristic evaluations were always on registered states (so we could use the
> state_id as context). This assumption is obviously wrong for heuristics like
> selective_max, merge_and_shrink, pattern_generation_haslum and
> probe_state_space_sample. But since this belongs to issue77 its probably best
to
> defer this until issue344 is done.
>  * An idea for probe_state_space_sample --> see my comment there.

Done. If there are issues with this, please discuss them in patch set 2.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode75
src/search/state.cc:75: assert(handle.is_valid());
On 2012/09/07 10:33:03, Malte wrote:
> This sounds potentially nasty; none of the solution is really appealing. My
> suggestion is to go with whatever you prefer, but we might want to revisit
this
> later to clean things up.

Done. I'll go with the first option for now and we can discuss it in a third
patch set when I'm finished.

http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode89
src/search/state.cc:89: assert(other.handle.is_valid());
On 2012/08/16 09:00:05, karpase wrote:
> This assertion does not hold when running ipdb():
> downward-1-debug --search "astar(ipdb())" < output
> 
> Also probably because of the state space sampling creating unregistered
states.

Done. Yes this is the same issue. The assertion is no longer in patch set 2.

http://codereview.appspot.com/6461087/diff/1/src/search/state.h
File src/search/state.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state.h#newcode28
src/search/state.h:28: // TODO why is g_initial_state a pointer?
On 2012/09/07 10:33:03, Malte wrote:
> On 2012/08/31 17:48:36, flo.pom wrote:
> > Since this is a named constructor, how do you like
> > "construct_(un)registered_successor"
> 
> I had the same thought and only neglected to mention it because of the length
of
> the word "construct", which is probably a stupid reason. So yes, fine with me.
> 
> > From what I read, all modern compilers should be able to avoid the
additional
> > temporary copy as long as it is used like a constructor.
> > http://www.parashift.com/c++-faq-lite/named-ctor-idiom.html (At the very end
> of
> > the article)
> > http://www.parashift.com/c++-faq-lite/return-by-value-optimization.html
> > 
> > That is, there should be no copy operation if it is used like this:
> >   State succ = State::construct_registered_successor(...);
> 
> Sounds good.
> 
> > But there has to be a copy operation (even with a normal constructor) if it
is
> > used like this:
> >   State succ;
> >   /* succ used in some other way */
> >   succ = State::construct_registered_successor(...);
> 
> I think State shouldn't have a default constructor anyway (does it
currently?),
> so this shouldn't compile.

Done.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc
File src/search/state_handle.cc (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:55: : representation(new
StateRepresentation(*(other.representation))) {
On 2012/09/03 09:25:06, Florian wrote:
> On 2012/08/30 16:38:32, flo.pom wrote:
> > On 2012/08/20 15:16:34, Malte wrote:
> > > Hmmm... big conceptual mismatch for me here.
> > > 
> > > My intuition of copying a handle is not that the associated data is
copied.
> > I'd
> > > expect the initialization "representation(other.representation)" here.
> > > 
> > > If we really need a copy here, I think there's something fishy with our
use
> of
> > > these handles.
> > 
> > Right now the actual data is not copied, only the StateRepresentation object
> > which contains a pointer to the data. This might be one indirection to much
or
> > just a bad name for the StateRepresentation class. I'll think about this
again
> > after I fixed the ownership issue that we talked about before. I copied the
> > basic template for the PIMPL pattern from Wikipedia. There the
implementation
> > object (*representation in our case) is deep copied because the handle has
> > ownership of it. I reckon this will be clearer once I figured out how to
> manage
> > the ownership of the data correctly in our case.
> > 
> 
> Done. See new patch set.
Repeated this "Done" because I didn't publish it the last time.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:60: std::swap(this->representation,
other.representation);
On 2012/09/03 09:25:06, Florian wrote:
> On 2012/08/30 16:38:32, flo.pom wrote:
> > On 2012/08/17 14:12:31, Malte wrote:
> > > On 2012/08/16 09:00:05, karpase wrote:
> > > > Should this change other?
> > > > Seems strange to me, but I don't have the complete picture yet.
> > > 
> > > Agreed. If this is intentional, it needs explanation.
> > 
> > This was also part of the Wikipedia implementation. I guess the reasoning is
> > that "other" is given by value and so we can change the copy. By swapping
the
> > pointers we ensure the correct destruction of anything that was previously
in
> > "this". For now, I added a comment explaining this, but this method might be
> > unnecessary altogether if the Handle doesn't have ownership of the
> > representation. 
> 
> Done. See new patch set.
Repeated this "Done" because I didn't publish it the last time.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:65: delete representation;
On 2012/09/03 09:25:06, Florian wrote:
> On 2012/08/30 16:38:32, flo.pom wrote:
> > On 2012/08/20 15:16:35, Malte wrote:
> > > Related to the issue above: getting rid of a handle shouldn't get rid of
the
> > > data. I'd expect the destructor to do nothing.
> > > 
> > > (The main reason we have handles is that we can cheaply move states around
> --
> > > but if every copying/destruction of a handle essentially involves
> > > copying/destroying the state info, we lose this possibility.)
> > As mentioned above, this doesn't really delete the data, only the
> > StateRepresentation object, which contains but does not own the state_var_t
> > pointer. So at the moment it does the right thing, but will probably change
> with
> > the ownership issue
> 
> Done. See new patch set.
Repeated this "Done" because I didn't publish it the last time.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:77: return representation->id != INVALID_HANLDE;
On 2012/09/03 09:25:06, Florian wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > I don't like "invalid" representations. I'd much prefer if a state
> > representations always actually represents a state.
> > 
> > Would it be possible to use representation == 0 to signify invalid handles
> > instead, assuming that we need invalid handles at all. (Actually I'd like to
> get
> > rid of invalid handles, too.)
> 
> Done. See new patch set.

Repeated this "Done" because I didn't publish it the last time.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:93: // This case happens during state registration.
On 2012/09/03 09:25:06, Florian wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > Do we have to do it this way? I'd much prefer if a handle was *always* a
> pointer
> > to an already registered state (or 0 if invalid), so that operator== would
> > really just be a comparison of representation.
> 
> Done. See new patch set.
Repeated this "Done" because I didn't publish it the last time.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:97: } else {
On 2012/09/03 09:25:06, Florian wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > "contains no data" for me should be the same as "invalid"; it'd be good to
be
> > consistent in terminology.
> 
> Done. See new patch set.

Repeated this "Done" because I didn't publish it the last time.

http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newco...
src/search/state_handle.cc:101: }
On 2012/09/03 09:25:06, Florian wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > In summary, I think this method should be:
> >     return representation == other.representation;
> > (and should maybe be inlined?).
> 
> Done. See new patch set.

Repeated this "Done" because I didn't publish it the last time.

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h
File src/search/state_registry.h (right):

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newc...
src/search/state_registry.h:10: typedef __gnu_cxx::hash_set<StateHandle>
HandleSet;
On 2012/09/03 09:25:06, Florian wrote:
> On 2012/08/20 15:16:35, Malte wrote:
> > OK, now I see why StateHandle has the value-based comparisons in the
equality
> > function and in the hashing code. I'd prefer to keep this functionality out
of
> > StateHandle -- which is a user-facing class -- and have it inside the
> > StateRegistry implementation instead.
> > 
> > One way to do this is to use the three-argument form of hash_set. Then the
> > hashing and value-based comparison code could live inside the state registry
> > code, and there would be no trace of them in the interface of StateHandle.
> > 
> > I also think it might be clearer to replace HandleSet with a
> > hash_set<StateRepresentation *, ...> instead, since it makes its clear that
> > we're really doing something different from storing handles here.
> 
> Done. See new patch set.

Repeated this "Done" because I didn't publish it the last time.

http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newc...
src/search/state_registry.h:24: State get_registered_state(const State &state);
On 2012/09/03 09:25:06, Florian wrote:
> On 2012/08/30 16:38:32, flo.pom wrote:
> > On 2012/08/20 15:16:35, Malte wrote:
> > > Maybe clearer (as a later TODO?) to have this return a StateHandle? And
> maybe
> > > call it "get_state_handle" or "get_handle"?
> > 
> > Added a TODO for now. An alternative would be to leave it like this until we
> > split up the State class and then change it to:
> > RegisteredState get_registered_state(const UnregisteredState
> > &unregistered_state);
> 
> Done. See new patch set.
Repeated this "Done" because I didn't publish it the last time.

Sign in to reply to this message.

karpase

I don't have time to give this a thorough review right now. However, I did ...

11 years, 7 months ago (2012-09-28 08:54:13 UTC) #12

I don't have time to give this a thorough review right now.
However, I did take a brief look, and it looks good to me.
I'll try to do a more thorough review  next week.

Cheers,
Erez.


On Thu, Sep 27, 2012 at 11:48 AM, <flo.pom@gmx.de> wrote:

> As we discussed yesterday, here is a list of comment threads that are
> still open or are handled in the second patch set.
> I didn't email my last set of comments where I also marked a few things
> as handled in patch set 2. To make this email comprehensive I repeated
> those comments here. With 2 exceptions everything that is still open is
> in this email.
> The exceptions are:
>
> * How to handle unregistered states: We have already discussed this in
> the comments. I'll tackle this together with your next batch of comments
> and publish a third patch set including it. I'll post another comment
> about it then.
>
> * TODOs that are already in the code but that should be done after the
> first evaluation: I'll send comments about those once I finished the
> evaluation.
>
>
>
http://codereview.appspot.com/**6461087/diff/1/src/search/**globals.cc<http:/...
> File src/search/globals.cc (right):
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
globals.cc#newcode248<http://codereview.appspot.com/6461087/diff/1/src/search/globals.cc#newcode248>
> src/search/globals.cc:248: // state in the output format
> On 2012/08/30 16:38:32, Florian wrote:
>
>> On 2012/08/20 15:16:34, Malte wrote:
>> > I think this is fine as is -- we generally try to break the output
>>
> format only
>
>> > if the benefit is really large.
>> I talked to Gabi about this and she said that there is an upcoming
>>
> change in the
>
>> output format that would break compatibility with older versions
>>
> anyway. If
>
>> there are no other reasons to keep this order, this might be a good
>>
> time to
>
>> change it.
>>
>
>
> Should I leave the TODO?
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
learning/probe_state_space_**sample.cc<http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_space_sample.cc>
> File src/search/learning/probe_**state_space_sample.cc (right):
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
learning/probe_state_space_**sample.cc#newcode90<http://codereview.appspot.com/6461087/diff/1/src/search/learning/probe_state_space_sample.cc#newcode90>
> src/search/learning/probe_**state_space_sample.cc:90:
> samp[s].resize(heuristics.**size());
> On 2012/09/07 10:33:03, Malte wrote:
>
>> On 2012/08/31 17:48:36, flo.pom wrote:
>> > samp and temporary_samp are of type map<State, vector<int> >.
>> > Would it make sense to use a StateRegistry object here, register the
>>
> states
>
>> and
>> > use a PerStateInformation instead of that map? If we did not use the
>>
> global
>
>> > StateRegistry but a local object we could delete it and the
>> PerStateInformation
>> > after sampling.
>> > See also: my comment on state.cc#newcode75
>>
>
>  Sounds reasonable, but as a general note, I don't know the learning
>>
> code well
>
>> enough to comment and am generally happy to let Erez make all
>>
> decisions there
>
>> without additional coordination.
>>
>
> Done. Its not in Patchset 2 yet, but I'll try this.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
search_node_info.h<http://codereview.appspot.com/6461087/diff/1/src/search/search_node_info.h>
> File src/search/search_node_info.h (left):
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
search_node_info.h#oldcode14<http://codereview.appspot.com/6461087/diff/1/src/search/search_node_info.h#oldcode14>
> src/search/search_node_info.h:**14: int h : 31; // TODO:CR - should we get
> rid of it
> On 2012/08/16 09:00:05, karpase wrote:
>
>> The PerStateInformation class gives us the chance to get rid of this
>>
> (finally).
>
>> We can discuss this in more detail later.
>>
>
> Done. I'll mark this as "Done" because there already is an issue for
> this in the tracker (issue339).
>
>
http://codereview.appspot.com/**6461087/diff/1/src/search/**state.cc<http://c...
> File src/search/state.cc (right):
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state.cc#newcode58<http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode58>
> src/search/state.cc:58: return new State(registered_state);
> On 2012/08/31 17:48:36, Florian wrote:
>
>> On 2012/08/30 18:35:54, Malte wrote:
>> > I guess we should look at how g_initial_state is used. I think that
>>
> the
>
>> searches
>> > shouldn't do more with it than put it into the open list at the
>>
> start of the
>
>> > search at the moment. So for me, it would make sense for them to
>>
> register it
>
>> > like they register everything else they put into open. I don't think
>>
> they need
>
>> > to hang on to the initial state for any other purpose, but I'm not
>>
> really
>
>> sure.
>>
>
>  You were right, its not a big problem for the searches. There are two
>> exceptions,
>> however: In lazy and eager search there are two situations were we
>>
> need a valid
>
>> SearchNode and use the node of the initial state:
>>   * In lazy search we need the node as a dummy parent node for the
>>
> initial state.
>
>>   * In eager search it is used as a dummy return type in case the
>>
> search fails.
>
>> Both cases are only technical dependencies that stem from the fact
>>
> that
>
>> SearchNode
>> has no default constructor. The actual state is never used. Both cases
>>
> are also
>
>> only called once per search so they are not time critical.
>>
>
>  For now I registered the inital state again just before it is used to
>>
> get the
>
>> SearchNode to keep the hack as local as possible.
>>
>
>
>  > The heuristics that use it probably use it for generating random
>>
> walks in the
>
>> > state space (Erez's learning stuff and the iPDB code) and don't want
>> registered
>> > states.
>>
>
>  Right again. The only two things I ran into here were:
>>   * When I started introducing the search context (issue77) I assumed
>>
> that
>
>> heuristic evaluations were always on registered states (so we could
>>
> use the
>
>> state_id as context). This assumption is obviously wrong for
>>
> heuristics like
>
>> selective_max, merge_and_shrink, pattern_generation_haslum and
>> probe_state_space_sample. But since this belongs to issue77 its
>>
> probably best to
>
>> defer this until issue344 is done.
>>   * An idea for probe_state_space_sample --> see my comment there.
>>
>
> Done. If there are issues with this, please discuss them in patch set 2.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state.cc#newcode75<http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode75>
> src/search/state.cc:75: assert(handle.is_valid());
> On 2012/09/07 10:33:03, Malte wrote:
>
>> This sounds potentially nasty; none of the solution is really
>>
> appealing. My
>
>> suggestion is to go with whatever you prefer, but we might want to
>>
> revisit this
>
>> later to clean things up.
>>
>
> Done. I'll go with the first option for now and we can discuss it in a
> third patch set when I'm finished.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state.cc#newcode89<http://codereview.appspot.com/6461087/diff/1/src/search/state.cc#newcode89>
> src/search/state.cc:89: assert(other.handle.is_valid()**);
> On 2012/08/16 09:00:05, karpase wrote:
>
>> This assertion does not hold when running ipdb():
>> downward-1-debug --search "astar(ipdb())" < output
>>
>
>  Also probably because of the state space sampling creating
>>
> unregistered states.
>
> Done. Yes this is the same issue. The assertion is no longer in patch
> set 2.
>
>
http://codereview.appspot.com/**6461087/diff/1/src/search/**state.h<http://co...
> File src/search/state.h (right):
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state.h#newcode28<http://codereview.appspot.com/6461087/diff/1/src/search/state.h#newcode28>
> src/search/state.h:28: // TODO why is g_initial_state a pointer?
> On 2012/09/07 10:33:03, Malte wrote:
>
>> On 2012/08/31 17:48:36, flo.pom wrote:
>> > Since this is a named constructor, how do you like
>> > "construct_(un)registered_**successor"
>>
>
>  I had the same thought and only neglected to mention it because of the
>>
> length of
>
>> the word "construct", which is probably a stupid reason. So yes, fine
>>
> with me.
>
>  > From what I read, all modern compilers should be able to avoid the
>>
> additional
>
>> > temporary copy as long as it is used like a constructor.
>> >
http://www.parashift.com/c++-**faq-lite/named-ctor-idiom.html<http://www.para...
the
>>
> very end
>
>> of
>> > the article)
>> >
>>
> http://www.parashift.com/c++-**faq-lite/return-by-value-**
>
optimization.html<http://www.parashift.com/c++-faq-lite/return-by-value-optimization.html>
>
>> >
>> > That is, there should be no copy operation if it is used like this:
>> >   State succ = State::construct_registered_**successor(...);
>>
>
>  Sounds good.
>>
>
>  > But there has to be a copy operation (even with a normal
>>
> constructor) if it is
>
>> > used like this:
>> >   State succ;
>> >   /* succ used in some other way */
>> >   succ = State::construct_registered_**successor(...);
>>
>
>  I think State shouldn't have a default constructor anyway (does it
>>
> currently?),
>
>> so this shouldn't compile.
>>
>
> Done.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_handle.cc<http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc>
> File src/search/state_handle.cc (right):
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_handle.cc#newcode55<http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newcode55>
> src/search/state_handle.cc:55: : representation(new
> StateRepresentation(*(other.**representation))) {
> On 2012/09/03 09:25:06, Florian wrote:
>
>> On 2012/08/30 16:38:32, flo.pom wrote:
>> > On 2012/08/20 15:16:34, Malte wrote:
>> > > Hmmm... big conceptual mismatch for me here.
>> > >
>> > > My intuition of copying a handle is not that the associated data
>>
> is copied.
>
>> > I'd
>> > > expect the initialization "representation(other.**representation)"
>>
> here.
>
>> > >
>> > > If we really need a copy here, I think there's something fishy
>>
> with our use
>
>> of
>> > > these handles.
>> >
>> > Right now the actual data is not copied, only the
>>
> StateRepresentation object
>
>> > which contains a pointer to the data. This might be one indirection
>>
> to much or
>
>> > just a bad name for the StateRepresentation class. I'll think about
>>
> this again
>
>> > after I fixed the ownership issue that we talked about before. I
>>
> copied the
>
>> > basic template for the PIMPL pattern from Wikipedia. There the
>>
> implementation
>
>> > object (*representation in our case) is deep copied because the
>>
> handle has
>
>> > ownership of it. I reckon this will be clearer once I figured out
>>
> how to
>
>> manage
>> > the ownership of the data correctly in our case.
>> >
>>
>
>  Done. See new patch set.
>>
> Repeated this "Done" because I didn't publish it the last time.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_handle.cc#newcode60<http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newcode60>
> src/search/state_handle.cc:60: std::swap(this->**representation,
> other.representation);
> On 2012/09/03 09:25:06, Florian wrote:
>
>> On 2012/08/30 16:38:32, flo.pom wrote:
>> > On 2012/08/17 14:12:31, Malte wrote:
>> > > On 2012/08/16 09:00:05, karpase wrote:
>> > > > Should this change other?
>> > > > Seems strange to me, but I don't have the complete picture yet.
>> > >
>> > > Agreed. If this is intentional, it needs explanation.
>> >
>> > This was also part of the Wikipedia implementation. I guess the
>>
> reasoning is
>
>> > that "other" is given by value and so we can change the copy. By
>>
> swapping the
>
>> > pointers we ensure the correct destruction of anything that was
>>
> previously in
>
>> > "this". For now, I added a comment explaining this, but this method
>>
> might be
>
>> > unnecessary altogether if the Handle doesn't have ownership of the
>> > representation.
>>
>
>  Done. See new patch set.
>>
> Repeated this "Done" because I didn't publish it the last time.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_handle.cc#newcode65<http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newcode65>
> src/search/state_handle.cc:65: delete representation;
> On 2012/09/03 09:25:06, Florian wrote:
>
>> On 2012/08/30 16:38:32, flo.pom wrote:
>> > On 2012/08/20 15:16:35, Malte wrote:
>> > > Related to the issue above: getting rid of a handle shouldn't get
>>
> rid of the
>
>> > > data. I'd expect the destructor to do nothing.
>> > >
>> > > (The main reason we have handles is that we can cheaply move
>>
> states around
>
>> --
>> > > but if every copying/destruction of a handle essentially involves
>> > > copying/destroying the state info, we lose this possibility.)
>> > As mentioned above, this doesn't really delete the data, only the
>> > StateRepresentation object, which contains but does not own the
>>
> state_var_t
>
>> > pointer. So at the moment it does the right thing, but will probably
>>
> change
>
>> with
>> > the ownership issue
>>
>
>  Done. See new patch set.
>>
> Repeated this "Done" because I didn't publish it the last time.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_handle.cc#newcode77<http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newcode77>
> src/search/state_handle.cc:77: return representation->id !=
> INVALID_HANLDE;
> On 2012/09/03 09:25:06, Florian wrote:
>
>> On 2012/08/20 15:16:35, Malte wrote:
>> > I don't like "invalid" representations. I'd much prefer if a state
>> > representations always actually represents a state.
>> >
>> > Would it be possible to use representation == 0 to signify invalid
>>
> handles
>
>> > instead, assuming that we need invalid handles at all. (Actually I'd
>>
> like to
>
>> get
>> > rid of invalid handles, too.)
>>
>
>  Done. See new patch set.
>>
>
> Repeated this "Done" because I didn't publish it the last time.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_handle.cc#newcode93<http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newcode93>
> src/search/state_handle.cc:93: // This case happens during state
> registration.
> On 2012/09/03 09:25:06, Florian wrote:
>
>> On 2012/08/20 15:16:35, Malte wrote:
>> > Do we have to do it this way? I'd much prefer if a handle was
>>
> *always* a
>
>> pointer
>> > to an already registered state (or 0 if invalid), so that operator==
>>
> would
>
>> > really just be a comparison of representation.
>>
>
>  Done. See new patch set.
>>
> Repeated this "Done" because I didn't publish it the last time.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_handle.cc#newcode97<http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newcode97>
> src/search/state_handle.cc:97: } else {
> On 2012/09/03 09:25:06, Florian wrote:
>
>> On 2012/08/20 15:16:35, Malte wrote:
>> > "contains no data" for me should be the same as "invalid"; it'd be
>>
> good to be
>
>> > consistent in terminology.
>>
>
>  Done. See new patch set.
>>
>
> Repeated this "Done" because I didn't publish it the last time.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_handle.cc#newcode101<http://codereview.appspot.com/6461087/diff/1/src/search/state_handle.cc#newcode101>
> src/search/state_handle.cc:**101: }
> On 2012/09/03 09:25:06, Florian wrote:
>
>> On 2012/08/20 15:16:35, Malte wrote:
>> > In summary, I think this method should be:
>> >     return representation == other.representation;
>> > (and should maybe be inlined?).
>>
>
>  Done. See new patch set.
>>
>
> Repeated this "Done" because I didn't publish it the last time.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_registry.h<http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h>
> File src/search/state_registry.h (right):
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_registry.h#newcode10<http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newcode10>
> src/search/state_registry.h:**10: typedef __gnu_cxx::hash_set<**
> StateHandle>
> HandleSet;
> On 2012/09/03 09:25:06, Florian wrote:
>
>> On 2012/08/20 15:16:35, Malte wrote:
>> > OK, now I see why StateHandle has the value-based comparisons in the
>>
> equality
>
>> > function and in the hashing code. I'd prefer to keep this
>>
> functionality out of
>
>> > StateHandle -- which is a user-facing class -- and have it inside
>>
> the
>
>> > StateRegistry implementation instead.
>> >
>> > One way to do this is to use the three-argument form of hash_set.
>>
> Then the
>
>> > hashing and value-based comparison code could live inside the state
>>
> registry
>
>> > code, and there would be no trace of them in the interface of
>>
> StateHandle.
>
>> >
>> > I also think it might be clearer to replace HandleSet with a
>> > hash_set<StateRepresentation *, ...> instead, since it makes its
>>
> clear that
>
>> > we're really doing something different from storing handles here.
>>
>
>  Done. See new patch set.
>>
>
> Repeated this "Done" because I didn't publish it the last time.
>
> http://codereview.appspot.com/**6461087/diff/1/src/search/**
>
state_registry.h#newcode24<http://codereview.appspot.com/6461087/diff/1/src/search/state_registry.h#newcode24>
> src/search/state_registry.h:**24: State get_registered_state(const State
> &state);
> On 2012/09/03 09:25:06, Florian wrote:
>
>> On 2012/08/30 16:38:32, flo.pom wrote:
>> > On 2012/08/20 15:16:35, Malte wrote:
>> > > Maybe clearer (as a later TODO?) to have this return a
>>
> StateHandle? And
>
>> maybe
>> > > call it "get_state_handle" or "get_handle"?
>> >
>> > Added a TODO for now. An alternative would be to leave it like this
>>
> until we
>
>> > split up the State class and then change it to:
>> > RegisteredState get_registered_state(const UnregisteredState
>> > &unregistered_state);
>>
>
>  Done. See new patch set.
>>
> Repeated this "Done" because I didn't publish it the last time.
>
>
http://codereview.appspot.com/**6461087/<http://codereview.appspot.com/6461087/>
>



-- 

--------------------------------------------------------------
"Adventure is just bad planning."
    Roald Amundsen
    Norwegian Arctic & Antarctic explorer
    (1872 - 1928)
--------------------------------------------------------------

Sign in to reply to this message.

karpase

Hi Florian, Nice work indeed. I just had one meta-comment, which I don't really think ...

11 years, 7 months ago (2012-10-01 08:30:56 UTC) #13

malte.helmert

11 years, 3 months ago (2013-01-07 13:33:28 UTC) #14

This is in reply to the email I received on 2007-09-27 -- hope I didn't miss
anything in between.

Only one more comment this time, plus a reply to a comment for the email:

> * How to handle unregistered states: We have already
> discussed this in the comments. I'll tackle this together
> with your next batch of comments and publish a third
> patch set including it. I'll post another comment
> about it then.

My suggestion is to keep this as simple for now, e.g. only having a single
global state registry (if that's the simplest thing). If that breaks the
learning code (which I don't hope), we can refine the strategy later; we
shouldn't let that keep us from starting to merge the coe. I don't think it
should affect anything else, right?

https://codereview.appspot.com/6461087/diff/1/src/search/globals.cc
File src/search/globals.cc (right):

https://codereview.appspot.com/6461087/diff/1/src/search/globals.cc#newcode248
src/search/globals.cc:248: // state in the output format
On 2012/09/27 09:48:55, Florian wrote:
> Should I leave the TODO?

Output format changes are disruptive, so if there are multiple things we'd like
to change, it'd be good to change them at the same time. So I think instead of a
TODO in the code, it's better to open a tracker issue that collects suggested
changes for the next output format change. If you think this is a good idea,
please open such an issue and send a mail to downward-dev about it since it's of
general interest.

Sign in to reply to this message.

Issue 6461087: issue344 introduced state handles

Description

Patch Set 1 #

Patch Set 2 : Rewrote implementation of StateHandle #

Messages