Re: CF: object structure layout.

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

[Mark Wedel]

>    I was thinking something similar - at least for players.  A list
>   for visible object, and a list for invisible objects.  This makes
>   searching for something easier (you can know attributes or skills
>   or whatever would be in the invis list), and also makes logic for
>   things like drop or client updates easier (don't have to deal with
>   going over invisible objects and how that syncs up)

Remember the player can click on a monster to see its inventory, so
this could just as well be handled by the same logic, I think.

>    That said, the limited subtyping method does have some
>   disadvantages - for some objects, there will be unused fields (for
>   example, the scroll vs rod - if we assume there will be a
>   recharge_time and a charges field, the scroll only uses the
>   charges and cares less about recharge_time, while the rod is
>   opposite)

Yes, we can't worry about minor differences like that, then we'll need
one object type per archetype.  I think the subtyping should be done
according to how much code they have in common, not how many
attributes they share.

>    So from my perspective, it is easier to have a top level object
>   with a union of the necessary sub item types - things like maps,
>   inventory lists, and so on use the top level object which then
>   contains the type.  For example, here is the definition as I have
>   it:
>   
>   /* To see better details about this, look at doc/objects */
>   typedef struct obj {
>       struct obj *next;       /* Pointer to the next object in the free/used */
>                               /* list */
>       struct obj *prev;       /* Pointer to the previous object in the */
>                               /* free/used list*/
>       struct obj *active_next;    /* Next & previous object in the 'active' */
>       struct obj *active_prev;    /* List.  This is used in process_events */
>                                   /* so that the entire object list does not */
>                                   /* need to be gone through. */

What are the advantages of keeping used and free objects in the same list?

I think it would be better to separate this into two lists, this
reduces the object size and results in less pointer manipulation when
allocating (I think).

Another point which I've been thinking a bit about lately, is the
cache friendliness of code like this.  If we have 4000 objects @ 512
bytes each, we're blasting through 2 MB of data when traversing the
list.  This _really_ thrashes the cache and memory (and 4000 objects
is very conservative).  A memory stall is extremely expensive these
days (it's measured in hundreds of nanoseconds), so it would be good
to take this into account when redoing these structures.

The goal is to reduce the amount of data accessed when going through
the linked list.  This means the the object is split in two, one small
chunck with the next pointer and the most often accessed data, and a
pointer to the full data.  E.g.:

struct obj {
	struct obj *next;
        float speed;
        float speed_left;
        uint32 tag;
	struct objdata *data;
}

This reduces the object size to 20 bytes, and the above example of
4000 objects fits into 80 kB.

Note I think the previous pointer is not important enough, it is put
into objdata instead.  I haven't actually looked at the code, but all
loops which go through all objects should preferably have the
necessary attributes available right there.  Perhaps anim_speed should
go there as well.  It will almost certainly be larger than 20 bytes,
but even 32 or 64 bytes would be a great improvement over our current
312 bytes (which will grow after the ambiguities have resolved).

<aside>
	I think the speed and speed_left should be redone to use
	integers and timestamps.  I.e.
	    t = pticks << 8;  # 32 bit ints => 24 days before wraparound.
	    for each obj {
	        if (obj.wakeup >= t) {
		    obj.wakeup += obj.speed;
		    do stuff (obj);
		}
	    }
	obj.speed is calculated when loading the map as:
	obj.speed = (1/speed) * max_time * 256;

	The advantage of this is that there is only one compare for
	each object, instead of a subtract, compare and a write back
	into memory.
</aside>

>    So in a sense, things like background, monster, etc and children
>   of the top level object.  But this model allows things like the
>   lists to track objects to remain unchanged - what does change is
>   how to interpert the values of the subobjects.

I understand you are wary of fixing thousands of lines of code...  I'm
willing to help doing the above, though.

>    The disadvantage with the above method is that the object
>   structure size is determined by the largest subitem size.  So
>   while there may be tons of backgrounds, since the monster object
>   is likely to be the biggest, you waste space there.  But that is
>   how things are currently done, and hopefully the overall object
>   size can still be kept small enough this is not a big problem (the
>   other solution would be to dynamically allocate the sub item
>   information and have pointers instead - that may be a better way
>   to go in the long term, but is likely to also cause more bugs - at
>   least in the above model, if something things it is dealing with a
>   weapon and writes into the subitem when the object is really a
>   background, things may get messed up, but only for that one
>   background)

I think we should consider using a garbage collector for this.  I'd
like to use <URL:http://reality.sgi.com/boehm_mti/gc.html>, it sounds
very cool, and perfect for our purposes (its assumptions will hold
true, so it will seldom guess wrong, I think).  I haven't tried using
it before, though.  In this case, perhaps it is best to keep a common
list for free and used objects, but let the "usedness" be denoted by a
NULL objdata pointer.


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]