Re: CF: object structure layout.

[Kjetil Torgrim Homme <kjetilho@ifi.uio.no>]

[Mark Wedel]

>    I assume you mean active/non active there, and not free/used
>   (free and use are already on seperate lists.)

I was confused :-)

>    For active/non active, you are probably right - seperate lists
>   makes sense.

Wow, lucky shot :-)

>    Generally, we only go through the active lists, which tend to be
>    smaller.

Ah, good.

>   And on further thinking, the list of 'active' objects could
>   perhaps be even further reduced - animated objects are considered
>   active (to update face information) - that can all be handled on
>   the client, so any object which is scenary but is animated would
>   no longer need to be on the active list.

That'd be nice.  It would reduce the bandwidth requirements, too.

>    I guess the performance may depend on the compiler/cpu and how it
>   deals with cache loads?  For example, if the object is 512 bytes
>   lets say, but you are only accessing stuff in the first 20, does
>   it still load all 512, or does it only load the 20 bytes?  My
>   knowledge in that area isn't that good, but if it is only loading
>   the 20 bytes or whatever, then the key is to organize the
>   structure so the most needed fields are first.

You are correct, it will load just one cache line.  The length of a
cache line varies from CPU to CPU.  On the P6 family (Pentium II) it's
32 bytes, and I think this is a common value.  So there are two issues
to think about: Keeping the frequently used attributes grouped
together (like you said), and making the structure cache line aligned
(that is, pad it out to a multiple of 32 bytes).


>    You probably need to add the map pointer to the above.  The main
>   object traversal is each tick when it goes and sees what objects
>   need to do something.  At times, that traversal needs the map
>   object.
>   
>    Another issue is that for the objects that do need to do
>   something, the rest of the object structure is going have to get
>   loaded anyways.  So if you wanted to get more clever, you could
>   have various run queus - ie, the 1 tick away run queue, the 2 tick
>   away, 3 tick,.. to 5+ tick away.

Very interesting idea!  It needn't complicate the code much, either.
This removes the need for a wakeup attribute, since it is implicit if
you have enough queues. The penalty for having many queues is very low
(it's just a pointer per queue), so that's OK.  The slowest object in
Crossfire right now is the Skull generator with speed 0.0002.  That's
5000 ticks, though.  Hmm.  Does it make sense to have objects which
only do something every 10 minutes?  The slow objects are currently
generators and diseases.

>    And these cycle around.  This doesn't work well for things that
>   change speed, but typically that is only the player which is
>   likely to be handled special in any case.

The speed change will take effect on the next update.  That should be
good enough in most cases.

>   If when processing a queue, you run accross something that isn't
>   ready to run yet, it gets placed back into the best estimate again
>   for next run time.
>   
>    But frankly, if we do follow up with some of the proposals on
>   future game play and reduce the number of monsters, and do some
>   other clean up, the only thing on the active queue will be
>   monsters and spell effects (firebolt, lightning bolt, etc) - all
>   animation will be done by the client.  If that is done, I don't
>   see the active list being all that large even with quite a few
>   players.

Probably true.

>    In some sense, I would like to keep things simpler for now - at
>   current time it doesn't seem to be stuff like the object traversal
>   being a limiting time factor/causing slowness on the server, but
>   other tasks like map loading/saving.

Very true.  I don't have any clever ideas, there.  As long as people
are running the server off NFS, there will be problems with loading
times, no matter what optimisation we come up with.  Well, actually
one very simple approach is to stop saving to disk and rely on the OS'
paging/swapping instead.  If nothing else, this saves spending CPU on
converting object data to/from ASCII.

>    I know in one of my mail messages a while back following up on
>   David's idea of a more unified scale would be to only process
>   objects in the vincinity of the player (so if you had a 50x50 map
>   for example, only objects with 10 spaces of the player gets
>   processed).

My hunch is that the code for this will be complex.

>    Even if that doesn't happen, it could make sense to store active
>   objects on a per map linked list, so you can completely ignore
>   objects you don't need to process.  You could do something like:

A much better idea.  This is incompatible with the one queue per tick
idea above.  If we stop doing swapping ourselves, a list per map is
almost required.

>   1) Keep track of last tick a player was on any particular map.
>   2) Have individual maps be setable for their swapout time and how
>      long to still move monsters for after last player leaves.
>   3) Only process objects for maps players are on or that fall into
>      parameters set in #2 above.
>   
>    There are advantages here:
>   1) Some commonly used maps could have very long swap out times
>      without adversely affecting server performance (only memory for
>      the objects in ram).
>   2) If the only referances to objects on a map are within the map
>      object itself (and not global lists), it should be easier to
>      require threaded load/save routines since there would be less
>      synchronization needed with other lists.
>   3) Following up with #2 above, it would be quite conceivable for
>      each map to have its own thread to handle the creatures on the
>      map.

3 is interesting, but be careful so that the design doesn't make
teleport between maps impossible.

>    I think with the move towards SMP systems and the fact that
>   various actions can cause the server to block, thinking about
>   possible ideas to utilize threading (and thus, multiple processors
>   indirectly) would probably be a good thing.

Agreed.


Kjetil T.
-
[you can put yourself on the announcement list only or unsubscribe altogether
by sending an email stating your wishes to crossfire-request@ifi.uio.no]