Re: [gnugo-devel] connection reader speed optimization

[Paul Pogonyshev]

Arend wrote:
> Paul wrote:
> > Arend wrote:
> > > One change in this patch is that only the origin, not all stones, of a
> > > string get added to the connection queue. Is this necessary/useful?
>
> (...)
>
> > Well, this was a speed optimization attempt :)  It reduces the number of
> > queue scans a lot, but on the second thought that probably doesn't matter
> > much in terms of speed.  So, this change can be taken out of the patch.
> >
> > However, i have a counter-proposal.  Is it really the intention to have
> > partial strings in break-in goal array?  Maybe fixing this will give an
> > improvement in break-in efficiency?  In other words i propose you to
> > investigate the matter :)
>
> I haven't seen an example of this yet, but yes, I need to improve the
> code in compute_smaller_goal(), for example. (Are you sure this happens
> without your patch?)

Yes, when i looked into ego:10 (that subnode you pointed out in one of
the previous messages), unpatched version had distances 0.0 and 0.9 on
a same string -- this would have been completely impossible if the whole
string had been in the goal, right?

And if you look at the code in compute_smaller_goal() (unpatched), you
can spot at least two places where results for stones of a same string
can deviate.  Namely, the Manhattan distance calculation and the check
for the number of neighbors in goal.

> But I think it would be easier to do this if we revert your change
> to the connection queues. For example, you have (inadvertently, I
> believe) changed the logic in compute_smaller_goal(), and it would be
> easier to restore (and improve) it in that case.

No, the change was intentional.  As i mentioned above, the Manhattan
distance stuff seemed bogus to me and i changed it, thus having fixed
one fail which the patch used to cause on early stages.  Correct me if
i missed something, but your version heavily depended on stone position
and therefore could produce different results for stones of a same string.

Basically, we need to clarify one thing: how bad is that break-in code
puts incomplete strings into goal?  From your replies it seems that this
is not a "feature".  Then we have two options: either it's a (severe)
bug, or it was not specifically coded to work this way, but doesn't
matter much.

In any case a string seems to be a fundamental unit to me and i cannot
think of reason to split it into goal part and non-goal part.  Hence it
seems to me that having only origins in the queue is actually a good
idea, because it in some way forces to treat strings as units.

> Maybe it's most productive if I continue to work with your patch?

Agreed.  I would recommend that you first try to make break-in code
think in terms of strings, not stones.  I'm pretty sure that you can
eliminate expand_connection_queue() call -- i just don't understand
break-in code that well to do it.  But if you really feel like
reverting all stones/origin only change, go ahead.

From your earlier message:
> I found it quite convenient in uses of the connection queue (e.g. in my
> escape owl patch) to have all stones explicitly in there. And already
> now you have two places in the code where you need to expand the queue
> element containing the origin to the complete list of stones in the
> string -- does that really make the code clearer?

About two places where i expand the queue.  If we count the number of
lines with the word "findstones" we'll get 6.  3 of them starting with
plus, 3 with minus.  If the call to expand_connection_queue() can be
eliminated, one of the findstones() call can be replaced with two calls
to mark_string() -- one in compute_smaller_goal() and the other in
break_in_goal_from_str().

I don't think i ever looked at your owl escape patch, so i can't really
comment on that.  Are you sure you absolutely need all stones of a string?
What for?

sort_connection_queue_tail() has nothing to do with the queue contents
and is probably not needed.  It can potentially (and in very rare cases)
influent the results of break_in_goal_from_str() and break_in_goal().

And finaly note that the connection reading code itself never needs to
expand the queue.  Isn't that a well-written code? ;)

Paul