[Freeciv-Dev] Re: list cleaning

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

On Sun, Nov 30, 2003 at 09:19:53PM +0000, Vasco Alexandre Da Silva Costa wrote:
> On Sun, 30 Nov 2003, Raimar Falke wrote:
> > On Sun, Nov 30, 2003 at 02:06:10PM +0000, Per I. Mathisen wrote:
> 
> > > 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
> 
> Don't be so sure about the low speed impact. I have experienced this
> solution before. It trashes the cache a lot, besides, you get to test
> lists which haven't even been modified, which isn't the case with most
> of the other solutions.

Yes the speed impact is higher if the frequency of unlinks is higher.

> > 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
> 
> I prefer this solution in combination with 2).

Can you describe this?

> Because lists which haven't been modified don't get tested, for one.

I assumed two optimizations which are orthogonal to these solutions:
 - detect the need to do pruning by a "deleted" flag (3,4,5)
 - do a non-lazy unlink when there are no outer iterators (4)

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "> WHY?! Isn't it better to put $(shell cat cscope.files) on the list of
  I only have a yellow belt in makefile kungfu.  These fancy gnu make things
  are relatively new to some of us..."
    -- Mark Frazer to Vassilii Khachaturov in linux-kernel