Crossfire Mailing List Archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: CF: object structure layout.



Frank Tore Johansen wrote:
> 
> To "free" up memory in a way that makes it possible to swap out
> efficiently, all pointers to objects must be rewritten to be two-way, so
> that you can easily move an object in memory.  That way you can have some
> garbace-cleaning algorithm putting all free objects in the same memory
> space.  This would mean going away from normal malloc for objects...
> Probably not worth it, as you loose out when you start swapping anywa.
> And with ram prices these days...Crossfire was made to run on a Sun 3/50
> with, hmm what was it, 8Mb of ram?
> Btw, all pointers really should become two-way anyway, so that when an
> object is freed, you can quickly remove all pointers to it.  This used to
> be the #1 bug in crossfire...I added some hacks to avoid it as much as
> possible, but it was never perfect.

 I'm a little unclear by what you mean by two way pointers.

 I am guessing you mean that the object structure should have another pointer
which points to whatever object is 'using' this object.  But that isn't quite
perfect because multiple things could be using an object.

 The other meaning I could take would be some form of indirect pointers (ie, 
the pointer to an object refers to a handle, and you have code that looks up and
see what that handle really points to and if it is still valid or not).  This is
sort of implementing MMU functions in the program itself.

 All lists an object is on is doubly linked, so from that perspective, updating
the list is easy to do. 

 But the above does bring up an interesting point.

 Since an object is also sure to be less than a page size, and how objects get
allocated is sort of random at best, even if you contain the lists the object is
on so you don't referance unneed objects (ie, have the lists on a map basis, so
other objects on other maps aren't accessed), the paging that can take place may
not be fully optimized - while the objects on the other 3 maps may not have been
accessed in a long time, objects on the current map have been, and very likely
at least some of those objects are on the same pages as the inactive objects,
and as such, those pages can not be paged out.

 So ideally, you would want to use a contiguous block of memory for objects that
are localized with each other (ie, one big block for all objects on some map,
another block for objects on another map, etc), so if they aren't being used,
all the memory can be swapped out.  This starts getting much mroe complicated -
especially since objects within that block may get freed or you may need
additional objects (I guess you could do a realloc in the later case).  Having
free lists per maps seems to start getting a bit excessive.
 

> The advantage of just 1 list is that when an object is freed, you only
> have to find and remove it from this one list (by way of two-way pointer
> back from object to binary time-event tree).

 I think the way I am going to currently do it is have the active and non active
object lists per map (not global).  The only global list would be the free
objects.

 Being this is the case, and most maps don't have a huge number of active
objects, I am going to keep the same basic list traversal for object actions. 
For a small set of active objects, this is almost certainly more
efficient than some of the more complicated method (for large sets of active
objects, the more complicated methods are likely to be faster, but with speed of
most systems, I don't see that as much of a problem)
-
[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]