[Freeciv-Dev] Re: [PATCH] Re: {gen,spec,sort}list stuff

[Justin Moore <justin@xxxxxxxxxxx>]

> >    If this is accepted, I have a slew of patches (all small :)) that I can
> > throw out to start moving from the slower iterators to the newer ones.
>
> If I would accept the new version now there would be an improvement
> loss. IMHO you should prepare the main code using patches so that the
> introduction of the new version will yield an immediate performance
> gain.

   The sequence of patches in that case would be:

1. Define the STABLE_* iterators to be the current (slow) iterators.
2. Define stable_*_list_iterate to use the new (slow) STABLE_* iterators.
3. Find all the places that will use the new iterators and change them
    to the stable_*list_iterate macros.
4. Submit the genlist.[ch] patch.

   This will result in an immediate performance gain, but is it worth
patching genlist.h first (in step 1), then essentially overwrite the patch
in step 4?  I can do this, too, it just seems to have unnecessary steps.
I saw it as:

1. Submit genlist.[ch] patch.
2. Change header files to use the stable_*_list_iterate functions.
3. Submit patches for places the use the new iterators.

> I still dislike the extra "if(!pgenlist->capacity) {" in
> genlist_resize. It is unnecessary. Same in genlist_unlink_all.

   I'll remove it.

> Why do you make an extra "void **arr = pgenlist->data;" in
> genlist_find_index? I'm sure the compiler will optimize this. Same in
> genlist_unlink.

   *shrug* Again, my still-growing stock of compiler knowledge shows. :)

> +  if(pos == pgenlist->nelements) {
> +    pgenlist->data[pgenlist->nelements] = data;
> +  } else {
> +    int i;
> +
> +    /* Start at the end and move everything "up" one spot.
> +     * We start at the end so as not to overwrite anything as we go. */
> +    void **arr = pgenlist->data;
> +    for(i = pgenlist->nelements;i > pos;i--)
> +      arr[i] = arr[i-1];
> +    arr[pos] = data;
>    }
>
> This can IMHO be folded in one case where the for loop is never
> entered in the case "pos == pgenlist->nelements".

   *nod*

> +  /* If the insert position is invalid, put the data onto the end. */
> +  if((pos < 0) || (pos >= pgenlist->nelements)) {
> +    pos = pgenlist->nelements;
> +  }
>
> This is not so much to do with the patch but I would like to know if
> these really exists?

   Yes.  Inserting into position '-1' is defined to be inserting into the
end of the list.  It is used in several places.

> It looks like this branch:
> +        if(cp == -1) {
> +          iter->curr_data = NULL;  /* Our data disappeared!! */
> +          return NULL;
> +        } else {
> +          iter->curr_pos = cp;
> +          iter->curr_data = list->data[cp];
> +          return iter->curr_data;
> +        }
> and this one
> +      if(cp == -1) {
> +        iter->curr_data = NULL;
> +        iter->curr_pos = -1;
> +        return NULL;
> +      } else {
> +        iter->curr_pos = cp;
> +        iter->curr_data = list->data[cp];
> +        return iter->curr_data;
> +      }
> are the same/almost the same. Can they be merged?
>
> It looks like some of the code of genlist_iterator_ptr,
> genlist_iterator_next and genlist_iterator_prev can be merged. What
> about a "ensure_valid_position" method?

   Macros? *shrug* I'll take a look at it.

> IMHO the names STABLE and SAFE should be changed. STABLE means the
> list can be used if the iteration won't change something. SAFE means
> something other. SAFE should be MODIFYING or so.

   I selected SAFE to indicate it was "safe" to mess with it (remove one
or more elements from the list, insert stuff into the list, etc).
MODIFYING just seems a bit ... unnecessarily verbose. ;p

-jdm

Department of Computer Science, Duke University, Durham, NC 27708-0129
Email:  justin@xxxxxxxxxxx