[Freeciv-Dev] Re: [PATCH] Small improvement at genlist and maphand

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

This may not be applicable to a lot of lists, but there will be subtle
effects on game play and AI moves if for example it always processes
its unit_list in a fixed order. Or always evaluates city actions in a
NW to SE (i.e. 0,0 to map.xsize,map.ysize) direction.

It is actually better to have a stack or circular list for a lot of
game objects where if one accesses them they get put back at the head
or tail. If one needs to push/pop them for some reason, like filling 
up a transport then having it be the next unit to move, one uses stack
like operations, but if one is presumably done processing it, it goes 
to the end. If one awakens a stack of caravnns to be sent to Wonderland
in Tobruk, it is *very* irritating to not have moves stacked and have 
the move selection bounce all around the map before it gets back to the
next one (because the unit sort order was by home city or something).

This order has a play pattern, which may be appreciated by humans but it 
is not a rigorous mechanical sort based on some obscure computer thingie
and can be changed as units are awakened for out-of-list-order events.

I'd like to know exactly which lists are to be sorted and why before any 
CVS code changes are made.

Cheers,
RossW
=====

At 07:13 PM 01/08/21 -0400, Justin Moore wrote:
>
>> I'm still not convinced that an always sorted list is necessary. The
>> removal of this would simplify the code. The only place which uses
>> sorting is in server/savegame.c.
>
>   A sorted list may not be necessary, but for data with infrequent
>inserts and frequent searches it is much faster.  Especially since genlist
>uses a horrendeously inefficient doubly-linked list.
>
>   I'll make a series of patches that convert a few of the genlists to
>sortlists and see how that changes the performance.  I maintain that even
>if a sorted list is unnecessary, as long as it is not incorrect for the
>given data it is preferable.
>
>   Also, what are people's thoughts about having the option of passing a
>function to sortlist_init() that would work the same way as the
>comparison function in qsort?
>
>-jdm
>
>Department of Computer Science, Duke University, Durham, NC 27708-0129
>Email:  justin@xxxxxxxxxxx