[Freeciv-Dev] Re: list cleaning

[Raimar Falke <i-freeciv-lists@xxxxxxxxxxxxx>]

On Sun, Nov 30, 2003 at 02:06:10PM +0000, Per I. Mathisen wrote:
> On Sun, 30 Nov 2003, Raimar Falke wrote:
> > > > > Not if deletions only happen in extremely rare cases. This does 
> > > > > happen.
> > > >
> > > > Yes. However we will know that this happens.
> > >
> > > Not if we don't catch it. Players test more code paths in the game than we
> > > do.
> >
> > We catch it with the assert.
> 
> How can you be sure we will test the code path that generates the rare
> bug? Autogames do not test every code path.

Before it will turn into a problem the assert will catch it. It
doesn't matter if this is found during the testing or by a user.

> > Look we have unsafe iterators (unlink during iterate). In the past we
> > used a safe version in the rare cases were we needed it.
> 
> Actually a number of different approaches were used. Sometimes the
> iterator pointer was passed to a function that might do an unlink,
> sometimes unit_list_iterate_safe was used, and sometimes a custom solution
> was made that did almost the same as unit_list_iterate_safe
> (ai_manage_units, civil war and another). It used to be pretty ugly, and
> it became quite buggy.
> 
> The reasons it 'became' buggy was 1) allied transports and 2) AI
> diplomacy. The former generated a high number of subtle errors and the
> latter uncovered a number of rare errors that had always been there.

It was possible at this time that all these different approaches could
have been converted to the safe iterators approach.

> > The safe versions then were removed. So we can either revert the change
> > and reinstall the safe versions (this was rejected of reasons which may be
> > facts or not) or we replace it with something better. And better here
> > means for me that we build a safer version which always works. The
> > older code with the safe iterators had low runtime impact and used to
> > have low code impact.
> 
> I agree we should find something better with low runtime impact and low
> code impact. I hold that the solution I suggested is the best in both
> respects - it is fastest and requires least changes to present and future
> code.

> I am not sure why we are having this meta-discussion, though. Can we get
> back to the technical merits of the different approaches, please?

Ok lets enumerate all possibilities

1) safe iterators
 - low code impact
 - low speed impact
 - low memory impact
 - not safe

2) safe iterators where needed
 - requires balanced iterators (which have medium/high code impact)
 - low code impact by itself
 - low speed impact
 - low memory impact
 - safe

3) lazy deletion with explicit pruning (once per turn for example)
 - medium/high code impact
 - low speed impact
 - low memory impact (higher if prune call is missed)
 - safe

4) lazy deletion with implicit pruning at leaving the outer most
iterator
 - requires balanced iterators (which have medium/high code impact)
 - low code impact by itself
 - low speed impact
 - low memory impact
 - safe

5) lazy deletion with explicit pruning via global list of current
genlists
 - low code impact
 - low speed impact
 - low memory impact
 - safe

5) looks like the clear winner but has the problem that it won't work
without an genlist_destroy function. Assume this code:

 {
  struct genlist list;

  genlist_init(&list);
  ... use list
  genlist_unlink(&list, ...);
  ... use list some more
 }
 ...
 global_prune_function();

global_prune_function will find random data at the time the function
is called.

We have such similar code in control.c:process_caravan_arrival() (with
a static list variable).

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Life is too short for reboots."