[Freeciv-Dev] Re: [PATCH] Map cleanups (PR#1208)

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Sun, Jan 06, 2002 at 04:32:02AM -0800, jdorje@xxxxxxxxxxxxxxxxxxxxx wrote:
> Ross W. Wetmore wrote:
> 
> > This series of patches cleans up a number of cosmetic and real issues
> > in map.c and map.h. It is split into a number of sub-patches for the 
> > convenience of reviewers, but is intended as a single submission, and
> > only tested in a fully installed state.
> > 
> > It is the first installment of a set to merge fixes in the corecleanup
> > into CVS completing the map and topology related updates.
> > 
> > 0)  mapclean_00.dif
> >     This is a pure cut and paste line rearrangement of the existing
> > files intended to improve the grouping of related functionality and
> > simplify/localize the subsequent changes. The line and character
> > count (wc) should be unchanged. One can repeat this by doing cut and 
> > paste operations on a clean CVS file to match side-by-side views with 
> > the patch result, and use diff as a final verify step if you are
> > consciencious or lacking in trust :-).
> 
> I trust you, and everything looks sane here.
> 
> There are advantages and disadvantages to this change.  In the long run, 
> only the advantages matter.  As more and more functions have been 
> added,there has been some consistency in their placement but no 
> overriding organization.  Re-ordering them to match a completely 
> consistent theme will certainly make future coding easier.
> 
> On the other hand, this will make many existing patches to these files 
> (map.[ch]) fail to apply.  In most cases this should be easily fixable. 
>   It is in any case a short-term problem.
> 
> Summary: assuming you agree with the organization Ross introduces, this 
> should be a beneficial change.  And if it's going to be applied, the 
> sooner the better.
> 
> I do disagree with some of the organization.  It takes code that is 
> topology-dependent and is currently (mostly) clumped together and 
> separates it all out.  Although is_normal / is_real / normalize / 
> nearest_real_map_pos are all placed together, regular_is_normal and 
> is_border have been separated from them, as has map_distance_vector.  I 
> do think these should eventually all go into a separate file 
> topology.[ch], and if there is some agreement on this I'd provide a 
> separate patch to accomplish this.  So it shouldn't stand in the way of 
> inclusion.

I think that it is hard to come up with a good (everybody agree to it)
organization. Also a seperation like map_topology.[ch],
map_tiles.[ch], map_part3.[ch],... may be better. The borders are just
more clear this way. So I think it should be applied but there may be
other opinions.

> > 1)  mapclean_01.dif
> >     This is a series of local cosmetic and minor updates which should
> > have no global scope or significant impact on game execution. They can
> > largely be scanned in a superficial way, i.e. no heavy thinking.
> 
> For the most part, yes.  But you've slipped some comments in that do 
> require thought.
> 
> This patch seems to consist of the following:
> 
> * A lot of places that have been changed only in spacing, i.e. to match 
> freeciv's indentation rules.  Although purely formatting changes are 
> frowned upon, most of it is pretty innocuous stuff (i.e. nothing 
> controversial), and the rest is stuff that indent would probably mangle 
> (by splitting lines at the wrong place).
> 
> You do have
>    -  c=map_get_terrain(x,y);
>    +  c = map_get_terrain(x,y);
> in which the spacing on the second line should be fixed.

> * A lot of places that replace map_get_tile(x, y) with MAP_TILE(x, y). 
> This is faster and just as correct.  Some of them are in one-line if() 
> statements which have not been separated out; Raimar may want them 
> separated (although I imagine other maintainers won't care).  

> It would be better IMO to get rid of MAP_TILE altogether and make
> map_get_tile a macro, but that's easily done later.

Ack.

> * 1 re-ordering of an if() statement.  This makes it both easier to read 
> (IMO) and faster.
> 
> 
> * You've added comments in some places.  This can only be a good thing, 
> so long as they tell the truth.  In other places you've changed 
> comments, which may be more questionable.  See below.
> 
> 

> * You have moved the call to reset_move_costs down to the bottom of 
> change_terrain().  Although this makes sense logically, I can't directly 
> answer to its correctness.

It is ok since S_MINE, S_FARMLAND nor S_IRRIGATION change the move
costs.

> * You've changed several lines of the form "return foo;" to "return 
> (foo);".  I can't say I agree with this change; any of my patches would 
> most likely just change it back :-).  Perhaps this is a question for 
> another style vote?  (Or did we already vote on it and I missed it?)

It is definitely a style question. I'm also not sure if we have
already covered it or not. I still have to apply the results of the
first part.

> * Some of your changed/added comments are very questionable to me.
> 
> The following added lines in the function header comment for 
> map_distance_vector:
>    +sq_map_distance is defined to be the square or the trigonometric 
> distance.
>    +
>    +map_distance is the city grid distance, i.e. no diagonal moves allowed.
> need to be improved on.  "sq_map_distance is the square of the 
> trigonometric or Pythagorean distance, and the sum of the squares of the 
> distances in the x and y direction", while "map_distance is the grid or 
> 'Manhattan' distance, and the sum of the distances in the x and y 
> direction".
> 
> Then we have the following comments for normalize_map_pos:
>    +FIXME: This should test for realness using is_real_tile() before 
> touching
>    +       coordinates and update only if needed, thus avoiding side 
> effects.
> normalize_map_pos() has _inherent_ side effects, and trying to pretend 
> otherwise is foolishness IMO.  As I've said before, there are three 
> things we could legitimately do to unreal coordinates: (1) leave them as 
> they are, (2) wrap them linearly as if they were real (the equivalent of 
> Gaute's wrap_map_pos), or (3) find the nearest_normal_map_pos().  #1 is 
> my preference and yours, but defining things this way would be bad.  I 
> would write this change like so:
> 
> /**************************************************************************
>   Attempt to normalize the map position (to wrap it into the set of
>   "normal" positions.
>     - If the position is real, the function returns TRUE and (*x, *y) are
>       changed to be the equivalent normal position.
>     - If the position is not real, the function returns FALSE and
>       (*x, *y) become undefined.
> **************************************************************************/
> int normalize_map_pos(int *x, int *y)
> {
>    /*
>     * FIXME: this should test for realness before touching coordinates
>     * and update only if needed, thus avoiding side effects.
>     */
> 
> You write comments of the form:
>    /*  ===============...===============  */
> and
>    /******************...******************/
> What's up with that?  Just stick to the second one.
> 
> The following segment
>    +/* Map topology definitions and map dimension related macros */
>    +/* The default definition reflects a cylindrical map wrapping at 
> map.xsize  */
> should be one comment, not two.
> 
> In the following comment
>   /*
> - * Sets (dest_x, dest_y) to the new map position or a real map
> - * position near. In most cases it is better to use MAPSTEP instead of
> - * SAFE_MAPSTEP.
> + * Sets (dest_x, dest_y) to the new map position or a nearby real position.
> + *
> + * In almost all cases it is better to use MAPSTEP and deal with the unreal
> + * coordinate case explicitly, instead of SAFE_MAPSTEP and the 
> void_tile-ish
> + * problems that produce surprises later.
>    */

> although I agree with you in principle ("in almost all cases it is 
> better to use MAPSTEP"), the "void_tile-ish problems that produce 
> suprises later" part is completely misplaced.  First of all, there will 
> be no void_tile-ish problems by definition, since unreal coordinates 
> will _never_ be returned by the macro.  Secondly, this comment is aimed 
> at convincing the casual user to not use this macro, but it will only be 
> understood by someone who knows the history of the internals of map.c.

Ack. void_tile is gone and shouldn't been mentioned anymore.

> This comment
>    +/* This is a temporary measure to track down
>    +   non-normal cordinate use */
>     #define CHECK_MAP_POS(x,y) assert(is_normal_map_pos((x),(y)))
> seems quite wrong to me.  Although the current form of CHECK_MAP_POS may 
> be quite temporary, it's neither feasible nor desirable IMO to go back 
> to the old system of using normalize_map_pos everywhere and returning 
> void_tile if we ever end up with an unreal tile.  One possible change 
> would be something like
> 
> #ifdef DEBUG
> # define CHECK_MAP_POS(x,y) assert(is_normal_map_pos((x), (y)))
> #else
> # define CHECK_MAP_POS(x,y)               \
> #   if (!normalize_map_pos(&(x), &(y))) { \
> #     freelog(...);                       \
> #     abort();                            \
> #   }
> #endif
> 
> but calling CHECK_MAP_POS "temporary" just seems like a misplaced 
> attempt to make it so :-).
> 
> 
> Summary: this patch is a collection of disjointed changes.  Although the 
> map_get_tile->MAP_TILE ones are good and the straight formatting changes 
> are decent, I have objections to a lot of the comments you've changed. 
> Another opinion is needed on this.
> 
> 
> > 2)  mapclean_02.dif
> >     This contains a small number of more significant changes plus an
> > extensive update of map.h non-directional macros and fixes outstanding
> > bugs with normalize_map_pos() and friends. While the functional versions
> > are both equivalent and fixed, most program use should now be via macro 
> > for increased performance. These features have been in the corecleanups 
> > for 6 months and are completely compatible with the current CVS codebase,
> > so there should be little or no concern about risk.
> 
> Ahh, now we get into real disagreement :-).
> 
> 
> > a)  map_city_radius_iterate -> city_map_checked_iterate
> >     This fixes unnormalized access to map_get_terrain which can no longer
> >     deal with real but non-normal coordinates.
> 
> As a side note, I don't think either of these names are particularly 
> good.  map_city?  checked?  huh?  I have to look the city macros up 
> every time I use them.

So what is the long term goal? remove map_city_radius_iterate altogether?

> > b)  && -> || mistake
> >     One T_UNKNOWN state can be handled, two cannot, and none is excessive
> >     restriction on the server AI.
> 
> Gotta ask the AI people on this one...
> 
> 
> > c)  is_normal_map_pos() -> normalize_map_pos()
> >     Returned values must be normalized, so just do it and return.
> 
> 
>     do {
>       *x = myrand(map.xsize);
>       *y = myrand(map.ysize);
> -  } while (!is_normal_map_pos(*x, *y));
> +  } while (!normalize_map_pos(x, y));
>   }
> 
> This change is incorrect.  Consider an iso-rectangular cylinder.  In 
> this case, all positions will be real, and so will be accepted by 
> normalize_map_pos.  However, it is only normal positions that we are 
> interested in.  Changing the code like this will result in some 
> positions being picked more often than others.
> 
> If you want to rewrite the function entirely to take topology into 
> account, that is a valid change.  (I'd wait to get a second topology 
> before doing this, however :-).)  Doing it like this is just asking for 
> trouble.
> 
> 
> > d)  is_real_tile() is a test, not a full normalization, make it so.

This spreads out knowledge about the topology. Provide numbers which
show how much faster it gets this way.

> > e)  normalize_map_pos() should test for realness before it undertakes
> >     any transformation. This fixes any potential bugs from side effects.
> 
> Heh.  The bug is not here, but you should fix it anyway :-).
> 
> 

> > f)  nearest_real_pos() is defined consistently with normalize_map_pos()
> >     to return FALSE for unreal coordinates and TRUE for real. The only
> >     difference is that it returns arbitrary but normal results in the 
> >     unreal case, i.e. controlled side effects.

The changes are ok.

> This is sensible.
> 

> Note one alternative would be to get rid of nearest_real_pos
> entirely and give this functionality to normalize_map_pos.

Ack. However I have no idea how hard it is to convert the remaining 3
(three) cases.

> I don't advocate doing this (it will _very_ easily lend itself to
> misuse), but it would allow us to eliminate one function.
> 
> 
> > g)  RANGE_CHECK macros are added and used to improve performance by
> >     reducing execution in most cases where applicable by a factor of two.
> 
> 
> I find the whole RANGE_CHECK_0 thing pretty unreadable and worthless. 
> Even if such a thing were included in CVS, I'd still write
>    if (0 <= a && a < b)
> instead of
>    if (RANGE_CHECK_0(b, a))
> Although I haven't checked it, I find it hard to believe that any 
> worthwhile compiler couldn't optimize this.

This is a chicken-and-egg problem. Ross can't show the nubmers until
all code is converted. I won't accept it until I have some
numbers. Ross however won't start until he has the promise that it is
accepted.

> > h)  Wrap and clipping macros are added to standardize code use. Overtime
> >     all map code that does local flavours should be updated to use these.

> > i)  map_adjust_x() and map_adjust_y() are redefined to be explicit
> >     wrap and clip operations for the standard cylindrical map, as the
> >     first instance of standardization :-).
> 
> This is very bad IMO.  Standardization requires that 
> map_adjust_x/map_adjust_y be removed entirely.  This change just adds a 
> lot of importance to their definitions - you take 7 lines of 
> #definitions that are currently only used in a very few places 
> (hopefully soon to be removed), and change them into 30 lines of 
> #definitions within #definitions with #definitions, plus extensive 
> comments explaining how they should be used (including saying that 
> they're about to be removed, fortunately :-).

Ack. map_adjust_[xy] should die/definition moved out of
common/map.h. Move it (in its current form) to client/mapview_common.c
I will be happy.

> Also, the "void_tile-ish" comment here is in a similar position to the 
> one mentioned above.
> 
> 
> > j)  map_to_index() is defined as the start of the map_inx() removal.
> >     When the corecleanup and topology fixes are all applied, this will
> >     be completely gone. index_to_map_pos() as the reverse operation is
> >     defined in the standard manner, i.e. returns updated coordinates
> >     and a status return indicating success or failure.
> 
> I definitely like the name change (although I would call it 
> map_pos_to_index).  I'm not sure what you mean by map_inx removal, but I 
> don't think I'm going to like it :-).
> 
> 
> > k)  Macro forms for is_real_tile() and family are defined for the
> >     cylindrical map. These will be upgraded to full topological forms
> >     when further capabilities (i.e. topological state) are added.
> 
> This is something Gaute has wanted to do for a while, and as you've 
> found the speedup is very significant.  It makes the code pretty 
> ugly/unreadable, but it's tough to argue with the results.
> 
> 
> > l)  The generic border tile macro is added and used in the current case.
> 
> Ugh.
> 
> Summary: I don't like most of these changes at all.  So we need another 
> opinion (aside from the is_normal->normalize change which must be fixed).
> 
> 
> > The changes have been sanity tested and client and server autogames run
> > for a combined 24 hour period without a problem.
> > 
> > In one case, savegames chksummed identically through end in 1885. 
> 
> I believe it.  I see nothing which could change the behavior.
> 
> 
> > Times were ...
> >   9:05  CVS-Jan04
> >   7:03  patched
> 
> Very impressive.  But a greater speedup can be achieved just by changing 
> is_real_tile, is_normal_map_pos, normalize_map_pos, AND map_get_tile 
> into macros - without the need for RANGE_CHECK or any of the other 
> implementation hacks you use.
> 
> In my test, I get the following times for an autogame (compiled with 
> DEBUG and -O2 and only run once, so maybe not a very good benchmark...):
> 
> CVS: 3m39s = 219 sec
> mapclean patch: 3m6s = 186s ~ 15% speedup
> simple macro patch: 2m36s = 156s ~ 28% speedup
> 
> savegames were identical for all three, so I can back you up on that.

I feel not ready for another thread about performance, macros and
inline usage. So Ross please drop the RANGE_CHECK thing for now or
show some drastic numbers (with RANGE_CHECK only).

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Last year, out in California, at a PC users group, there was a demo of
  smart speech recognition software. Before the demonstrator could begin
  his demo, a voice called out from the audience: "Format c, return. Yes,
  return." Damned short demo, it was.